Submission #1051931

#TimeUsernameProblemLanguageResultExecution timeMemory
1051931vjudge1Divide and conquer (IZhO14_divide)C++17
0 / 100
1 ms348 KiB
/* ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░ ░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░ ░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░ ░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░ ░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░ ░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░ ░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ */ // skibidi rizz #include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie() #define ll long long #define ull unsigned long long #define pb push_back #define endl "\n" #define int ll #define F first #define S second #define db double #define ld long double #define short unsigned short #define pii pair<int,int> using namespace std; const ll inf = 1e11,MOD=998244353,N=1e5+10,MN=1e9+7,lim=1e6; const long db Pie=acos(-1); //...and justice for all int binpow(int a,int p); struct mine{ int x,g,d; }; mine a[N]; int n; int ans=0; void rec(int l,int r){ if(l==r){ ans=max(ans,a[l].g); return ; } int m=(l+r)/2; rec(l,m); rec(m+1,r); int curg=0,cure=0; vector<pair<int,int>>v; for(int i=m+1;i<=r;i++){ v.pb({a[i].d-(a[i].x-a[m+1].x),a[i].g}); } sort(v.begin(),v.end()); vector<int>suf(v.size()+1,-inf); for(int i=v.size()-1;i>=0;i--){ suf[i]=max(suf[i+1],v[i].S); } for(int i=m;i>=l;i--){ cure+=a[i].d-(a[i+1].x-a[i].x); curg+=a[i].g; int lx=0,rx=v.size()-1; int res=-1; while(lx<=rx){ int mid=(lx+rx)/2; if(-cure<=v[mid].F){ lx=mid+1; res=mid; } else{ rx=mid-1; } } if(res!=-1){ ans=max(ans,suf[res]); } } } const void solve(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i].x>>a[i].g>>a[i].d; } rec(0,n-1); cout<<ans<<endl; } main() { srand(time(NULL)); IOS; //freopen("c oins.in", "r", stdin); //freopen("coins.out", "w", stdout); int UwU=1; // cin>>UwU; for(int i=1;i<=UwU;i++) { // cout<<"Case "<<i<<": "; solve(); // cout<<endl; } cout<<fixed<<setprecision(10); cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; } // int binmul(int a,int b){} int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

Compilation message (stderr)

divide.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...