#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<int,int>>fish[100001];
vector<ll>sum_down[100001];
vector<ll>sum_right[100001];
vector<ll>sum_left[100001];
vector<ll>next_right[100001];
vector<ll>next_left[100001];
int h[100001];
vector<ll>dp1[1000001];
vector<bool>dpt1[1000001];
vector<ll>dp2[1000001];
vector<bool>dpt2[1000001];
vector<ll>dp3[1000001];
vector<bool>dpt3[1000001];
ll dp4[1000001];
bool dpt4[1000001];
ll get_slope_down(int x,int y);
ll get_slope_up(int x,int y);
ll get_gap(int x,ll min_sum);
ll get_full(int x);
ll get1(int y2,int x){
if(y2<0)
return LLONG_MIN;
ll res=get_slope_down(x+1,y2);
res=max(res,get1(y2-1,x));
return res;
}
ll get_slope_down(int x,int y){
if(x==n-1){
return 0;
}
if(dpt1[x][y])
return dp1[x][y];
ll res=get1(next_right[x][y]-1,x)-sum_down[x][y]+sum_right[x][y];
ll res2=get_gap(x+1,sum_right[x][y])-sum_down[x][y];
res=max(res,res2);
dpt1[x][y]=true;
dp1[x][y]=res;
return res;
}
ll get2(int y2,int x){
if(y2<0)
return LLONG_MIN;
ll res=get_slope_up(x+1,y2);
res=max(res,get2(y2-1,x));
return res;
}
ll get_slope_up(int x,int y){
if(x==n-1){
return 0;
}
if(dpt2[x][y])
return dp2[x][y];
ll res=get2(next_right[x][y]-1,x)-sum_down[x][y]+sum_left[x][y];
ll res2=get_full(x+1)+sum_left[x+1].back()-sum_down[x][y]+sum_left[x][y];
res=max(res,res2);
dpt2[x][y]=true;
dp2[x][y]=res;
return res;
}
ll get_gap(int x,ll min_sum){
if(x==n-1)
return min_sum;
ll res=0;
res=max(res,get_full(x+1)+sum_left[x+1].back());
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_up(x+1,y2)+max(sum_left[x+1][y2],min_sum)-sum_left[x+1][y2];
res=max(res,res2);
}
return res;
}
ll get_full(int x){
if(x==n-1)
return 0;
if(dpt4[x])
return dp4[x];
ll res=0;
res=max(res,get_gap(x+1,sum_right[x].back()));
for(int y2=0;y2<h[x+1];y2++){
ll res2=get_slope_down(x+1,y2)+sum_right[x].back();
res=max(res,res2);
}
dpt4[x]=true;
dp4[x]=res;
return res;
}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
n=N+1;
for(int i=0;i<M;i++)
fish[X[i]+1].push_back({Y[i],W[i]});
for(int i=0;i<n;i++)
sort(fish[i].begin(),fish[i].end());
for(int i=0;i<n;i++)
fish[i].push_back({n,0});
for(int i=0;i<n;i++)
h[i]=(int)fish[i].size();
for(int i=0;i<n;i++){
sum_down[i].resize(h[i]);
for(int j=1;j<h[i];j++){
sum_down[i][j]=sum_down[i][j-1]+fish[i][j-1].second;
}
}
for(int i=0;i<n;i++){
dp1[i].resize(h[i]);
dpt1[i].resize(h[i]);
dp2[i].resize(h[i]);
dpt2[i].resize(h[i]);
dp3[i].resize(h[i]);
dpt3[i].resize(h[i]);
}
sum_right[n-1].resize(h[n-1]);
for(int i=0;i<n-1;i++){
sum_right[i].resize(h[i]);
next_right[i].resize(h[i]);
int i2=0;
ll sum=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i+1]&&fish[i][i1].first>fish[i+1][i2].first){
sum+=fish[i+1][i2].second;
i2++;
}
sum_right[i][i1]=sum;
}
i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i+1]&&fish[i][i1].first>=fish[i+1][i2].first)
i2++;
next_right[i][i1]=i2;
}
}
sum_left[0].resize(h[0]);
for(int i=1;i<n;i++){
sum_left[i].resize(h[i]);
next_left[i].resize(h[i]);
int i2=0;
ll sum=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i-1]&&fish[i][i1].first>fish[i-1][i2].first){
sum+=fish[i-1][i2].second;
i2++;
}
sum_left[i][i1]=sum;
}
i2=0;
for(int i1=0;i1<h[i];i1++){
while(i2<h[i-1]&&fish[i][i1].first>=fish[i-1][i2].first)
i2++;
next_left[i][i1]=i2;
}
}
return get_gap(0,0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
180 ms |
252024 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '9223372036631013451' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
87 ms |
202188 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
155 ms |
248800 KB |
Output is correct |
| 2 |
Correct |
148 ms |
248908 KB |
Output is correct |
| 3 |
Correct |
169 ms |
245440 KB |
Output is correct |
| 4 |
Correct |
194 ms |
250020 KB |
Output is correct |
| 5 |
Correct |
214 ms |
251524 KB |
Output is correct |
| 6 |
Correct |
191 ms |
251524 KB |
Output is correct |
| 7 |
Correct |
195 ms |
251436 KB |
Output is correct |
| 8 |
Correct |
225 ms |
251464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
202136 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
202136 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
202136 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
155 ms |
248800 KB |
Output is correct |
| 2 |
Correct |
148 ms |
248908 KB |
Output is correct |
| 3 |
Correct |
169 ms |
245440 KB |
Output is correct |
| 4 |
Correct |
194 ms |
250020 KB |
Output is correct |
| 5 |
Correct |
214 ms |
251524 KB |
Output is correct |
| 6 |
Correct |
191 ms |
251524 KB |
Output is correct |
| 7 |
Correct |
195 ms |
251436 KB |
Output is correct |
| 8 |
Correct |
225 ms |
251464 KB |
Output is correct |
| 9 |
Incorrect |
193 ms |
251212 KB |
1st lines differ - on the 1st token, expected: '99999', found: '74999' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
180 ms |
252024 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '9223372036631013451' |
| 2 |
Halted |
0 ms |
0 KB |
- |
