# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
314798 | 2020-10-21T08:48:22 Z | noob_c0de | 수열 (APIO14_sequence) | C++17 | 3 ms | 384 KB |
#include<bits/stdc++.h> using namespace std; #define int long long #define ar array #define db double const int mxn=3002,INF=2e18; int n,k; int a[mxn]; int pref[mxn]; int dp[mxn][mxn]; int track[mxn][mxn]; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); cin>>n>>k; for (int i=1;i<=n;i++) { cin>>a[i]; pref[i]=pref[i-1]+a[i]; } int sum=pref[n]; for (int i=0; i<=n; i++) for (int j=0; j<=k+1; j++) dp[i][j]=INF; for (int i=1; i<=n; i++) dp[i][1]=pref[i]*pref[i]; for (int i=2;i<=n;i++) { for (int j=2;j<=k+1;j++) { for (int i2=1; i2<i; i2++) { int tmp=pref[i]-pref[i2]; if (dp[i][j]>dp[i2][j-1]+tmp*tmp) { dp[i][j]=dp[i2][j-1]+tmp*tmp; track[i][j]=i2; } } } } cout<<(sum*sum-dp[n][k+1])/2<<"\n"; stack<int> ans; while(track[n][k+1]) { n=track[n][k+1]; ans.push(n); k--; } while(!ans.empty()) { cout<<ans.top()<<" "; ans.pop(); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |