Submission #1051945

#TimeUsernameProblemLanguageResultExecution timeMemory
1051945vjudge1Divide and conquer (IZhO14_divide)C++17
48 / 100
12 ms6816 KiB
#include <bits/stdc++.h> using namespace std; #define SPEED ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define str string #define pb push_back #define pf push_front #define nl "\n" #define ll long long #define int long long #define all(v) (v).begin() , (v).end() #define rall(v) (v).rbegin(), (v).rend() #define ff first #define ss second #define len(a) a.size() #define pii pair<int,int> const int N = 3e6 + 1; const ll md = 998244353; const ll mod = 1e9 + 7; const ll mega = 1e6 + 3; const ll inf = 100100; int x[N] , g[N] , d[N] , pref[N] , pref2[N] ,n , ans , mx; void add(int l){ ans += d[l]; } void del(int l){ ans -= d[l]; } void solve() { cin >> n; for(int i = 1; i <= n; ++i){ cin >> x[i] >> g[i] >> d[i]; pref[i] = pref[i - 1] + d[i]; pref2[i] = pref2[i - 1] + g[i]; } int mx = 0; if(n <= 5000){ for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ if(x[j] - x[i] <= pref[j] - pref[i - 1]){ mx = max(mx , pref2[j] - pref2[i - 1]); } } } cout << mx; } else if(n <= 5000){ for(int i = 1; i <= n; ++i){ int l = i , r = n; while(l <= r){ int m = (l + r) / 2; if(pref[m] - pref[i - 1] >= x[m] - x[i]){ l = m + 1; mx = max(mx , pref2[m] - pref2[i - 1]); } else{ r = m - 1; } } } cout << mx; } } signed main() { SPEED; int t = 1; // cin >> t; while (t--) { solve(); } // #ifndef ONLINE_JUDGE // cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; // #endif // return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...