# 某岛

… : "…アッカリ～ン . .. . " .. .
October 20, 2021

## AtCoder Regular Contest 128

arc 好难。。。（虽然题面都很简单）

## C Max Dot

（。。我猜是斜率 DP？。。。没能写出来。。）

const int N = int(5e3) + 9;

int n,m,s;
int a[N];

DB gao(int n, DB m, DB s) {
vector<pair<DB,int>> avg; DB ss = 0;
DWN(i, n, 0) {
ss += a[i];
avg.PB({ss / (n-i), i});
}
int t = max_element(ALL(avg))->se;
DB x = s / (n-t);
if (x <= m) {
DB z = 0;
FOR(i, t, n) z += x * a[i];
return z;
} else {
DB z = 0;
FOR(i, t, n) z += m * a[i];
return z + gao(t, m, s-(n-t)*m);
}
}

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n,m,s); REP(i,n)RD(a[i]);
OT(gao(n,m,s));
}


## D Neq Neq

f[i] = f[i-1] + f[i-2] + pre，其中 pre 是所有符合上述判定的前缀和，注意别和长度 <= 3 的算重复了。

const int N = int(2e5) + 9;

Int f[N]; int a[N], c[N], cn;
int n;

x = a[x];
if (!c[x]) ++cn;
c[x] += 1;
}

void dec(int x) {
x = a[x];
c[x] -= 1;
if (!c[x]) --cn;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n); REP_1(i, n) RD(a[i]);

f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
Int z = 1, pre = 0;

int l = 1; REP_1(i, n) {
if (a[i] == a[i-1]) {
z *= f[i-1]; f[i-1] = 0; f[i] = 1;
while (l < i) dec(l++); add(i); pre = 0;
} else {
add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
f[i] = f[i-1] + f[i-2] + pre;
}
}
cout << z << endl;
}


## E K Different Values

(1 hour later … )