Submission #314798

#TimeUsernameProblemLanguageResultExecution timeMemory
314798noob_c0deSplit the sequence (APIO14_sequence)C++17
0 / 100
3 ms384 KiB
#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 (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |     freopen("sequence.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     freopen("sequence.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...