Submission #1003561

#TimeUsernameProblemLanguageResultExecution timeMemory
1003561ThegeekKnight16Autobahn (COI21_autobahn)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, K, X; cin >> N >> K >> X; vector<tuple<int, int, int>> sweep; for (int i = 0; i < N; i++) { int L, T, R; cin >> L >> T >> R; T = min(L+T-1, R+1); sweep.emplace_back(L, 0, -1); sweep.emplace_back(T+1, 1, -1); sweep.emplace_back(R+1, 2, -1); sweep.emplace_back(T, 3, 3*i); sweep.emplace_back(T+X, 4, 3*i); sweep.emplace_back(R-X, 3, 3*i + 1); sweep.emplace_back(R, 4, 3*i + 1); sweep.emplace_back(L-1, 3, 3*i + 2); sweep.emplace_back(L+X-1, 4, 3*i + 2); } vector<int> possResp(3*N); sort(sweep.begin(), sweep.end()); int totPeople = 0, totPaying = 0, totPay = 0, lastX = 0, resp = 0; for (auto [x, type, id] : sweep) { totPay += (int)(totPeople >= K) * totPaying * (x - lastX); lastX = x; // cerr << "x: " << x << ", totPeople: " << totPeople << ", totPaying: " << totPaying << ", totPay: " << totPay << '\n'; if (type == 0) totPeople++; else if (type == 1) totPaying++; else if (type == 2) totPeople--, totPaying--; else if (type == 3) possResp[id] = totPay; else resp = max(resp, totPay - possResp[id]); } cout << resp << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...