Submission #823886

#	Time	Username	Problem	Language	Result	Execution time	Memory
823886		esomer	Catfish Farm (IOI22_fish)	C++17	100 / 100	228 ms	56336 KiB

fish

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int try_next(int i, vector<pair<int, int>>& v){
	if(i >= (int)v.size()) return 1e9;
	else return v[i].first;
}

ll precalcgreater(vector<vector<ll>>& dp, vector<vector<int>>& which, vector<vector<pair<int, int>>>& fish, int i){
	int ind = 0;
	ll mx = 0;
	ll add = 0;
	for(int j = 0; j < (int)dp[i-1].size(); j++){
		int y = which[i-1][j];
		while(ind < (int)fish[i].size() && fish[i][ind].first <= y){
			add += fish[i][ind].second;
			ind++;
		}
		mx = max(mx, dp[i-1][j] + add);
	}
	return mx;
}

ll precalcsmaller(vector<vector<ll>>& dpmine, vector<vector<int>>& which, vector<vector<pair<int, int>>>& fish, int i){
	int ind = (int)fish[i-1].size() - 1;
	ll mx = 0;
	ll add = 0;
	for(int j = (int)dpmine[i-1].size() - 1; j >= 0; j--){
		int y = which[i-1][j];
		while(ind >= 0 && fish[i-1][ind].first > y){
			add += fish[i-1][ind].second;
			ind--;
		}
		mx = max(mx, dpmine[i-1][j] + add);
	}
	return mx;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
	vector<vector<pair<int, int>>> fish(N);
	vector<vector<ll>> dp(N); //DP stores the maximum ans if I build a pier up to some state.
							//It is always optimal that this pier is in one of the catfishes of adjacent.
	vector<vector<ll>> dpmine(N); //DPmine stores the maximum if I take my catfishes up to some state.
	vector<vector<int>> which(N);
	for(int i = 0; i < M; i++){
		fish[X[i]].push_back({Y[i], W[i]});
	}
	for(int i = 0; i < N; i++){
		sort(fish[i].begin(), fish[i].end());
	}
	for(int i = 0; i < N; i++){
		int ind1 = 0;
		int ind2 = 0;
		int ind3 = 0;
		which[i].push_back(-1);
		dp[i].push_back(0);
		vector<pair<int, int>> prev, next, act;
		if(i > 0) prev = fish[i-1];
		if(i < N - 1) next = fish[i+1];
		act = fish[i];
		while(ind1 < (int)prev.size() || ind2 < (int)next.size() || ind3 < (int)act.size()){
			int mn1 = try_next(ind1, prev);
			int mn2 = try_next(ind2, next);
			int mn3 = try_next(ind3, act);
			if(mn1 <= mn2 && mn1 <= mn3){
				dp[i].push_back(0);
				which[i].push_back(prev[ind1].first);
				ind1++;
			}else if(mn2 <= mn1 && mn2 <= mn3){
				dp[i].push_back(0);
				which[i].push_back(next[ind2].first);
				ind2++;
			}else{
				dp[i].push_back(0);
				which[i].push_back(act[ind3].first);
				ind3++;
			}
		}
	}
	dpmine = dp;
	for(int i = 1; i < N; i++){
		int ind = 0;
		ll subs = 0;
		ll mx = precalcgreater(dp, which, fish, i); //The initial value for each of the DP of the last one. In order.
		for(int j = 0; j < (int)dp[i].size(); j++){
			int y = which[i][j];
			while(ind < (int)fish[i].size() && fish[i][ind].first <= y){
				subs += fish[i][ind].second;
				ind++;
			}
			dp[i][j] = max(dp[i][j], mx - subs);
		}
		ind = (int)fish[i-1].size() - 1;
		subs = 0;
		mx = precalcsmaller(dpmine, which, fish, i);
		for(int j = (int)dp[i].size() - 1; j >= 0; j--){
			int y = which[i][j];
			while(ind >= 0 && fish[i-1][ind].first > y){
				subs += fish[i-1][ind].second;
				ind--;
			}
			dpmine[i][j] = max(dpmine[i][j], mx - subs);
			dp[i][j] = max(dp[i][j], mx - subs);
		}
		vector<ll> prefix((int)dp[i].size(), 0);
		ind = 0;
		subs = 0;
		for(int j = 0; j < (int)dp[i].size(); j++){
			int y = which[i][j];
			while(ind < (int)fish[i].size() && fish[i][ind].first <= y){
				subs += fish[i][ind].second;
				ind++;
			}
			prefix[j] = subs;
		}
		mx = -1e18;
		ind = (int)dp[i-1].size() - 1;
		for(int j = (int)dp[i].size() - 1; j >= 0; j--){
			int y = which[i][j];
			while(ind >= 0 && which[i-1][ind] >= y){
				mx = max(mx, dp[i-1][ind]);
				ind--;
			}
			dpmine[i][j] = max(dpmine[i][j], mx + prefix[j]);
		}
	}
	ll ans = 0;
	for(ll x : dp[N - 1]) ans = max(ans, x);
	for(ll x : dpmine[N - 1]) ans = max(ans, x);
	return ans;
}

// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));

//   std::vector<int> X(M), Y(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//   }

//   long long result = max_weights(N, M, X, Y, W);
//   printf("%lld\n", result);
//   return 0;
// }

• 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