Submission #1023423

#TimeUsernameProblemLanguageResultExecution timeMemory
1023423hasan2006Divide and conquer (IZhO14_divide)C++17
100 / 100
24 ms6256 KiB
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e5 + 9 , mod = 1e9 + 7; ll d[N] , dp[N] , A[N] , B[N] , C[N]; void solve() { ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ; cin>>n; for(i = 1; i <= n; i++){ dp[i] = dp[i + 1] = -1e18; cin>>A[i]>>C[i]>>B[i]; B[i] += B[i - 1] , C[i] += C[i - 1]; } for(i = n; i >= 1; i--) dp[i] = max(dp[i + 1] , B[i] - A[i]); for(i = 1; i <= n; i++){ l = i , r= n; while(l != r){ m = (l + r + 1) / 2; if(dp[m] >= (B[i - 1] - A[i])) l = m; else r = m - 1; } mx = max(mx , C[l] - C[i - 1]); } cout<<mx<<"\n"; } int main(){ TL; /* #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ int t = 1; // cin>>t; while(t--) { solve(); } } // Author : حسن

Compilation message (stderr)

divide.cpp: In function 'void solve()':
divide.cpp:26:12: warning: unused variable 'q' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
divide.cpp:26:20: warning: unused variable 'j' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
divide.cpp:26:30: warning: unused variable 'x' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
divide.cpp:26:34: warning: unused variable 'y' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
divide.cpp:26:38: warning: unused variable 's' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
divide.cpp:26:46: warning: unused variable 'f' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
divide.cpp:26:50: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                  ^
divide.cpp:26:58: warning: unused variable 'mn' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...