oj.uz

Submission #968921

# Submission time Handle Problem Language Result Execution time Memory
968921 2024-04-24T09:45:09 Z noyancanturk Split the sequence (APIO14_sequence) C++17
0 / 100
 11 ms 4184 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=1e5+100;
const int mod=1e9+7;
    
using pii=pair<int,int>;
    
void solve(){
    int n,k;
    cin>>n>>k;
    int a[n+1];
    a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    int dp[k+1][n+1];
    memset(dp,0,sizeof(dp));
    #define b(x) (dp[i-1][x]-a[x]*a[x])
    for(int i=1;i<=k;i++){
        deque<int>h;
        h.pb(i);
        for(int j=i+1;j<=n;j++){
            int sz;
            while(1<(sz=h.size())&&
                b(h[sz-1])+a[j]*a[h[sz-1]]
                <=
                b(h[sz-2])+a[j]*a[h[sz-2]]
            )h.pop_back();
            dp[i][j]=b(h[sz-1])+a[j]*a[h[sz-1]];
            while(1<h.size()&&
                (b(j)-b(h[0]))*(a[h[0]]-a[h[1]])
                <=
                (b(h[1])-b(h[0]))*(a[h[0]]-a[j])
            )h.pop_front();
            h.push_front(j);
        }
    }
    int ans=dp[k][n];
    cout<<ans<<"\n";
    int r=n;
    for(int i=n-1;0<=i;i--){
        if((a[r]-a[i])*a[i]+dp[k-1][i]==ans){
            cout<<i<<" ";
            ans-=(a[r]-a[i])*a[i];
            r=i;
            k--;
        }
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB contestant found the optimal answer: 108 == 108
2 Incorrect 0 ms 348 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB contestant didn't find the optimal answer: 1091288 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Extra information in the output file
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB contestant didn't find the optimal answer: 20180056 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4184 KB contestant didn't find the optimal answer: 6292740000 < 19795776960
2 Halted 0 ms 0 KB -