Submission #682805

#TimeUsernameProblemLanguageResultExecution timeMemory
682805sunwukong123Catfish Farm (IOI22_fish)C++17
81 / 100
1020 ms148044 KiB
#include "fish.h" #include <bits/stdc++.h> #define int long long using namespace std; #define FOR(i,s,e) for(int i = s; i <= (int)e; ++i) #define DEC(i,s,e) for(int i = s; i >= (int)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define reach #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <int, int> pi; typedef tuple<int,int,int> ti3; typedef tuple<int,int,int,int> ti4; int rand(int a, int b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (long long)1e18 + 500; template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; } template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; } const int MAXN = 100005; map<int,int> dp[MAXN][2]; // dp[i][has this node been added by the left?][height] map<pi,int> V; int ans; vector<int> H[MAXN]; vector<int> P[MAXN]; vector<pi> S[MAXN]; int S1, S3; vector<pi> S2, S4; #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native") int query1(int h) { return S1; } int query3(int h) { return S3; } int query2(int h){ int res=prev(upper_bound(all(S2), pi(h,oo)))->s; return res; } int query4(int h) { reach int res=lower_bound(all(S4), pi(h,-oo))->s; reach return res; } long long max_weights(int32_t n, int32_t m, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) { int height = 0; FOR(i,0,m-1){ ++Y[i]; V[pi(X[i],Y[i])]=W[i]; chmax(height, (int)Y[i]); H[X[i]].pb(Y[i]); H[X[i]].pb(Y[i]-1); } FOR(i,0,n) { H[i].pb(0); H[i].pb(height); sort(all(H[i])); H[i].resize(unique(all(H[i])) - H[i].begin()); } FOR(i,0,n){ int t=0; S[i].pb({0,0}); for(auto curh:H[i]) { t+=V[pi(i,curh)]; if(S[i].back().s != t)S[i].pb({curh,t}); } } FOR(i,0,n-1) { if(i){ for(auto h:H[i]) { chmax(dp[i][0][h], query1(h)); // chmax(dp[i][h][0], dp[i-1][y][1]); int s1=prev(upper_bound(all(S[i-1]), pi(h,oo)))->s; chmax(dp[i][0][h], s1 + query2(h)); //y<=h: chmax(dp[i][h][0], max{dp[i-1][y][0] - ss[i-1][y]} + ss[i-1][h]) //chmax(dp[i][h][0], max(dp[i-1][y][0], dp[i-1][y][1])); chmax(dp[i][0][h], query3(h)); // chmax(dp[i][h][0], dp[i-1][y][0]); int s2=prev(upper_bound(all(S[i]), pi(h,oo)))->s; chmax(dp[i][1][h], query4(h) - s2); //y>h: chmax(dp[i][h][1], max(dp[i-1][y][0], dp[i-1][y][1]) + ss[i][y]-ss[i][h]); chmax(ans, dp[i][0][h]); chmax(ans, dp[i][1][h]); //chmax(dp[i][h][1], max(dp[i-1][y][0], dp[i-1][y][1]) + cc); } } { S1=0;S3=0; for(auto y:H[i]) { chmax(S1, dp[i][1][y]); chmax(S3, dp[i][0][y]); } S2.clear(); S4.clear(); S2.pb({0,0}); for(auto y:H[i]) { db(y); db2(S[i][0].f,S[i][0].s); int sum = prev(upper_bound(all(S[i]),pi(y,oo)))->s; db(sum); int val=dp[i][0][y] - sum; if(val > S2.back().s) { S2.pb({y, val}); } } S4.pb({height, 0}); for(auto it=H[i].rbegin(); it!=H[i].rend(); it++){ int y=*it; int sum=prev(upper_bound(all(S[i+1]), pi(y,oo))) -> s; int val=max(dp[i][0][y], dp[i][1][y]) + sum; if(val > S4.back().s) { S4.pb({y, val}); } } reverse(all(S4)); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...