제출 #20192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20192		jihoon	Split the sequence (APIO14_sequence)	C++98	71 / 100	2088 ms	86 KiB

sequence

#include<stdio.h>
int n,k;
long long sum[100001];
long long hsum[100001];
long long square[100001];
int backtrack[100001][201];
long long stk[100001][2];
long long dp[100001][2];
int stp;
long long inf;

long long calc(int i,int j,int turn){
    long long a = sum[i],c = sum[j],b = dp[i][turn]-hsum[i],d = dp[j][turn]-hsum[j];
    //printf("%lld %lld\n",a,c);
    if(a==c){
        if(b<d) return inf;
        else return 0;
    }
    if(b<d){
        return (b-d)/(c-a);
    }else{
        return (b-d+c-a-1)/(c-a);
    }
}

int main(){
    int now,target;
    long long ans,ansn;
    long long res;
    scanf("%d %d",&n,&k);
    inf = (1 << 31);
    inf*=inf;
    inf+=inf;
    inf--;
    for(int i=1;i<=n;i++){
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    for(int i=1;i<=n;i++){
        hsum[i]=sum[i]*sum[n];
        square[i]=sum[i]*sum[i];
    }
    for(int i=1;i<=n;i++){
        dp[i][1]=hsum[i]-square[i];
    }
    for(int j=2;j<=k;j++){
        stp=1;now=0;
        stk[0][0]=j-1;
        stk[0][1]=0;
        for(int i=j;i<=n;i++){
            while(now<stp-1){
                if(stk[now+1][1]<=sum[i]){
                    now++;
                }else{
                    break;
                }
            }
            target=(int)stk[now][0];
            //printf("%d\n",target);
            dp[i][j%2]=sum[target];
            dp[i][j%2]*=sum[i];
            dp[i][j%2]+=dp[target][1-(j%2)];
            dp[i][j%2]-=hsum[target];
            dp[i][j%2]+=hsum[i];
            dp[i][j%2]-=square[i];
            backtrack[i][j]=target;
            /*
            printf("Now Stack:\n");
            for(int ist=0;ist<stp;ist++){
                printf("%lld %lld\n",stk[ist][0],stk[ist][1]);
            }
            printf("%d %d %lld %d\n",i,j,dp[i][j%2],target);
            */
            while(stp>0){
                res=calc(stk[stp-1][0],i,1-(j%2));
                if(res<=stk[stp-1][1]){
                    stp--;
                    if(now==stp) now--;
                }else{
                    break;
                }
            }
            if(stp==0) res=0;
            stk[stp][0]=i;
            stk[stp][1]=res;
            stp++;
        }
    }
    ans=0;
    for(int i=1;i<=n;i++){
        if(dp[i][k%2]>ans){
            ans=dp[i][k%2];
            ansn=i;
        }
    }
    printf("%lld\n",ans);
    for(int stp=k;stp>=1;stp--){
        printf("%lld ",ansn);
        ansn=backtrack[ansn][stp];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
                         ^
sequence.cpp:36:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&sum[i]);
                              ^
sequence.cpp:99:33: warning: 'ansn' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ansn=backtrack[ansn][stp];
                                 ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29