이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
typedef long long int lli;
typedef vector<lli> vi;
typedef pair<lli,lli> ii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define pb push_back
#define fi first
#define se second
#define all(v) begin(v),end(v)
const lli INF = 4e18;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
map<ii,lli> inc, dec;
inc[{-1,-INF}] = dec[{-1,-INF}] = 0;
inc[{-1,INF}] = dec[{-1,INF}] = 0;
vector<pair<ii,lli>> ptw;
FOR(i,0,M) ptw.pb({{X[i],Y[i]},W[i]});
FOR(i,0,N) ptw.pb({{i,INF},0});
sort(all(ptw));
vector<ii> pts;
vector<lli> wts{0};
FOR(i,0,M+N) {
pts.pb(ptw[i].fi);
wts.pb(wts.back()+ptw[i].se);
}
//counts fish in [{x,y1},{x,y2}], inclusive of endpoints
function<lli(lli,lli,lli)> countFish = [&] (lli x, lli y1, lli y2) {
if(y1 > y2) return 0LL;
else {
int l = lower_bound(all(pts),ii{x,y1}) - begin(pts);
int r = upper_bound(all(pts),ii{x,y2}) - begin(pts);
return wts[r]-wts[l];
}
};
FOR(i,0,N) {
map<ii,lli> colInc[3];
map<ii,lli> colDec;
int l = lower_bound(all(pts), ii{i,0}) - begin(pts);
int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
int p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
FOR(j,l,r) {
if(j>l) colInc[0][pts[j]]=max(colInc[0][pts[j]],colInc[0][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1));
while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<pts[j].se) {
colInc[0][pts[j]]=max(colInc[0][pts[j]],dec[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1));
p++;
}
}
p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
while(p<int(pts.size())&&pts[p].fi==i-2) colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]),p++;
FOR(j,l+1,r) colInc[1][pts[j]] = max(colInc[1][pts[j]],colInc[1][pts[j-1]]);
p = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
FOR(j,l,r) {
if(j>l) colInc[2][pts[j]]=max(colInc[2][pts[j]],colInc[2][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1));
while(p<int(pts.size())&&pts[p].fi==i-1&&pts[p].se<pts[j].se) {
colInc[0][pts[j]]=max(colInc[0][pts[j]],inc[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1));
p++;
}
}
p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts);
ROF(j,l,r) {
if(j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+countFish(i,pts[j].se,pts[j+1].se-1));
while(p>=0&&pts[p].fi==i-1&&pts[p].se>pts[j].se) {
colDec[pts[j]]=max(colDec[pts[j]],dec[pts[p]]+countFish(i,pts[j].se,pts[p].se-1));
p--;
}
}
FOR(j,l,r) {
FOR(k,0,3) {
inc[pts[j]] = max(inc[pts[j]],colInc[k][pts[j]]);
}
dec[pts[j]] = max(dec[pts[j]],colDec[pts[j]]);
}
assert(dec[ii({i,INF})] == 0);
dec[ii{i,INF}] = inc[ii{i,INF}];
}
lli ans = max(inc[{N-1,INF}],dec.lower_bound({N-1,0})->second);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |