Submission #1000818

#TimeUsernameProblemLanguageResultExecution timeMemory
1000818vjudge1Split the sequence (APIO14_sequence)C++17
71 / 100
304 ms131072 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+100; 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{ int m,c; int eval(int x){ return m*x+c; } ld inter(line l){ return (ld)(c-l.c)/(l.m-m); } }; int n,k; int a[N]; int dp[202][N]; int 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(int m,int b){ line x={m,b}; while(q.size()>=2&&check(q[q.size()-2],q.back(),x)){ q.pop_back(); } q.push_back(x); } int query(int x){ while(q.size()>=2&&q[0].eval(x)<=q[1].eval(x)){ q.pop_front(); } return q.front().eval(x); } 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[i-1][j-1]-pref[j-1]*pref[j-1]); dp[i][j]=query(pref[j]); } } vector<int>v; int cur=n; for(int i=k-1;i>=0;i--){ for(int j=cur;j>=1;j--){ int d=dp[i][j-1]+pref[j-1]*(pref[cur]-pref[j-1]); if(dp[i+1][cur]==d){ cur=j-1; v.push_back(j-1); break; } } } // for(int i=1;i<=k;i++){ // for(int j=1;j<=n;j++){ // cout<<dp[i][j]<<' '; // } // cout<<'\n'; // } cout<<dp[k][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...