제출 #92226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92226		Vardanyan	수열 (APIO14_sequence)	C++14	0 / 100	2080 ms	96404 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
const long long N = 1000*100+5;
const long long INF = 1000000000000000000;
struct line{
    long long k,b;
    line():k(0),b(0){}
    line(long long _k,long long _b):k(_k),b(_b){}
};
struct node{
    node* l;
    node* r;
    line ln;
    node():l(NULL),r(NULL){}
};
long long f(line a,  long long x) {
    if(a.k == 0 && a.b == 0) return INF;
    return (a.k*x+a.b);
}
const long long maxn = 1000000000;
long long n;
void add_line(line nw, node* v, long long l = 0, long long r = maxn) {
    long long m = (l + r) / 2;
    bool lef = f(nw, l) < f(v->ln, l);
    bool mid = f(nw, m) < f(v->ln, m);
    if(mid) {
        swap(v->ln, nw);
    }
    if(r - l == 1) return;
    else if(lef != mid) {
        if(v->l == NULL) v->l = new node();
        add_line(nw, v->l, l, m);
    } else {
        if(v->r == NULL) v->r = new node();
        add_line(nw, v->r, m, r);
    }
}
long long get(long long x, node* v, long long l = 0, long long r = maxn) {
    long long m = (l + r) / 2;
    if(r - l == 1) {
        if(v == NULL) v = new node();
        return f(v->ln, x);
    }
    else if(x < m) {
        if(v->l == NULL) v->l = new node();
        return min(f(v->ln, x), get(x, v->l, l, m));
    }
    else {
        if(v->r == NULL) v->r = new node();
        return min(f(v->ln, x), get(x, v->r, m, r));
    }
}
long long dp[N][205];
long long a[N];
long long pref[N];
long long get(long long l,long long r){
    return pref[r]-pref[l-1];
}
long long prevv[N][205];
int main()
{
    ios_base::sync_with_stdio(false);
    long long n,k;
    cin>>n>>k;
    for(long long i = 1;i<=n;i++) cin>>a[i];
    for(long long i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
    long long ps = 0;
    for(long long kk = 1;kk<=k;kk++){
        for(long long i = 1;i<=n;i++){
            for(long long j = 0;j<i;j++){

                long long u = dp[j][kk-1]+get(j+1,i)*get(i+1,n);
                    if(u>=dp[i][kk]){
                        dp[i][kk] = u;
                        prevv[i][kk] = j;
                        if(kk == k && (u>dp[ps][kk] || ps == 0)){
                            ps = i;
                        }
                    }
            }
        }
   //     cout<<dp[kk][kk]<<endl;
    }
    cout<<dp[ps][k]<<endl;
    cout<<ps<<endl;
    long long kkk = k;
    long long i = ps;
    while(1){
        i = prevv[i][kkk];
        if(i == 0) break;
        cout<<i<<endl;
        kkk--;
    }
    return 0;
}

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