Submission #851726

#	Time	Username	Problem	Language	Result	Execution time	Memory
851726		iah	Split the sequence (APIO14_sequence)	C++14	100 / 100	882 ms	84700 KiB

sequence

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

#define ll long long
#define fi first
#define se second
#define sz(x) (int32_t) (x.size())

constexpr int Nmax = 1e5;
ll a[Nmax + 5], dp[Nmax + 5], pre[Nmax + 5];
int trace[Nmax + 5][205];

struct line{
	ll a, b;
	ll calc (ll x) {
		return a * x + b;
	}
	double intersect(line x) {
		return (double) (x.b - b) / (double) (a - x.a);
	}
	
	bool equal(line x) {
		return (a == x.a);
	}
};
signed main() {
    if (fopen("sequence.in","r")) {
        freopen("sequence.in","r",stdin);
        freopen("sequence.out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    int n, lim;
    cin >> n >> lim;
    // vector < ll > a(n + 1, 0);
    // vector < vector < ll > > dp(n + 1, vector < ll > (lim + 2, 0));
    // vector < vector < int > > trace(n + 1, vector < int > (lim + 2, 0));
    // dp[i][j] = max(dp[k][j - 1] - a[k] * a[k] + a[i] * a[k]);
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i];
    	a[i] += a[i - 1];
    }
    
    for (int j = 1; j <= lim + 1; j ++) {	
		deque < pair < line , int > > dq;
    	dq.push_back({line{a[j - 1], pre[j - 1] - a[j - 1] * a[j - 1]}, j - 1});
    	for (int i = j; i <= n; i ++) {
    		while (sz(dq) >= 2 && dq[0].fi.intersect(dq[1].fi) <= a[i]) {
    			dq.pop_front();
    		}
    		
    		dp[i] = dq[0].fi.calc(a[i]);
    		trace[i][j] = dq[0].se;
    		// cout << i << " " << j << " " << dp[i][j] << " " << dq[0].fi.a << " " << dq[0].fi.b << " " << dq[0].se << "\n";
    		
    		line cur_line = {a[i], pre[i] - a[i] * a[i]};
    		pre[i] = dp[i];
    		if (j == 1) continue;
    		while (sz(dq) >= 1 && dq[sz(dq) - 1].fi.equal(cur_line)) {
    			dq.pop_back();
    		}
    		while (sz(dq) >= 2 && dq[sz(dq) - 2].fi.intersect(cur_line) <= dq[sz(dq) - 2].fi.intersect(dq[sz(dq) - 1].fi)) {
    			dq.pop_back();
    		}
    		dq.push_back({cur_line, i});
    	}
    }
    cout << dp[n] << "\n";
    int cur_pos = trace[n][lim + 1], cur_k = lim;
    while (cur_k > 0) {
    	cout << cur_pos << " ";
    	cur_pos = trace[cur_pos][cur_k];
    	cur_k --;
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen("sequence.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("sequence.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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