oj.uz

Submission #748653

# Submission time Handle Problem Language Result Execution time Memory
748653 2023-05-26T17:04:50 Z QwertyPi Catfish Farm (IOI22_fish) C++17
32 / 100
 425 ms 79484 KB 
#include "fish.h"
#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int N_MAX = 1e5 + 11;
const int INC = 0;
const int DEC = 1;
const int ZERO = 2;
 
vector<pair<int, long long>> fish[N_MAX];
int N;
 
void chmax(long long& x, long long y){
	x = max(x, y);
}

long long g(int x, int y){ // [x, x] times [0, y)
	if(x <= 0 || x > N) return 0;
	auto ptr = lower_bound(fish[x].begin(), fish[x].end(), pair<int, long long>{y, -1LL});
	if(ptr == fish[x].begin()) return 0;
	return (--ptr)->se;
}
 
vector<long long> dp[N_MAX][3];
vector<int> sp[N_MAX]; 
int L[N_MAX];

int at(int x, int y){
	if(0 <= y && y < sp[x].size())
		return sp[x][y];
	assert(0 == 1);
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {

	::N = N;
	for(int i = 0; i < M; i++) X[i]++;
	
	for(int i = 0; i < M; i++){
		fish[X[i]].push_back({Y[i], W[i]});
	}
	for(int i = 1; i <= N; i++){
		sort(fish[i].begin(), fish[i].end());
		for(int j = 1; j < fish[i].size(); j++){
			fish[i][j].se += fish[i][j - 1].se;
		}
	}
	
	for(int i = 0; i < M; i++){
		int x = X[i], y = Y[i];
		if(x > 1) sp[x - 1].push_back(y + 1);
		if(x < N) sp[x + 1].push_back(y + 1); 
	}
	
	for(int i = 0; i <= N; i++){
		sp[i].push_back(0);
		for(int j = 0; j < 10; j++){
			sp[i].push_back(j);
		}
		sort(sp[i].begin(), sp[i].end());
		sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
		for(int j = 0; j < 3; j++){
			dp[i][j].resize(sp[i].size());
			fill(all(dp[i][j]), -1E18);
		}
		L[i] = sp[i].size();
	}
	
	dp[0][ZERO][0] = 0;
	
	for(int x = 1; x <= N; x++){
	
		/*
			for(int y = 0; y <= N; y++){
				chmax(dp[ZERO][x + 1][y], dp[INC][x][y]);
				chmax(dp[ZERO][x + 1][y], dp[DEC][x][y]);
				chmax(dp[ZERO][x + 1][0], dp[ZERO][x][y]);
			}
			for(int y = 0; y < N; y++){
				chmax(dp[ZERO][x + 1][y + 1], dp[ZERO][x + 1][y]);
			}
		*/	
		
		// ZERO
		{
			for(int y = 0; y < L[x - 1]; y++){
				chmax(dp[x][ZERO][0], dp[x - 1][ZERO][y]);
			}
			int y1 = 0;
			for(int y2 = 0; y2 < L[x]; y2++){
				while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
					chmax(dp[x][ZERO][y2], dp[x - 1][INC][y1]);
					chmax(dp[x][ZERO][y2], dp[x - 1][DEC][y1]);
					y1++;
				}
			}
			for(int y = 0; y < L[x] - 1; y++){
				chmax(dp[x][ZERO][y + 1], dp[x][ZERO][y]);
			}
		}
		
		long long value = -(1LL << 60);
		
		/*
		
		for(int y2 = 0; y2 <= N; y2++){
			value = max(value, dp[INC][x][y2] - g(x, y2) - g(x - 1, y2));
			chmax(dp[INC][x + 1][y2], value + g(x + 1, y2) + g(x - 1, y2));
		}
		
		value = -(1LL << 60);
		for(int y2 = 0; y2 <= N; y2++){
			chmax(value, dp[ZERO][x][y2] - g(x - 1, y2));
			chmax(dp[INC][x + 1][y2], dp[ZERO][x][y2] + g(x + 1, y2));
			chmax(dp[INC][x + 1][y2], value + g(x + 1, y2) + g(x - 1, y2));
		}
		
		*/
		
		// INC
		{
			int y1 = 0;
			for(int y2 = 0; y2 < L[x]; y2++){
				while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
					chmax(value, dp[x - 1][INC][y1] - g(x, at(x - 1, y1)) - g(x - 1, at(x - 1, y1)));
					y1++;
				}
				chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
			}
			
			value = -(1LL << 60);
			y1 = 0;
			for(int y2 = 0; y2 < L[x]; y2++){
				while (y1 < L[x - 1] && at(x - 1, y1) <= at(x, y2)) {
					chmax(value, dp[x - 1][ZERO][y1] - g(x - 1, at(x - 1, y1)));
					y1++;
				}
				chmax(dp[x][INC][y2], dp[x - 1][ZERO][L[x - 1] - 1] + g(x + 1, at(x, y2)));
				chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
			}
		}
		
		/*
		
		for(int y2 = N; y2 >= 0; y2--){
			chmax(value, dp[DEC][x][y2]); chmax(value, dp[INC][x][y2]);
			chmax(dp[DEC][x + 1][y2], value + g(x + 1, y2) - g(x, y2));
		}
		
		*/
		
		// DEC
		{
			value = -(1LL << 60);
			int y1 = L[x - 1] - 1;
			for(int y2 = L[x] - 1; y2 >= 0; y2--){
				while (y1 >= 0 && at(x - 1, y1) >= at(x, y2)) {
					chmax(value, dp[x - 1][DEC][y1]); chmax(value, dp[x - 1][INC][y1]);
					y1--;
				}
				chmax(dp[x][DEC][y2], value + g(x + 1, at(x, y2)) - g(x, at(x, y2)));
			}
		}
	}
	
	long long ans = 0;
	/*
	for(int i = 0; i <= N; i++){
		for(int k = 0; k < 3; k++){
			for(int j = 0; j < L[i]; j++){
				cout << dp[i][k][j] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	for(int k = 0; k < 3; k++){
		for(int y = 0; y < L[N]; y++){
			ans = max(ans, dp[N][k][y]);
		}
	}
	return ans;
}

Compilation message

fish.cpp: In function 'int at(int, int)':
fish.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if(0 <= y && y < sp[x].size())
      |               ~~^~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j = 1; j < fish[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 50188 KB Output is correct
2 Correct 157 ms 55112 KB Output is correct
3 Correct 105 ms 48344 KB Output is correct
4 Correct 109 ms 48428 KB Output is correct
5 Correct 364 ms 76852 KB Output is correct
6 Correct 425 ms 79484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 269 ms 58024 KB Output is correct
3 Correct 286 ms 64540 KB Output is correct
4 Correct 147 ms 50088 KB Output is correct
5 Correct 163 ms 55012 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 108 ms 48424 KB Output is correct
11 Correct 105 ms 48312 KB Output is correct
12 Correct 173 ms 52532 KB Output is correct
13 Correct 193 ms 57968 KB Output is correct
14 Correct 173 ms 51424 KB Output is correct
15 Correct 187 ms 55740 KB Output is correct
16 Correct 153 ms 51388 KB Output is correct
17 Correct 178 ms 55852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 48420 KB Output is correct
2 Correct 105 ms 48432 KB Output is correct
3 Correct 134 ms 47948 KB Output is correct
4 Correct 130 ms 50596 KB Output is correct
5 Correct 185 ms 54576 KB Output is correct
6 Correct 183 ms 54468 KB Output is correct
7 Correct 172 ms 54476 KB Output is correct
8 Correct 171 ms 54472 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12024 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 8 ms 12232 KB Output is correct
13 Correct 8 ms 11988 KB Output is correct
14 Correct 8 ms 12188 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12024 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 8 ms 12232 KB Output is correct
13 Correct 8 ms 11988 KB Output is correct
14 Correct 8 ms 12188 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct
16 Correct 9 ms 12244 KB Output is correct
17 Correct 52 ms 16396 KB Output is correct
18 Correct 49 ms 17084 KB Output is correct
19 Correct 43 ms 17036 KB Output is correct
20 Correct 43 ms 16784 KB Output is correct
21 Correct 41 ms 16820 KB Output is correct
22 Correct 85 ms 21672 KB Output is correct
23 Incorrect 18 ms 13200 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3058635416604'
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12024 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 8 ms 12232 KB Output is correct
13 Correct 8 ms 11988 KB Output is correct
14 Correct 8 ms 12188 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct
16 Correct 9 ms 12244 KB Output is correct
17 Correct 52 ms 16396 KB Output is correct
18 Correct 49 ms 17084 KB Output is correct
19 Correct 43 ms 17036 KB Output is correct
20 Correct 43 ms 16784 KB Output is correct
21 Correct 41 ms 16820 KB Output is correct
22 Correct 85 ms 21672 KB Output is correct
23 Incorrect 18 ms 13200 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3058635416604'
24 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 48420 KB Output is correct
2 Correct 105 ms 48432 KB Output is correct
3 Correct 134 ms 47948 KB Output is correct
4 Correct 130 ms 50596 KB Output is correct
5 Correct 185 ms 54576 KB Output is correct
6 Correct 183 ms 54468 KB Output is correct
7 Correct 172 ms 54476 KB Output is correct
8 Correct 171 ms 54472 KB Output is correct
9 Correct 245 ms 59308 KB Output is correct
10 Correct 113 ms 35352 KB Output is correct
11 Correct 253 ms 58732 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11960 KB Output is correct
17 Correct 7 ms 12048 KB Output is correct
18 Correct 99 ms 48516 KB Output is correct
19 Correct 101 ms 48424 KB Output is correct
20 Correct 116 ms 48424 KB Output is correct
21 Correct 99 ms 48352 KB Output is correct
22 Incorrect 213 ms 57708 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45212413514693'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 50188 KB Output is correct
2 Correct 157 ms 55112 KB Output is correct
3 Correct 105 ms 48344 KB Output is correct
4 Correct 109 ms 48428 KB Output is correct
5 Correct 364 ms 76852 KB Output is correct
6 Correct 425 ms 79484 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 269 ms 58024 KB Output is correct
9 Correct 286 ms 64540 KB Output is correct
10 Correct 147 ms 50088 KB Output is correct
11 Correct 163 ms 55012 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 108 ms 48424 KB Output is correct
17 Correct 105 ms 48312 KB Output is correct
18 Correct 173 ms 52532 KB Output is correct
19 Correct 193 ms 57968 KB Output is correct
20 Correct 173 ms 51424 KB Output is correct
21 Correct 187 ms 55740 KB Output is correct
22 Correct 153 ms 51388 KB Output is correct
23 Correct 178 ms 55852 KB Output is correct
24 Correct 104 ms 48420 KB Output is correct
25 Correct 105 ms 48432 KB Output is correct
26 Correct 134 ms 47948 KB Output is correct
27 Correct 130 ms 50596 KB Output is correct
28 Correct 185 ms 54576 KB Output is correct
29 Correct 183 ms 54468 KB Output is correct
30 Correct 172 ms 54476 KB Output is correct
31 Correct 171 ms 54472 KB Output is correct
32 Correct 7 ms 11988 KB Output is correct
33 Correct 7 ms 11988 KB Output is correct
34 Correct 7 ms 11988 KB Output is correct
35 Correct 6 ms 12024 KB Output is correct
36 Correct 7 ms 11988 KB Output is correct
37 Correct 6 ms 11988 KB Output is correct
38 Correct 7 ms 11988 KB Output is correct
39 Correct 6 ms 11980 KB Output is correct
40 Correct 7 ms 12116 KB Output is correct
41 Correct 9 ms 12244 KB Output is correct
42 Correct 8 ms 12116 KB Output is correct
43 Correct 8 ms 12232 KB Output is correct
44 Correct 8 ms 11988 KB Output is correct
45 Correct 8 ms 12188 KB Output is correct
46 Correct 7 ms 12116 KB Output is correct
47 Correct 9 ms 12244 KB Output is correct
48 Correct 52 ms 16396 KB Output is correct
49 Correct 49 ms 17084 KB Output is correct
50 Correct 43 ms 17036 KB Output is correct
51 Correct 43 ms 16784 KB Output is correct
52 Correct 41 ms 16820 KB Output is correct
53 Correct 85 ms 21672 KB Output is correct
54 Incorrect 18 ms 13200 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3058635416604'
55 Halted 0 ms 0 KB -