?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
270886057 |
Practice: jay_shreee_ram |
1866G - 6 | C++20 (GCC 13-64) | Time limit exceeded on test 20 | 3000 ms | 27928 KB | 2024-07-16 17:22:22 | 2024-07-16 17:22:22 |
#include<bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; // template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; // #pragma GCC optimize("Ofast") // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimization("unroll-loops") // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("fast-math") // #pragma GCC optimize("no-stack-protector") // #define ll __int128 // #define ll long long #define ll int #define f(i,a,b) for(ll i=a;i<b;i++) #define mod 1000000007 // #define mod 998244353 #define mp make_pair #define uniq(v) (v).erase(unique(all(v)),(v).end()) #define ff first #define ss second #define rf(i,a,b) for(ll i=a;i>=b;i--) #define sc(a) scanf("%lld",&a) #define pf printf #define sz(a) (int)(a.size()) #define psf push_front #define ppf pop_front #define ppb pop_back #define pb push_back #define pq priority_queue #define all(s) s.begin(),s.end() #define sp(a) setprecision(a) #define rz resize #define ld long double #define inf (ll)1e18 #define ub upper_bound #define lb lower_bound #define bs binary_search #define eb emplace_back const double pi = acos(-1); ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;} ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;} using namespace std; ll n,l,r,mid,ans; vector<ll> a,d; vector<multiset<pair<ll,ll> > > arr; void merge(multiset<pair<ll,ll> > &a, multiset<pair<ll,ll> > &b) { for(auto temp:b) a.insert(temp); } int main() { ios_base::sync_with_stdio(false); // freopen("xortransform.in","r",stdin); // freopen("xortransform.out","w",stdout); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int z=1; // cin>>z; f(ilu,1,z+1) { cin>>n; a.rz(n),d.rz(n),arr.rz(n); r=0,l=1e9; f(i,0,n) cin>>a[i],r=max(r,a[i]),l=min(l,a[i]); f(i,0,n) cin>>d[i]; f(i,0,n) { ll lid=max(0,i-d[i]),duri=i+d[i]; arr[lid].insert(mp(duri,a[i])); } while(l<=r) { mid=(l+r)/2; multiset<pair<ll,ll> > s; int flag=1; f(i,0,n) { merge(s,arr[i]); ll rem=mid; while(sz(s) && rem>0) { auto temp=(*s.begin()); ll duri=temp.ff,c=temp.ss; s.erase(s.begin()); if(duri<i){ flag=0; break; } ll sub=min(rem,c); rem-=sub,c-=sub; if(c) s.insert(mp(duri,c)); } } if((!sz(s)) && flag) ans=mid,r=mid-1; else l=mid+1; } cout<<ans; } }
?
?
?
?