| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1248164 | meisgood | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std ;
#define test
// #ifndef test
#include "fish.h"
#endif
////////////////////////////////////////////////////////////////////////#include "fish.h"
#include <vector>
vector <pair<int,long long>> ps[100003] ;
vector <pair<int,long long>> fs[100003] ;
vector <pair<int,long long>> dp[100003][2] ;
long long get(int x,int y){
return (*--upper_bound(ps[x].begin(),ps[x].end(),pair<int,long long>{y,INT_MAX})).second ;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
int i,j ;
for (i = 0 ; i < M ; i ++){
X[i]++ ;
Y[i]++ ;
fs[X[i]].push_back({Y[i],W[i]}) ;
}
for (i = 1 ; i <= N ; i ++) sort(fs[i].begin(),fs[i].end()) ;
for (i = 0 ; i <= N+1 ; i ++){
ps[i].push_back({-1,0}) ;
for (auto [a,b] : fs[i]){
ps[i].push_back({a,(*--ps[i].end()).second+b}) ;
}
}
// cout << get(1,2) << endl ;
dp[0][0].push_back({0,0}) ;
for (i = 1 ; i <= N ; i ++){
vector <int> cs ;
cs.push_back(0) ;
for (auto [a,b] : fs[i-1]) cs.push_back(a) ;
for (auto [a,b] : fs[i+1]) cs.push_back(a) ;
sort(cs.begin(),cs.end()) ;
cs.resize(unique(cs.begin(),cs.end())-cs.begin()) ;
for (auto x : cs) dp[i][0].push_back({x,0}) ;
for (auto x : cs) dp[i][1].push_back({x,0}) ;
int nw=0 ;
j=-1 ;
long long mx=0 ;
dp[i][0][0].second=max(dp[i][0][0].second,dp[i-1][0][0].second) ;
dp[i][1][0].second=max(dp[i][1][0].second,dp[i][0][0].second) ;
for (auto x : cs){
// cout << x << endl ;
j++ ;
if (x==0) continue ;
while (nw<dp[i-1][0].size()&&dp[i-1][0][nw].first<=x){
mx=max(mx,dp[i-1][0][nw].second-get(i,dp[i-1][0][nw].first)-get(i-1,dp[i-1][0][nw].first)) ;
nw++ ;
}
dp[i][0][j].second=max(dp[i][0][j].second,mx+get(i-1,x)+get(i+1,x)) ;
dp[i][1][j].second=max(dp[i][1][j].second,dp[i][0][j].second) ;
// cout << i << " " << x << " " << dp[i][0][j].second << endl ;
}
nw=dp[i-1][1].size()-1 ;
mx=0 ;
for (j = cs.size()-1 ; j >= 0 ; j --){
int x=cs[j] ;
if (x==0) continue ;
while (nw>=0&&dp[i-1][1][nw].first>=x){
mx=max(mx,dp[i-1][1][nw].second) ;
nw-- ;
}
dp[i][1][j].second=max(dp[i][1][j].second,mx-get(i,x)+get(i+1,x)) ;
}
if (i>=2){
nw=0 ;
j=-1 ;
mx=0 ;
for (auto x : cs){
j++ ;
while (nw<dp[i-2][1].size()&&dp[i-2][1][nw].first<=x){
mx=max(mx,dp[i-2][1][nw].second-get(i-1,dp[i-2][1][nw].first)) ;
nw++ ;
}
dp[i][0][j].second=max(dp[i][0][j].second,mx+get(i-1,x)+get(i+1,x)) ;
dp[i][1][j].second=max(dp[i][1][j].second,dp[i][0][j].second) ;
// cout << i << " " << x << " " << dp[i][0][j].second << endl ;
}
mx=0 ;
for (auto [a,b] : dp[i-2][1]){
mx=max(mx,b) ;
}
j=-1 ;
for (auto x : cs){
j++ ;
dp[i][0][j].second=max(dp[i][0][j].second,mx+get(i+1,x)) ;
dp[i][1][j].second=max(dp[i][1][j].second,dp[i][0][j].second) ;
}
}
}
long long mx=0 ;
for (i = 1 ; i <= N ; i ++){
for (auto [a,b] : dp[i][0]){
// cout << i << " " << a << " " << b << endl ;
mx=max(mx,b) ;
}
for (auto [a,b] : dp[i][1]) mx=max(mx,b) ;
}
return mx ;
}
////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
// #include "fish.h"
#include <cassert>
#include <cstdio>
#include <vector>
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}
#endif