#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 ans, pr, left, right;
int coord;
fish(int coord,ll val) : ans(0), pr(val), left(0), right(0), coord(coord){}
};
vector<fish>v[maxn];
vector<ll>dp1[maxn], dp2[maxn], dp3[maxn];
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){
v[Y[i]+1].pb(fish(X[i]+1,W[i]));
}
for(int i=0;i<=N;++i){
v[i].pb(fish(0,0));
sort(all(v[i]), comp);
for(int j=1;j<sz(v[i]);++j)v[i][j].pr += v[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(v[x]);++i){
while(cur<sz(v[idx])-1&&v[idx][cur+1].coord<=v[x][i].coord)++cur;
ll y = v[idx][cur].pr;
if(type)v[x][i].right = y;
else v[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=0;i<=N;++i){
int cur = 0, cur2 = 0;
for(auto& x:v[i]){
//2 casos:
//a minha coordenada é k
//1: a linha à minha esquerda é menor do que eu:
//max(dp[i-1][j]-qnt[i][j]-qnt[i-1][j])+qnt[i-1][k]+qnt[i+1][k]
//2:a linha à minha esquerda é maior do que eu:
//max(dp[i-1][j]) - qnt[i][k] - qnt[i-1][k] + qnt[i+1][k]
//corner case: o cara do meu lado é igual a zero
if(i<=1){
x.ans = x.right;
}else{
if(i>=3)x.ans = dp2[i-3][0];//duas colunas anteriores sao 0
while(cur<sz(v[i-1])-1&&
v[i-1][cur+1].coord<=x.coord)++cur;
while(cur2<sz(v[i-2])-1&&
v[i-2][cur2+1].coord<=x.coord)++cur2;
//coluna anterior é igual a zero
ckmax(x.ans,max(dp3[i-2][cur2]+x.left+x.right,
(cur2==sz(dp2[i-2])-1?0:dp2[i-2][cur+1]+x.right)));
ckmax(x.ans,dp1[i-1][cur] + x.pr + x.right);
if(cur!=sz(dp1[i-1])-1){
ckmax(x.ans, dp2[i-1][cur+1]-x.pr+x.right);
}
}
}
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){
dp1[i][j] = max(dp1[i][j-1],v[i][j].ans-v[i][j].pr
-v[i][j].right);
dp3[i][j] = max(dp3[i][j-1], v[i][j].ans - v[i][j].right);
}
for(int j=sz(v[i])-1;j>=0;--j){
dp2[i][j] = v[i][j].ans;
if(j!=sz(v[i])-1)ckmax(dp2[i][j], dp2[i][j+1]);
}
}
return dp2[N][0];
}
// 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;
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
64 ms |
28156 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '23053534069664' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
35 ms |
23780 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
35 ms |
23780 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
64 ms |
28156 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '23053534069664' |
| 2 |
Halted |
0 ms |
0 KB |
- |
