제출 #1225532

#제출 시각아이디문제언어결과실행 시간메모리
1225532denislavNile (IOI24_nile)C++20
6 / 100
2095 ms7568 KiB
# include <iostream> # include <vector> # include <algorithm> # include <cassert> using namespace std; # include "nile.h" //# include "grader.cpp" const long long INF=1e18; const int MAX=1e5+11; int n; long long s; pair<int,long long> a[MAX]; struct segtree { long long tree[MAX*4]; void build(int v=1, int l=1, int r=n) { if(l==r) { tree[v]=0; return ; } int mid=(l+r)/2; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v]=max(tree[v*2],tree[v*2+1]); } void update(int pos, long long d, int v=1, int l=1, int r=n) { if(l==r) { tree[v]=max(tree[v],d); return ; } int mid=(l+r)/2; if(pos<=mid) update(pos,d,v*2,l,mid); else update(pos,d,v*2+1,mid+1,r); tree[v]=max(tree[v*2],tree[v*2+1]); } long long query(int le, int ri, int v=1, int l=1, int r=n) { if(ri<l or r<le) return 0; if(le<=l and r<=ri) return tree[v]; int mid=(l+r)/2; return max(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r)); } }tree; int lm[MAX]; long long dp[MAX]; long long calc(long long d) { int ptr=1; for(int i=1;i<=n;i++) { while(a[i].first-a[ptr].first>d) ptr++; lm[i]=ptr; } tree.build(); for(int i=1;i<=n;i++) dp[i]=0; for(int i=1;i<=n;i++) { //if(lm[i]!=i) dp[i]=max(dp[i],tree.query(lm[i],i-1)+a[i].second); if(lm[i]!=i) dp[i]=max(dp[i],dp[i-2]+a[i-1].second+a[i].second); dp[i]=max(dp[i],dp[i-1]); tree.update(i,dp[i-1]+a[i].second); } long long ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i]); return ans; } std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { n=W.size(); for(int i=0;i<n;i++) { a[i+1]={W[i],A[i]-B[i]}; s+=A[i]; } sort(a+1,a+n+1); vector<pair<long long,long long>> ans; long long from=1,res=calc(1); ans.push_back({from,res}); while(from!=1e9+1) { long long l=from,r=1e9,mx=l; while(l<=r) { long long mid=(l+r)/2; long long resp=calc(mid); if(resp==res) { l=mid+1; mx=mid; } else r=mid-1; } if(mx==1e9) break; from=mx+1; res=calc(from); ans.push_back({from,res}); if((int)ans.size()>n) assert(0); } //for(auto pa: ans) cout<<pa.first<<" "<<pa.second<<"\n"; vector<long long> Final; Final.resize(E.size()); for(int i=0;i<(int)E.size();i++) { int id=upper_bound(ans.begin(),ans.end(),make_pair((long long)E[i],INF))-ans.begin()-1; Final[i]=s-ans[id].second; } return Final; } /** 5 15 5 1 12 4 2 2 5 2 10 6 3 21 3 2 3 5 9 1 */
#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...