# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
159137 | 2019-10-21T07:30:16 Z | nafis_shifat | 수열 (APIO14_sequence) | C++14 | 353 ms | 131076 KB |
#include<bits/stdc++.h> #define pii pair<int,int> #define ll long long using namespace std; const ll inf=1e15; int path[100000+10][200+10]={}; void print(int st,int k) { if(path[st][k]==0) { cout<<st<<" "; return; } print(path[st][k],k-1); cout<<st<<" "; } int main() { int n,k; cin>>n>>k; ll dp[n+10][k+10]={}; ll a[n+5]={}; ll cum1[n+5]={}; ll cum2[n+5]={}; for(int i=1;i<=n;i++) { cin>>a[i]; cum1[i]=cum1[i-1]+a[i]; } for(int i=n;i>0;i--)cum2[i]=cum2[i+1]+a[i]; for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=0; for(int i=0;i<=n;i++) { dp[i][0]=0; dp[i][1]=cum1[i]*cum2[i+1]; path[i][1]=0; } for(int i=1;i<n;i++) { for(int j=2;j<=k && j<=i;j++) { int r=i-1; int l=j-1; int p=0; if(l==r) { dp[i][j]=dp[i-1][j-1]+(cum1[i]-cum1[i-1])*cum2[i+1]; path[i][j]=i-1; continue; } while(r>=l) { int mid1 = l+(r-l)/3; int mid2 = r-(r-l)/3; if(dp[mid1][j-1]+(cum1[i]-cum1[mid1])*cum2[i+1]>dp[mid2][j-1]+(cum1[i]-cum1[mid2])*cum2[i+1]) { r=mid2-1; p=mid1; } else { p=mid2; l=mid1+1; } } //cout<<i<<" "<<j<<endl; dp[i][j]=dp[p][j-1]+(cum1[i]-cum1[p])*cum2[i+1]; path[i][j]=p; } } ll mx=0,st; for(int i=1;i<=n;i++) { if(dp[i][k]>mx) { mx=dp[i][k]; st=i; } } cout<<mx<<endl; print(st,k); //for(int i=1;i<=10;i++)cout<<dp[i][3]+(cum1[11]-cum1[i])*cum2[12]<<" "<<dp[i][3]<<endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 2 ms | 256 KB | contestant found the optimal answer: 999 == 999 |
3 | Runtime error | 6 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Correct | 2 ms | 376 KB | contestant found the optimal answer: 1005304678 == 1005304678 |
6 | Incorrect | 2 ms | 376 KB | contestant didn't find the optimal answer: 933701 < 933702 |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Correct | 4 ms | 760 KB | contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 | Correct | 2 ms | 504 KB | contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 | Correct | 3 ms | 760 KB | contestant found the optimal answer: 1019625819 == 1019625819 |
6 | Correct | 4 ms | 760 KB | contestant found the optimal answer: 107630884 == 107630884 |
7 | Correct | 4 ms | 892 KB | contestant found the optimal answer: 475357671774 == 475357671774 |
8 | Correct | 3 ms | 632 KB | contestant found the optimal answer: 193556962 == 193556962 |
9 | Incorrect | 3 ms | 504 KB | contestant didn't find the optimal answer: 482389909806 < 482389919803 |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1272 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 3 ms | 1272 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Correct | 22 ms | 2808 KB | contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 | Correct | 3 ms | 1400 KB | contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 | Incorrect | 23 ms | 2900 KB | contestant didn't find the optimal answer: 679388317 < 679388326 |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 9848 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 14 ms | 9848 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Correct | 353 ms | 25436 KB | contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 | Correct | 17 ms | 9848 KB | contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 | Incorrect | 257 ms | 18936 KB | contestant didn't find the optimal answer: 1085432160 < 1085432199 |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 153 ms | 95224 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 155 ms | 95276 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Runtime error | 118 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |