Submission #23160

#	Time	Username	Problem	Language	Result	Execution time	Memory
23160		ngkan146	Split the sequence (APIO14_sequence)	C++98	71 / 100	779 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,a[100005];
vector <ll> dp[205];
int last[100005][205];
vector <ll> M,B,ID;
bool check(int id){
   return (B[id] - B[id-2]) * (M[id-2] - M[id-1]) <= (B[id-1] - B[id-2]) * (M[id-2] - M[id]);
}
void add_line(ll slope,ll val,ll id){
   M.push_back(slope);
   B.push_back(val);
   ID.push_back(id);
   while(M.size() >= 2 && M[M.size()-2] == M[M.size()-1]){
      if (B[M.size()-2] <= B[M.size()-1]){
         M.erase(M.end()-2);
         B.erase(B.end()-2);
         ID.erase(ID.end()-2);
      }
      else{
         M.erase(M.end()-1);
         B.erase(B.end()-1);
         ID.erase(ID.end()-1);
      }
   }
   while(M.size() >= 3 && check(M.size()-1)) ID.erase(ID.end()-2), M.erase(M.end()-2), B.erase(B.end()-2);
}
int ctrl;
ll get(ll x){
   ctrl = min(ctrl, (int)M.size()-1);
   while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] <= M[ctrl+1] * x + B[ctrl+1])
      ++ctrl;
   return ctrl;
}
int main(){
   scanf("%d %d",&n,&k);
   k++;
   for(int i=1;i<=n;i++)
      scanf("%d",&a[i]),
      a[i] += a[i-1];
   dp[0].assign(n+5,-(ll) 1e18);
   dp[0][0] = 0;
   for(int t=1;t<=k;t++){
      M.clear(); B.clear(); ID.clear();
      add_line(0,0,0);
      if (t >= 2) dp[t-2].clear();
      dp[t].assign(n+5,0);
      for(int i=1;i<=n;i++){
         int id = get(a[i]);
         dp[t][i] = M[id] * a[i] + B[id];
         last[i][t] = ID[id];
         add_line(a[i], dp[t-1][i] - 1ll * a[i] * a[i], i);
      }
   }
   vector <int> res;
   int mjk = n;
   for(int t=k;t>1;t--){
      res.push_back(last[mjk][t]);
      mjk = last[mjk][t];
   }
   reverse(res.begin(),res.end());
   printf("%lld\n",dp[k][n]);
   for(int i=0;i<res.size();i++) printf("%d ",res[i]);
   //cout << endl; for(int i=0;i<res.size();i++) cout << dp[i+1][res[i]] << ' ';
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'long long int get(long long int)':
sequence.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] <= M[ctrl+1] * x + B[ctrl+1])
               ^
sequence.cpp: In function 'int main()':
sequence.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<res.size();i++) printf("%d ",res[i]);
                 ^
sequence.cpp:37:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&n,&k);
                        ^
sequence.cpp:41:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       a[i] += a[i-1];
                     ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29