oj.uz

Submission #748467

# Submission time Handle Problem Language Result Execution time Memory
748467 2023-05-26T10:32:01 Z QwertyPi Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 1108504 KB 
#include "fish.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define fi first
#define se second
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;
}

long long f(int x, int y0, int y1, int y2){ // (x - 1, y1) -> (x, y2) transition
	return g(x + 1, y2) + g(x - 1, y2) - g(x, min(y1, y2)) - g(x - 1, min(y2, max(y0, y1)));
}

long long dp[3][5001][5001];

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++){
		fish[X[i]].push_back({Y[i], W[i]});
	}
	for(int i = 0; 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 <= N; i++){
		for(int j = 0; j <= N; j++){
			dp[0][i][j] = dp[1][i][j] = dp[2][i][j] = -(1LL << 60); 
		}
	}
	
	dp[ZERO][0][0] = 0;
	for(int x = 0; x < N; x++){
		// ZERO
		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]);
		}
		
		// INC
		for(int y1 = 0; y1 <= N; y1++){
			for(int y2 = y1; y2 <= N; y2++){
				chmax(dp[INC][x + 1][y2], dp[INC][x][y1] + g(x + 1, y2) - g(x, y1) + g(x - 1, y2) - g(x - 1, y1));
				chmax(dp[INC][x + 1][y2], dp[ZERO][x][y1] + g(x + 1, y2) + g(x - 1, y2) - g(x - 1, min(y2, y1)));
			}
		}
		
		// DEC
		for(int y1 = 0; y1 <= N; y1++){
			for(int y2 = 0; y2 <= y1; y2++){
				chmax(dp[DEC][x + 1][y2], dp[DEC][x][y1] + g(x + 1, y2) - g(x, y2));
				chmax(dp[DEC][x + 1][y2], dp[INC][x][y1] + g(x + 1, y2) - g(x, y2));
			}
		}
	}
	
	/*
	for(int k = 0; k < 3; k++){
		for(int x = 0; x <= N; x++){
			for(int y = 0; y <= N; y++){
				cout << dp[k][x][y] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	
	long long ans = 0;
	for(int k = 0; k < 3; k++){
		for(int y = 0; y <= N; y++){
			ans = max(ans, dp[k][N][y]);
		}
	}
	return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41: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]
   41 |   for(int j = 1; j < fish[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 948120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 1108504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 76 ms 5076 KB Output is correct
10 Correct 758 ms 8532 KB Output is correct
11 Correct 90 ms 5076 KB Output is correct
12 Correct 599 ms 8536 KB Output is correct
13 Correct 11 ms 3668 KB Output is correct
14 Correct 558 ms 8508 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 76 ms 5076 KB Output is correct
10 Correct 758 ms 8532 KB Output is correct
11 Correct 90 ms 5076 KB Output is correct
12 Correct 599 ms 8536 KB Output is correct
13 Correct 11 ms 3668 KB Output is correct
14 Correct 558 ms 8508 KB Output is correct
15 Correct 573 ms 8464 KB Output is correct
16 Correct 33 ms 3860 KB Output is correct
17 Execution timed out 1078 ms 11192 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 76 ms 5076 KB Output is correct
10 Correct 758 ms 8532 KB Output is correct
11 Correct 90 ms 5076 KB Output is correct
12 Correct 599 ms 8536 KB Output is correct
13 Correct 11 ms 3668 KB Output is correct
14 Correct 558 ms 8508 KB Output is correct
15 Correct 573 ms 8464 KB Output is correct
16 Correct 33 ms 3860 KB Output is correct
17 Execution timed out 1078 ms 11192 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 1108504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 948120 KB Time limit exceeded
2 Halted 0 ms 0 KB -