Submission #746092

#	Time	Username	Problem	Language	Result	Execution time	Memory
746092		sofapuden	Catfish Farm (IOI22_fish)	C++17	100 / 100	549 ms	65144 KiB

fish

#include"fish.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxN = 4e5+5;

vector<array<int,3>> v;
ll dp[mxN][2][2];
int N;
vector<vector<pair<ll,ll>>> pref;

ll pr(int x, ll y1, ll y2){ // [y1, y2[
	auto z1 = prev(lower_bound(pref[x].begin(),pref[x].end(),make_pair(y1,-1ll)));
	auto z2 = prev(lower_bound(pref[x].begin(),pref[x].end(),make_pair(y2,-1ll)));
	return z2->second - z1->second;
}

ll nxt(int x, int y){
	return lower_bound(v.begin(),v.end(),(array<int,3>){x+1,y,-1}) - v.begin();
}

ll f(int ind, int dir, int point){
	if(~dp[ind][dir][point])return dp[ind][dir][point];
	auto &d = dp[ind][dir][point] = 0;
	auto z = nxt(v[ind][0],v[ind][1]);
	if(dir == 1){
		if(ind != N - 1 && v[ind][0] == v[ind+1][0]) 
			d = max(d, f(ind+1,1,point) + point * (v[ind][0] ? pr(v[ind][0]-1, v[ind][1], v[ind+1][1]) : 0));
		if(z != N)
			d = max(d, f(z,1,1) + pr(v[ind][0], v[ind][1], v[z][1]));
	}
	else{
		if(ind != 0 && v[ind][0] == v[ind-1][0]) 
			d = max(d, f(ind-1,0,1) + v[ind-1][2]);
	}
	if(z != N && v[z][0] == v[z-1][0])
		d = max(d, f(z-1,0,1) + v[z-1][2]);
	auto z2 = nxt(v[ind][0]+1,v[ind][1]);
	auto z3 = nxt(v[ind][0]+1,-5);
	if(z3 != N)
		d = max(d, f(z3,1,0) + pr(v[ind][0]+1,-2,v[ind][1]));
	if(z2 != N)
		d = max(d, f(z2,1,1) + pr(v[ind][0]+1,-2,v[z2][1]));
	return d;
}

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
	memset(dp,-1,sizeof dp);
	pref.resize(n,{{-5,0}});
	for(int i = 0; i < m; ++i)v.push_back({x[i],y[i],w[i]});
	for(int i = 0; i < n; ++i)v.push_back({i,n,0});
	sort(v.begin(),v.end());
	N = v.size();
	for(int i = 0; i < N; ++i){
		pref[v[i][0]].emplace_back(v[i][1], pref[v[i][0]].back().second + v[i][2]);
	}
	return f(0,1,1);
}

• 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