| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 630654 | CSQ31 | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define sz(a) (int)(a.size())
//0 -> previous is lower
//1 -> previous is higher
const int MAXN = 111111;
vector<int>st[MAXN];
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],pre[3][MAXN];
int cnt[MAXN];
const ll INF = -1e17;
long long max_weights(int n, int m, vector<int> X, vector<int> Y,vector<int> W) {
for(int i=0;i<m;i++){
X[i]++;
Y[i]++;
fish[X[i]].push_back({Y[i],i});
}
for(int i=0;i<=n;i++){
vector<pii>f;
st[i].push_back(0);
if(i){
for(auto x:fish[i-1]){
st[i].push_back(x.fi);
f.push_back(x);
}
}
for(auto x:fish[i]){
st[i].push_back(x.fi);
f.push_back(x);
}
for(auto x:fish[i+1]){
st[i].push_back(x.fi);
f.push_back(x);
}
sort(st[i].begin(),st[i].end());
sort(f.begin(),f.end());
st[i].resize(unique(st[i].begin(),st[i].end()) - st[i].begin());
cnt[i] = st[i].size();
for(int k=0;k<3;k++)pre[k][i].assign(cnt[i],0);
for(int k=0;k<2;k++)dp[k][i].assign(cnt[i],INF);
int ptr = -1;
for(int j=0;j<cnt[i];j++){
while(ptr+1 < sz(f) && f[ptr+1].fi <= st[i][j]){
ptr++;
int id = f[ptr].se;
if(Y[id] != st[i][j])continue;
if(X[id] == i-1)pre[0][i][j]+=W[id];
if(X[id] == i )pre[1][i][j]+=W[id];
if(X[id] == i+1)pre[2][i][j]+=W[id];
}
}
for(int k=0;k<3;k++){
for(int j=1;j<cnt[i];j++)pre[k][i][j]+=pre[k][i][j-1];
}
}
dp[0][0][0] = 0;
for(int i=1;i<=n;i++){
ll mx = INF;
int ptr = -1;
for(int j=0;j<cnt[i];j++){
while(ptr+1<cnt[i-1] && st[i-1][ptr+1] <= st[i][j]){
ptr++;
mx = max(mx,dp[0][i-1][ptr] - pre[1][i-1][ptr]);
}
dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
}
mx = INF;
ptr = cnt[i-1];
for(int j=cnt[i]-1;j>=0;j--){
while(ptr-1>=0 && st[i-1][ptr-1] >= st[i][j]){
ptr--;
mx = max(mx,dp[0][i-1][ptr] + pre[1][i][j]);
mx = max(mx,dp[1][i-1][ptr] + pre[1][i][j]);
}
dp[1][i][j] = max(dp[1][i][j],mx - pre[1][i][j]);
}
if(i<2)continue;
mx = INF;
ptr = -1;
for(int j=0;j<cnt[i];j++){
while(ptr+1 < cnt[i-2] && st[i-2][ptr+1] <= st[i][j]){
ptr++;
mx = max(mx,dp[0][i-2][ptr]);
mx = max(mx,dp[1][i-2][ptr]);
}
dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
}
}
ll ans = 0;
for(ll x:dp[0][n])ans = max(ans,x);
for(ll x:dp[1][n])ans = max(ans,x);
return ans;
}
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;
}