Submission #758230

#	Time	Username	Problem	Language	Result	Execution time	Memory
758230		amunduzbaev	Catfish Farm (IOI22_fish)	C++17	100 / 100	440 ms	82180 KiB

fish

#include "fish.h"

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef int32_t ii;
typedef long long ll;
#define int ll

/*

5 4
0 2 5
1 1 2
4 4 1
3 3 3

*/

const int INF = 1e18;

int max_weights(ii n, ii m, vector<ii> x, vector<ii> y, vector<ii> w) {
	
	vector<vector<ar<int, 2>>> a(n + 1);
	for(int i=0;i<m;i++){
		x[i]++, y[i]++;
		for(int t=-1;t<2;t++){
			if(0 < x[i] + t && x[i] + t <= n){
				a[x[i] + t].push_back({y[i], (t == 0) * w[i]});
			}
		}
	}
	
	vector<vector<ar<int, 2>>> dp(n + 1);
	vector<vector<int>> pref(n + 2);
	vector<vector<int>> tp(n + 1);
	for(int i=0;i<=n;i++){
		a[i].push_back({0, 0});
		sort(a[i].begin(), a[i].end());
		vector<ar<int, 2>> b;
		for(auto [x, w] : a[i]){
			if(b.empty() || b.back()[0] != x) b.push_back({x, 0});
			b.back()[1] += w;
		}
		swap(a[i], b);
		pref[i].resize(a[i].size());
		dp[i].resize(a[i].size());
		tp[i].resize(a[i].size());
		for(int j=1;j<(int)pref[i].size();j++){
			pref[i][j] = pref[i][j-1] + a[i][j][1];
		}
	}
	//~ auto low = [&](int i, int j){
		//~ int p = upper_bound(a[i].begin(), a[i].end(), (ar<int, 2>){j, INF}) - a[i].begin();
		//~ return p - 1;
	//~ };
	//~ auto upp = [&](int i, int j){
		//~ int p = lower_bound(a[i].begin(), a[i].end(), (ar<int, 2>){j, 0ll}) - a[i].begin();
		//~ return p - 1;
	//~ };
	
	vector<int> pref_tp, suff_tp, pref_00, suff_11, suff_01;
	
	{
		pref_tp.resize(a[1].size());
		pref_00.resize(a[1].size());
		suff_tp.resize(a[1].size());
		suff_01.resize(a[1].size());
		suff_11.resize(a[1].size());
	}
	
	vector<int> mx(n + 1);
	
/*	

5 4
0 2 5
1 1 2
4 4 1
3 3 3

*/
	
	for(int i=1;i<=n;i++){
		int j_ = 0;
		for(int j=1;j<(int)a[i].size();j++){ // int j_ = a[i][j][0];
			while(j_ + 1 < (int)a[i - 1].size() && a[i - 1][j_ + 1][0] <= a[i][j][0]) j_++;
			dp[i][j][0] = pref[i - 1][j_];
			if(3 <= i) dp[i][j][0] += mx[i - 3];
			
			if(i > 1){
				dp[i][j][0] = max(dp[i][j][0], pref_00[j] + pref[i - 1][j_]);
				dp[i][j][1] = max(dp[i][j][1], suff_11[j] - pref[i][j]);
				dp[i][j][1] = max(dp[i][j][1], suff_01[j] - pref[i][j]);
			}
			if(i > 2){
				dp[i][j][0] = max(dp[i][j][0], pref_tp[j] + pref[i - 1][j_]);
				dp[i][j][0] = max(dp[i][j][0], suff_tp[j]);
			}
			
			tp[i][j] = max(dp[i][j][0], dp[i][j][1]);
			mx[i] = max(mx[i], tp[i][j]);
		}
		
		//~ cout<<"here"<<endl;
		
		if(i < n){
			pref_00.resize(a[i + 1].size());
			pref_tp.resize(a[i + 1].size());
			
			suff_tp.resize(a[i + 1].size() + 1);
			suff_11.resize(a[i + 1].size() + 1);
			suff_01.resize(a[i + 1].size() + 1);
			
			int j_ = 1;
			for(int j=1;j<(int)a[i + 1].size();j++){
				pref_00[j] = pref_00[j - 1];
				while(j_ < (int)a[i].size() && a[i][j_][0] <= a[i + 1][j][0]){
					pref_00[j] = max(pref_00[j], dp[i][j_][0] - pref[i][j_]);
					j_++;
				} 
				//~ pref_00[j] = max(pref_00[j], dp[i][j][0] - pref[i][j]);
			}
			{
				int j_ = (int)a[i].size() - 1, _j = (int)a[i + 1].size() - 1;
				for(int j=_j;j>0;j--){
					suff_11[j] = suff_11[j + 1];
					while(j_ >= 0 && a[i][j_][0] > a[i + 1][j][0]){
						while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
						suff_11[j] = max(suff_11[j], dp[i][j_][1] + pref[i + 1][_j]);
						j_--;
					}
					while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
					suff_11[j] = max(suff_11[j], dp[i][j_][1] + pref[i + 1][_j]);
				}
				
				j_ = (int)a[i].size() - 1, _j = (int)a[i + 1].size() - 1;
				for(int j=_j;j>0;j--){
					suff_01[j] = suff_01[j + 1];
					while(j_ >= 0 && a[i][j_][0] > a[i + 1][j][0] + 1){
						while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
						suff_01[j] = max(suff_01[j], dp[i][j_][0] + pref[i + 1][_j]);
						j_--;
					}
					while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
					suff_01[j] = max(suff_01[j], dp[i][j_][0] + pref[i + 1][_j]);
				}
			}
			
			if(1 < i){
				int j_ = 1;
				for(int j=1;j<(int)a[i + 1].size();j++){
					pref_tp[j] = pref_tp[j - 1];
					while(j_ < (int)a[i - 1].size() && a[i - 1][j_][0] <= a[i + 1][j][0]){
						pref_tp[j] = max(pref_tp[j], tp[i - 1][j_]);
						j_++;
					}
				}
				
				{
					int j_ = (int)a[i - 1].size() - 1, _j = (int)a[i].size() - 1;
					for(int j = (int)a[i + 1].size() - 1;j>0;j--){
						suff_tp[j] = suff_tp[j + 1];
						while(j_ >= 0 && a[i - 1][j_][0] > a[i + 1][j][0]){
							while(a[i - 1][j_][0] < a[i][_j][0]) _j--;
							suff_tp[j] = max(suff_tp[j], tp[i - 1][j_] + pref[i][_j]);
							j_--;
						}
						while(a[i - 1][j_][0] < a[i][_j][0]) _j--;
						suff_tp[j] = max(suff_tp[j], tp[i - 1][j_] + pref[i][_j]);
					}
				}
			}
			
			{
				int j_ = 0;
				for(int j=1;j<(int)a[i].size();j++){
					while(j_ + 1 < (int)a[i + 1].size()	&& a[i + 1][j_ + 1][0] <= a[i][j][0]){
						j_++;
					}
					
					mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j_]);
				}
			}
			
			//~ for(int j=1;j<=n;j++){
				//~ mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j]);
				 
				//~ if(i > 1){
					//~ pref_tp[j] = max(pref_tp[j - 1], tp[i - 1][j]);
				//~ } 
				//~ pref_00[j] = max(pref_00[j - 1], dp[i][j][0] - pref[i][j]);
			//~ }
			//~ for(int j=n;j>=1;j--){
				//~ if(i > 1){
					//~ suff_tp[j] = max(suff_tp[j + 1], tp[i - 1][j] + pref[i][j]);
				//~ } 
				
				//~ suff_11[j] = max(suff_11[j + 1], dp[i][j][1] + pref[i + 1][j]);
				//~ suff_01[j] = max(suff_01[j + 1], dp[i][j][0] + pref[i + 1][j]);
			//~ }
		}
		mx[i] = max(mx[i-1], mx[i]);
	}
	
	return mx[n];
}

• 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