oj.uz

Submission #968923

# Submission time Handle Problem Language Result Execution time Memory
968923 2024-04-24T09:45:41 Z noyancanturk Split the sequence (APIO14_sequence) C++17
22 / 100
 16 ms 4696 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 348 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 348 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 348 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 348 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 344 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 344 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 348 KB contestant found the optimal answer: 1 == 1
9 Correct 0 ms 344 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 348 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 348 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 600 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 344 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 600 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 1 ms 348 KB contestant found the optimal answer: 805 == 805
16 Correct 1 ms 344 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 348 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 348 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 604 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 344 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 0 ms 348 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 600 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 352 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 0 ms 352 KB contestant found the optimal answer: 687136 == 687136
9 Correct 0 ms 348 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 0 ms 348 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 1 ms 348 KB Extra information in the output file
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

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