oj.uz

Submission #666694

# Submission time Handle Problem Language Result Execution time Memory
666694 2022-11-29T11:26:20 Z flappybird Catfish Farm (IOI22_fish) C++17
12 / 100
 161 ms 21956 KB 
#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);
		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(1);
		ll sum = 0;
		for (auto& v : locs[i]) sum += v.second;
		tdp[i] = max(tdp[i], sum + tdp[i - 2]);
	}
	return fend.get(1);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12824 KB Output is correct
2 Correct 62 ms 13676 KB Output is correct
3 Correct 20 ms 10436 KB Output is correct
4 Correct 19 ms 10552 KB Output is correct
5 Correct 143 ms 20120 KB Output is correct
6 Correct 161 ms 21956 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10444 KB Output is correct
2 Correct 17 ms 10476 KB Output is correct
3 Correct 41 ms 13168 KB Output is correct
4 Correct 35 ms 12444 KB Output is correct
5 Correct 65 ms 16008 KB Output is correct
6 Correct 67 ms 15948 KB Output is correct
7 Correct 71 ms 15988 KB Output is correct
8 Correct 64 ms 16012 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10444 KB Output is correct
2 Correct 17 ms 10476 KB Output is correct
3 Correct 41 ms 13168 KB Output is correct
4 Correct 35 ms 12444 KB Output is correct
5 Correct 65 ms 16008 KB Output is correct
6 Correct 67 ms 15948 KB Output is correct
7 Correct 71 ms 15988 KB Output is correct
8 Correct 64 ms 16012 KB Output is correct
9 Incorrect 68 ms 15996 KB 1st lines differ - on the 1st token, expected: '99999', found: '99998'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12824 KB Output is correct
2 Correct 62 ms 13676 KB Output is correct
3 Correct 20 ms 10436 KB Output is correct
4 Correct 19 ms 10552 KB Output is correct
5 Correct 143 ms 20120 KB Output is correct
6 Correct 161 ms 21956 KB Output is correct
7 Incorrect 4 ms 7380 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -