oj.uz

Submission #304413

# Submission time Handle Problem Language Result Execution time Memory
304413 2020-09-21T09:53:23 Z vipghn2003 Split the sequence (APIO14_sequence) C++14
0 / 100
 24 ms 4224 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int K=205;
int n,k,a[N],s[N],dp[K][N],opt[K][N];

void calc(int lev,int l,int r,int L,int R)
{
    if(l>r) return ;
    int mid=(l+r)/2;
    dp[lev][mid]=1e9;
    for(int i=L;i<=min(mid-1,R);i++)
    {
        if(dp[lev][mid]>dp[lev-1][i]+(s[mid]-s[i])*(s[mid]-s[i]))
        {
            dp[lev][mid]=dp[lev-1][i]+(s[mid]-s[i])*(s[mid]-s[i]);
            opt[lev][mid]=i;
        }
    }
    calc(lev,l,mid-1,L,opt[lev][mid]);
    calc(lev,mid+1,r,opt[lev][mid],R);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    k++;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    int res=s[n]*s[n];
    dp[1][0]=1e9;
    for(int i=1;i<=n;i++)
    {
        dp[1][i]=s[i]*s[i];
        opt[1][i]=i;
    }
    for(int lev=2;lev<=k;lev++) calc(lev,1,n,0,n-1);
    res-=dp[k][n];
    cout<<res/2<<'\n';
    int cur=n;
    while(k>1)
    {
        cur=opt[k][cur];
        k--;
        cout<<cur<<' ';
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 384 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Incorrect 0 ms 384 KB Integer 0 violates the range [1, 9]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 384 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 1 ms 896 KB Integer 0 violates the range [1, 49]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 384 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 3 ms 2560 KB Integer 0 violates the range [1, 199]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 384 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 16 ms 3840 KB Integer 0 violates the range [1, 999]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 KB Integer 0 violates the range [1, 9999]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4224 KB declared answer doesn't correspond to the split scheme: declared = -721128227, real = 7868806365
2 Halted 0 ms 0 KB -