Submission #1155696

#TimeUsernameProblemLanguageResultExecution timeMemory
1155696SangSplit the sequence (APIO14_sequence)C++20
100 / 100
686 ms96188 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--) #define fi first #define se second #define pb push_back #define ALL(a) (a).begin(), (a).end() #define task "kbsiudthw" typedef vector<int> vi; typedef pair<int, int> ii; typedef pair<int, ii> pii; const int N = 1e5 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 2277; int n, k, a[N], dp[205]; int32_t opt[N][205]; struct Line{ int a, b, pos; Line(int a = 0, int b = 0, int pos = -1) : a(a), b(b), pos(pos) {}; int eval(int x){ return a * x + b ;} long double intersectX(Line A){ return (long double)(b - A.b)/(A.a - a); } }; deque<Line> hull[205]; bool bad(Line A, Line B, Line C){ return A.intersectX(C) <= A.intersectX(B); } void addLine(int x, int y, int pos, int id){ Line nw(x, y, pos); while (hull[id].size() >= 2 && bad(hull[id][hull[id].size() - 2], hull[id].back(), nw)) hull[id].pop_back(); hull[id].pb(nw); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> k; FOR (i, 1, n) cin >> a[i], a[i] += a[i-1]; addLine(0, 0, 0, 0); int pos = 1, val = -1e9; FOR (i, 1, n){ FOR (j, 1, k) dp[j] = -1e9; FORD (j, k, 1){ if (hull[j-1].empty()) continue; while (hull[j-1].size() >= 2 && hull[j-1][0].eval(a[i]) <= hull[j-1][1].eval(a[i])) hull[j-1].pop_front(); dp[j] = hull[j-1][0].eval(a[i]) - a[i] * a[i] + a[i] * a[n]; opt[i][j] = hull[j-1][0].pos; addLine(a[i], -a[i] * a[n] + dp[j], i, j); } if (dp[k] > val){ val = dp[k]; pos = i; } } cout << val << '\n'; vi ans; while (pos){ ans.pb(pos); pos = opt[pos][k--]; } reverse(ALL(ans)); for (int &x : ans) cout << x << ' '; return 0; }

Compilation message (stderr)

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