제출 #1256097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256097		anonymousbunny	메기 농장 (IOI22_fish)	C++20	0 / 100	497 ms	80928 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010

int X[maxn], Y[maxn], weight[maxn];
int n, maxcord;

vector <int> checkpoints[maxn];
vector < pair <int, int > > store[maxn];
vector <long long int> dp_1[maxn], dp_2[maxn], dp_3[maxn], dp_4[maxn];


/*

dp[i][1] --> i is in increasing range, right contribution not counted
dp[i][2] --> i is in decreasing range, right contribution not counted
dp[i][3] --> segment of i had ended, right contribution counted

*/


long long int st[8*maxn+10], lz[8*maxn+10];
int marked[8*maxn+10];

void push (int N, int L, int R){
	if (marked[N]){
		st[N]+=lz[N];
		int mid= (L+R)/2;
		if (L <= mid) {
			marked[2*N+1]=1;
			lz[2*N+1]+=lz[N];
		}
		if (mid+1<=R){
			marked[2*N+2]=1;
			lz[2*N+2]+=lz[N];
		}
		lz[N]=0;
		marked[N]=0;
	}
}

void upd (int N, int L, int R, int S, int E, long long int val){
	if (L>R) return;
	push (N, L, R);
	if (L>=S and R<=E){
		lz[N]=val;
		marked[N]=1;
		push(N, L, R);
		return;
	}
	if (L>E or S>R) return;
	int mid= (L+R)/2;
	upd (2*N+1, L, mid, S, E, val);
	upd (2*N+2, mid+1, R, S, E, val);
	st[N]= max(st[2*N+1], st[2*N+2]);
}

long long int query (int N, int L, int R, int S, int E){
	if (L>R) return -1;
	push(N, L, R);
	if (L>E or S>R) return -1;
	if (L>=S and R<=E) return st[N];
	int mid= (L+R)/2;
	return max (query (2*N+1, L, mid, S, E), query(2*N+2, mid+1, R, S, E));
}

vector < pair <int, int> > tmp;


void update_dp_1 (int pos){
	for (int i=0; i<checkpoints[pos-2].size(); i++){
		int y= checkpoints[pos-2][i];
		upd (0, 0, maxcord, y, y, dp_3[pos-2][i]);
	}

	tmp.clear();
	for (pair <int, int> p:store[pos-1]){
		tmp.push_back(p);
	}

	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
	sort(tmp.begin(), tmp.end());
	int counter=0;
	for (pair <int, int> p:tmp){
		int y=p.first, w=p.second;
		if (w<5*maxn) {
			upd (0, 0, maxcord, 0, y-1, w);
		}
		else{
			dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter++;
		}
	}

	for (int i=0; i<checkpoints[pos-2].size(); i++){
		int y= checkpoints[pos-2][i];
		upd (0, 0, maxcord, y, y, -dp_3[pos-2][i]);
	}

	for (pair <int, int> p:tmp){
		int y=p.first, w=p.second;
		if (w<5*maxn) upd (0, 0, maxcord, 0, y-1, -w);
	
	}


}

void update_dp_2(int pos){
	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		//if (pos==3) cout<<"upd "<<y<<" "<<y<<" --> "<<dp_1[pos-1][i]<<endl;
		upd (0, 0, maxcord, y, y, dp_1[pos-1][i]);
	}
	tmp.clear();
	for (pair <int, int> p:store[pos-1]) tmp.push_back(p);
	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
	sort(tmp.begin(), tmp.end());
	int counter=0;
	for (pair <int, int> p:tmp){
		int y= p.first, w= p.second;
		if (w<5*maxn){
			//if (pos==3) cout<<"upd "<<0<<" "<<y-1<<" --> "<<w<<endl;
			upd (0, 0, maxcord, 0, y-1, w);
		}
		else{
		//	if (pos==3) cout<<"query "<<query(0, 0, maxcord, 0 , maxcord)<<endl;
			dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter++;
		}
	}	

	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		upd (0, 0, maxcord, y, y, -dp_1[pos-1][i]);
	}


	for (pair <int, int> p:tmp){
		int y= p.first, w= p.second;
		if (w<5*maxn){
			upd (0, 0, maxcord, 0, y-1, -w);
		}
	}	


}

void update_dp_3 (int pos){
	for (int i=0; i<checkpoints[pos].size(); i++) dp_2[pos][i]= dp_1[pos][i];

	int highest_checkpoint=0;	
	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		highest_checkpoint= max(highest_checkpoint, y);
		upd(0, 0, maxcord, y, y, dp_2[pos-1][i]);
	}	
	tmp.clear();

	for (pair <int, int> p:store[pos]) tmp.push_back(p);
	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
	sort(tmp.begin(), tmp.end());
	reverse(tmp.begin(), tmp.end());
	int counter= checkpoints[pos].size()-1;
	for (pair <int, int> p:tmp){
		int y= p.first, w=p.second;
		if (w<5*maxn) {
			upd(0, 0, maxcord, y, maxcord, w);
		}
		else{
			if (pos>2) dp_2[pos][counter]= max(dp_2[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter--;
		}
	}	

	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		upd(0, 0, maxcord, y, y, -dp_2[pos-1][i]);
	}	

	for (pair <int, int> p:tmp){
		int y= p.first, w=p.second;
		if (w<5*maxn) upd(0, 0, maxcord, y, maxcord, -w);
		
	}	


}

void update_dp_4 (int pos){
	tmp.clear();
	for (pair<int,int> p:store[pos+1]) tmp.push_back(p);
	for (int i:checkpoints[pos]) {
		tmp.push_back(make_pair(i,5*maxn));
	}
	sort(tmp.begin(), tmp.end());
	long long int cur_sum=0;
	int counter=0;
	for (pair <int, int> p:tmp){
		int y=p.first, w=p.second;
		if (w<5*maxn) cur_sum+=w;
		else {
			dp_3[pos][counter]= dp_2[pos][counter]+cur_sum;
			counter++;
		}
	}


}


long long max_weights(int max_cord, int COUNT, std::vector<int> A, std::vector<int> B, std::vector<int> W){
	n=COUNT;
	maxcord=max_cord+2;
	for (int i=1; i<=n; i++){
		X[i]= A[i-1]+2;
		Y[i]= B[i-1]+2;
		weight[i]= W[i-1];
	}


	
	for (int i=1; i<=n; i++) store[X[i]].push_back(make_pair(Y[i], weight[i]));
	for (int i=0; i<=maxcord; i++) sort(store[i].begin(), store[i].end());	

	for (int i=1; i<=n; i++){
		if (Y[i]>1) checkpoints[X[i]].push_back(Y[i]-1);
	}

	for (int i=0; i<=maxcord; i++) {
		checkpoints[i].push_back(0);
		if (i>=2) checkpoints[i].push_back(maxcord);
	}
	for (int i=0; i<=maxcord; i++) sort(checkpoints[i].begin(), checkpoints[i].end());	

	for (int i=0; i<=maxcord; i++){
		for (int j=0; j<checkpoints[i].size(); j++){
			dp_1[i].push_back(0);
			dp_2[i].push_back(0);
			dp_3[i].push_back(0);
			dp_4[i].push_back(0);			
		}
	}




	for (int i=2; i<=maxcord; i++){
		update_dp_1(i);
		update_dp_2(i);
		update_dp_3(i);
		update_dp_4(i);
	}

	

	return dp_3[maxcord][0];

}

• 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