Submission #552512

#TimeUsernameProblemLanguageResultExecution timeMemory
552512tht2005Split the sequence (APIO14_sequence)C++17
0 / 100
62 ms131072 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = numeric_limits<LL>::max() / 2; const int N = 100001; const int K = 201; int n, kk, s[N]; LL f[K][N]; int main() { scanf("%d %d", &n, &kk); for(int i = 1; i <= n; ++i) { int a; scanf("%d", &a); s[i] = s[i - 1] + a; } memset(f, 0, sizeof(f)); for(int t = 1; t <= kk; ++t) { for(int i = t + 1; i <= n; ++i) { for(int j = i - 1; j >= t; --j) { f[t][i] = max(f[t][i], f[t - 1][j] + (LL)s[j] * (s[i] - s[j])); } } } printf("%lld\n", f[kk][n]); for(int i, j = n; kk--; ) { for(i = j; i--; ) { if(f[kk + 1][j] == f[kk][i] + (LL)s[i] * (s[j] - s[i])) { printf("%d ", i); j = i; break; } } } return 0; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d %d", &n, &kk);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
#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...