Submission #666700

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
666700	2022-11-29T11:34:58 Z	flappybird	Catfish Farm (IOI22_fish)	C++17	18 / 100	151 ms	21944 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAX 302020
typedef long long ll;
typedef pair<int, int> pii;

ll tdp[MAX]; // full dp
ll bdp[MAX]; // zero dp

vector<pii> locs[MAX];

struct bit {
	int N;
	bool rev;
	vector<ll> tree;
	bit(int N, bool rev) :N(N + 2), rev(rev) { tree = vector<ll>(N + 3, -1e18); }
	void upd(int i, ll v) {
		if (!(0 <= i && i < N)) return;
		if (rev) i = N - i - 1;
		i++;
		while (i <= N) {
			tree[i] = max(tree[i], v);
			i += i & -i;
		}
	}
	ll get(int i) {
		if (!(0 <= i && i < N)) return -1e18;
		if (rev) i = N - i - 1;
		i++;
		ll ans = -1e18;
		while (i) {
			ans = max(ans, tree[i]);
			i -= i & -i;
		}
		return ans;
	}
};

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	int i;
	for (auto& v : X) v++;
	for (auto& v : Y) v++;
	for (i = 0; i < M; i++) locs[X[i]].emplace_back(Y[i], W[i]);
	for (i = 0; i < N; i++) if (locs[i].size()) sort(locs[i].begin(), locs[i].end());
	bit fenu(N + 1, false), fend(N + 1, true);
	fenu.upd(0, 0);
	for (i = 1; i <= N; i++) {
		if (i > 2) fend.upd(N + 1, tdp[i - 2]);
		if (i > 1) fenu.upd(0, bdp[i - 1]);
		if (i > 1) fend.upd(N + 1, 0);
		for (auto& [y, w] : locs[i]) fenu.upd(y, fenu.get(y - 1) + w);
		tdp[i] = fenu.get(N + 1);
		for (int j = locs[i].size() - 1; j >= 0; j--) {
			ll y = locs[i][j].first;
			ll w = locs[i][j].second;
			fend.upd(y, fend.get(y + 1) + w);
		}
		bdp[i] = fend.get(0);
		ll sum = 0;
		for (auto& v : locs[i]) sum += v.second;
		tdp[i] = max(tdp[i], sum + tdp[i - 2]);
	}
	ll ans = fend.get(0);
	for (i = 1; i < N; i++) ans = max(ans, tdp[i]);
	for (i = 1; i <= N; i++) ans = max(ans, bdp[i]);
	return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	12840 KB	Output is correct
