제출 #45885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45885		Extazy	Split the sequence (APIO14_sequence)	C++17	0 / 100	21 ms	17212 KiB

sequence

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const int N = 10007;
const int K = 204;
 
struct convex_hull_trick {
    struct line {
        long long a, b;
        
        line(){}
        line(long long x, long long y): a(x), b(y) {}
        
        template < class T >
        T eval(T x) {
            return a*x+b;
        }
    };
 
    vector < line > v;
 
    void clear() {
        v.clear();
    }
 
    double crossx(line l1, line l2) {
        double x=(double)(l2.b-l1.b)/(double)(l1.a-l2.a);
        return x;
    }
 
    double crossy(line l1, line l2) {
        double x=(double)(l2.b-l1.b)/(double)(l1.a-l2.a);
        return l1.eval(x);
    }
 
    void add_line(long long a, long long b) {
        line l(a,b);
 
        while(v.size()>=2 && crossy(l,v[v.size()-2])>=crossy(v[v.size()-1],v[v.size()-2])) {
            v.pop_back();
        }
 
        v.push_back(l);
    }
 
    long long get(long long x) {
        if(v.empty()) return numeric_limits < long long >::min();
 
        long long ans=max(v[0].eval(x),v[v.size()-1].eval(x));
        if(v.size()<=2) return ans;
 
        int left=0,right=(int)(v.size())-1,middle;
        while(right-left>1) {
            middle=(left+right)>>1;
            if(crossx(v[middle],v[middle+1])>=x) left=middle;
            else right=middle;
        }
 
        ans=max(ans,v[left].eval(x));
 
        return ans;
    }
};
 
int n,k,a[N],s[N],all_s;
long long dp[N][K];
convex_hull_trick cht[K];
vector < int > path;
 
void restore(int pos, int groups) {
    if(groups==1) return;
 
    int i;
    for(i=pos;i<=n;i++) {
        long long curr=(s[i]-s[pos-1])*1ll*(all_s-s[i]+s[pos-1])+dp[i+1][groups-1];
        if(curr==dp[pos][groups]) {
            path.push_back(i);
            restore(i+1,groups-1);
            return;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j;
 
    scanf("%d %d", &n, &k);
    for(i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        s[i]=a[i]+s[i-1];
    }
 
    all_s=s[n];
 
    for(i=n;i>=1;i--) {
        for(j=min(k+1,n-i+1);j>1;j--) {
            dp[i][j]=cht[j-1].get(s[i-1])-s[i-1]*1ll*all_s-s[i-1]*1ll*s[i-1];
            cht[j].add_line(2*s[i-1],s[i-1]*1ll*all_s-s[i-1]*1ll*s[i-1]+dp[i][j]);
        }
 
        dp[i][1]=(s[n]-s[i-1])*1ll*(all_s-s[n]+s[i-1]);
        cht[1].add_line(2*s[i-1],s[i-1]*1ll*all_s-s[i-1]*1ll*s[i-1]+dp[i][1]);
    }
 
    printf("%lld\n", dp[1][k+1]/2);
    restore(1,k+1);
    for(i=0;i<(int)(path.size());i++) {
        if(i>0) printf(" ");
        printf("%d", path[i]);
    }
    printf("\n");
 
    return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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