Submission #1000679

#TimeUsernameProblemLanguageResultExecution timeMemory
1000679vjudge1Split the sequence (APIO14_sequence)C++17
49 / 100
2037 ms89276 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 30, MOD = 1e9 + 7; int n,k; ll a[N]; ll pref[N],sf[N]; int p[N][201]; ll dp[N],tdp[N]; struct line{ ll k,b; int pos = 0; ll get(ll x){ return k * x + b; } }; long double cross(line a,line b){ return ((a.b - b.b) * 1.0 / ((b.k - a.k) * 1.0)); } void add(vector<line> &st,line l){ while((int)st.size() > 1 && cross(l,st[(int)st.size() - 2]) <= cross(l,st.back())){ st.pop_back(); } st.push_back(l); } pair<ll,ll> get(vector<line> &st,ll x){ int l = -1,r = (int)st.size() - 1; while(r - l > 1){ int mid = (l + r) >> 1; if(mid == (int)st.size() - 1 || (st[mid].b - st[mid + 1].b) * 1.0 >= x * 1.0 * (st[mid + 1].k - st[mid].k)){ r = mid; }else{ l = mid; } } ll ret =0 ,pos = 0; for(int i = 0;i < (int)st.size();i++){ if(st[i].get(x) > ret){ ret = st[i].get(x); pos = st[i].pos; } } // cout << x << ' ' << st[0].k << ' ' << st[1].k<< ' ' << r << "x\n"; return {st[r].get(x),st[r].pos}; } void test(){ cin >> n >> k; for(int i = 1;i <= n;i++){ cin >> a[i]; } for(int i = 1;i <= n;i++){ pref[i] = pref[i - 1] + a[i]; } for(int i = n;i >= 1;i--){ sf[i] = sf[i + 1] + a[i]; } for(int i = 1;i <= k;i++){ vector<line> st; add(st,{0,0}); for(int j = 1;j <= n;j++){ pair<ll,ll> G = get(st,sf[j + 1]); dp[j] = G.first+ pref[j] * sf[j + 1]; p[j][i] = G.second; line nv = {-pref[j],tdp[j],j}; add(st,nv); // for(int prev = 0;prev < j;prev++){ // dp[j] = max(dp[j],tdp[prev] + pref[j] * sf[j + 1] - pref[prev] * sf[j + 1]); // } } for(int j = 1;j <= n;j++){ tdp[j] = dp[j]; dp[j] =0 ; } } ll res = 0; int ps = 0; for(int i = 1;i <= n;i++){ if(tdp[i] > res){ res = tdp[i]; ps = i; } } vector<int> f; cout << res << '\n'; int k1 = k; while(k){ f.push_back(ps); ps = p[ps][k--]; } reverse(f.begin(),f.end()); assert((int)f.size() == k1); for(int j:f){ cout << j << ' '; } } int main() { ios_base::sync_with_stdio(false);cin.tie(0); int t = 1; // cin >> t; while(t--){ test(); } }

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> get(std::vector<line>&, ll)':
sequence.cpp:40:16: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   40 |     ll ret =0 ,pos = 0;
      |                ^~~
#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...