#include<cstdio>
#include<stack>
#include<climits>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
// #define fread fread_unlocked
// #define fwrite fwrite_unlocked
inline char gtx(){
const int N=4096;
static char buffer[N];
static char *p=buffer,*end=buffer;
if(p==end){
if((end=buffer+fread(buffer,1,N,stdin))==buffer)return EOF;
p=buffer;
} return *p++;
}
template<typename T>
inline bool rit(T &x){
char c=0; bool fg=0;
while(c=gtx(), (c<'0' && c!='-') || c>'9')if(c==EOF)return false;
c=='-' ? (fg=1,x=0) : (x=c&15);
while(c=gtx(), c>='0' && c<='9')x=x*10+(c&15);
if(fg)x=-x; return true;
}
template<typename T,typename ...Args>
inline bool rit(T& x,Args& ...args){return rit(x)&&rit(args...);}
struct outputter{
char buffer[4112],*ptr=buffer,*end=buffer+4096;
template<typename T>inline void write(T x,char endc='\n'){
if(x<0)*ptr='-',++ptr,x=-x; if(!x)*ptr='0',++ptr;
char *s=ptr,c; T t;
while(x){t=x/10; c=x-10*t+'0'; *ptr=c,++ptr,x=t;}
char *f=ptr-1; while(s<f)swap(*s,*f),++s,--f;
if(ptr>end)fwrite(buffer,sizeof(char),ptr-buffer,stdout),ptr=buffer;
*ptr=endc,++ptr;
}
template<typename T>
inline void output(T x){ write(x,'\n'); }
template<typename T,typename ...Args>
inline void output(T x,Args ...args){ write(x,' '); output(args...); }
template<typename ...Args> inline void operator()(Args ...args){ output(args...); }
outputter(){}
~outputter(){ fwrite(buffer,sizeof(char),ptr-buffer,stdout); }
} pit;
#pragma GCC diagnostic pop
int n,k;
ll a[100005],pre[100005],dp[205][100005];
int tp[205][100005];
#ifdef meow
val=(pre[n]-pre[j])*(pre[j]-pre[k-1])+dp[i-1][k-1];
=pre[n]*pre[j]-pre[n]*pre[k-1]-pre[j]^2+pre[j]*pre[k-1]+dp[i-1][k-1]
=pre[j]*pre[k-1]-pre[n]*pre[k-1]+dp[i-1][k-1]+pre[n]*pre[j]-pre[j]^2
k from i to j
#endif
struct line{
ll m,y;
int i;
ll get(ll x){ return m*x+y; }
line(ll m,ll y,int i):m(m),y(y),i(i){}
};
double crx(line a,line b){
return (double)(b.y-a.y)/(a.m-b.m);
}
ostream& operator<<(ostream &o,line l){
o<<"("<<l.m<<" , "<<l.y<<" : "<<l.i<<")";
return o;
}
template<typename T> ostream& operator<<(ostream &o,deque<T> dq){
o<<"[";
for(T i:dq)cout<<i<<" , ";
o<<"]";
return o;
}
int main(){
rit(n,k);
for(int i=1;i<=n;++i)rit(a[i]);
for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i];
memset(dp+1,0xb0,100004<<3);
for(int i=1;i<=k;++i){
deque<line> dq;
for(int j=i;j<=n;++j){
line nl(pre[j-1],-pre[n]*pre[j-1]+dp[i-1][j-1],j-1);
// while(dq.size()>1u && crx(dq[dq.size()-2],nl)<=crx(dq[dq.size()-1],nl))dq.pop_back();
while(dq.size()>1u && (__int128)(nl.y-dq[dq.size()-2].y)*(dq[dq.size()-1].m-nl.m)>=(__int128)(nl.y-dq[dq.size()-1].y)*(dq[dq.size()-2].m-nl.m))dq.pop_back();
dq.push_back(nl);
while(dq.size()>1u && dq[0].get(pre[j])<=dq[1].get(pre[j])){
// cout<<dq[0].get(pre[j])<<" "<<dq[1].get(pre[j])<<endl;
dq.pop_front();
}
dp[i][j]=dq[0].get(pre[j])+pre[n]*pre[j]-pre[j]*pre[j];
tp[i][j]=dq[0].i;
// cout<<i<<" "<<j<<" "<<dq<<endl;
}
/* for(int j=n;j>=i;--j){
if(i==1)tp[i-1][j]=1;
if(j==n)tp[i][j+1]=n;
ll mx=LLONG_MIN,val;
int p=-1;
for(int k=tp[i-1][j];k<=tp[i][j+1];++k){
val=(pre[n]-pre[j])*(pre[j]-pre[k-1])+dp[i-1][k-1];
if(val>mx){
mx=val;
p=k;
}
}
tp[i][j]=p;
dp[i][j]=mx;
} */
}
ll mx=LLONG_MIN;
int p=-1;
for(int i=k;i<=n;++i){
if(dp[k][i]>mx){
mx=dp[k][i];
p=i;
}
}
pit(mx);
int zi=k,zj=p;
stack<int> ans;
while(zi){
ans.push(zj);
zj=tp[zi][zj];
--zi;
}
while(ans.size()){
pit.write(ans.top(),' ');
ans.pop();
}
/* for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
cout<<tp[i][j]<<" ";
}
cout<<endl;
}
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
cout<<dp[i][j]<<" ";
}
cout<<endl;
} */
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1144 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
3 ms |
1144 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
3 ms |
1160 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
2 ms |
1236 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
2 ms |
1492 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
2 ms |
1492 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
3 ms |
1492 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
2 ms |
1492 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
3 ms |
1504 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1504 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
3 ms |
1504 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
4 ms |
1892 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
2 ms |
1892 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
3 ms |
1892 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
7 ms |
3556 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
3 ms |
3556 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
5 ms |
3556 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
5 ms |
3556 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
5 ms |
3760 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
4 ms |
3760 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
3 ms |
3760 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
4 ms |
3760 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3760 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
4 ms |
3760 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
14 ms |
5484 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
3 ms |
5484 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
14 ms |
5612 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
18 ms |
5612 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
14 ms |
5612 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
11 ms |
5612 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
5 ms |
5612 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
7 ms |
5612 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5612 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
5 ms |
5612 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Correct |
136 ms |
26896 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 |
Correct |
4 ms |
26896 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 |
Correct |
120 ms |
26896 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
6 |
Correct |
92 ms |
26896 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
7 |
Correct |
96 ms |
26896 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
8 |
Correct |
67 ms |
26896 KB |
contestant found the optimal answer: 3099592898816 == 3099592898816 |
9 |
Correct |
72 ms |
26896 KB |
contestant found the optimal answer: 1241131419367412 == 1241131419367412 |
10 |
Correct |
103 ms |
26896 KB |
contestant found the optimal answer: 1243084101967798 == 1243084101967798 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
26896 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
2 |
Correct |
19 ms |
26896 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
3 |
Correct |
988 ms |
237160 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
4 |
Correct |
19 ms |
237160 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
5 |
Correct |
1228 ms |
237172 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
6 |
Correct |
975 ms |
237172 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
7 |
Correct |
954 ms |
237172 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
8 |
Correct |
729 ms |
237172 KB |
contestant found the optimal answer: 309959349080800 == 309959349080800 |
9 |
Correct |
890 ms |
237172 KB |
contestant found the optimal answer: 124113525649823701 == 124113525649823701 |
10 |
Correct |
1075 ms |
237172 KB |
contestant found the optimal answer: 124309619349406845 == 124309619349406845 |