#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define pb push_back
const int N = 100100;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<pll> dp[N][2];
vector<pll> suf[N];
vector<pll> pref[N];
vector<int> posi[N];
vector<int> ys[N];
vector<pll> peixes[N];
vector<pll> peixesSum[N];
const ll inf = 1e18;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
for(auto &it : Y)it++;
rep(i,0,M){
peixes[X[i]].pb(pll(Y[i],W[i]));
ys[X[i]].pb(Y[i]);
}
for(int i=0;i<N;i++){
sort(all(peixes[i]));
rep(j,0,sz(peixes[i])){
peixesSum[i].pb(peixes[i][j]);
if(j)peixesSum[i][j].ss+=peixesSum[i][j-1].ss;
}
posi[i].pb(0);
if(i)for(auto it : ys[i-1]){
posi[i].pb(it);
}
if(i+1<N)for(auto it : ys[i+1]){
posi[i].pb(it);
}
Unique(posi[i]);
}
for(int i=0;i<N;i++){
// calc my dp
for(int j=0;j<2;j++){
if(j == 0){
// subindo!
// h(i-1) <= h(i).
// pego um prefixo + valores dos peixes dele
ll val=0;
int pt=0;
int ptPref=0;
for(auto it : posi[i]){
if(i == 0){
dp[i][j].pb(pll(it,0));
continue;
}
while(pt < sz(peixes[i-1]) && peixes[i-1][pt].ff<=it){
val+=peixes[i-1][pt].ss;
pt++;
}
while(ptPref + 1 < sz(pref[i-1]) && pref[i-1][ptPref+1].ff <= it)
ptPref++;
dp[i][j].pb(pll(it,pref[i-1][ptPref].ss + val));
}
}else{
// descendo
// h(i-1) >= h[i]
// pega sufixo - valores dos meus peixes
ll val=0;
int pt=0;
for(auto it : peixes[i])val+=it.ss;
for(auto it : posi[i]){
if(i == 0){
dp[i][j].pb(pll(it,0));
continue;
}
while(pt < sz(peixes[i]) && peixes[i][pt].ff<=it){
val-=peixes[i][pt].ss;
pt++;
}
auto ItSuf = lower_bound(all(suf[i-1]),pll(it,-inf));
if(ItSuf == suf[i-1].end()){
dp[i][j].pb(pll(it,0));
}else{
dp[i][j].pb(pll(it,val + ItSuf->ss));
}
}
}
}
// calc suf -> somar peixes de i+1
for(auto it : dp[i][1]){
ll peixesNext = 0;
if(i+1<N){
int pos = upper_bound(all(peixes[i+1]),pll(it.ff,inf)) - peixes[i+1].begin() - 1;
if(pos >= 0)peixesNext = peixesSum[i+1][pos].ss;
}
suf[i].pb(pll(it.ff,it.ss + peixesNext));
}
for(int j=sz(suf[i])-2;j>=0;j--){
suf[i][j].ss = max(suf[i][j].ss,suf[i][j+1].ss);
}
// calc pref -> subtrair os peixes de i
ll val=0;
int pt=0;
for(auto it : dp[i][0]){
while(pt < sz(peixes[i]) && peixes[i][pt].ff <= it.ff){
val+=peixes[i][pt].ss;
pt++;
}
pref[i].pb(pll(it.ff,it.ss - val));
}
continue;
rep(j,0,2){
cout << "=========\n";
cout << i<<" "<<j<<endl;
for(auto it : dp[i][j])cout << it.ff<<" "<<it.ss<<endl;
}
}
ll res=0;
rep(j,0,2)for(auto it : dp[N-1][j])res=max(res,it.ss);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
44856 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 |
Correct |
12 ms |
19028 KB |
Output is correct |
| 2 |
Incorrect |
159 ms |
62132 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '80958394776886' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
34636 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 |
Correct |
10 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18996 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
18992 KB |
1st lines differ - on the 1st token, expected: '4044', found: '8088' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18996 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
18992 KB |
1st lines differ - on the 1st token, expected: '4044', found: '8088' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18996 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
18992 KB |
1st lines differ - on the 1st token, expected: '4044', found: '8088' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
34636 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 |
89 ms |
44856 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
