Submission #856715

#TimeUsernameProblemLanguageResultExecution timeMemory
856715Amirreza_FakhriSplit the sequence (APIO14_sequence)C++17
50 / 100
399 ms131072 KiB
// In the name oF the God #include <bits/stdc++.h> #define ll long long #define int long long #define pb push_back #define F first #define S second #define mp make_pair #define pii pair <int, int> #define smin(x, y) (x) = min((x), (y)) #define smax(x, y) (x) = max((x), (y)) #define halt(x) cout << x << '\n', exit(0) using namespace std; const int inf = 1e9 + 7; const int mod = 998244353; const int maxN = 1e5 + 5, maxK = 2e2 + 5; int n, k, ps[maxN], dp[2][maxN], opt[maxK][maxN]; int cost(int l, int r) { return ps[l] * (ps[r] - ps[l]); } void optimize(int q, int l, int r, int optl, int optr) { int mid = (r + l) >> 1, o; for (int i = optl; i < min(mid, optr); i++) { if (dp[1][mid] <= dp[0][i] + cost(i, mid)) { dp[1][mid] = dp[0][i] + cost(i, mid); o = i; } } if (r - l == 1) { opt[q][mid] = o; return; } optimize(q, l, mid, optl, o + 1); optimize(q, mid, r, o, optr); } void f(int pos, int q) { if (!q) return; cout << pos << ' '; f(opt[q][pos], q - 1); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; k++; for (int i = 1; i <= n; i++) { cin >> ps[i]; ps[i] += ps[i-1]; } for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = -inf * inf; dp[0][0] = 0; for (int i = 1; i <= k; i++) { optimize(i, i, n + 1, 0, n); for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i]; for (int i = 0; i <= n; i++) dp[1][i] = -inf * inf; } cout << dp[0][n] << '\n'; f(opt[k][n], k - 1); cout << '\n'; return 0; }

Compilation message (stderr)

sequence.cpp: In function 'void optimize(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:37:13: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     optimize(q, l, mid, optl, o + 1);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...