Submission #23156

#	Time	Username	Problem	Language	Result	Execution time	Memory
23156		ngkan146	Split the sequence (APIO14_sequence)	C++98	0 / 100	59 ms	89580 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() >= 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 ID[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;
         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]-1;
   }
   reverse(res.begin(),res.end());
   printf("%lld\n",dp[k][n]);
   for(int i=0;i<res.size();i++) printf("%d ",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:20: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:52: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:25: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:29: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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29