Submission #951871

#TimeUsernameProblemLanguageResultExecution timeMemory
951871Mohamed_Kachef06Fuel Station (NOI20_fuelstation)C++17
0 / 100
3041 ms18556 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void doWork(){ int n , d; cin >> n >> d; vector<array<int , 3>> v; vector<int> B(1 , 1e18); for (int i = 1 ; i <= n ; i++){ int x , a , b; cin >> x >> a >> b; v.push_back({x , a , b}); B.push_back(b); } sort(v.begin() , v.end()); sort(B.begin() , B.end()); int x[n+2] = {} , a[n+2] = {} , b[n+2] = {}; for (int i = 1 ; i <= n ; i++){ x[i] = v[i-1][0]; a[i] = v[i-1][1]; b[i] = v[i-1][2]; } x[n+1] = d; int ans = 1e18; for (int i = 0 ; i <= n ; i++){ // cout << B[i] << '\n' << '\n'; int mn = 0 , sum = 0 , temp = 0; for (int j = 1 ; j <= n+1 ; j++){ if (x[j] != x[j-1]) { sum += temp; temp = 0; } // cout << x[j] << ' ' << sum << '\n'; mn = min(mn , -x[j] + sum); if (b[j] <= B[i]) temp += a[j]; } //cout << '\n'; //cout << '\n'; if (-mn <= B[i]) ans = min(ans , -mn); } cout << ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); doWork(); }
#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...