제출 #42739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42739		Hassoony	수열 (APIO14_sequence)	C++14	71 / 100	660 ms	86084 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1e5+9;
ll n,K,pos,a[MX],dp[MX],dp1[MX],p[MX];
vector<ll>M,B;
vector<int>ID;
int fdp[202][MX];
bool bad(ll m1,ll b1,ll m2,ll b2,ll m3,ll b3){
    return 1.0*(b1-b3)*(m2-m1)<1.0*(b1-b2)*(m3-m1);
}
void add(ll m,ll b,ll idx){
    while(M.size()>=2&&bad(M[M.size()-2],B[B.size()-2],M[M.size()-1],B[B.size()-1],m,b))
        M.pop_back(),B.pop_back(),ID.pop_back();
    M.push_back(m);
    B.push_back(b);
    ID.push_back(idx);
}
ll query(ll x){
    if(pos>(int)M.size()-1)pos=(int)M.size()-1;
    while(pos+1<(int)M.size()&&1.0*M[pos+1]*x+B[pos+1]>=1.0*M[pos]*x+B[pos])
        pos++;
    return M[pos]*x+B[pos];
}
int main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        p[i]=p[i-1]+a[i];
    }
    for(int i=1;i<=K;i++){
        B.clear();
        M.clear();
        ID.clear();
        pos=0;
        add(p[i],-p[i]*p[i]+dp[i],i);
        for(int j=i+1;j<=n;j++){
            if(j>i+1&&p[j]==p[j-1]){
                dp1[j]=dp1[j-1];
                fdp[i][j]=fdp[i][j-1];
                continue;
            }
            dp1[j]=query(p[j]);
            if(pos>(int)ID.size()-1)pos=ID.size()-1;
            fdp[i][j]=ID[pos];
            if(p[j]!=p[j-1])add(p[j],-p[j]*p[j]+dp[j],j);
        }
        for(int k=1;k<=n;k++)dp[k]=dp1[k];
    }
    printf("%lld\n",dp[n]);
    for(int i=K,j=n;i>=1;){
        j=fdp[i][j];
        i--;
        printf("%d ",j);
    }
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:28:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^

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