Submission #1255254

#TimeUsernameProblemLanguageResultExecution timeMemory
1255254duybinhbeoSplit the sequence (APIO14_sequence)C++20
0 / 100
182 ms158784 KiB
#include <bits/stdc++.h> #define ll long long #define int long long using namespace std; int dp[100001][201]; int a[100001]; int b[100001]; int trace[100001][201]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); freopen("inp.txt","r",stdin); freopen("out.txt","w",stdout); int n,k; cin >> n >> k; for (int i = 1; i <= n; ++i){ cin >> a[i]; b[i]=b[i-1]+a[i]; } for (int j = 2; j <= k+1; ++j){ for (int i = 1; i <= n; ++i){ for (int q = 1; q < i; ++q){ if (dp[i][j] <= dp[q][j-1]+b[q]*(b[i]-b[q])){ dp[i][j] = max(dp[i][j],dp[q][j-1]+b[q]*(b[i]-b[q])); trace[i][j] = q; } } } } cout << dp[n][k+1] << '\n'; int d = k+1,u = n; vector<int>ans; while (d > 1){ ans.push_back(trace[u][d]); u = trace[u][d]; --d; } reverse(ans.begin(),ans.end()); for (int i : ans) cout << i << ' '; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("inp.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("out.txt","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...