Submission #392557

#	Time	Username	Problem	Language	Result	Execution time	Memory
392557		anonymity	Split the sequence (APIO14_sequence)	C++17	100 / 100	1914 ms	83864 KiB

sequence

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <cassert>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <unordered_map>
#include <chrono>
#define int long long
#define ii pair<int, int> 
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
using namespace std;
int n, k, a[100005], pref[100005], l = 1, r, cur, now;
int f[100005][2];
int32_t trace[100005][205];
vector <int> part;
void dp(int u, int v, int x, int y) {
	if (u > v) return;
	int mid = (u + v) >> 1;
	for (int i = x; i <= min(y, mid - 1); i++) 
	{
		cur = (pref[i] - pref[mid]) * (pref[i] - pref[mid]);
		//cout << i << ' ' << cur << endl;
		if(f[i][(now + 1) % 2] + cur <= f[mid][now % 2])
			f[mid][now % 2] = f[i][(now + 1) % 2] + cur, trace[mid][now] = i;
	}
	dp(u, mid - 1, x, trace[mid][now]), dp(mid + 1, v, trace[mid][now], y);
}
signed main() {
	cin >> n >> k;
	k++;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 2; j++)
			f[i][j] = 1e18;
	for(int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) f[i][1] = pref[i] * pref[i];
	for (int i = 2; i <= k; i++) now = i, dp(1, n, 0, n - 1);
	cur = trace[n][k];
	for (int i = k - 1; i > 0; i--)
	{
		part.pb(cur);
		cur = trace[cur][i];
	}
	cout << (pref[n] * pref[n] - f[n][k % 2]) / 2 << endl;
	reverse(part.begin(), part.end());
	for (int i = 0; i < part.size(); i++)
		cout << part[i] << ' ';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:73:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < part.size(); 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