| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 825024 | alvingogo | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "fish.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
const long long inf=1e16;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
for(int i=0;i<n;i++){
x.push_back(i);
y.push_back(0);
w.push_back(0);
}
m=x.size();
vector<vector<pair<int,long long> > > v(n);
vector<vector<int> > lis(n);
vector<int> s(n),vs(n);
for(int i=0;i<m;i++){
v[x[i]].push_back({y[i],w[i]});
if(y[i]-1>=0){
lis[x[i]].push_back(y[i]-1);
}
lis[x[i]].push_back(y[i]);
if(x[i]-1>=0){
lis[x[i]-1].push_back(y[i]);
}
if(x[i]+1<n){
lis[x[i]+1].push_back(y[i]);
}
}
for(int i=0;i<n;i++){
sort(v[i].begin(),v[i].end());
vs[i]=v[i].size();
for(int j=1;j<vs[i];j++){
v[i][j].sc+=v[i][j-1].sc;
}
v[i].push_back({1e9,v[i][vs[i]-1].sc});
sort(lis[i].begin(),lis[i].end());
lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
s[i]=lis[i].size();
}
auto get=[&](int i,int a){
return lower_bound(lis[i].begin(),lis[i].end(),a)-lis[i].begin();
};
auto get2=[&](int i,int a){
return upper_bound(v[i].begin(),v[i].end(),pair<int,long long>(a,inf))-v[i].begin()-1;
};
auto get3=[&](int i,int a){
return upper_bound(v[i].begin(),v[i].end(),pair<int,long long>(a,-1))-v[i].begin();
};
vector<vector<long long> > dp[3];
dp[0].resize(n);
dp[1].resize(n);
dp[2].resize(n);
// 0: i-1 >= i, 1: i-1 < i, 2: i = 0, j = the chosen blocks in col i-1
for(int i=0;i<n;i++){
dp[0][i].resize(s[i]);
dp[1][i].resize(s[i]);
if(i){
dp[2][i].resize(s[i-1]);
}
else{
dp[2][i].resize(1);
}
}
for(int i=0;i<s[0];i++){
dp[1][0][i]=-inf;
}
for(int i=1;i<n;i++){
//dp[0][i][j] = max(dp[0][i-1][j]+cnt[i]);
// 0 -> 0
// 1 -> 0
int r=s[i-1]-1;
long long mx=0;
for(int j=s[i]-1;j>0;j--){
while(r>=0 && lis[i-1][r]>=lis[i][j]){
mx=max(mx,max(dp[0][i-1][r],dp[1][i-1][r])+v[i][get3(i,lis[i-1][r])].sc);
r--;
}
dp[0][i][j]=mx-v[i][get2(i,lis[i][j])].sc;
}
// 1 -> 1
int l=0;
mx=0;
for(int j=1;j<s[i];j++){
while(l<s[i-1] && lis[i-1][l]<lis[i][j]){
mx=max(mx,dp[1][i-1][l]-v[i-1][get2(i-1,lis[i-1][l])].sc);
l++;
}
dp[1][i][j]=mx+v[i-1][get3(i-1,lis[i][j])].sc;
}
// 2 -> 1
if(i-2>=0){
l=0;
mx=0;
for(int j=1;j<s[i];j++){
while(l<s[i-2] && lis[i-2][l]<lis[i][j]){
mx=max(mx,dp[2][i-1][l]-v[i-1][get2(i-1,lis[i-2][l])].sc);
l++;
}
dp[1][i][j]=max(dp[1][i][j],mx+v[i-1][get3(i-1,lis[i][j])].sc);
}
r=s[i-2]-1;
mx=0;
for(int j=s[i]-1;j>0;j--){
while(r>=0 && lis[i-2][r]>=lis[i][j]){
mx=max(mx,dp[2][i-1][r]+v[i-1][get3(i-1,lis[i-2][r])].sc);
r--;
}
dp[1][i][j]=max(dp[1][i][j],mx-v[i-1][get2(i-1,lis[i][j])].sc);
}
}
else{
for(int j=1;j<n;j++){
dp[1][i][j]=max(dp[1][i][j],dp[0][i-1][0]+v[i-1][get3(i-1,lis[i][j])].sc);
}
}
// 0 -> 2
// 1 -> 2
for(int j=0;j<s[i-1];j++){
dp[2][i][j]=max(dp[0][i-1][j],dp[1][i-1][j])+v[i-1][get3(i-1,lis[i-1][j])].sc;
}
// 2 -> 2
if(i>=2){
for(int j=0;j<s[i-2];j++){
dp[2][i][0]=max(dp[2][i][0],dp[2][i-1][j]);
}
}
else{
dp[2][i][0]=max(dp[2][i][0],0);
}
}
long long ans=0;
for(int i=0;i<2;i++){
for(int j=0;j<s[n-1];j++){
ans=max(ans,dp[i][n-1][j]);
}
}
for(int i=0;i<s[n-2];i++){
ans=max(ans,dp[2][n-1][i]);
}
return ans;
}