oj.uz

Submission #748471

# Submission time Handle Problem Language Result Execution time Memory
748471 2023-05-26T10:37:08 Z QwertyPi Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 332988 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);
}

map<long long, long long> MSG;

long long id(int x, int y){
	return ((long long) x << 32) + y;
}


long long w[5001][5001];
long long g(int x, int y){ // [x, x] times [0, y)
	return w[x][y]; 
}

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 j = 0; j < fish[i].size(); j++){
			w[i][fish[i][j].fi + 1] = fish[i][j].se;
		}
		for(int j = 1; j <= N; j++){
			if(w[i][j] == 0) w[i][j] = w[i][j - 1];
		}
	}
	
	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:45: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]
   45 |   for(int j = 1; j < fish[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~
fish.cpp:48: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]
   48 |   for(int j = 0; j < fish[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 202012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 557 ms 204900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 540 ms 198364 KB Execution killed with signal 11
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 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 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 11 ms 5844 KB Output is correct
10 Correct 65 ms 10524 KB Output is correct
11 Correct 11 ms 5844 KB Output is correct
12 Correct 65 ms 10452 KB Output is correct
13 Correct 4 ms 4052 KB Output is correct
14 Correct 64 ms 10348 KB Output is correct

Subtask #5
21.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 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 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 11 ms 5844 KB Output is correct
10 Correct 65 ms 10524 KB Output is correct
11 Correct 11 ms 5844 KB Output is correct
12 Correct 65 ms 10452 KB Output is correct
13 Correct 4 ms 4052 KB Output is correct
14 Correct 64 ms 10348 KB Output is correct
15 Correct 66 ms 10324 KB Output is correct
16 Correct 4 ms 4180 KB Output is correct
17 Correct 93 ms 12624 KB Output is correct
18 Correct 78 ms 13732 KB Output is correct
19 Correct 82 ms 13588 KB Output is correct
20 Correct 85 ms 13564 KB Output is correct
21 Correct 79 ms 13564 KB Output is correct
22 Correct 97 ms 16668 KB Output is correct
23 Correct 67 ms 10976 KB Output is correct
24 Correct 74 ms 12284 KB Output is correct
25 Correct 69 ms 10452 KB Output is correct
26 Correct 66 ms 10828 KB Output is correct

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 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 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 11 ms 5844 KB Output is correct
10 Correct 65 ms 10524 KB Output is correct
11 Correct 11 ms 5844 KB Output is correct
12 Correct 65 ms 10452 KB Output is correct
13 Correct 4 ms 4052 KB Output is correct
14 Correct 64 ms 10348 KB Output is correct
15 Correct 66 ms 10324 KB Output is correct
16 Correct 4 ms 4180 KB Output is correct
17 Correct 93 ms 12624 KB Output is correct
18 Correct 78 ms 13732 KB Output is correct
19 Correct 82 ms 13588 KB Output is correct
20 Correct 85 ms 13564 KB Output is correct
21 Correct 79 ms 13564 KB Output is correct
22 Correct 97 ms 16668 KB Output is correct
23 Correct 67 ms 10976 KB Output is correct
24 Correct 74 ms 12284 KB Output is correct
25 Correct 69 ms 10452 KB Output is correct
26 Correct 66 ms 10828 KB Output is correct
27 Execution timed out 1096 ms 332988 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 540 ms 198364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 202012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -