제출 #1104465

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

sequence

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second 
#define N 100005
#define oo 1e18
#define int long long

typedef pair<int, long long> ii;
typedef pair<int, pair<long long, long long>> iii;

struct cht{
    deque<iii> q;
    long long get(ii tmp, long long x){
        return tmp.fi * x + tmp.se;
    }
    bool cal(ii a, ii b, ii c){
        return ((long long) 1ll * (c.se - a.se)  * (b.fi - c.fi) >= 1ll * (c.se - b.se) * (a.fi - c.fi));
    }
    void add(long long a, long long b, int pos){
        iii nw = {pos, {a, b}};
        while ((int) q.size() >= 2 && cal(q[(int)q.size() - 2].se, q[(int)q.size() - 1].se, nw.se)) q.pop_back();
        q.push_back(nw);
    }
    ii get(long long pos){
        if (!(int) q.size()) return {0, -oo};
        while ((int) q.size() >= 2 && get(q[0].se, pos) <= get(q[1].se, pos)) q.pop_front();
        return {q[0].fi, get(q[0].se, pos)};
    }
    void reset(){
        q.clear();
    }
} c1;

long long pre[N], suf[N];
int par[201][N], n, k;
vector<long long> cur, lst;
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> pre[i];
        pre[i] = pre[i - 1] + pre[i];
    }

    for (int i = 1; i <= n; i++){
        suf[i] = pre[n] - pre[i - 1];
    }
 
    cur.resize(n + 1, -oo);
    lst.resize(n + 1, -oo);

    for (int i = 1; i <= k; i++){
        lst = cur;
        c1.reset();
        if (i == 1) c1.add(0, 0, 0);
        for (int j = 1; j < n; j++){
            ii gt = c1.get(-suf[j + 1]);
            par[i][j] = gt.fi;
            cur[j] = gt.se + suf[j + 1] * pre[j];
            c1.add(pre[j], lst[j], j);
        }
    }   

    long long res = -oo; int pos = 0, nn = k;
    for (int i = 1; i < n; i++){
        if (cur[i] > res){
            res = cur[i];
            pos = i;
        }
    }

    vector<int> vec;
    while (pos != 0){
        vec.push_back(pos);
        pos = par[k][pos];
        k--;
    }

    sort(vec.begin(), vec.end());
    cout << res << "\n";
    for (auto x : vec) cout << x << " ";

    return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:69:39: warning: unused variable 'nn' [-Wunused-variable]
   69 |     long long res = -oo; int pos = 0, nn = 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