| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 807264 | I_Love_EliskaM_ | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(ll i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second
const ll N=100005;
vector<ll> pr[N];
vector<pi> f[N];
ll sum(ll i, ll j) {
ll l=0, r=f[i].size();
while (l<r) {
ll m=(l+r+1)>>1;
if (f[i][m-1].f>j) r=m-1;
else l=m;
}
return pr[i][r];
}
vector<pi> dp[N], dp2[N], dp3[N];
vector<ll> prmx[N], prmx2[N], sfmx[N];
ll prmxquery(ll i, ll j) {
ll l=0, r=dp[i].size();
while (l<r) {
ll m=(l+r+1)>>1;
if (dp[i][m-1].f > j) r=m-1;
else l=m;
}
return prmx[i][r];
}
ll prmx2query(ll i, ll j) {
ll l=0, r=dp3[i].size();
while (l<r) {
ll m=(l+r+1)>>1;
if (dp3[i][m-1].f > j) r=m-1;
else l=m;
}
return prmx2[i][r];
}
ll sfmxquery(ll i, ll j) {
ll l=0, r=dp2[i].size();
while (l<r) {
ll m=(l+r)>>1;
if (dp2[i][m].f<j) l=m+1;
else r=m;
}
return sfmx[i][r];
}
ll max_weights(ll n, ll m, vector<ll> x, vector<ll> y, vector<ll> w) {
forn(i,m) {
f[x[i]+1].pb({y[i]+1,w[i]});
}
for(ll i=1;i<=n;++i) {
sort(all(f[i]));
f[i].pb({n+1,0});
pr[i]={0};
forn(j,f[i].size()) pr[i].pb(pr[i].back()+f[i][j].s);
}
dp[0].pb({0,0});
dp[0].pb({n,0});
pr[0]={0,0,0};
dp2[0]=dp3[0]=dp[0];
prmx[0]={0,0};
prmx2[0]=sfmx[0]=prmx[0];
pr[n+1]={0,0,0};
for(ll i=1; i<=n; ++i) {
if (f[i][0].f!=1) {
ll j=0;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
for(auto&x:f[i]) {
ll j=x.f-1;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
prmx[i]={-1000000000000000000ll};
prmx2[i]=sfmx[i]=prmx[i];
for (ll j=0; j<dp[i].size(); ++j) {
prmx[i].pb(max(prmx[i].back(),dp[i][j].s));
prmx2[i].pb(max(prmx2[i].back(),dp3[i][j].s-sum(i,dp3[i][j].f)));
}
reverse(all(dp2[i]));
for (ll j=0; j<dp2[i].size(); ++j) {
sfmx[i].pb(max(sfmx[i].back(),dp2[i][j].s));
}
reverse(all(dp2[i]));
reverse(all(sfmx[i]));
}
ll ans=0;
for(auto&x:dp[n]) ans=max(ans,x.s);
return ans;
return prmx[n].back();
}