Submission #20820

#	Time	Username	Problem	Language	Result	Execution time	Memory
20820		kdh9949	Split the sequence (APIO14_sequence)	C++14	100 / 100	613 ms	88748 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

struct Cht{
	struct Line{
		ll a, b; int x;
	};
    double cr(Line p, Line q){
        return (q.b - p.b) * 1.0 / (p.a - q.a);
    }
	Line dq[100010];
	int f, r;
	void clr(){ f = r = 0; }
	void upd(ll a, ll b, int x){
		Line cur = {a, b, x};
        while(f + 1 < r && ((dq[r - 1].a == cur.a && dq[r - 1].b <= cur.b) ||
							(dq[r - 1].a != cur.a && cr(dq[r - 2], cur) <= cr(dq[r - 2], dq[r - 1])))) r--;
        if(f == r || dq[r - 1].a != cur.a) dq[r++] = cur;
	}
	pli query(ll x){
		while(f + 1 < r && x >= cr(dq[f], dq[f + 1])) f++;
		return {dq[f].a * x + dq[f].b, dq[f].x};
	}
}C;

int n, k, b[210][100010];
ll s[100010], dp[2][100010];

void btk(int x, int y){
	if(!x) return;
	btk(x - 1, b[x][y]);
	printf("%d ", b[x][y]);
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%lld", s + i);
		s[i] += s[i - 1];
	}
	for(int i = 1; i <= n; i++) dp[0][i] = s[i] * (s[n] - s[i]);
	for(int i = 1, f = 1; i <= k; i++, f = !f){
        C.clr();
        C.upd(s[i], dp[!f][i], i);
        for(int j = i + 1; j <= n; j++){
			ll t = s[n] - s[j];
			pli q = C.query(-t);
            dp[f][j] = q.first + t * s[j];
            b[i][j] = q.second;
            C.upd(s[j], dp[!f][j], j);
        }
	}
	printf("%lld\n", dp[k % 2][n]);
	btk(k, n);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:38:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:40:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", s + i);
                       ^

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