Submission #683220

#TimeUsernameProblemLanguageResultExecution timeMemory
683220Markomafko972Split the sequence (APIO14_sequence)C++14
71 / 100
2085 ms84688 KiB
#include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); int n, k; int a[100005]; ll p[100005]; ll dp[100005][2]; int gdje[100005][205]; vector< pair<int, int> > v; void rek(int x, int y) { if (y == 0) return; cout << x << " "; rek(gdje[x][y], y-1); } int ccw(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3) { ll out = p1.X * (p2.Y - p3.Y) + p2.X * (p3.Y - p1.Y) + p3.X * (p1.Y - p2.Y); if (out > 0) return 1; if (out == 0) return 0; if (out < 0) return -1; } pair<ll, ll> cord(int x, int y) { return {p[x], dp[x][0]-p[x]*p[x]}; } ll val(int x, int y, ll tren) { return dp[x][0]-p[x]*p[x]+p[x]*tren; } void dodaj(int x, int y) { if (v.size() == 0) { v.push_back({x, y}); return; } pair<int, int> z = v.back(); v.pop_back(); while ((int)v.size() > 0 && ccw(cord(v.back().X, v.back().Y), cord(z.X, z.Y), cord(x, y)) >= 0) { z = v.back(); v.pop_back(); } v.push_back(z); v.push_back({x, y}); } int query(int pref) { int lo = 0, hi = (int)v.size()-2; while (lo < hi) { int mid = (lo + hi) / 2; if (val(v[mid].X, v[mid].Y, pref) < val(v[mid+1].X, v[mid+1].Y, pref)) lo = mid+1; else hi = mid; } if (val(v[lo].X, v[lo].Y, pref) < val(v[lo+1].X, v[lo+1].Y, pref)) return v[lo+1].X; return v[lo].X; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = p[i-1] + a[i]; } for (int i = 2; i <= k+1; i++) { for (int j = 1; j <= n; j++) { if (dp[j][0] != -INF) dodaj(j, i-1); } for (int j = 1; j <= n; j++) { int pos = query(p[j]); pos = min(pos, j-1); gdje[j][i] = pos; if (dp[pos][0] == -INF) dp[j][1] = -INF; else dp[j][1] = val(pos, i-1, p[j]); if (pos < 1) dp[j][1] = -INF; } for (int j = 1; j <= n; j++) { dp[j][0] = dp[j][1]; dp[j][1] = 0; } v.clear(); } cout << dp[n][0] << "\n"; rek(gdje[n][k+1], k); return 0; }

Compilation message (stderr)

sequence.cpp: In function 'int ccw(std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
sequence.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^
#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...