#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));
#define mod 1000000007
#define maxn 100005
int num[maxn];
vector<int> yval[maxn],impt[maxn];
map<int,ll> wpfx[maxn];
vector<ll> dp[3][maxn],dppfx[3][maxn],dpsfx[3][maxn];
ll max_weights(int N,int M,vi X,vi Y,vi W){
for(int i=0;i<M;++i){
++X[i],++Y[i];
yval[X[i]].pb(Y[i]);
wpfx[X[i]][Y[i]]=W[i];
if(X[i]-1>=1)impt[X[i]-1].pb(Y[i]);
if(X[i]+1<=N)impt[X[i]+1].pb(Y[i]);
}
impt[0].pb(0);
for(int i=0;i<=N+1;++i){
yval[i].pb(0);
sort(all(yval[i]));
for(int x=0;x<=2;++x){
dp[x][i].resize(num[i]+5,0);
dppfx[x][i].resize(num[i]+5,0);
dpsfx[x][i].resize(num[i]+5,0);
}
disc(impt[i]);
num[i]=impt[i].size();
#ifdef DEBUG
pf("impt %d: ",i);
for(int x:impt[i]){
pf("%d ",x);
}
pf("\n");
#endif
for(int j=1;j<num[i];++j){
int ycur=yval[i][j],ypv=yval[i][j-1];
wpfx[i][ycur]+=wpfx[i][ypv];
}
}
for(int pos=N;pos>=1;--pos){
//pf("%d\n",pos);
for(int pvid=0;pvid<num[pos-1];++pvid){
int pv=impt[pos-1][pvid];
int low1=yval[pos-1][ub(yval[pos-1],pv)-1];
int low=yval[pos][ub(yval[pos],pv)-1];
dbg("low1: %d, low: %d\n",low1,low);
int i=lb(impt[pos],pv);
mxto(dp[0][pos][pvid],dpsfx[0][pos+1][i]-wpfx[pos-1][low1]);
i=ub(impt[pos],pv)-1;
mxto(dp[1][pos][pvid],dppfx[1][pos+1][i]+wpfx[pos][low]);
mxto(dp[1][pos][pvid],dp[2][pos+1][pvid]+wpfx[pos][low]);
i=lb(impt[pos],pv);
mxto(dp[2][pos][pvid],dpsfx[0][pos+1][i]-wpfx[pos-1][low1]);
i=ub(impt[pos],pv)-1;
mxto(dp[2][pos][pvid],dppfx[2][pos+1][i]);
if(pvid!=0)mxto(dp[0][pos][pvid],dp[1][pos][pvid]);
#ifdef DEBUG
pf("dp %d %d(=%d): ",pos,pvid,pv);
for(int x=0;x<3;++x){
pf("%d ",dp[x][pos][pvid]);
}
pf("\n");
#endif
if(pos==1)continue;
int low2=yval[pos-2][ub(yval[pos-2],pv)-1];//lowest thing higher than pv
dppfx[0][pos][pvid]=dpsfx[0][pos][pvid]=dp[0][pos][pvid]+wpfx[pos-2][low2];
dppfx[1][pos][pvid]=dpsfx[1][pos][pvid]=dp[1][pos][pvid]+wpfx[pos-1][low1];
dppfx[2][pos][pvid]=dpsfx[2][pos][pvid]=dp[2][pos][pvid];
}
for(int i=1;i<num[pos-1];++i){
for(int x=0;x<3;++x){
mxto(dppfx[x][pos][i],dppfx[x][pos][i-1]);
}
}
for(int i=num[pos-1]-2;i>=0;--i){
for(int x=0;x<3;++x){
mxto(dpsfx[x][pos][i],dpsfx[x][pos][i+1]);
}
}
}
return dp[0][1][0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
160316 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
30840 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
76620 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
30740 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
30740 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
30740 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
76620 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
160316 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