2	Correct	62 ms	13828 KB	Output is correct
3	Correct	19 ms	10452 KB	Output is correct
4	Correct	17 ms	10452 KB	Output is correct
5	Correct	141 ms	20108 KB	Output is correct
6	Correct	151 ms	21944 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	80 ms	15344 KB	Output is correct
3	Correct	121 ms	17028 KB	Output is correct
4	Correct	50 ms	12872 KB	Output is correct
5	Correct	59 ms	13696 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	18 ms	10496 KB	Output is correct
11	Correct	19 ms	10408 KB	Output is correct
12	Correct	68 ms	12836 KB	Output is correct
13	Correct	70 ms	13740 KB	Output is correct
14	Correct	57 ms	12860 KB	Output is correct
15	Correct	59 ms	13588 KB	Output is correct
16	Correct	49 ms	13000 KB	Output is correct
17	Correct	52 ms	13572 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	10504 KB	Output is correct
2	Correct	18 ms	10452 KB	Output is correct
3	Correct	41 ms	13132 KB	Output is correct
4	Correct	41 ms	12492 KB	Output is correct
5	Correct	59 ms	15892 KB	Output is correct
6	Correct	53 ms	15920 KB	Output is correct
7	Correct	62 ms	15948 KB	Output is correct
8	Correct	60 ms	15904 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7380 KB	Output is correct
2	Correct	4 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7416 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Incorrect	4 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7380 KB	Output is correct
2	Correct	4 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7416 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Incorrect	4 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7380 KB	Output is correct
2	Correct	4 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7416 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Incorrect	4 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	10504 KB	Output is correct
2	Correct	18 ms	10452 KB	Output is correct
3	Correct	41 ms	13132 KB	Output is correct
4	Correct	41 ms	12492 KB	Output is correct
5	Correct	59 ms	15892 KB	Output is correct
6	Correct	53 ms	15920 KB	Output is correct
7	Correct	62 ms	15948 KB	Output is correct
8	Correct	60 ms	15904 KB	Output is correct
9	Correct	68 ms	15980 KB	Output is correct
10	Correct	56 ms	12820 KB	Output is correct
11	Correct	116 ms	18336 KB	Output is correct
12	Correct	4 ms	7380 KB	Output is correct
13	Correct	4 ms	7380 KB	Output is correct
14	Correct	4 ms	7380 KB	Output is correct
15	Correct	4 ms	7380 KB	Output is correct
16	Correct	4 ms	7380 KB	Output is correct
17	Correct	5 ms	7380 KB	Output is correct
18	Correct	18 ms	10520 KB	Output is correct
19	Correct	18 ms	10452 KB	Output is correct
20	Correct	19 ms	10452 KB	Output is correct
21	Correct	18 ms	10516 KB	Output is correct
22	Incorrect	80 ms	14920 KB	1st lines differ - on the 1st token, expected: '45561826463480', found: '45561636063706'
23	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	12840 KB	Output is correct
2	Correct	62 ms	13828 KB	Output is correct
3	Correct	19 ms	10452 KB	Output is correct
4	Correct	17 ms	10452 KB	Output is correct
5	Correct	141 ms	20108 KB	Output is correct
6	Correct	151 ms	21944 KB	Output is correct
7	Correct	4 ms	7380 KB	Output is correct
8	Correct	80 ms	15344 KB	Output is correct
9	Correct	121 ms	17028 KB	Output is correct
10	Correct	50 ms	12872 KB	Output is correct
11	Correct	59 ms	13696 KB	Output is correct
12	Correct	4 ms	7380 KB	Output is correct
13	Correct	4 ms	7380 KB	Output is correct
14	Correct	4 ms	7380 KB	Output is correct
15	Correct	4 ms	7380 KB	Output is correct
16	Correct	18 ms	10496 KB	Output is correct
17	Correct	19 ms	10408 KB	Output is correct
18	Correct	68 ms	12836 KB	Output is correct
19	Correct	70 ms	13740 KB	Output is correct
20	Correct	57 ms	12860 KB	Output is correct
21	Correct	59 ms	13588 KB	Output is correct
22	Correct	49 ms	13000 KB	Output is correct
23	Correct	52 ms	13572 KB	Output is correct
24	Correct	18 ms	10504 KB	Output is correct
25	Correct	18 ms	10452 KB	Output is correct
26	Correct	41 ms	13132 KB	Output is correct
27	Correct	41 ms	12492 KB	Output is correct
28	Correct	59 ms	15892 KB	Output is correct
29	Correct	53 ms	15920 KB	Output is correct
30	Correct	62 ms	15948 KB	Output is correct
31	Correct	60 ms	15904 KB	Output is correct
32	Correct	5 ms	7380 KB	Output is correct
33	Correct	4 ms	7380 KB	Output is correct
34	Correct	4 ms	7380 KB	Output is correct
35	Correct	4 ms	7380 KB	Output is correct
36	Correct	4 ms	7416 KB	Output is correct
37	Correct	4 ms	7380 KB	Output is correct
38	Correct	4 ms	7380 KB	Output is correct
39	Correct	4 ms	7380 KB	Output is correct
40	Incorrect	4 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
41	Halted	0 ms	0 KB	-

Submission #666700

Compilation message