oj.uz

Submission #673721

# Submission time Handle Problem Language Result Execution time Memory
673721 2022-12-21T20:11:22 Z US3RN4M3 Catfish Farm (IOI22_fish) C++17
0 / 100
 125 ms 32748 KB 
#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100005;
vector<pair<int, int>> fish[mx];
ll bests[mx];
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	for(int i = 0; i < M; i++) {
		fish[X[i] + 3].push_back({Y[i], W[i]});
	}
	for(int i = 0; i <= M + 2; i++) {
		sort(fish[i].begin(), fish[i].end());
		if(i < 3) continue;
		int cur = i;
		if(i > 3)
		bests[i - 3] = max(bests[i - 3], bests[i - 4]);
		bests[i - 2] = max(bests[i - 2], bests[i - 3]);
		/* double dock */
		{
			/* i am full */
			{
				ll cur_sum = 0;
				for(auto [pos, val] : fish[i - 1]) cur_sum += val;
				for(auto [pos, val] : fish[i + 1]) cur_sum += val;
				ll best_sum = cur_sum;
				int pp_idx = 0;
				int p_idx = 0;
				while(p_idx != fish[cur - 1].size()) {
					while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
						cur_sum += fish[cur - 2][pp_idx].second;
						best_sum = max(best_sum, cur_sum);
						pp_idx++;
					}
					cur_sum -= fish[cur - 1][p_idx].second;
					p_idx++;
				}
				//cout << i - 3 << ",0:  " << best_sum << endl;
				bests[i] = max(bests[i], bests[i - 3] + best_sum);
			}
			/* prev is full */
			{
				ll cur_sum = 0;
				for(auto [pos, val] : fish[i - 2]) cur_sum += val;
				for(auto [pos, val] : fish[i]) cur_sum += val;
				ll best_sum = cur_sum;
				int c_idx = 0;
				int n_idx = 0;
				while(c_idx != fish[cur].size()) {
					while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
						cur_sum += fish[cur + 1][n_idx].second;
						best_sum = max(best_sum, cur_sum);
						n_idx++;
					}
					cur_sum -= fish[cur][c_idx].second;
					c_idx++;
				}
				//cout << i - 3 << ",1:  " << best_sum << endl;
				bests[i] = max(bests[i], bests[i - 3] + best_sum);
			}
		}
		/* single dock */
		{
			ll cur_sum = 0;
			for(auto [pos, val] : fish[i - 1]) cur_sum += val;
			for(auto [pos, val] : fish[i + 1]) cur_sum += val;
			bests[i] = max(bests[i], bests[i - 2] + cur_sum);
			//cout << i - 3 << ",2: " << cur_sum << endl;
		}
	}
	//for(int i = 3; i < M + 2; i++) cout << bests[i] << " ";
	return bests[M + 2];
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(p_idx != fish[cur - 1].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |      while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(c_idx != fish[cur].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |      while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7280 KB Output is correct
2 Correct 38 ms 8360 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Runtime error 125 ms 32748 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 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 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7280 KB Output is correct
2 Correct 38 ms 8360 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Runtime error 125 ms 32748 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -