oj.uz

Submission #748636

# Submission time Handle Problem Language Result Execution time Memory
748636 2023-05-26T16:26:24 Z QwertyPi Catfish Farm (IOI22_fish) C++17
9 / 100
 418 ms 61912 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];
		sp[x].push_back(y + 1);
		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); 
		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++){
		// 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);
		// 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)));
			}
		}
		
		// 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 103 ms 31420 KB Output is correct
2 Correct 114 ms 34376 KB Output is correct
3 Correct 32 ms 24936 KB Output is correct
4 Correct 38 ms 25044 KB Output is correct
5 Correct 401 ms 61912 KB Output is correct
6 Correct 418 ms 60768 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 208 ms 37900 KB Output is correct
3 Correct 224 ms 41896 KB Output is correct
4 Correct 105 ms 31520 KB Output is correct
5 Correct 130 ms 34572 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 31 ms 24900 KB Output is correct
11 Correct 33 ms 24852 KB Output is correct
12 Correct 125 ms 33660 KB Output is correct
13 Correct 155 ms 37136 KB Output is correct
14 Correct 126 ms 32424 KB Output is correct
15 Correct 133 ms 32824 KB Output is correct
16 Correct 120 ms 32480 KB Output is correct
17 Correct 143 ms 34768 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24940 KB Output is correct
2 Correct 32 ms 24956 KB Output is correct
3 Incorrect 69 ms 26600 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21253799925440'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12028 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 9 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 8 ms 12156 KB Output is correct
11 Correct 8 ms 12124 KB Output is correct
12 Incorrect 9 ms 12188 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449632882918'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12028 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 9 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 8 ms 12156 KB Output is correct
11 Correct 8 ms 12124 KB Output is correct
12 Incorrect 9 ms 12188 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449632882918'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12028 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 9 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 8 ms 12156 KB Output is correct
11 Correct 8 ms 12124 KB Output is correct
12 Incorrect 9 ms 12188 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '449632882918'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24940 KB Output is correct
2 Correct 32 ms 24956 KB Output is correct
3 Incorrect 69 ms 26600 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21253799925440'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 31420 KB Output is correct
2 Correct 114 ms 34376 KB Output is correct
3 Correct 32 ms 24936 KB Output is correct
4 Correct 38 ms 25044 KB Output is correct
5 Correct 401 ms 61912 KB Output is correct
6 Correct 418 ms 60768 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 208 ms 37900 KB Output is correct
9 Correct 224 ms 41896 KB Output is correct
10 Correct 105 ms 31520 KB Output is correct
11 Correct 130 ms 34572 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 31 ms 24900 KB Output is correct
17 Correct 33 ms 24852 KB Output is correct
18 Correct 125 ms 33660 KB Output is correct
19 Correct 155 ms 37136 KB Output is correct
20 Correct 126 ms 32424 KB Output is correct
21 Correct 133 ms 32824 KB Output is correct
22 Correct 120 ms 32480 KB Output is correct
23 Correct 143 ms 34768 KB Output is correct
24 Correct 35 ms 24940 KB Output is correct
25 Correct 32 ms 24956 KB Output is correct
26 Incorrect 69 ms 26600 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21253799925440'
27 Halted 0 ms 0 KB -