Submission #538675

#	Time	Username	Problem	Language	Result	Execution time	Memory
538675		nicholask	Split the sequence (APIO14_sequence)	C++14	0 / 100	64 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[100001][201];
int bac[100001][201];
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,k;
    cin>>n>>k;
    k++;
    for (int i=0; i<=n; i++){
        for (int j=1; j<=k; j++) dp[i][j]=-1e18;
    }
    int a[n+1];
    for (int i=1; i<=n; i++) cin>>a[i];
    int ps[n+1]={};
    for (int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i];
    for (int j=1; j<=k; j++){
        deque <int> q;
        if (j==1) q.push_back(0);
        for (int i=1; i<=n; i++){
            while (q.size()>=2&&dp[q[1]][j-1]-dp[q[0]][j-1]>(ps[n]-ps[i])*(ps[q[1]]-ps[q[0]])) q.pop_front();
            if (q.size()) dp[i][j]=dp[q[0]][j-1]+(ps[i]-ps[q[0]])*(ps[n]-ps[i]);
            if (q.size()) bac[i][j]=q[0];
            while (q.size()>=2&&(dp[q.back()][j-1]-dp[q[q.size()-2]][j-1])*(ps[i]-ps[q.back()])<(dp[i][j-1]-dp[q.back()][j-1])*(ps[q.back()]-ps[q[q.size()-2]])) q.pop_back();
            q.push_back(i);
        }
    }
    cout<<dp[n][k]<<'\n';
    vector <int> v;
    v.push_back(n);
    for (int i=k; i>1; i--) v.push_back(bac[v.back()][i]);
    reverse(v.begin(),v.end());
    for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()];
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()];
      |                   ~~~^~~~~~~~~
sequence.cpp:34:59: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()];
      |                                                        ~~~^~~~~~~~~~

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