Submission #626642

#	Time	Username	Problem	Language	Result	Execution time	Memory
626642		mohammad_kilani	Catfish Farm (IOI22_fish)	C++17	100 / 100	203 ms	75360 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 300010;

vector< pair< int , int > > grid[N];

vector< long long > dp[N][2] , cur[N][2];

vector< long long > sum[N];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	for(int i = 0 ;i < M;i++){
		grid[X[i]].push_back(make_pair(Y[i] , W[i]));
	}
	for(int i = 0 ;i < N;i++){
		sort(grid[i].begin(),grid[i].end());
		for(int j = 0 ;j < (int)grid[i].size();j++){
			sum[i].push_back(grid[i][j].second);
			if(j)
				sum[i][j] += sum[i][j - 1];
		}
		dp[i][0].resize((int)grid[i + 1].size() + 1);
		dp[i][1].resize((int)grid[i + 1].size());
	}
	for(int i = 0 ;i < N;i++){
		cur[i][0].resize((int)grid[i].size());
		cur[i][1].resize((int)grid[i].size());

		for(int j = 0 ;j < (int)grid[i].size();j++){
			cur[i][0][j] = (long long)grid[i][j].second;
			if(i > 0)
				cur[i][0][j] = max(cur[i][0][j] , grid[i][j].second + dp[i - 1][0][j]);
			if(j > 0)
				cur[i][0][j] = max(cur[i][0][j] , grid[i][j].second + cur[i][0][j - 1]);
		}

		for(int j = (int)grid[i].size() - 1;j >= 0;j--){
			if(i == 0){
				cur[i][1][j] = -(long long)1e18;
				continue;
			}
			cur[i][1][j] = sum[i][j] + dp[i - 1][1][j];
			if(j < (int)grid[i].size() - 1)
				cur[i][1][j] = max(cur[i][1][j] , cur[i][1][j + 1]);
		}


		for(int k = -1 , last , j = 0 ;j < (int)dp[i][0].size();j++){
			last = (j == (int)grid[i + 1].size() ? N : grid[i + 1][j].first - 1); 
			while(k + 1 < (int)grid[i].size() && grid[i][k + 1].first <= last) k++;

			dp[i][0][j] = (i == 0 ? 0 : dp[i - 1][0][(int)grid[i].size()]);

			if(k != -1)
				dp[i][0][j] = max(dp[i][0][j] , cur[i][0][k]);
			if(k + 1 < (int)grid[i].size())
				dp[i][0][j] = max(dp[i][0][j] , cur[i][1][k + 1]);

		}



		for(int k = (int)grid[i].size(), last , j = (int)dp[i][1].size() - 1;j >= 0;j--){
			last = grid[i + 1][j].first + 1;
			while(k - 1 >= 0 && grid[i][k - 1].first >= last)
				k--;
			dp[i][1][j] = (i == 0 ? 0 : dp[i - 1][0][(int)grid[i].size()]);
			if(k < (int)grid[i].size())
				dp[i][1][j] = max(dp[i][1][j] , cur[i][1][k] - (k == 0 ? 0 : sum[i][k - 1]));
		}
	}

	long long ans = dp[N - 2][0][(int)grid[N - 1].size()];

	for(int j = 0 ;j < (int)grid[N  - 1].size();j++){
		ans = max(ans , sum[N - 1][j] + dp[N - 2][1][j]);
	}
	return ans;
}

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