| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1056118 | mychecksedad | 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;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 100005;
// ll dp[N][N], pref[N][N], mx[N], dp2[N][N], suf[N][N];
vector<ll> dp2[N], dp[N], pref[N], suf[N], mxpref[N], mxpref2[N];
vector<pair<ll, ll>> a[N];
vector<ll> b[N];
ll mx[N];
ll get(int pos, ll idx){
if(idx >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : pref[pos][x]);
}
ll getmxpref2(int pos, ll idx){
if(idx >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : mxpref2[pos][x]);
}
ll getmxpref(int pos, ll idx){
if(idx >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : mxpref[pos][x]);
}
ll getsuf(int pos, ll idx){
if(idx >= n) return 0;
int x = lower_bound(all(b[pos]), idx) - b[pos].begin();
return (x == b[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
if(idx >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
if(idx >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : dp2[pos][x]);
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
for(int i = 0; i < m; ++i){
a[X[i]].pb({Y[i] + 1, W[i]});
// a[X[i]][Y[i] + 1] = W[i];
b[X[i]].pb(Y[i]);
}
for(int i = 0; i < n; ++i){
a[i].pb({n + 1, 0});
b[i].pb(n);
sort(all(a[i]));
}
for(int i = 0; i < n; ++i){
pref[i].resize(b[i].size() + 1);
suf[i].resize(b[i].size() + 1);
dp[i].resize(b[i].size() + 1);
dp2[i].resize(b[i].size() + 1);
mxpref[i].resize(b[i].size() + 1);
mxpref2[i].resize(b[i].size() + 1);
pref[i][0] = 0;
for(int j = 1; j < b[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < b[i].size(); ++j) cout << pref[i][j] << ' ';
// en;
// }
// en;en;
for(int i = 0; i < b[0].size(); ++i){
dp[0][i] = dp2[0][i] = get(1, b[0][i]);
}
mx[0] = pref[1].back();
suf[0][b[0].size()] = 0;
for(int j = b[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
int i = 0;
mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);
for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
for(i = 1; i < n; ++i){
mx[i] = 0;
ll mx_pref = 0, mx_pref2 = 0;
for(int j = 0; j < b[i].size(); ++j){
ll pos = b[i][j];
ll A = get(i - 1, pos);
ll B = get(i, pos);
ll C = get(i + 1, pos);
ll add = A + C; //pref[i + 1][j] + pref[i - 1][j];
dp[i][j] = add;
if(i > 2) dp[i][j] = max(dp[i][j], mx[i - 3] + add);
dp2[i][j] = dp[i][j];
// cout << i << ' ' << j << ' ' << add1 << ' ' <<add2 << ' ';
ll x = add - B - A; //add - pref[i - 1][j] - pref[i][j];
// for(int j2 = j + 1; j2 <= n; ++j2){
// dp[i][j] = max(dp[i][j], dp[i - 1][j2] + x);
// }
mx_pref2 = max(mx_pref2, getmxpref2(i - 1, pos));//max(mx_pref2, getdp2(i - 1, pos) - A - B); //dp2[i - 1][j] - pref[i - 1][j] - pref[i][j]);
dp[i][j] = max(dp[i][j], mx_pref2 + add);
dp2[i][j] = max(dp2[i][j], mx_pref2 + add);
dp[i][j] = max(dp[i][j], getsuf(i - 1, pos) + x);//suf[i - 1][j] + x);
if(i > 1){
mx_pref = max(mx_pref, getmxpref(i - 2, pos));//dp[i - 2][j] - pref[i - 1][j]);
dp[i][j] = max(dp[i][j], mx_pref + add);
dp[i][j] = max(dp[i][j], getsuf(i - 2, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
dp2[i][j] = max(dp2[i][j], mx_pref + add);
dp2[i][j] = max(dp2[i][j], getsuf(i - 2, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
}
// cout << dp[i][j] << ' ' << i << ' ' << pos << endl;
mx[i] = max(mx[i], dp[i][j]);
}
suf[i][b[i].size()] = 0;
for(int j = int(b[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);
mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);
for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
// for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
// en;
}
ll ans = mx[n - 1];
return ans;
}