Submission #60908410

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
const ll inf=1e18;
int n,k;
ll a[N],pre[N];
vector<vector<vector<ll>>>solve(int l,int r){
    int sum=(r-l)/k+1;
    vector<vector<vector<ll>>>f(k,vector<vector<ll>>(k,vector<ll>(sum+1,-inf)));
    if(l==r){
        for(int i=0;i<k;i++){
            for(int j=0;j<k;j++){
                f[i][j][0]=0;
                if(k==1){
                    f[i][j][1]=a[l];
                }
            }
        }
        return f;
    }
    int mid=(l+r)/2;
    vector<vector<vector<ll>>>fl=solve(l,mid),fr=solve(mid+1,r);
    int suml=(mid-l)/k+1,sumr=(r-mid-1)/k+1;
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            int p=0,q=0;
            while(p<=suml&&q<=sumr){
                f[i][j][p+q]=max(f[i][j][p+q],fl[i][0][p]+fr[0][j][q]);
                if(p==suml&&q==sumr){
                    break;
                }
                if(q==sumr||(p!=suml&&fl[i][0][p+1]-fl[i][0][p]>=fr[0][j][q+1]-fr[0][j][q])){
                    ++p;
                }else{
                    ++q;
                }
            }
            for(int x=1;x<k;x++){
                if(i+x>mid-l+1){
                    continue;
                }
                if(j+k-x>r-mid){
                    continue;
                }
                int p=0,q=0;
                while(p<=suml&&q<=sumr){
                    if(p+q+1<=sum){
                        f[i][j][p+q+1]=max(f[i][j][p+q+1],fl[i][x][p]+fr[k-x][j][q]+(pre[mid+k-x]-pre[mid-x]));
                    }
                    if(p==suml&&q==sumr){
                        break;
                    }
                    if(q==sumr||(p!=suml&&fl[i][x][p+1]-fl[i][x][p]>=fr[k-x][j][q+1]-fr[k-x][j][q])){
                        ++p;
                    }else{
                        ++q;
                    }
                }
            }
        }
    }
    return f;
}
ll ans[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    vector<vector<vector<ll>>>f=solve(1,n);
    memset(ans,-0x3f,sizeof ans);
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            for(int p=1;p<=n/k;p++){
                ans[p]=max(ans[p],f[i][j][p]);
            }
        }
    }
    for(int i=1;i<=n/k;i++){
        printf("%lld ",ans[i]);
    }
    printf("\n");
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:67:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Judge Result