oj.uz

Submission #1039322

# Submission time Handle Problem Language Result Execution time Memory
1039322 2024-07-30T17:41:13 Z fimh Split the sequence (APIO14_sequence) C++14
0 / 100
 20 ms 45148 KB 
#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 i=n,j=k+1;
    while (1){
        path.push_back(trace[i][j]-1);
        i=trace[i][j]-1; --j;
        if (j==1) break;
    }
    for (int i=isz(path)-1;i>=0;--i)cout<<path[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 Correct 1 ms 2392 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 2396 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 2396 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 2396 KB contestant found the optimal answer: 302460000 == 302460000
3 Runtime error 6 ms 4696 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 2 ms 6236 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 6 ms 6908 KB declared answer doesn't correspond to the split scheme: declared = 161463848256, real = 49671699352896
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 5208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -