| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 626842 | welleyth | 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>
using namespace std;
constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)2e18 + 10;
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")
int cnt[NN];
vector<pair<int,long long>> val[NN];
vector<int> possibleLen[NN];
long long getSum(int x,int r){
if(val[x].empty())
return 0;
if(val[x][0].first >= r)
return 0;
return (upper_bound(val[x].begin(),val[x].end(),make_pair(r-1,INF))-1)->second;
}
mt19937 rnd(time(nullptr));
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
long long dp[2][333][333];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 333; j++){
for(int t = 0; t < 333; t++){
dp[i][j][t] = 0;
}
}
}
set<int> st[N+22];
for(int i = 0; i < M; i++){
// g[X[i]+2][Y[i]] = W[i];
val[X[i]+2].push_back(make_pair(Y[i],W[i]));
for(int j = max(2,X[i]+1); j <= X[i]+3; j++){
st[j].insert(Y[i]+1);
}
}
for(int i = 0; i < N+2; i++){
st[i].insert(0);
st[i].insert(N);
possibleLen[i] = vector<int>(st[i].begin(),st[i].end());
sort(val[i].begin(),val[i].end());
for(int j = 1; j < val[i].size(); j++){
val[i][j].second += val[i][j-1].second;
}
}
// cerr << getSum(2,3) << "\n";
// return 0;
long long ans = 0;
for(int i = 2; i < N+2; i++){
int pr[2];
for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
int lcur = possibleLen[i][cur];
int l1 = possibleLen[i-2][pr[1]];
pr[0] = lower_bound(possibleLen[i-1].begin(),possibleLen[i-1].end(),min(l1,lcur)-1) - possibleLen[i-1].begin();
pr[0] = max(0ll,pr[0]);
pr[0] = min((int)possibleLen[i-1].size()-1,pr[0]);
for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
int l0 = possibleLen[i-1][pr[0]];
if(lcur <= l0){
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,lcur));
} else if(lcur <= l1){
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0));
} else {
dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0)
+ max(0ll,getSum(i-1,lcur)-getSum(i-1,l0)) - max(0ll,getSum(i-1,l1)-getSum(i-1,l0)));
}
ans = max(ans,dp[1][pr[0]][cur]);
// cerr << i << " " << l1 << " " << l0 << " " << lcur << " " << dp[1][pr[0]][cur] << "\n";
// if(dp[0][pr[0]][cur] == 0)
// continue;
}
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
dp[0][pr[1]][pr[0]] = 0;
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
dp[0][pr[0]][cur] = dp[1][pr[0]][cur];
}
}
for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
for(int cur = 0; cur < possibleLen[i].size(); cur++){
dp[1][pr[0]][cur] = 0;
}
}
}
// for(int i = 0; i < N+2; i++){
// for(int j = 0; j < 10; j++){
// for(int t = 0; t < 10; t++){
// ans = max(ans,dp[i][j][t]);
// }
// }
// }
return ans;
}
/**
10000 2
0 0 1
0 1 1
5 4
0 2 5
1 1 2
4 4 1
3 3 3
**/