Submission #1197676

#TimeUsernameProblemLanguageResultExecution timeMemory
1197676TahirAliyevSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // #define int long long #define ld long double #define ll long long #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; const int oo = 1e9 + 9; const int MAX = 4000 + 5, LOGMAX = 20, B = 441, MOD = 998244353; struct line{ int k, b; int f(int x){ return x * k + b; } ld inter(line a){ return (a.b - b) / (k - a.k); } }; void solve(){ int n, k; cin >> n >> k; k++; int arr[n + 1]; int pre[n + 1]; pre[0] = 0; for(int i = 1; i <= n; i++){ cin >> arr[i]; pre[i] = pre[i - 1] + arr[i]; } vector<int> dp(n + 1, -oo); dp[0] = 0; //dp[i] = (dp[j] - pre[j] * pre[j]) + pre[i] * pre[j]; vector<int> par[k]; while(k--){ vector<int> ndp(n + 1, -oo); par[k].resize(n + 1, 0); deque<line> dq; deque<int> id; dq.push_back({0, dp[0]}); id.push_back(0); for(int i = 1; i <= n; i++){ while(dq.size() >= 2 && dq[0].f(pre[i]) < dq[1].f(pre[i])){ dq.pop_front(); id.pop_front(); } ndp[i] = dq[0].f(pre[i]); par[k][i] = id[0]; line a = {pre[i], dp[i] - pre[i] * pre[i]}; while(dq.size() >= 2 && a.k != dq.back().k && a.inter(dq[dq.size()-2]) >= dq.back().inter(dq[dq.size()-2])){ dq.pop_back(); id.pop_back(); } while(dq.size() >= 2 && a.k == dq.back().k && a.b >= dq.back().b){ dq.pop_back(); id.pop_back(); } if(!dq.size() || dq.back().k != a.k){ dq.push_back(a); id.push_back(i); } } swap(ndp, dp); } cout << dp[n] << '\n'; int i = n; k = 0; while(i != 0){ if(i != n) cout << i << ' '; i = par[k][i]; k++; } cout << '\n'; } signed main(){ // ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); int t = 1; // cin >> t; while(t--) solve(); }
#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...