oj.uz

Submission #1057071

# Submission time Handle Problem Language Result Execution time Memory
1057071 2024-08-13T13:52:51 Z dozer Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 59524 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define MAXN 300005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


ll start[MAXN], dp[2][MAXN];
vector<pii> fish[MAXN];


long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	int n = N, m = M;
	vector<array<int, 3>> v;
	map<pii, int> done;
	for (int i = 0; i < m; i++) done[{X[i], Y[i]}] = 1;
	for (int i = 0; i < n; i++){
		if (done.count({i, 0}) == 0){
			X.pb(i), Y.pb(0), W.pb(0);
		}
	}

	m = X.size();
	for (int i = 0; i < m; i++) v.pb({X[i] + 1, Y[i], W[i]});
	sort(v.begin(), v.end());
    vector<int> x(m + 5), y(m + 5), w(m + 5);
    for (int i = 1; i <= m; i++) x[i] = v[i - 1][0], y[i] = v[i - 1][1], w[i] = v[i - 1][2];
    for (int i = 1; i <= m; i++) fish[x[i]].pb({y[i], i});

    vector<ll> pre(m + 5, 0);
	for (int i = 1; i <= m; i++) pre[i] = pre[i - 1] + w[i];

	for (int i = n; i >= 1; i--){
		start[i] = max(start[i + 1], start[i + 2] + pre[fish[i].back().nd] - pre[fish[i].front().nd - 1]);

		if (i == n) continue; // hopefully??
		for (auto j : fish[i]){
			int k = j.nd;
			int a = x[k], b = y[k];

			//todo : continue decreasing

			int to = lower_bound(fish[i + 1].begin(), fish[i + 1].end(), make_pair(b, 0)) - fish[i + 1].begin();
			to--;
			if (to >= 0){
				int to2 = fish[i + 1][to].nd;
				for (auto o : fish[i + 1]){
					if (o.st <= b){
						dp[0][k] = max(dp[0][k], pre[to2] - pre[o.nd - 1] + dp[0][o.nd]);
						assert(to2 >= o.nd - 1);
					}
				}
			}

			//todo : switch to increasing

			if (b == 0){
				dp[0][k] = max(dp[0][k], dp[1][fish[i + 1].front().nd]);
			}

			//todo : continue increasing
			for (auto o : fish[i + 1]){
				if (o.st >= b){
					int to = lower_bound(fish[i].begin(), fish[i].end(), make_pair(o.st, 0)) - fish[i].begin();
					to--;
					if (to >= 0){ 
						int to2 = fish[i][to].nd;
						dp[1][k] = max(dp[1][k], dp[1][o.nd] + pre[to2] - pre[k - 1]);
					}
					
				}
			}


			//todo : connect to full column
			dp[1][k] = max(dp[1][k], start[i + 2] + pre[fish[i].back().nd] - pre[k - 1]);
		}
		

		for (int j = 0; j < fish[i].size(); j++){
			int curr = fish[i][j].nd;
			start[i] = max(start[i], dp[0][curr] + pre[fish[i].back().nd] - pre[curr - 1]);
		}
	}

	ll ans = start[2];
	for (int i = 1; i <= m; i++) {
		ans = max(ans, max(dp[0][i], dp[1][i]));
	}
	return ans;
}

/*

int main() {
	fileio();
	int N, M;
	assert(2 == scanf("%d %d", &N, &M));

	std::vector<int> X(M), Y(M), W(M);
	for (int i = 0; i < M; ++i) {
		assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
	}

	long long result = max_weights(N, M, X, Y, W);
	printf("%lld\n", result);
	return 0;
}
*/

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:52:8: warning: unused variable 'a' [-Wunused-variable]
   52 |    int a = x[k], b = y[k];
      |        ^
fish.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int j = 0; j < fish[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 27444 KB Output is correct
2 Correct 62 ms 31284 KB Output is correct
3 Correct 11 ms 19012 KB Output is correct
4 Correct 11 ms 18996 KB Output is correct
5 Correct 202 ms 59020 KB Output is correct
6 Correct 218 ms 59524 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Execution timed out 1098 ms 38364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19012 KB Output is correct
2 Correct 10 ms 19016 KB Output is correct
3 Correct 35 ms 20884 KB Output is correct
4 Correct 29 ms 22092 KB Output is correct
5 Correct 58 ms 27588 KB Output is correct
6 Correct 55 ms 27180 KB Output is correct
7 Correct 65 ms 27480 KB Output is correct
8 Correct 58 ms 27596 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 1 ms 8792 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 98 ms 14792 KB Output is correct
18 Correct 104 ms 15152 KB Output is correct
19 Correct 62 ms 15060 KB Output is correct
20 Correct 69 ms 14840 KB Output is correct
21 Correct 64 ms 15056 KB Output is correct
22 Correct 241 ms 21196 KB Output is correct
23 Correct 8 ms 10036 KB Output is correct
24 Correct 41 ms 12944 KB Output is correct
25 Correct 2 ms 8792 KB Output is correct
26 Correct 7 ms 10036 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 1 ms 8792 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 98 ms 14792 KB Output is correct
18 Correct 104 ms 15152 KB Output is correct
19 Correct 62 ms 15060 KB Output is correct
20 Correct 69 ms 14840 KB Output is correct
21 Correct 64 ms 15056 KB Output is correct
22 Correct 241 ms 21196 KB Output is correct
23 Correct 8 ms 10036 KB Output is correct
24 Correct 41 ms 12944 KB Output is correct
25 Correct 2 ms 8792 KB Output is correct
26 Correct 7 ms 10036 KB Output is correct
27 Correct 3 ms 9304 KB Output is correct
28 Execution timed out 1006 ms 39188 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19012 KB Output is correct
2 Correct 10 ms 19016 KB Output is correct
3 Correct 35 ms 20884 KB Output is correct
4 Correct 29 ms 22092 KB Output is correct
5 Correct 58 ms 27588 KB Output is correct
6 Correct 55 ms 27180 KB Output is correct
7 Correct 65 ms 27480 KB Output is correct
8 Correct 58 ms 27596 KB Output is correct
9 Correct 75 ms 31536 KB Output is correct
10 Correct 58 ms 24256 KB Output is correct
11 Correct 126 ms 39932 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8816 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 10 ms 19016 KB Output is correct
19 Correct 12 ms 19120 KB Output is correct
20 Correct 10 ms 19016 KB Output is correct
21 Correct 10 ms 18932 KB Output is correct
22 Correct 79 ms 32340 KB Output is correct
23 Correct 156 ms 50328 KB Output is correct
24 Correct 147 ms 49300 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 27444 KB Output is correct
2 Correct 62 ms 31284 KB Output is correct
3 Correct 11 ms 19012 KB Output is correct
4 Correct 11 ms 18996 KB Output is correct
5 Correct 202 ms 59020 KB Output is correct
6 Correct 218 ms 59524 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Execution timed out 1098 ms 38364 KB Time limit exceeded
9 Halted 0 ms 0 KB -