제출 #1169886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169886		thelegendary08	Catfish Farm (IOI22_fish)	C++17	23 / 100	166 ms	94340 KiB

fish

#include "fish.h"
// #include "grader.cpp"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define mp make_pair
using namespace std;
vector<vector<pair<int,int>>>v;
int sum(int col, int l, int r){
	if(l > r)return 0;
	int ret = 0;
	if(v[col][0].first >= l && v[col][0].first <= r)ret += v[col][0].second;
	if(v[col][1].first >= l && v[col][1].first <= r)ret += v[col][1].second;
	return ret;
}
int max_weights(signed n, signed m, std::vector<signed> x, std::vector<signed> y,
                      std::vector<signed> w) {
	int ans = 0;
	vector<vector<pair<int,int>>>v(n);
	f0r(i,m){
		v[x[i]].pb(make_pair(y[i], w[i]));
	}
	f0r(i, n){
		if(v[i].size() == 0){
			v[i].pb(mp(0,0));
			v[i].pb(mp(1,0));
		}
		else if(v[i].size() == 1){
			if(v[0][0].first == 0){
				v[i].pb(mp(1,0));
			}
			else v[i].pb(mp(0,0));
		}
		sort(v[i].begin(), v[i].end());
	}
	::v = v;
	f0r(i,n){
		// for(auto u : v[i])cout<<u.first<<' '<<u.second<<'\n';
		// cout<<'\n';
	}
	vector<set<int>>jd(n);
	for(auto u : v[1])jd[0].insert(u.first + 1);
	for(auto u : v[n-2])jd[n-1].insert(u.first + 1);
	FOR(i, 1, n-1){
		for(auto u : v[i-1])jd[i].insert(u.first + 1);
		for(auto u : v[i+1])jd[i].insert(u.first + 1);
	}
	f0r(i, n){
		jd[i].insert(0);
	}
	vector<vector<int>>jd2(n);
	f0r(i,n){
		for(auto u : jd[i])jd2[i].pb(u);
	}
	f0r(i, n){
		//vout(jd2[i]);
	}
	/*
	f0r(i,n){
		f0r(j, n)cout<<s[i][j]<<' ';
		cout<<'\n';
	}
	*/
	int kaw = 5;
	// vout(v);
	// cout<<sum(0, 0, 5)<<"hi"<<'\n';
	
	vector<vector<vi>> dp(n, vector<vi>(kaw, vi(kaw)));
	/*
	f0r(i, kaw){
		f0r(j, kaw){
			dp[1][i][j] = sum(0, i, j-1);
		}
	}
	*/
	// for(auto u : jd2[1])cout<<u<<' ';
	// cout<<'\n';
	FOR(i, 1, n){
		f0r(j, jd2[i-1].size()){
			f0r(k, jd2[i].size()){
				int stupid;
				if(i == 1)stupid = 1;
				else stupid = jd2[i-2].size();
				f0r(l, stupid){
					if(jd2[i][k] < jd2[i-1][j])dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][j] + sum(i, jd2[i][k], jd2[i-1][j]-1));
					else if(i != 1) dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][j] + sum(i-1, max(jd2[i-2][l],jd2[i-1][j]), jd2[i][k]-1));
					else{
						dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][j] + sum(i-1, max(0LL,jd2[i-1][j]), jd2[i][k]-1));
						/*
						if(k == 2 && j == 0){
							cout<<dp[i][j][k]<<"HEL"<<'\n';
						}
						*/
					}
				}
			}
		}
	}
	// cout<<dp[1][2][0]<<'\n';
	/*
	f0r(i, kaw){
		f0r(j, kaw){
			cout<<dp[1][i][j]<<' ';
		}
		cout<<'\n';
	}
	*/
	f0r(i, kaw)f0r(j,kaw)ans = max(ans, dp[n-1][i][j]);
	return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16