| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1159570 | Math4Life2020 | 메기 농장 (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5+5; const ll INF = 1e18;
vector<pii> vctf[Nm];
map<ll,ll> psw[Nm]; //current x, lower bound at y0 -> sum of ws with y>=y0
vector<ll> yc[Nm]; //ys to consider
map<ll,ll> dp1[Nm];
map<ll,ll> dp2[Nm];
map<ll,ll> dp3[Nm];
//dp1: ...,a,0; store a
//dp2: ...,a,b; a<=b; store b
//dp3: ...,a,b; a>=b; store b
ll getps(ll xc, ll v) {
auto A0 = *(psw[xc].lower_bound(v));
return A0.second;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (ll i=0;i<M;i++) {
vctf[X[i]].push_back({Y[i],W[i]});
}
for (ll i=0;i<Nm;i++) {
sort(vctf[i].begin(),vctf[i].end());
psw[i][INF]=0;
ll swcur = 0;
for (ll T=(vctf[i].size()-1);T>=0;T--) {
swcur += vctf[i][T].second;
psw[i][vctf[i][T].first]=swcur;
}
}
for (ll i=0;i<N;i++) {
set<ll> scur;
if (i>0) {
for (pii p0: vctf[i-1]) {
scur.insert(p0.first-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
}
if (i<(N-1)) {
for (pii p0: vctf[i+1]) {
scur.insert(p0.first-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
}
for (pii p0: vctf[i]) {
scur.insert(p0.first-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
yc[i].push_back(0);
for (ll x0: scur) {
if (x0>=0) {
yc[i].push_back(x0+1);
}
}
}
//DP: # of terms active -> value at <=(current x) SO FAR
//dp1: ...,a,0; store a
//dp2: ...,a,b; a<=b; store b
//dp3: ...,a,b; a>=b; store b; MUST go down
dp1[0][0]=0;
for (ll i=0;i<N;i++) {
//dp1 -> dp1
for (pii p0: dp1[i]) {
dp1[i+1][0]=max(dp1[i+1][0],p0.second);
}
//dp1 -> dp2
ll PMAX1 = -INF;
for (pii p0: dp1[i]) {
PMAX1 = max(PMAX1,p0.second);
}
for (ll yv: yc[i]) {
dp2[i+1][yv]=max(dp2[i+1][yv],PMAX1);
}
if (i>0) {
vector<pii> vt1;
vt1.push_back({-INF,-INF});
ll cmax = -INF;
for (pii p0: dp1[i]) {
ll vcur = p0.second+getps(i-1,p0.first);
if (vcur > cmax) {
cmax = vcur;
vt1.push_back({p0.first,vcur});
}
}
for (ll yv: yc[i]) {
auto A0 = --lower_bound(dp2[i+1].begin(),dp2[i+1].end(),{yc,INF});
dp2[i+1][yv]=max(dp2[i+1][yv],(*A0).second-getps(i-1,yv));
}
}
// for (ll yv: yc[i]) {
// for (pii p0: dp1[i]) {
// if (i>0) {
// dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i-1,p0.first)-getps(i-1,max(p0.first,yv)));
// //2 cases: p0.first >= yv -> just vanilla what we have above
// //and p0.first < yv -> dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i-1,p0.first)-getps(i-1,yv))
// }
// //[0,p0.first] -> [0,max(p0.first,yv)]
// }
// }
//dp2 -> dp1
for (pii p0: dp2[i]) {
dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
}
//dp2 -> dp2
for (ll yv: yc[i]) {
for (pii p0: dp2[i]) {
if (yv>=p0.first) {
dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i-1,p0.first)-getps(i-1,yv));
}
}
}
//dp2 -> dp3
for (ll yv: yc[i]) {
for (pii p0: dp2[i]) {
if (yv<=p0.first) {
//FIX??
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv)-getps(i,p0.first));
}
}
}
//dp3 -> dp1
for (pii p0: dp3[i]) {
dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
}
//dp3 -> dp3
vector<pii> vt5I,vt5;
for (pii p0: dp3[i]) {
vt5I.push_back({p0.first,p0.second-getps(i,p0.first)});
}
sort(vt5I.rbegin(),vt5I.rend());
ll cmaxv = -INF;
for (pii p0: vt5I) {
if (p0.second>cmaxv) {
cmaxv = p0.second;
vt5.push_back(p0);
}
}
vt5.push_back({INF,-INF});
sort(vt5.begin(),vt5.end());
for (ll yv: yc[i]) {
pii p0 = *lower_bound(vt5.begin(),vt5.end(),(pii){yv,-INF});
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv));
}
// for (ll yv: yc[i]) {
// for (pii p0: dp3[i]) {
// if (yv<=p0.first) {
// dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv)-getps(i,p0.first));
// }
// }
// }
// cout << "print states after reading column i="<<i<<"\n";
// cout << "dp1:\n";
// for (pii p0: dp1[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
// cout << "dp2:\n";
// for (pii p0: dp2[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
// cout << "dp3:\n";
// for (pii p0: dp3[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
}
ll ans = 0;
for (pii p0: dp1[N]) {
ans = max(ans,p0.second);
}
for (pii p0: dp2[N]) {
ans = max(ans,p0.second);
}
for (pii p0: dp3[N]) {
ans = max(ans,p0.second);
}
return ans;
}