#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
ll dp[MAXN][201], pre[MAXN], par[MAXN][201];
int N, K;
struct line
{
mutable ll m, c, p, ind;
bool operator < (const line & o) const {return m < o.m;}
bool operator < (ll x) const {return p < x;}
};
struct CHT : multiset<line, less<>>
{
ll div(ll a,ll b) { return a/b - ((a^b) < 0 && a%b);}
bool isect(iterator x, iterator y)
{
if(y == end()) {x->p = INF; return false;}
if(x->m == y-> m) x->p = (x->c > y->c ) ? INF: -INF;
else x->p = div((y->c - x->c), (x->m - y->m));
return (x->p >= y->p);
}
void add(ll sl, ll in, ll i)
{
auto z = insert({sl, in, 0, i}), y = z++, x = y;
while(isect(y, z)) z = erase(z);
if(x != begin() && isect(--x,y)) isect(x, y = erase(y));
while((y=x) != begin() && (--x)->p >= y->p) isect(x,erase(y));
}
pll query(ll x)
{
if(empty()) while(true) cout<<1;
auto l = *lower_bound(x);
return mp(l.m * x + l.c, l.ind);
}
}box[201];
signed main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
ll p, q = INF;
cin>>N>>K;
pre[0] = 0;
F0Re(i, N)
cin>>p, pre[i] = p + pre[i-1];
p = 0;
// F0Re(i, N)
// cout<<pre[i]<<' ';
// cout<<endl;
F0R(i, N+1)
F0R(j, K+1)
dp[i][j] = par[i][j] = 0;
// F0Rr(k, j-1, i) dp[i][j] = max(dp[k][j-1] + pre[N]*pre[i] - pre[i]*pre[i] - pre[N]*pre[k] + pre[i]*pre[k]), dp[i][j]);
F0Re(i, N)
{
F0Re(j, min(i, K))
{
if(j == 1)
dp[i][j] = pre[i]*(pre[N] - pre[i]);
else {pll v = box[j-1].query(pre[i]); dp[i][j] = pre[N]*pre[i] - pre[i]*pre[i] + v.ff; par[i][j] = v.ss;}
// p = max(p, dp[i][j]);
}
if(i >= K) p = max(p, dp[i][K]);
F0Re(j,min(i, K))
box[j].add(pre[i], dp[i][j] - pre[i] * pre[N], i);
}
F0Re(i, N)
F0Re(j, K)
p = max(p, dp[i][j]);//, cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<", par["<<i<<"]["<<j<<"] = "<<par[i][j]<<'\n';
cout<<p<<'\n';
F0Re(i, N)
if(dp[i][K] == p)
{
q = i; break;
}
while(q and K)
{
cout<<q<<' ';
q = par[q][K--];
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
416 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
1 ms |
384 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
0 ms |
384 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
1 ms |
640 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
1 ms |
512 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1024 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
1024 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
8 ms |
2560 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
1 ms |
1024 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
8 ms |
2048 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
8 ms |
2048 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
6 ms |
2432 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
3 ms |
1536 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
3 ms |
1280 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
4 ms |
1664 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3712 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
3 ms |
3712 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
88 ms |
17528 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
3 ms |
3712 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
91 ms |
13816 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
62 ms |
11640 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
116 ms |
16888 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
108 ms |
17400 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
18 ms |
6144 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
30 ms |
8696 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
33664 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
37 ms |
33400 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Runtime error |
1542 ms |
131076 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
111 ms |
131076 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |