제출 #197494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197494		handlename	수열 (APIO14_sequence)	C++17	71 / 100	2045 ms	84112 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
deque<pair<long long,long long> > dq;
deque<int> id;
long long f(pair<long long,long long> line, long long x){
    return line.first*x + line.second;
}
pair<long long,int> qry(long long x){
    while(dq.size()>1){
        if(f(dq[0],x)<f(dq[1],x)){
            dq.pop_front();
            id.pop_front();
        }
        else break; 
    }
    return make_pair(f(dq[0],x),id[0]);
}
long double intersect(long long m1, long long c1, long long m2, long long c2){
    return (long double)(c2-c1)/(m1-m2);
}
long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){
    return intersect(p1.first,p1.second,p2.first,p2.second);
}
void ins(long long m,long long c,int index) {//insert line y=mx+c
    pair<long long,long long> line=make_pair(m,c);
    while (dq.size()>1) {
        long long s=dq.size();
        if (intersect(dq[s-1],line)<=intersect(dq[s-2],line)){
            dq.pop_back();
            id.pop_back();
        }
        else break;
    }
    dq.push_back(line);
    id.push_back(index);
}
long long n,k;
long long arr[100001],pre[100001];
int dp[100001][201];
long long dp2[100001];
bool vis[100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>arr[i];
    for (int i=1;i<=n;i++) pre[i]=pre[i-1]+arr[i];
    ins(0,0,0);
    long long ans=-1,pos=1;
    for (int j=1;j<=k;j++){
        for (int i=1;i<n;i++){
            pair<long long,int> cur=qry(pre[i]-pre[n]);
            cur.first+=pre[i]*(pre[n]-pre[i]);
            //dp[x][j-1].first+(pre[i]-pre[x])*(pre[n]-pre[i]);
            dp[i][j]=cur.second;
            dp2[i]=cur.first;
            if (j==k){
                if (cur.first>=ans){
                    ans=cur.first;
                    pos=i;
                }
            }
        }
        dq.clear();
        id.clear();
        ins(0,0,0);
        for (int i=1;i<n;i++){
            ins(pre[i],dp2[i],i);
        }
    }
    cout<<ans<<'\n';
    while (pos!=0 && k>0){
        cout<<pos<<' ';
        vis[pos]=true;
        pos=dp[pos][k];
        k--;
    }
    for (int i=1;i<n;i++){
        if (k==0) break;
        if (!vis[i]){
            cout<<i<<' ';
            k--;
        }
    }
}

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