Submission #1215285

#TimeUsernameProblemLanguageResultExecution timeMemory
1215285cpdreamerSplit the sequence (APIO14_sequence)C++17
71 / 100
421 ms196608 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = (ll)1e9+7; #define P pair #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() void file() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } struct li_chao { private: struct line { ll m,p; ll evaluate(ll x) { return m*x+p; } line(ll _m=0,ll _p=-1e18):m(_m),p(_p){} }; struct node { line l; int id; node *left=nullptr; node *right=nullptr; node(line _l=line(),int _id=-1):l(_l),left(nullptr),right(nullptr),id(_id){} }; node neutral={line(),-1}; public: node *root=nullptr; ll x_min,x_max; void init(ll a,ll b) { x_min=a,x_max=b; } void insert(line x,int id,ll lx,ll rx,node *&nd) { if (!nd) { nd=new node(x,id); return; } ll m=(lx+rx)/2; bool m_b=x.evaluate(m)>nd->l.evaluate(m); bool l_b=x.evaluate(lx)>nd->l.evaluate(lx); if (m_b) { swap(x,nd->l); swap(id,nd->id); } if (rx-lx==0) { return; } if (l_b!=m_b) { insert(x,id,lx,m,nd->left); } else insert(x,id,m+1,rx,nd->right); } void insert(ll m,ll p,int id) { insert(line(m,p),id,x_min,x_max,root); } node calc(ll x,ll lx,ll rx,node *nd) { if (!nd) { return node(); } ll val=nd->l.evaluate(x); if (rx-lx==0) { return {nd->l,nd->id}; } ll m=(lx+rx)/2; if (x<=m) { node a=calc(x,lx,m,nd->left); if (val>a.l.evaluate(x)) { return {nd->l,nd->id}; } else { return a; } } else { node b=calc(x,m+1,rx,nd->right); if (val>b.l.evaluate(x)) { return {nd->l,nd->id}; } else { return b; } } } int calc(ll x) { return calc(x,x_min,x_max,root).id; } }; void solve() { int n,k; cin>>n>>k; k++; int a[n+1]; for (int i=1;i<=n;i++) { cin>>a[i]; } ll dp[n+1][k+1]; int best[n+1][k+1]; dp[0][0]=0LL; li_chao tree[k+1]; for (int i=0;i<=k;i++) { tree[i].init(0,1e9); } ll pref[n+1]; pref[0]=0LL; for (int i=1;i<=n;i++) { pref[i]=pref[i-1]+a[i]; } for (int i=1;i<=n;i++) { for (int j=1;j<=k;j++) { if (j==1) { dp[i][1]=0; best[i][1]=0; } else { int g=tree[j-1].calc(pref[i]); best[i][j]=g; if (g!=-1) { dp[i][j]=dp[g][j-1]+(pref[i]-pref[g])*pref[g]; } } } for (int j=1;j<=k;j++) { if (best[i][j]!=-1) { tree[j].insert(pref[i],dp[i][j]-pref[i]*pref[i],i); } } } cout<<dp[n][k]<<endl; int cur=n; V<int>vp; for (int i=k;i>=2;i--) { vp.pb(best[cur][i]); cur=best[cur][i]; } reverse(all(vp)); for (auto u:vp) { cout<<u<<" "; } cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //file(); solve(); return 0; }

Compilation message (stderr)

sequence.cpp: In function 'void file()':
sequence.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("output.txt","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...