#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) x.begin(),x.end()
bool deb_inf_col=false;
bool deb_inf_state=false;
void pri(string s, vector<ll> v){
printf("%s: ",s.c_str());
for(ll i: v) printf("%lld ",i);
printf("\n");
}
void pri(string s, vector<ll> a, vector<ll> b){
printf("%s: ",s.c_str());
for(ll i: a) printf("%lld ",b[i]);
printf("\n");
}
void fill(vector<ll> &pier, vector<ll> &fish, vector<ll> &v){
for(int i=0,j=0;i<(int)pier.size();)
if(j==(int)fish.size()-1 || (pier[i]>=fish[j] && pier[i]<fish[j+1])){
v[i]=j;
i++;
}
else j++;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<ll> sum[n],fish[n],temp_pier[n],pier[n];
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<n;i++){
sum[i].push_back(0); fish[i].push_back(0); temp_pier[i].push_back(0);
sort(all(inf_fish[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) temp_pier[i-1].push_back(inf_fish[i][j].first);
if(i!=n-1) temp_pier[i+1].push_back(inf_fish[i][j].first);
}
}
for(int i=0;i<n;i++){
sort(all(temp_pier[i]));
pier[i].push_back(temp_pier[i][0]);
for(int j=1;j<(int)temp_pier[i].size();j++)
if(temp_pier[i][j]!=temp_pier[i][j-1])
pier[i].push_back(temp_pier[i][j]);
for(int j=1;j<(int)fish[i].size();j++)
sum[i][j]+=sum[i][j-1];
}
vector<ll> left[n],me[n],right[n];
for(int i=0;i<n;i++){
left[i].assign(pier[i].size(),0);
me[i].assign(pier[i].size(),0);
right[i].assign(pier[i].size(),0);
if(i) fill(pier[i],fish[i-1],left[i]);
fill(pier[i],fish[i],me[i]);
if(i!=n-1) fill(pier[i],fish[i+1],right[i]);
}
if(deb_inf_col){
for(int i=0;i<n;i++){
printf("%d:\n",i);
pri("fish:",fish[i]);
pri("sum:",sum[i]);
pri("pier:",pier[i]);
if(i) pri("left:",left[i],fish[i-1]);
pri("me:",me[i],fish[i]);
if(i!=n-1) pri("right:",right[i],fish[i+1]);
printf("\n");
}
}
vector<vector<ll>> dec[n],inc[n];
for(int i=0;i<n;i++){
int j=(i) ? pier[i-1].size() : 1;
int k=pier[i].size();
dec[i].assign(j,vector<ll>(k,0));
inc[i].assign(j,vector<ll>(k,0));
}
for(int i=0;i<(int)pier[0].size();i++){
for(int j=0;j<(int)pier[1].size();j++){
ll act=0;
if(pier[0][i]>=pier[1][j])
act+=sum[1][right[0][i]]-sum[1][me[1][j]];
else
act+=sum[0][left[1][j]]-sum[0][me[0][i]];
dec[1][i][j]=inc[1][i][j]=act;
}
}
for(int i=2;i<n;i++){
for(int j=0;j<(int)pier[i-1].size();j++){
//decreasing:
ll prev=0,pos=0;
for(int k=0;k<(int)pier[i-2].size();k++){
if(pier[i-2][k]<pier[i-1][j]) continue;
ll aux=max(dec[i-1][k][j],inc[i-1][k][j]);
if(aux>=prev){
pos=k;
prev=aux;
}
}
if(pier[i-1][j]){
for(int k=0;k<(int)pier[i].size();k++){
if(pier[i][k]>pier[i-1][j]) break;
if(deb_inf_state){
ll up=sum[i][right[i-1][j]];
ll down=sum[i][me[i][k]];
printf("decrasing non empty %d\n",i-1);
printf("%d: %lld\n",i-1,pier[i-1][j]);
printf("%d: %lld\n",i,pier[i][k]);
printf("prev: %lld at %lld %d\n",prev,pos,i-1);
printf("-> %lld - %lld = %lld\n",up,down,up-down);
printf("-> %lld\n\n",prev+up-down);
}
dec[i][j][k]+=prev;
dec[i][j][k]+=sum[i][right[i-1][j]]-sum[i][me[i][k]];
}
}
else{
for(int k=0;k<(int)pier[i].size();k++){
if(deb_inf_state){
ll up=sum[i-1][left[i][k]];
ll down=sum[i-1][right[i-2][pos]];
printf("decrasing empty %d\n",i-1);
printf("%d: %lld\n",i-1,pier[i-1][j]);
printf("%d: %lld\n",i,pier[i][k]);
printf("prev: %lld at %lld %d\n",prev,pos,i-1);
if(pier[i][k]>pier[i-2][pos]){
printf("-> %lld - %lld = %lld\n",up,down,up-down);
printf("-> %lld\n\n",prev+up-down);
}
else
printf("-> %lld\n\n",prev);
}
dec[i][j][k]+=prev;
if(pier[i][k]>pier[i-2][pos])
dec[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][right[i-2][pos]];
}
}
//increasing:
prev=0,pos=0;
for(int k=0;k<(int)pier[i-2].size();k++){
ll aux=inc[i-1][k][j];
if(!pier[i-2][k]) aux=max(aux,dec[i-1][k][j]);
if(aux>=prev){
prev=aux;
pos=k;
}
}
for(int k=0;k<(int)pier[i].size();k++){
if(deb_inf_state){
printf("increasing\n");
printf("%d: %lld\n",i-1,pier[i-1][j]);
printf("%d: %lld\n",i,pier[i][k]);
printf("prev: %lld at %lld %lld\n",prev,pier[i-2][pos],pier[i-1][j]);
}
inc[i][j][k]+=prev;
if(pier[i-1][j]>=pier[i][k]){
if(deb_inf_state){
ll up=sum[i][right[i-1][j]];
ll down=sum[i][me[i][k]];
printf("sum at act %d\n",i);
printf("-> %lld - %lld = %lld\n",up,down,up-down);
printf("-> %lld\n\n",prev+up-down);
}
inc[i][j][k]+=sum[i][right[i-1][j]]-sum[i][me[i][k]];
}
else
if(pier[i][k]>=pier[i-2][pos]){
if(pier[i-1][j]>=pier[i-2][pos])
inc[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][me[i-1][j]];
else inc[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][right[i-2][pos]];
}
}
}
}
ll res=0;
for(int i=0;i<(int)pier[n-2].size();i++)
for(int j=0;j<(int)pier[n-1].size();j++)
res=max({res,dec[n-1][i][j],inc[n-1][i][j]});
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
125 ms |
71896 KB |
Output is correct |
| 2 |
Correct |
174 ms |
82120 KB |
Output is correct |
| 3 |
Correct |
98 ms |
58204 KB |
Output is correct |
| 4 |
Correct |
88 ms |
58272 KB |
Output is correct |
| 5 |
Correct |
343 ms |
181156 KB |
Output is correct |
| 6 |
Correct |
551 ms |
184012 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
92 ms |
58112 KB |
Output is correct |
| 2 |
Correct |
92 ms |
58208 KB |
Output is correct |
| 3 |
Incorrect |
135 ms |
64356 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '18300850571876' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
92 ms |
58112 KB |
Output is correct |
| 2 |
Correct |
92 ms |
58208 KB |
Output is correct |
| 3 |
Incorrect |
135 ms |
64356 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '18300850571876' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
125 ms |
71896 KB |
Output is correct |
| 2 |
Correct |
174 ms |
82120 KB |
Output is correct |
| 3 |
Correct |
98 ms |
58204 KB |
Output is correct |
| 4 |
Correct |
88 ms |
58272 KB |
Output is correct |
| 5 |
Correct |
343 ms |
181156 KB |
Output is correct |
| 6 |
Correct |
551 ms |
184012 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
