제출 #934478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934478		Darren0724	수열 (APIO14_sequence)	C++17	50 / 100	2051 ms	8820 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
const int INF=1e15;
const int mod=1e9+9;
struct Line{
    int a,b,id;
    int operator()(const int x){
        return a*x+b;
    }
};
bool check(Line l1,Line l2,Line l3){

}
int32_t main() {
    LCBorz;
    int n,k;cin>>n>>k;
    vector<int> v(n+1),pre(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        pre[i]=pre[i-1]+v[i];
    }
    vector dp(n+1,-INF);
    vector dp1(n+1,-INF);
    vector tran(k+1,vector(n+1,0));
    vector a(n+1,(int)0),b(n+1,(int)0);
    dp[0]=0;
    for(int i=1;i<=k;i++){
        deque<Line> dq;
        dq.push_back({0,0,0});
        for(int j=0;j<=n;j++){
            a[j]=pre[n]+pre[j];
            b[j]=dp[j]-pre[n]*pre[j];
        }
        for(int j=1;j<=n;j++){
            for(int p=0;p<j;p++){
                int cost=a[p]*pre[j]+b[p]-pre[j]*pre[j];
                if(cost>=dp1[j]){
                    dp1[j]=cost;
                    tran[i][j]=p;
                }
            }
        }
        /*for(int j=1;j<=n;j++){
            while(dq.size()>=2&&dq[0](pre[j])<=dq[1](pre[j])){
                dq.pop_front();
            }
            dp1[j]=dq[0](pre[j]);
            tran[i][j]=dq[0].id;
            dq.push_back({a[j],b[j],j});
        }*/
        dp=dp1;
        dp1.assign(n+1,-INF);
    }
    cout<<endl;
    int now=0;
    for(int i=1;i<n;i++){
        if(dp[i]>=dp[now])now=i;
    }
    cout<<dp[now]<<endl;
    for(int i=k;i>0;i--){
        cout<<now<<' ';
        now=tran[i][now];
    }
    cout<<endl;


    return 0;
}

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

sequence.cpp: In function 'bool check(Line, Line, Line)':
sequence.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | }
      | ^

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