Submission #977012

#	Time	Username	Problem	Language	Result	Execution time	Memory
977012		Amaarsaa	Split the sequence (APIO14_sequence)	C++14	0 / 100	150 ms	3932 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;

	cin >> n >> m;
	
	ll a[n + 2], Sum[n + 2], Umnu[n +2], Daraa[n + 2];
	Sum[0] = 0;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		Sum[i] = Sum[i - 1] + a[i];
	}
	for (i = 1; i <= n; i ++) Umnu[i] = 0, Daraa[i] = n;
	ans = 0;
	vector < ll > v;
	for (i = 1; i <= m; i ++) {
		mx_cnt = mx = -1;
		for (j = 1; j <= n; j ++) {
			if ( Daraa[j] == j) continue;
			s = (Sum[j] - Sum[Umnu[j]]) * (Sum[Daraa[j]] - Sum[j]);
			if ( s > mx_cnt) {
				mx_cnt = s;
				mx = j;
			}
		}
		ans += mx_cnt;
		Umnu[mx] = Daraa[mx] = mx;
		v.push_back(mx);
		for (j = 2; j <= n; j ++) Umnu[j] = max(Umnu[j], Umnu[j - 1]);
		for (j = n - 1; j >= 1; j --) Daraa[j] = min(Daraa[j], Daraa[j + 1]);
	}
	cout << ans << endl;
	for ( ll X : v) cout << X << " ";
	cout << endl;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:10:5: warning: unused variable 't' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |     ^
sequence.cpp:10:34: warning: unused variable 'sum' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |                                  ^~~
sequence.cpp:10:39: warning: unused variable 'x' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |                                       ^
sequence.cpp:10:42: warning: unused variable 'y' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |                                          ^
sequence.cpp:10:45: warning: unused variable 'r' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |                                             ^
sequence.cpp:10:48: warning: unused variable 'p' [-Wunused-variable]
   10 |  ll t, n, m, ans, s, mx, mx_cnt, sum, x, y, r, p, i, j;
      |                                                ^

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