제출 #1288532

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

sequence

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

struct line {
    long long a, b;
    mutable long double p;
    int id;
    bool operator<(const line& other) const { return a < other.a; }
    bool operator<(long double x) const { return p < x; } // for heterogeneous lookup
};

struct LINE_CONTAINER {
    multiset<line, less<>> ms;
    static constexpr long double INF = 1e30L;

    inline bool isect(multiset<line, less<>>::iterator x, multiset<line, less<>>::iterator y){
        if (y == ms.end()){
            x->p = INF;
            return false;
        }
        if (x->a == y->a){
            x->p = (x->b >= y->b) ? INF : -INF;
        }
        else x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
        return x->p >= y->p;
    }

    inline void update(long long a, long long b, int i){
        auto x = ms.insert({a, b, 0.0L, i});
        auto y = next(x);
        while(isect(x, y)) y = ms.erase(y);
        if (x != ms.begin()){
            y = prev(x);
            if (isect(y, x)) { ms.erase(x); return; }
        } else y = x;
        while(y != ms.begin()){
            x = prev(y);
            if (isect(x, y)){
                isect(x, ms.erase(y));
                y = x;
            }
            else break;
        }
    }

    inline pair<long long, int> get(long long X){
        if (ms.empty()) return {LLONG_MIN/4, 0};
        auto it = ms.lower_bound((long double)X); // uses operator<(long double)
        if (it == ms.end()) --it;
        return { it->a * X + it->b, it->id };
    }
};


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	vector<LINE_CONTAINER> lc(k);
	lc[0].update(0, 0, 0);
	for (int i = 0; i <= n; ++i)
  	for (int j = 0; j <= k; ++j) {
    	dp[i][j] = -1e18;
    	trace[i][j] = 0;
  	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= min(i, k); ++j){
			pair<long long, int> g = lc[j - 1].get(pre[n] - pre[i]);
			dp[i][j] = g.first + pre[i] * (pre[n] - pre[i]);
			if (j < k && dp[i][j] > -1e18) lc[j].update(-(long long)pre[i], dp[i][j], i);
			if (j == k && i < n && dp[i][k] > dp[bestPos][k]) bestPos = i;
			trace[i][j] = g.second;
		}
	}
	cout << dp[bestPos][k] << '\n';
	int curPos = bestPos;
	int curK = k;
	vector<int> cuts;
	while (curPos != 0 && curK > 0) {
		cuts.push_back(curPos);
		int prev = trace[curPos][curK];
		curPos = prev;
		--curK;
	}
	reverse(cuts.begin(), cuts.end());
	for (int x : cuts) cout << x << ' ';
	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