Submission #673734

#	Time	Username	Problem	Language	Result	Execution time	Memory
673734		US3RN4M3	Catfish Farm (IOI22_fish)	C++17	18 / 100	122 ms	17472 KiB

fish

#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100105;
vector<pair<int, int>> fish[mx];
ll bests[mx];
ll maxs[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] + 10].push_back({Y[i], W[i]});
	}
	for(int i = 0; i < mx; i++) {
		fish[i].push_back({N + 10, 0});
	}
	for(int i = 10; i < N + 10; i++) {
		sort(fish[i].begin(), fish[i].end());
		if(i < 10) 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 */
		if(i != 10) {
			/* 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 - 10 << ",1: " << cur_sum << endl;
				bests[i] = max(bests[i], maxs[i - 4] + best_sum);
			}
			//cout << bests[i] << " ";

			/* 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 - 10 << ",2: " << cur_sum << endl;
				bests[i] = max(bests[i], maxs[i - 4] + best_sum);
			}
			//cout << bests[i] << " ";
		}
		/* single dock */
		{
			ll cur_sum = 0;
			for(auto [pos, val] : fish[i + 1]) cur_sum += val;
			bests[i] = max(bests[i], maxs[i - 2] + cur_sum);
			for(auto [pos, val] : fish[i - 1]) cur_sum += val;
			bests[i] = max(bests[i], maxs[i - 3] + cur_sum);
			//cout << i - 10 << ",3: " << cur_sum << endl;
		}
		//cout << bests[i] << endl;
		maxs[i] = max(bests[i], maxs[i - 1]);
	}
	//for(int i = 10; i < N + 10; i++) cout << bests[i] << " ";
	return bests[N + 9];
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:33: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]
   33 |     while(p_idx != fish[cur - 1].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:34: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]
   34 |      while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:55: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]
   55 |     while(c_idx != fish[cur].size()) {
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:56: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]
   56 |      while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16