Submission #1067040

#TimeUsernameProblemLanguageResultExecution timeMemory
1067040epicci23Catfish Farm (IOI22_fish)C++17
9 / 100
450 ms76748 KiB
#include "bits/stdc++.h" #include "fish.h" //#define int64_t long long #define all(v) v.begin() , v.end() #define sz(a) (int64_t)a.size() using namespace std; const int64_t INF = 1e15; long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){ int64_t n,m,ans=0; n=N,m=M; vector<array<int64_t,3>> ar(m); for(int64_t i=0;i<m;i++){ ar[i][0]=X[i]; ar[i][1]=Y[i]; ar[i][2]=W[i]; ar[i][0]++; } vector<int64_t> consider[n+5]; vector<array<int64_t,2>> pre[n+5]; vector<array<int64_t,2>> fish[n+5]; for(int64_t i=0;i<m;i++){ if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]); if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]); } for(int64_t i=0;i<=n;i++){ consider[i].push_back(0); sort(all(consider[i])); consider[i].erase(unique(all(consider[i])),consider[i].end()); } for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]}); for(int64_t i=1;i<=n;i++){ fish[i].push_back({0,0}); sort(all(fish[i])); int64_t cur=0; for(auto x:fish[i]){ cur+=x[1]; pre[i].push_back({x[0],cur}); } } vector<int64_t> dp[n+5][2]; for(int64_t i=0;i<=n;i++){ dp[i][0].assign(sz(consider[i]),0); dp[i][1].assign(sz(consider[i]),0); } auto get_sum=[&](int64_t i,int64_t j)->int64_t{ if(i<1 || i>n) return 0; array<int64_t,2> bs={j+1,-1}; int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin(); if(it>0) return pre[i][it-1][1]; return 0; }; for(int64_t i=1;i<=n;i++){ // calc increasing dp vector<array<int64_t,2>> v; int64_t cur=0; for(int64_t j=0;j<sz(dp[i-1][0]);j++){ cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j])); v.push_back({consider[i-1][j],cur}); } auto get_val=[&](int64_t u,int64_t t)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(v),bs)-v.begin(); if(it-t>=0 && it-t<sz(v)) return v[it-t][1]; return -INF; }; for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; int64_t val=get_sum(i-1,u)+get_val(u,1); dp[i][0][j]=max(dp[i][0][j],val); } // calc decrasing dp v.clear(); cur=0; for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){ cur=max(cur,dp[i-1][1][j]); v.push_back({consider[i-1][j],cur}); } reverse(all(v)); for(int64_t j=0;j<sz(dp[i][1]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u)); } if(i>=2){ // new block vector<array<int64_t,2>> arka[2]; cur=0; for(int64_t j=0;j<sz(consider[i-2]);j++){ int64_t u=consider[i-2][j]; cur=max(cur,dp[i-2][0][j]); cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u)); arka[0].push_back({u,cur}); } cur=0; for(int64_t j=sz(consider[i-2])-1;j>=0;j--){ int64_t u=consider[i-2][j]; cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u)); cur=max(cur,dp[i-2][1][j]); arka[1].push_back({u,cur}); } reverse(all(arka[1])); auto get_kucuk=[&](int64_t u)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin(); if(it>0) return arka[0][it-1][1]; return -INF; }; auto get_buyuk=[&](int64_t u)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin(); if(it<sz(arka[1])) return arka[1][it][1]; return -INF; }; for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][0][j]=max(dp[i][0][j],get_buyuk(u)); dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u)); } for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u)); dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u)); } } // inc to dec v.clear(); cur=0; //cout << "kur: " << '\n'; for(int64_t j=sz(consider[i-1])-1;j>=0;j--){ int64_t u=consider[i-1][j]; //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n'; cur=max(cur,dp[i-1][0][j]+get_sum(i,u)); v.push_back({u,cur}); } reverse(all(v)); for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u)); //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n'; //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n'; //cout << dp[i][1][j] << '\n'; } for(int64_t j=0;j<sz(consider[i]);j++){ //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n'; //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n'; ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j])); ans=max(ans,dp[i][1][j]); } } return ans; } /*void _(){ int64_t n,m,ans=0; cin >> n >> m; vector<array<int64_t,3>> ar(m); for(int64_t i=0;i<m;i++){ cin >> ar[i][0] >> ar[i][1] >> ar[i][2]; ar[i][0]++; } vector<int64_t> consider[n+5]; vector<array<int64_t,2>> pre[n+5]; vector<array<int64_t,2>> fish[n+5]; for(int64_t i=0;i<m;i++){ if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]); if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]); } for(int64_t i=0;i<=n;i++){ consider[i].push_back(0); sort(all(consider[i])); consider[i].erase(unique(all(consider[i])),consider[i].end()); } for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]}); for(int64_t i=1;i<=n;i++){ fish[i].push_back({0,0}); sort(all(fish[i])); int64_t cur=0; for(auto x:fish[i]){ cur+=x[1]; pre[i].push_back({x[0],cur}); } } vector<int64_t> dp[n+5][2]; for(int64_t i=0;i<=n;i++){ dp[i][0].assign(sz(consider[i]),0); dp[i][1].assign(sz(consider[i]),0); } auto get_sum=[&](int64_t i,int64_t j)->int64_t{ if(i<1 || i>n) return 0; array<int64_t,2> bs={j+1,-1}; int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin(); if(it>0) return pre[i][it-1][1]; return 0; }; for(int64_t i=1;i<=n;i++){ // calc increasing dp vector<array<int64_t,2>> v; int64_t cur=0; for(int64_t j=0;j<sz(dp[i-1][0]);j++){ cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j])); v.push_back({consider[i-1][j],cur}); } auto get_val=[&](int64_t u,int64_t t)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(v),bs)-v.begin(); if(it-t>=0 && it-t<sz(v)) return v[it-t][1]; return -INF; }; for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; int64_t val=get_sum(i-1,u)+get_val(u,1); dp[i][0][j]=max(dp[i][0][j],val); //cout << "hm0: " << i << ' ' << j << ' ' << u << '\n'; //cout << dp[i][0][j] << '\n'; } // calc decrasing dp v.clear(); cur=0; for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){ cur=max(cur,dp[i-1][1][j]); v.push_back({consider[i-1][j],cur}); } reverse(all(v)); for(int64_t j=0;j<sz(dp[i][1]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u)); //cout << "hm1: " << i << ' ' << j << ' ' << u << '\n'; //cout << dp[i][1][j] << '\n'; } if(i>=2){ // new block vector<array<int64_t,2>> arka[2]; cur=0; for(int64_t j=0;j<sz(consider[i-2]);j++){ int64_t u=consider[i-2][j]; cur=max(cur,dp[i-2][0][j]); cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u)); arka[0].push_back({u,cur}); } cur=0; for(int64_t j=sz(consider[i-2])-1;j>=0;j--){ int64_t u=consider[i-2][j]; cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u)); cur=max(cur,dp[i-2][1][j]); arka[1].push_back({u,cur}); } reverse(all(arka[1])); auto get_kucuk=[&](int64_t u)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin(); if(it>0) return arka[0][it-1][1]; return -INF; }; auto get_buyuk=[&](int64_t u)->int64_t{ array<int64_t,2> bs={u+1,-1}; int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin(); if(it<sz(arka[1])) return arka[1][it][1]; return -INF; }; for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][0][j]=max(dp[i][0][j],get_buyuk(u)); dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u)); //cout << "b0: " << i << ' ' << j << ' ' << u << '\n'; //cout << dp[i][0][j] << '\n'; } for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u)); dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u)); //cout << "b1: " << i << ' ' << j << ' ' << u << '\n'; //cout << dp[i][1][j] << '\n'; } } // inc to dec v.clear(); cur=0; //cout << "kur: " << '\n'; for(int64_t j=sz(consider[i-1])-1;j>=0;j--){ int64_t u=consider[i-1][j]; //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n'; cur=max(cur,dp[i-1][0][j]+get_sum(i,u)); v.push_back({u,cur}); } reverse(all(v)); for(int64_t j=0;j<sz(consider[i]);j++){ int64_t u=consider[i][j]; dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u)); //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n'; //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n'; //cout << dp[i][1][j] << '\n'; } for(int64_t j=0;j<sz(consider[i]);j++){ //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n'; //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n'; ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j])); ans=max(ans,dp[i][1][j]); } } cout << ans << '\n'; } int64_t32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int64_t tc=1;//cin >> tc; while(tc--) _(); return 0; }*/
#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...