Submission #166131

#TimeUsernameProblemLanguageResultExecution timeMemory
166131ZwariowanyMarcinSplit the sequence (APIO14_sequence)C++14
78 / 100
1792 ms81912 KiB
#include <bits/stdc++.h> #define ll long long #define mp make_pair #define pb push_back #define ld long double #define ss(x) (int) x.size() #define FOR(i, n) for(int i = 1; i <= n; ++i) #define fi first #define se second #define cat(x) cout << #x << " = " << x << endl using namespace std; const int nax = 1e5 + 111; const long long inf = 1e18; int n, k; int a[nax]; ll dp[nax][2]; int opt[nax][202]; int pref[nax]; int ja, on, K; void solve(int l, int r, int optl, int optr) { if(l > r) return; int m = (l + r) / 2; for(int i = optl; i <= min(m, optr); ++i) { ll w = dp[i - 1][on] + 1ll * (pref[m] - pref[i - 1]) * (pref[m] - pref[i - 1]); if(w < dp[m][ja]) { opt[m][K] = i; dp[m][ja] = w; } } solve(l, m - 1, optl, opt[m][K]); solve(m + 1, r, opt[m][K], optr); } int main() { scanf("%d %d", &n, &k); k += 1; for(int i = 1; i <= n; ++i) { scanf("%d", a + i); pref[i] = pref[i - 1] + a[i]; } for(int i = 1; i <= n; ++i) dp[i][0] = inf; for(int i = 1; i <= k; ++i) { K = i; ja = i & 1; on = !ja; for(int j = 0; j <= n; ++j) dp[j][ja] = inf; solve(1, n, 1, n); } ll kwa = 1ll * pref[n] * pref[n]; printf("%lld\n", (kwa - dp[n][k & 1]) / 2); vector <int> v; int ind = n; while(k > 1) { assert(ind > 0); assert(opt[ind][k] > 1); v.pb(opt[ind][k]); ind = opt[ind][k] - 1; k -= 1; } reverse(v.begin(), v.end()); for(auto it : v) printf("%d ", it - 1); return 0; }

Compilation message (stderr)

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