oj.uz

Submission #673731

# Submission time Handle Problem Language Result Execution time Memory
673731 2022-12-21T20:38:46 Z US3RN4M3 Catfish Farm (IOI22_fish) C++17
18 / 100
 133 ms 24080 KB 
#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100105;
vector<pair<int, int>> fish[mx];
ll bests[mx];
ll maxs[mx];
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	for(int i = 0; i < M; i++) {
		fish[X[i] + 10].push_back({Y[i], W[i]});
	}
	for(int i = 10; i < N + 10; i++) {
		sort(fish[i].begin(), fish[i].end());
		fish[i].push_back({N + 10, 0});
		if(i < 10) continue;
		int cur = i;
		//if(i > 3)
		//bests[i - 3] = max(bests[i - 3], bests[i - 4]);
		//bests[i - 2] = max(bests[i - 2], bests[i - 3]);
		/* double dock */
		if(i != 10) {
			/* i am full */
			{
				ll cur_sum = 0;
				for(auto [pos, val] : fish[i - 1]) cur_sum += val;
				for(auto [pos, val] : fish[i + 1]) cur_sum += val;
				ll best_sum = cur_sum;
				int pp_idx = 0;
				int p_idx = 0;
				while(p_idx != fish[cur - 1].size()) {
					while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
						cur_sum += fish[cur - 2][pp_idx].second;
						best_sum = max(best_sum, cur_sum);
						pp_idx++;
					}
					cur_sum -= fish[cur - 1][p_idx].second;
					p_idx++;
				}
				//cout << i - 10 << ",1: " << cur_sum << endl;
				bests[i] = max(bests[i], bests[i - 4] + best_sum);
			}
			//cout << bests[i] << " ";

			/* prev is full */
			{
				ll cur_sum = 0;
				for(auto [pos, val] : fish[i - 2]) cur_sum += val;
				for(auto [pos, val] : fish[i]) cur_sum += val;
				ll best_sum = cur_sum;
				int c_idx = 0;
				int n_idx = 0;
				while(c_idx != fish[cur].size()) {
					while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
						cur_sum += fish[cur + 1][n_idx].second;
						best_sum = max(best_sum, cur_sum);
						n_idx++;
					}
					cur_sum -= fish[cur][c_idx].second;
					c_idx++;
				}
				//cout << i - 10 << ",2: " << cur_sum << endl;
				bests[i] = max(bests[i], bests[i - 4] + best_sum);
			}
			//cout << bests[i] << " ";
		}
		/* single dock */
		{
			ll cur_sum = 0;
			for(auto [pos, val] : fish[i + 1]) cur_sum += val;
			bests[i] = max(bests[i], bests[i - 2] + cur_sum);
			for(auto [pos, val] : fish[i - 1]) cur_sum += val;
			bests[i] = max(bests[i], bests[i - 3] + cur_sum);
			//cout << i - 10 << ",3: " << cur_sum << endl;
		}
		//cout << bests[i] << endl;
		maxs[i] = max(bests[i], maxs[i - 1]);
	}
	//for(int i = 10; i < N + 10; i++) cout << bests[i] << " ";
	return bests[N + 9];
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while(p_idx != fish[cur - 1].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(c_idx != fish[cur].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9296 KB Output is correct
2 Correct 47 ms 10480 KB Output is correct
3 Correct 10 ms 7236 KB Output is correct
4 Correct 10 ms 7252 KB Output is correct
5 Correct 116 ms 16788 KB Output is correct
6 Correct 133 ms 24080 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2564 KB Output is correct
2 Correct 73 ms 14796 KB Output is correct
3 Correct 86 ms 17008 KB Output is correct
4 Correct 36 ms 10736 KB Output is correct
5 Correct 44 ms 12232 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2552 KB Output is correct
10 Correct 9 ms 7344 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 37 ms 10816 KB Output is correct
13 Correct 43 ms 12164 KB Output is correct
14 Correct 36 ms 10760 KB Output is correct
15 Correct 43 ms 11756 KB Output is correct
16 Correct 36 ms 10752 KB Output is correct
17 Correct 40 ms 11624 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 8 ms 7252 KB Output is correct
3 Correct 31 ms 9060 KB Output is correct
4 Correct 19 ms 8780 KB Output is correct
5 Correct 43 ms 11232 KB Output is correct
6 Correct 43 ms 10608 KB Output is correct
7 Correct 43 ms 11244 KB Output is correct
8 Correct 45 ms 11160 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 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 2 ms 2644 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 2 ms 2644 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 7 ms 7252 KB Output is correct
2 Correct 8 ms 7252 KB Output is correct
3 Correct 31 ms 9060 KB Output is correct
4 Correct 19 ms 8780 KB Output is correct
5 Correct 43 ms 11232 KB Output is correct
6 Correct 43 ms 10608 KB Output is correct
7 Correct 43 ms 11244 KB Output is correct
8 Correct 45 ms 11160 KB Output is correct
9 Incorrect 40 ms 10980 KB 1st lines differ - on the 1st token, expected: '99999', found: '74999'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9296 KB Output is correct
2 Correct 47 ms 10480 KB Output is correct
3 Correct 10 ms 7236 KB Output is correct
4 Correct 10 ms 7252 KB Output is correct
5 Correct 116 ms 16788 KB Output is correct
6 Correct 133 ms 24080 KB Output is correct
7 Correct 2 ms 2564 KB Output is correct
8 Correct 73 ms 14796 KB Output is correct
9 Correct 86 ms 17008 KB Output is correct
10 Correct 36 ms 10736 KB Output is correct
11 Correct 44 ms 12232 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2552 KB Output is correct
16 Correct 9 ms 7344 KB Output is correct
17 Correct 7 ms 7252 KB Output is correct
18 Correct 37 ms 10816 KB Output is correct
19 Correct 43 ms 12164 KB Output is correct
20 Correct 36 ms 10760 KB Output is correct
21 Correct 43 ms 11756 KB Output is correct
22 Correct 36 ms 10752 KB Output is correct
23 Correct 40 ms 11624 KB Output is correct
24 Correct 7 ms 7252 KB Output is correct
25 Correct 8 ms 7252 KB Output is correct
26 Correct 31 ms 9060 KB Output is correct
27 Correct 19 ms 8780 KB Output is correct
28 Correct 43 ms 11232 KB Output is correct
29 Correct 43 ms 10608 KB Output is correct
30 Correct 43 ms 11244 KB Output is correct
31 Correct 45 ms 11160 KB Output is correct
32 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
33 Halted 0 ms 0 KB -