#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "fish.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
struct fish{
ll ans1, ans2, pr, left, right;
int coord;
fish(int coord,ll val) : ans1(0), ans2(0), pr(val), left(0), right(0), coord(coord){}
};
vector<fish>tmp[maxn], v[maxn];
vector<ll>dp1[maxn], dp2[maxn], dp3[maxn];//1: subindo, 2: descendo
//ideia: toda ponte termina em um bagre. todo conjunto conexo de pontes forma uma piramide
//(nao possui nenhum minimo local). Logo, pra cada conjunto vou subir e depois descer, sempre nessa ordem.
//nao necessariamente vou subir antes de descer ou descer depois de subir. As transições sao bem diretas mas chatas.
//dp1[i][j] -> considero o melhor valor no prefixo, tirando o right e o pr de cada um (SUBINDO)
//dp2[i][j] -> considero o melhor valor no sufixo (DESCENDO + SUBINDO)
//dp3[i][j] -> considero o melhor valor no prefixo, tirando o right de cada um (DESCENDO + SUBINDO)
bool comp(fish a,fish b){return a.coord<b.coord;}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int> W) {
for(int i=0;i<M;++i){
tmp[Y[i]+1].pb(fish(X[i]+1,W[i]));
}
for(int i=0;i<=N;++i){
tmp[i].pb(fish(0,0));
for(int j=1;j<sz(tmp[i]);++j)tmp[i][j].pr += tmp[i][j-1].pr;
}
auto processa = [&](int x,bool type){
int cur = 0, idx = (type?x+1:x-1);
for(int i=1;i<sz(tmp[x]);++i){
while(cur<sz(tmp[idx])-1&&tmp[idx][cur+1].coord<=tmp[x][i].coord)++cur;
ll y = (tmp[idx][cur].coord<=tmp[x][i].coord?tmp[idx][cur].pr:0);
if(type)tmp[x][i].right = y;
else tmp[x][i].left = y;
}
};
for(int i=1;i<=N;++i){
if(i!=1)processa(i,0);
if(i!=N)processa(i,1);
}
for(int i=1;i<=N;++i){
for(auto x:tmp[i]){
v[i+1].pb(x), v[i-1].pb(x);
}
}
for(int i=0;i<=N;++i){
v[i].pb(fish(0,0));
sort(all(v[i]), comp);
}
ll resp = 0;
for(int i=0;i<=N;++i){
int cur = 0, cur2 = 0;
if(i){
for(int j=0;j<sz(v[i]);++j){
auto& x = v[i][j];
//dp só guarda resultados onde eu coloco uma ponte
//o caso onde não tem ponte na esquerda é tratado separadamente
while(cur<sz(v[i-1])-1&&v[i-1][cur+1].coord<=x.coord)++cur;
if(i>1)while(cur2<sz(v[i-2])-1&&v[i-2][cur2+1].coord<=x.coord)++cur2;
//subindo
//ans1(i,j) = max(dp1[i-1][k]-pr[i][k]-pr[i-1][k]) + pr[i-1][j] + pr[i+1][j], k<=j
x.ans1 = dp1[i-1][cur] + x.left + x.right;
//descendo
//ans2(i,j) = max(dp2[i-1][k]) - pr[i][j] + pr[i+1][j], k>=j
if(cur!=sz(v[i-1])-1)x.ans2 = dp2[i-1][cur+1] - x.pr + x.right;
ll y = 0;
//i-1 é zero
if(i>=2)y = max(dp3[i-2][cur2]+x.left+x.right, (cur2!=sz(v[i-2])-1?dp2[i-2][cur2+1]+x.right:0));
//i-1 e i-2 são zero
if(i>=3)ckmax(y, dp2[i-3][0] + x.left + x.right);
ckmax(x.ans1,y), ckmax(x.ans2,y);
}
}else v[0][0].ans1 = v[0][0].ans2 = 0;
dp1[i].resize(sz(v[i])), dp2[i].resize(sz(v[i])), dp3[i].resize(sz(v[i]));
for(int j=1;j<sz(v[i]);++j){
auto x = v[i][j];
dp1[i][j] = max(dp1[i][j-1], x.ans1 - x.pr - x.right);
dp3[i][j] = max({dp3[i][j-1], x.ans1 - x.right, x.ans2});
ckmax(resp, max(x.ans1, x.ans2));
}
for(int j=sz(v[i])-1;j>=0;--j){
auto x = v[i][j];
if(j!=sz(v[i])-1)dp2[i][j] = dp2[i][j+1];
ckmax(dp2[i][j], max(x.ans1,x.ans2));
}
}
return resp;
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> X(M), Y(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
// }
// long long result = max_weights(N, M, X, Y, W);
// printf("%lld\n", result);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
69320 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '47112956573064' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
48140 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 |
6 ms |
11988 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 |
6 ms |
11988 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 |
6 ms |
11988 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 |
64 ms |
48140 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 |
142 ms |
69320 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '47112956573064' |
| 2 |
Halted |
0 ms |
0 KB |
- |
