Submission #997087

#TimeUsernameProblemLanguageResultExecution timeMemory
997087LOLOLOFuel Station (NOI20_fuelstation)C++14
0 / 100
303 ms21676 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 3e5 + 10; vector < vector <int>> v; bool check(int r) { int l = 0, pr = 0; for (auto x : v) { int d = x[0] - pr; pr = x[0]; r -= d; l -= d; if (r < 0) return 0; l = max(l, 0); r = min(r + x[1], max(r, x[2] + x[1])); } return l <= r; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, d; cin >> n >> d; for (int i = 0; i < n; i++) { int x, a, b; cin >> x >> a >> b; v.pb({x, a, b}); } v.pb({d, 0, 0}); sort(all(v)); int l = 1, r = d, m, ans = 0; while (l <= r) { m = (l + r) / 2; if (check(m)) { ans = m; r = m - 1; } else { l = m + 1; } } cout << ans << '\n'; return 0; }
#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...