#include "fish.h"
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int NN=3005;
ll catfish[NN][NN];
ll pf[NN+1][NN+1];
vector<ll> memo[NN][NN];
int maxclaimed[NN];
int PN;
vector<ll> dp(int i, int h){
//cout<<i<<" "<<h<<endl;
vector<ll> e={-1,-1,-1};
if (i>=PN)return {0,-1,-1};
if (memo[i][h].size()>0)return memo[i][h];
ll maxf=0;
int saving=0;
ll grandpa=0;
for (int y = 0;y<=PN;++y){
ll rslt = dp(i+1,y)[0];
ll claimednext=dp(i+1,y)[1];
//cout<<"Index: "<<i<<" | BF : "<<h<<" | H: "<<y<<" | MAXF: "<<claimednext<<endl;
//cout<<rslt<<endl;
if (i!=0 && y>h){
rslt+=(pf[i-1][y] - pf[i-1][h]);
}
//cout<<rslt<<endl;
///
if (dp(i+1,y)[2]<y && i<PN-1)rslt-=(pf[i][y] - pf[i][dp(i+1,y)[2]]);
else if (dp(i+1,y)[2]<y)rslt-=pf[i][y];
//cout<<rslt<<" "<<dp(i+1,y)[2]<<endl;
if (claimednext<y)rslt+=pf[i+1][y];
else if (y>claimednext)rslt+=((pf[i+1][y] - pf[i+1][claimednext]));
//cout<<rslt<<endl;
//rslt-=pf[i][min(maxclaimed[i]+1,y+1)];
//rslt+=pf[i+1][y];
//cout<<rslt<<endl;
//rslt-=pf[i][y];
if (rslt>maxf){
maxf=rslt;
saving=y;
grandpa=dp(i+1,y)[2];
//maxclaimed[i-1]=saving;
}
}
return memo[i][h]={maxf,grandpa,saving};
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
memset(memo, {}, sizeof memo);
memset(maxclaimed, -1, sizeof maxclaimed);
memset(pf, 0, sizeof pf);
memset(catfish, 0, sizeof catfish);
//cout<<"2hola"<<endl;
PN=N;
for (int i = 0; i < M;++i)catfish[X[i]][Y[i]]=W[i];
//cout<<"ho1la"<<endl;
for (int x = 0; x < N+1;++x){
ll c=0;
pf[x][0]=0;
for (int y =0;y<N+1;++y){
c+=catfish[x][y];
pf[x][y+1]=c;
}
}
//cout<<"hola"<<endl;
return dp(0,0)[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |