oj.uz

Submission #748625

# Submission time Handle Problem Language Result Execution time Memory
748625 2023-05-26T15:35:36 Z QwertyPi Catfish Farm (IOI22_fish) C++17
0 / 100
 399 ms 62000 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(y < sp[x].size())
		return sp[x][y];
	return 1 << 30;
}

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 > 0) sp[x - 1].push_back(y + 1);
		if(x < N - 1) 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 (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 (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 (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][y2] + 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 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:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if(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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 33676 KB Output is correct
2 Correct 140 ms 37232 KB Output is correct
3 Correct 44 ms 24836 KB Output is correct
4 Correct 36 ms 24908 KB Output is correct
5 Incorrect 399 ms 62000 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '1571252609096450358'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24940 KB Output is correct
2 Correct 33 ms 24876 KB Output is correct
3 Incorrect 77 ms 27520 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 Incorrect 6 ms 11948 KB 1st lines differ - on the 1st token, expected: '3', found: '50'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24940 KB Output is correct
2 Correct 33 ms 24876 KB Output is correct
3 Incorrect 77 ms 27520 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 118 ms 33676 KB Output is correct
2 Correct 140 ms 37232 KB Output is correct
3 Correct 44 ms 24836 KB Output is correct
4 Correct 36 ms 24908 KB Output is correct
5 Incorrect 399 ms 62000 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '1571252609096450358'
6 Halted 0 ms 0 KB -