Submission #31972

#	Time	Username	Problem	Language	Result	Execution time	Memory
31972		minimario	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	18664 KiB

sequence

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

#define int long long

const int MAX = 10005;
typedef pair<int, int> pii;


#define f first
#define s second


pii line[MAX];
int orig[MAX];
double hit[MAX];
int ct = 0;

double sect(pii l1, pii l2) {
	// l1.f * x + l1.s = l2.f * x + l2.s
	return (double)(l2.s - l1.s) / (double)(l1.f - l2.f);

}

int ptr = 1;

void add(int m, int b, int k) {
	pii l = {m, b};
	// l and line[2] > hit[2]
	while (ct > 1) {
		if (l.f != line[ct].f && sect(l, line[ct]) > hit[ct]) { break; }
		ct--;
	}
	ct++;
	ptr = min(ptr, ct);
	orig[ct] = k;
	line[ct] = l;
	if (ct != 1) { hit[ct] = sect(l, line[ct-1]); }
}

pii eval(int x) {
	pii l; int ind = -1;
	if (ct == 0) { return {0, 0}; }
	if (ct == 1) { 
		ptr = 1;
		l = line[1]; 
		ind = orig[1];
	}
	else {
		while (hit[ptr] < x) { ptr++; }
		ptr--;
		l = line[ptr]; 
		ind = orig[ptr];
	}
	return {l.f * x + l.s, ind};

}

int a[MAX];
int p[MAX];
int dp[MAX][2];
int last[MAX][205];
main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	int n, k0; scanf("%lld %lld", &n, &k0);
	for (int i=1; i<=n; i++) {
		scanf("%lld", &a[i]); 
		p[i] = p[i-1] + a[i];
	}
	for (int k=1; k<=k0+1; k++) {
		ct = 0;
		for (int i=k-1; i<=n; i++) {
			if (k == 1) { 
				dp[i][k] = 0;
			}
			else {
				add(-p[i], -dp[i][(k+1)%2]+p[i]*p[i], i);
				if (i != k-1) { 
					dp[i][k%2] = -eval(p[i]).f; 
					last[i][k] = eval(p[i]).s;
				}
			}
		}
	}
	k0++;
	printf("%lld\n", dp[n][k0%2]);
	while (k0 != 1) {
		int bef = last[n][k0];
		printf("%lld ", bef);
		n = bef; k0--;
	}

}

Compilation message (stderr)

sequence.cpp:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:64:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("a.in", "r", stdin);
                             ^
sequence.cpp:65:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("a.out", "w", stdout);
                               ^
sequence.cpp:66:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k0; scanf("%lld %lld", &n, &k0);
                                        ^
sequence.cpp:68:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]); 
                       ^

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