제출 #1288584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288584		harryleee	수열 (APIO14_sequence)	C++20	100 / 100	405 ms	84672 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k, trace[maxn + 1][201];
long long bestPos = 0, res = LLONG_MIN/4, pre[maxn + 1];

const long long NEG = LLONG_MIN/4;

struct Line {
    long long m; // slope (a)
    long long b; // intercept (b)
    int id;
    Line(long long _m=0, long long _b=0, int _id=0): m(_m), b(_b), id(_id) {}
};

inline bool bad(const Line &l1, const Line &l2, const Line &l3){
    long long left  = (long long)(l3.b - l1.b) * (long long)(l1.m - l2.m);
    long long right = (long long)(l2.b - l1.b) * (long long)(l1.m - l3.m);
    return left <= right;
}

struct CHT {
    vector<Line> hull;
    int ptr = 0;

    void clear(){ hull.clear(); ptr = 0; }

    void add(Line L){
        while(!hull.empty() && hull.back().m == L.m){
            if (hull.back().b >= L.b) return;
            else hull.pop_back();
        }
        while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), L))
            hull.pop_back();
        hull.push_back(L);
        if (ptr >= (int)hull.size()) ptr = (int)hull.size() - 1;
    }

    pair<long long,int> query(long long x){
        if (hull.empty()) return {NEG, 0};
        while(ptr + 1 < (int)hull.size()){
            long long v1 = (long long)hull[ptr].m * x + (long long)hull[ptr].b;
            long long v2 = (long long)hull[ptr+1].m * x + (long long)hull[ptr+1].b;
            if (v2 >= v1) ++ptr;
            else break;
        }
        long long val = (long long)((long long)hull[ptr].m * x + (long long)hull[ptr].b);
        return {val, hull[ptr].id};
    }
};

CHT lc;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; ++i){
        cin >> pre[i];
        pre[i] += pre[i - 1];
    }

    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= k; ++j) trace[i][j] = 0;
    }

	vector<long long> dp(n + 1, -1e18);
	for (int i = 1; i <= n; ++i) dp[i] = pre[i] * (pre[n] - pre[i]);
	for (int j = 2; j <= k; ++j){
		vector<long long> cur(n + 1, -1e18);
		lc.clear();
		for (int i = 1; i <= n; ++i){
			if (i >= j){
				pair<long long, int> g = lc.query(pre[i] - pre[n]);
				if (g.first != -1e18) cur[i] = g.first + pre[i] * (pre[n] - pre[i]);
				trace[i][j] = g.second;
			}
			if (dp[i] != -1e18) lc.add(Line(pre[i], dp[i], i));
		}
		swap(dp, cur);
	}

	for (int i = k; i <= n; ++i){
		if (dp[i] > res){
			res = dp[i];
			bestPos = i;
		}
	}

    cout << res << '\n';
    vector<int> cuts;
    while (bestPos != 0 && k > 0) {
        cuts.push_back((int)bestPos);
        bestPos = trace[bestPos][k];
        --k;
    }
    reverse(cuts.begin(), cuts.end());
    for (int i = 0; i < (int)cuts.size(); ++i){
        if (i) cout << ' ';
        cout << cuts[i];
    }
    cout << '\n';
    return 0;
}

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