Submission #1062112

#TimeUsernameProblemLanguageResultExecution timeMemory
1062112new_accCatfish Farm (IOI22_fish)C++17
100 / 100
185 ms29792 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=3e5+10; const int SS=1<<17; const int INFi=2e9; const ll INFl=1e13; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=1000696969; const ll p=70032301; const ull p2=913; const int L=20; vector<pair<int,int> > t[N]; struct tr{ ll seg[(SS<<1)+10]; void upd(int a,int b,ll x){ for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){ if(!(a&1)) seg[a+1]=max(seg[a+1],x); if(b&1) seg[b-1]=max(seg[b-1],x); } } ll Query(int a){ ll res=0; for(a+=SS;a>0;a>>=1) res=max(res,seg[a]); return res; } }; tr dp1,dp2; ll max_weights(int n,int m,vi x,vi y,vi w){ for(int i=1;i<=(SS<<1);i++) dp1.seg[i]=0,dp2.seg[i]=0; for(int i=0;i<m;i++) t[x[i]+1].push_back({y[i]+1,w[i]}); for(int i=1;i<=n;i++) sort(t[i].begin(),t[i].end()); ll sum=0; for(int i=1;i<=n;i++){ ll val=dp1.Query(n); dp1.upd(0,0,dp2.Query(1)); int pop=0; for(auto [u,c]:t[i]){ if(pop!=u-1) dp1.upd(pop+1,u-1,dp1.Query(pop)); dp1.upd(u,u,dp1.Query(u-1)+(ll)c); pop=u; sum+=(ll)c; } if(pop!=n) dp1.upd(pop+1,n,dp1.Query(pop)); dp1.upd(0,n,val); pop=n+1; reverse(t[i].begin(),t[i].end()); if(i==1) continue; for(auto [u,c]:t[i]){ if(pop!=u+1) dp2.upd(u+1,pop-1,dp2.Query(pop)); dp2.upd(u,u,dp2.Query(u+1)+(ll)c); pop=u; } if(pop!=1) dp2.upd(1,pop-1,dp2.Query(pop)); dp2.upd(1,n+1,val); } return dp2.Query(1); } /*int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int n,m; cin>>n>>m; vi x,y,w; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; x.push_back(a),y.push_back(b),w.push_back(c); } cout<<max_weights(n,m,x,y,w)<<"\n"; }*/
#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...