| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1169885 | thelegendary08 | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
#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;
}