Submission #632707

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
632707	2022-08-20T16:35:22 Z	rainboy	Catfish Farm (IOI22_fish)	C++17	44 / 100	101 ms	26168 KB

fish

#include "fish.h"
#include <vector>

using namespace std;
typedef vector<int> vi;

const int M = 100002;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[M], ii1[M], jj[M], jj1[M], ww[M], ww1[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = ii1[hh[j]] != ii1[h] ? ii1[hh[j]] - ii1[h] : jj1[hh[j]] - jj1[h];
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

long long dp[M], dq[M];

long long max_weights(int n, int m, vi ii_, vi jj_, vi ww_) {
	static int hh[M];
	for (int h = 0; h < m; h++)
		ii1[h] = ii_[h], jj1[h] = jj_[h], ww1[h] = ww_[h];
	ii1[m] = -1, jj1[m] = -1, ww1[m] = 0, m++;
	ii1[m] = n, jj1[m] = -1, ww1[m] = 0, m++;
	for (int h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	for (int h = 0; h < m; h++)
		ii[h] = ii1[hh[h]], jj[h] = jj1[hh[h]], ww[h] = ww1[hh[h]];
	dp[0] = -INF, dq[0] = 0;
	long long x = -INF, y;
	for (int i = 0, l = 0, h = 1, r; i <= n; i++, l = h, h = r) {
		r = h;
		while (r < m && ii[r] == i)
			r++;
		y = x;
		for (int f = h - 1, g = r - 1; g >= h; g--) {
			while (f >= l && jj[f] > jj[g])
				y = max(y, dp[f--]);
			dp[g] = y;
			if (dp[g] != -INF)
				dp[g] += ww[g];
			y = max(y, dp[g]);
		}
		for (int g = l; g < h; g++)
			x = max(x, dp[g]);
		y = x;
		for (int f = l, g = h; g < r; g++) {
			while (f < h && jj[f] < jj[g])
				y = max(y, dq[f++]);
			dq[g] = y;
			if (dq[g] != -INF)
				dq[g] += ww[g];
			y = max(y, dq[g]);
		}
		for (int g = l; g < h; g++)
			x = max(x, dq[g]);
	}
	return dp[m - 1];
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	6796 KB	Output is correct
2	Correct	46 ms	8388 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Runtime error	101 ms	26168 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	57 ms	15404 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	23 ms	4448 KB	Output is correct
4	Correct	17 ms	2800 KB	Output is correct
5	Correct	44 ms	6860 KB	Output is correct
6	Correct	40 ms	7628 KB	Output is correct
7	Correct	44 ms	7724 KB	Output is correct
8	Correct	44 ms	7764 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	356 KB	Output is correct
17	Correct	21 ms	3892 KB	Output is correct
18	Correct	21 ms	3904 KB	Output is correct
19	Correct	20 ms	3844 KB	Output is correct
20	Correct	26 ms	3916 KB	Output is correct
21	Correct	22 ms	3852 KB	Output is correct
22	Correct	41 ms	7256 KB	Output is correct
23	Correct	4 ms	852 KB	Output is correct
24	Correct	14 ms	2644 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	4 ms	852 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	356 KB	Output is correct
17	Correct	21 ms	3892 KB	Output is correct
18	Correct	21 ms	3904 KB	Output is correct
19	Correct	20 ms	3844 KB	Output is correct
20	Correct	26 ms	3916 KB	Output is correct
21	Correct	22 ms	3852 KB	Output is correct
22	Correct	41 ms	7256 KB	Output is correct
23	Correct	4 ms	852 KB	Output is correct
24	Correct	14 ms	2644 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	4 ms	852 KB	Output is correct
27	Correct	2 ms	468 KB	Output is correct
28	Runtime error	66 ms	19772 KB	Execution killed with signal 11
29	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	23 ms	4448 KB	Output is correct
4	Correct	17 ms	2800 KB	Output is correct
5	Correct	44 ms	6860 KB	Output is correct
6	Correct	40 ms	7628 KB	Output is correct
7	Correct	44 ms	7724 KB	Output is correct
8	Correct	44 ms	7764 KB	Output is correct
9	Correct	49 ms	7572 KB	Output is correct
10	Correct	48 ms	7928 KB	Output is correct
11	Runtime error	71 ms	18020 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	6796 KB	Output is correct
2	Correct	46 ms	8388 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Runtime error	101 ms	26168 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Submission #632707

Compilation message