Submission #625901

#	Time	Username	Problem	Language	Result	Execution time	Memory
625901		oolimry	Catfish Farm (IOI22_fish)	C++17	18 / 100	288 ms	55960 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

struct state{
	lint h, P, D, I;
	bool operator < (state &b){
		return this->h < b.h;
	}
	bool operator == (state &b){
		return this->h == b.h;
	}
};

vector<state> dp[200005];
vector<ii> sum[200005];

///get the sum of values in column x, up to height H
inline lint getsum(int x, lint H){
	if(x == -1) return 0;
	auto it = upper_bound(all(sum[x]), ii(H, 1023456678901234LL));
	if(it == sum[x].begin()) return 0;
	
	it--;
	return it->second;
}


long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> C){
	if(n == 1) return 0;
	
	///setting up sum counts
	for(int i = 0;i < m;i++){
		sum[X[i]].push_back(ii(Y[i], C[i]));
	}
	
	for(int i = 0;i < n;i++){
		sort(all(sum[i]));
		for(int j = 1;j < sz(sum[i]);j++){
			sum[i][j].second += sum[i][j-1].second;
		}
	}
	
	
	
	///set up the important values in the dp table
	for(int i = 0;i < m;i++){
		if(X[i] != 0) dp[X[i]-1].push_back({Y[i], 0, 0, 0});
		if(X[i] != n-1) dp[X[i]+1].push_back({Y[i], 0, 0, 0});
	}
	
	for(int i = 0;i < n;i++){
		dp[i].push_back({-1,0,0,0}); ///represent not taking anything
		sort(all(dp[i]));
		dp[i].erase(unique(all(dp[i])), dp[i].end());		
	}
	
	///now do dp
	for(auto &s : dp[0]){
		s.P = getsum(1, s.h);
		s.I = -getsum(0, s.h);
		s.D = getsum(1, s.h) - getsum(0, s.h);
	}
	
	for(int i = 1;i < n;i++){
		
		///I to I and I to P
		lint bestI = 0;
		auto it = dp[i-1].begin();
		for(auto &s : dp[i]){
			while(it != dp[i-1].end()){
				if(it->h >= s.h){
					bestI = max(bestI, it->I);
					it++;
				}
				else break;
			}
			
			///I to I
			s.I = max(s.I, bestI + getsum(i-1, s.h) - getsum(i, s.h));
			
			///I to P
			s.P = max(s.P, bestI + getsum(i-1, s.h) + getsum(i+1, s.h));
		}
		
		///D to D and P to D
		reverse(all(dp[i]));
		reverse(all(dp[i-1]));
		
		lint bestPD = 0;
		it = dp[i-1].begin();
		for(auto &s : dp[i]){
			while(it != dp[i-1].end()){
				if(it->h <= s.h){
					bestPD = max(bestPD, it->P);
					bestPD = max(bestPD, it->D);
					it++;
				}
				else break;
			}
			
			///D to D and P to D
			s.D = max(s.D, bestPD + getsum(i+1, s.h) - getsum(i, s.h));
		}
		
		reverse(all(dp[i]));
		reverse(all(dp[i-1]));
		
		///D -1 to I -1
		dp[i][0].I = max(dp[i][0].I, dp[i-1][0].D);
		
		///P to P 2 spaces away
		if(i >= 2){
			lint bestP = 0;
			for(auto &s : dp[i-2]) bestP = max(bestP, s.P);
			
			for(auto &s : dp[i]){
				s.P = max(s.P, bestP + getsum(i+1, s.h));
			}
		}
	}
	
	lint ans = 0;
	
	for(int i = 0;i < n;i++){
		/*
		show(i); 
		for(auto s : dp[i]){
			cerr << s.h << ": "; 
			show3(s.P, s.I, s.D); 
		}
		cerr << endl << endl;
		//*/
		for(auto &s : dp[i]){
			ans = max(ans, s.P);
			ans = max(ans, s.I);
			ans = max(ans, s.D);
		}
	}

	return ans;
}

• 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