#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) x.begin(),x.end()
int get_pos(vector<ll> &fish, ll x){
int pos=lower_bound(all(fish),x)-fish.begin();
if(x!=fish[pos]) pos--;
return pos;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<pair<ll,ll>> inf_fish[n];
for(int i=0;i<m;i++) inf_fish[x[i]].push_back({y[i]+1,w[i]});
for(int i=0;i<m;i++) sort(all(inf_fish[i]));
vector<ll> pier[n],fish[n],sum[n];
for(int i=0;i<n;i++){
pier[i].push_back(0);
fish[i].push_back(0);
sum[i].push_back(0);
}
for(int i=0;i<n;i++){
for(int j=0;j<(int)inf_fish[i].size();j++){
fish[i].push_back(inf_fish[i][j].first);
sum[i].push_back(inf_fish[i][j].second);
if(i) pier[i-1].push_back(inf_fish[i][j].first);
if(i!=n-1) pier[i+1].push_back(inf_fish[i][j].first);
}
}
for(int i=0;i<n;i++)
for(int j=1;j<(int)sum[i].size();j++)
sum[i][j]+=sum[i][j-1];
vector<vector<vector<ll>>> dp[n];
for(int i=0;i<n;i++){
int j=(i>=2) ? pier[i-2].size() : 1;
int k=(i) ? pier[i-1].size() : 1;
int l=pier[i].size();
dp[i].assign(j,vector<vector<ll>>(k,vector<ll>(l,0)));
}
for(int i=0;i<(int)pier[0].size();i++)
for(int j=0;j<(int)pier[1].size();j++){
if(pier[0][i]>=pier[1][j]){
int pos_up=get_pos(fish[1],pier[0][i]);
int pos_down=get_pos(fish[1],pier[1][j]);
dp[1][0][i][j]+=sum[1][pos_up]-sum[1][pos_down];
}
else{
int pos_up=get_pos(fish[0],pier[1][i]);
int pos_down=get_pos(fish[0],pier[0][j]);
dp[1][0][i][j]+=sum[0][pos_up]-sum[0][pos_down];
}
}
if(n<3){
ll res=0;
for(int i=0;i<(int)pier[0].size();i++)
for(int j=0;j<(int)pier[1].size();j++)
res=max(res,dp[1][0][i][j]);
return res;
}
for(int i=2;i<n;i++){
for(int j=0;j<(int)pier[i-2].size();j++){
for(int k=0;k<(int)pier[i-1].size();k++){
ll prev=0;
if(i>=3)
for(int l=0;l<(int)pier[i-3].size();l++)
prev=max(prev,dp[i-1][l][j][k]);
else
prev=dp[1][0][j][k];
for(int l=0;l<(int)pier[i].size();l++){
dp[i][j][k][l]+=prev;
/*
printf("%d: %lld\n",i-2,pier[i-2][j]);
printf("%d: %lld\n",i-1,pier[i-1][k]);
printf("%d: %lld\n",i,pier[i][l]);
printf("prev: %lld at %d\n",prev,pos);
*/
if(pier[i-1][k]>=pier[i][l]){
int pos_up=get_pos(fish[i],pier[i-1][k]);
int pos_down=get_pos(fish[i],pier[i][l]);
/*
ll act=sum[i][pos_up]-sum[i][pos_down];
printf("pos_up: %d -> %lld\n",pos_up,fish[i][pos_up]);
printf("pos_down: %d -> %lld\n",pos_down,fish[i][pos_down]);
printf("%lld - %lld -> %lld\n",sum[i][pos_up],sum[i][pos_down],act);
*/
dp[i][j][k][l]+=sum[i][pos_up]-sum[i][pos_down];
}
if(pier[i][l]>pier[i-1][k] && pier[i][l]>=pier[i-2][j]){
int pos_up=get_pos(fish[i-1],pier[i][l]);
int pos_down=get_pos(fish[i-1],max(pier[i-1][k],pier[i-2][j]));
/*
ll act=sum[i-1][pos_up]-sum[i-1][pos_down];
printf("pos_up: %d -> %lld\n",pos_up,fish[i-1][pos_up]);
printf("pos_down: %d -> %lld\n",pos_down,fish[i-1][pos_down]);
printf("%lld - %lld -> %lld\n",sum[i-1][pos_up],sum[i-1][pos_down],act);
*/
dp[i][j][k][l]+=sum[i-1][pos_up]-sum[i-1][pos_down];
}
//printf("%lld\n\n",dp[i][j][k][l]);
}
}
}
}
ll res=0;
for(int i=0;i<(int)pier[n-3].size();i++)
for(int j=0;j<(int)pier[n-2].size();j++)
for(int k=0;k<(int)pier[n-1].size();k++)
res=max(res,dp[n-1][i][j][k]);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
46552 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
30716 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 |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
30716 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 |
97 ms |
46552 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
