Submission #538698

#	Time	Username	Problem	Language	Result	Execution time	Memory
538698		nicholask	Split the sequence (APIO14_sequence)	C++14	0 / 100	59 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;
    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 i=1; i<=n-1; i++) dp[i][1]=ps[i]*(ps[n]-ps[i]);
    for (int i=1; i<=n-1; i++) bac[i][1]=i;
    for (int j=2; j<=k; j++){
        deque <int> q;
        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();
            dp[i][j]=dp[q[0]][j-1]+(ps[i]-ps[q[0]])*(ps[n]-ps[i]);
            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);
        }
    }
    int mx=-1e18,wh;
    for (int i=1; i<n; i++){
        if (dp[i][k]>mx){
            mx=dp[i][k];
            wh=i;
        }
    }
    cout<<mx<<'\n';
    vector <int> v;
    v.push_back(wh);
    for (int i=k; i>1; i--) v.push_back(bac[v.back()][i]);
    reverse(v.begin(),v.end());
    for (int i=0; i<v.size(); i++) cout<<v[i]<<" \n"[i+1==v.size()];
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:42:20: 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]
   42 |     for (int i=0; i<v.size(); i++) cout<<v[i]<<" \n"[i+1==v.size()];
      |                   ~^~~~~~~~~
sequence.cpp:42:57: 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]
   42 |     for (int i=0; i<v.size(); i++) cout<<v[i]<<" \n"[i+1==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