#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) { cerr<<"["<<#x<<"]=["; _PRINT(x); }
vector<vector<int>> ind;
vector<vector<pair<int,ll>>> fish;
vector<vector<ll>> dp[2];
map<int,ll> pref;
ll Sum(int l,int r){
ll prefr=prev(pref.upper_bound(r))->se;
ll prefl=prev(pref.upper_bound(l-1))->se;
return prefr-prefl;
}
void MaxSelf(ll& x,ll y){
x=max(x,y);
}
long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
ind.resize(N); fish.resize(N);
dp[0].resize(N); dp[1].resize(N);
for(int i=0;i<M;i++){
if(X[i]) ind[X[i]-1].pb(Y[i]+1);
if(X[i]+1<N) ind[X[i]+1].pb(Y[i]+1);
fish[X[i]].pb({Y[i],W[i]});
}
for(int x=0;x<N;x++){
ind[x].pb(0); ind[x].pb(N);
sort(all(ind[x]));
sort(all(fish[x]));
ind[x].resize(unique(all(ind[x]))-ind[x].begin());
dp[0][x].resize(sz(ind[x]));
dp[1][x].resize(sz(ind[x]));
}
for(int x=1;x<N;x++){
pref.clear(); pref[-1]=0;
for(int i=0;i<sz(fish[x-1]);i++){
int y=fish[x-1][i].fi;
int w=fish[x-1][i].se;
pref[y]=pref.upper_bound(y-1)->se+w;
}
if(x>1){
int i1=sz(ind[x-2])-1;
ll suf_max=-LINF;
for(int i=sz(ind[x])-1;i>=0;i--){
while(i1>=0 && ind[x-2][i1]>ind[x][i]){
ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
MaxSelf(suf_max,m+Sum(0,ind[x-2][i1]-1));
i1--;
}
MaxSelf(dp[1][x][i],suf_max);
}
i1=0;
ll pref_max=-LINF;
for(int i=0;i<sz(ind[x]);i++){
while(i1<sz(ind[x-2]) && ind[x-2][i1]<=ind[x][i]){
ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
MaxSelf(pref_max,m);
i1++;
}
MaxSelf(dp[1][x][i],pref_max+Sum(0,ind[x][i]-1));
}
i1=1;
pref_max=-LINF;
for(int i=0;i<sz(ind[x]);i++){
if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
i1++;
}
MaxSelf(dp[1][x][i],pref_max);
}
pref.clear(); pref[-1]=0;
for(int i=0;i<sz(fish[x]);i++){
int y=fish[x][i].fi;
int w=fish[x][i].se;
pref[y]=pref.upper_bound(y-1)->se+w;
}
i1=sz(ind[x-1])-1;
suf_max=-LINF;
for(int i=sz(ind[x])-1;i>=0;i--){
if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
while(i1>=0 && ind[x-1][i1]>ind[x][i]){
ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
i1--;
}
MaxSelf(dp[0][x][i],suf_max);
}
}
else if(x==1){
int i1=0;
ll pref_max=-LINF;
for(int i=0;i<sz(ind[x]);i++){
if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
i1++;
}
MaxSelf(dp[1][x][i],pref_max);
}
pref.clear(); pref[-1]=0;
for(int i=0;i<sz(fish[x]);i++){
int y=fish[x][i].fi;
int w=fish[x][i].se;
pref[y]=pref.upper_bound(y-1)->se+w;
}
i1=sz(ind[x-1])-1;
ll suf_max=-LINF;
for(int i=sz(ind[x])-1;i>=0;i--){
if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
while(i1>=0 && ind[x-1][i1]>ind[x][i]){
ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
i1--;
}
MaxSelf(dp[0][x][i],suf_max);
}
}
}
ll res=0;
for(int i=0;i<sz(ind[N-1]);i++){
ll m=max(dp[0][N-1][i],dp[1][N-1][i]);
MaxSelf(res,m);
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
122 ms |
28428 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Incorrect |
319 ms |
36472 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '1999943696' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
19024 KB |
Output is correct |
2 |
Correct |
42 ms |
18976 KB |
Output is correct |
3 |
Correct |
84 ms |
20968 KB |
Output is correct |
4 |
Correct |
73 ms |
21564 KB |
Output is correct |
5 |
Correct |
135 ms |
26188 KB |
Output is correct |
6 |
Correct |
133 ms |
25568 KB |
Output is correct |
7 |
Correct |
138 ms |
26116 KB |
Output is correct |
8 |
Correct |
149 ms |
26056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
19024 KB |
Output is correct |
2 |
Correct |
42 ms |
18976 KB |
Output is correct |
3 |
Correct |
84 ms |
20968 KB |
Output is correct |
4 |
Correct |
73 ms |
21564 KB |
Output is correct |
5 |
Correct |
135 ms |
26188 KB |
Output is correct |
6 |
Correct |
133 ms |
25568 KB |
Output is correct |
7 |
Correct |
138 ms |
26116 KB |
Output is correct |
8 |
Correct |
149 ms |
26056 KB |
Output is correct |
9 |
Correct |
156 ms |
29004 KB |
Output is correct |
10 |
Incorrect |
120 ms |
19136 KB |
1st lines differ - on the 1st token, expected: '36454348383152', found: '23772043885836' |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
122 ms |
28428 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243' |
2 |
Halted |
0 ms |
0 KB |
- |