Submission #673721

#	Time	Username	Problem	Language	Result	Execution time	Memory
673721		US3RN4M3	Catfish Farm (IOI22_fish)	C++17	0 / 100	125 ms	32748 KiB

fish

#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 (stderr)

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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16