Submission #1169334

#TimeUsernameProblemLanguageResultExecution timeMemory
1169334icebearSplit the sequence (APIO14_sequence)C++20
100 / 100
642 ms84552 KiB
//https://dmoj.ca/problem/apio14p2 // ~~ icebear love attttt ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebearat" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 1e5 + 5; int n, k, a[N], trace[N][205]; ll dp_before[N], dp_cur[N], pref[N]; class ConvexHullTrick { private: struct Line { long long a, b; int id; Line (long long _a = 0, long long _b = 0, int _id = 0): a(_a), b(_b), id(_id) {} long long eval(long long x) { return a * x + b; } }; deque<Line> hull; bool bad(Line l1, Line l2, Line l3) { // assert(l1.a != l2.a); // assert(l1.a != l3.a); /** if intersect of (l1, l3) < intersect of (l1, l2) then we dont need to use l2 because f_i(x) will better with l1 or l3 */ return (l3.b - l1.b) * (l1.a - l2.a) <= (l1.a - l3.a) * (l2.b - l1.b); } void eraseLine(long long x) { while(hull.size() >= 2 && hull[0].eval(x) <= hull[1].eval(x)) hull.pop_front(); } public: void reset() { hull.clear(); } void addLine(long long a, long long b, int id) { Line l = Line(a, b, id); while(hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), l)) hull.pop_back(); hull.push_back(l); } pair<long long, int> query(long long x) { /** find max f_i(x) */ assert(hull.size()); eraseLine(x); return make_pair(hull[0].eval(x), hull[0].id); } } CHT; void init(void) { cin >> n >> k; FOR(i, 1, n) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } } void process(void) { memset(dp_before, -0x3f, sizeof dp_before); const ll NEG_INF = dp_before[0]; dp_before[0] = 0; k++; FOR(j, 1, k) { memset(dp_cur, -0x3f, sizeof dp_cur); CHT.reset(); FOR(i, j, n) { if (dp_before[i - 1] != NEG_INF) CHT.addLine(pref[i - 1], dp_before[i - 1] - pref[i - 1] * pref[n], i - 1); auto cht = CHT.query(pref[i]); if (maximize(dp_cur[i], cht.first + pref[i] * (pref[n] - pref[i]))) trace[i][j] = cht.second; } FOR(i, 0, n) dp_before[i] = dp_cur[i]; } cout << dp_cur[n] << endl; while(n && k > 1) { cout << (n = trace[n][k--]) << ' '; } } int 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); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

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