Submission #1039326

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039326	2024-07-30T17:47:19 Z	fimh	Split the sequence (APIO14_sequence)	C++14	0 / 100	19 ms	59612 KB

sequence

#include <bits/stdc++.h>
// #define int long long
#define fi first
#define pll pair<long long,long long>
#define se second
#define isz(x) (int)(x).size()
using namespace std;
using ll=long long;

const long long inf = 1e18;
const int mod = 1e9+7;
const int maxn = 1e4+5;
const int block = 500;

int trace[maxn][maxn],ps[maxn];
ll dp[maxn][2];

void compute(int j,int l,int r,int optl,int optr){
    if (l>r)return;
    int mid=(l+r)>>1;
    pll best={inf,-1};
    for (int i=optl;i<=min(mid,optr);++i){
        int x=ps[mid]-ps[i-1];
        ll val=dp[i-1][0]+x*x;
        if (best.fi>=val){
            best={val,i};
            trace[mid][j]=i;
        }
    }
    dp[mid][1]=best.fi;
    int opt=best.se;
    compute(j,l,mid-1,optl,opt);
    compute(j,mid+1,r,opt,optr);
}

void test(){
    int n,k; cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>ps[i];
        ps[i]+=ps[i-1];
        dp[i][0]=ps[i]*ps[i];
    }
    for (int j=2;j<=k+1;++j){
        compute(j,1,n,1,n);
        for (int i=1;i<=n;++i)dp[i][0]=dp[i][1];
    }
    ll ans=(ps[n]*ps[n]-dp[n][0])/2;
    cout<<ans<<"\n";
    vector<int> path;
    int y=k+1,x=trace[n][y];
    while (y>1){
        path.push_back(x-1);
        x=trace[x-1][y]; --y;
    }
    reverse(path.begin(),path.end());
    for (int i : path) cout<<i<<" ";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    test();
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	1 ms	8540 KB	contestant found the optimal answer: 311760000 == 311760000
3	Runtime error	17 ms	17124 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-