Submission #1000831

#TimeUsernameProblemLanguageResultExecution timeMemory
1000831vjudge1Split the sequence (APIO14_sequence)C++17
100 / 100
625 ms83000 KiB
/** * hello * author: N29 * created: 2024-06-15 09:16:01 **/ #include<bits/stdc++.h> using namespace std; #define ll long long // #define int ll #define ld long double #define y1 cheza mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N=1e5+2; const int M=5001; const int B=447; const int mod=998244353; const ll INF=1e9; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; const double eps=1e-6; struct line{ ll m,c,j; ll eval(ll x){ return m*x+c; } ld inter(line l){ return (ld)(c-l.c)/(l.m-m); } }; int n,k; int a[N]; ll dp[2][N]; int pr[201][N]; ll pref[N]; deque<line>q; bool check(line x,line y,line z){ return (z.c-x.c)*(x.m-y.m)<=(y.c-x.c)*(x.m-z.m); } void add(ll m,ll b,ll j){ line x={m,b,j}; while(q.size()>=2&&check(q[q.size()-2],q.back(),x)){ q.pop_back(); } q.push_back(x); } void query(int x){ while(q.size()>=2&&q[0].eval(x)<=q[1].eval(x)){ q.pop_front(); } } void test(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; pref[i]=pref[i-1]+a[i]; } // k++; for(int i=1;i<=k;i++){ q.clear(); for(int j=i;j<=n;j++){ // lc.add(pref[j-1],dp[i-1][j-1]-pref[j-1]*pref[j-1]); add(pref[j-1],dp[0][j-1]-pref[j-1]*pref[j-1],j-1); query(pref[j]); pr[i][j]=q.front().j; dp[1][j]=q.front().eval(pref[j]); } for(int j=i;j<=n;j++){ swap(dp[0][j],dp[1][j]); } } vector<int>v; int cur=n; for(int i=k;i>=1;i--){ cur=pr[i][cur]; v.push_back(cur); } cout<<dp[0][n]<<'\n'; reverse(v.begin(),v.end()); for(auto i:v){ cout<<i<<' '; } cout<<'\n'; } /* */ signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); int t2=1; // cin>>t2; for(int i=1;i<=t2;i++){ test(); } }
#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...