| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 599569 |
2022-07-19T15:37:11 Z |
Pety |
Autobahn (COI21_autobahn) |
C++14 |
|
254 ms |
27048 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
ll n, k, x;
map<ll, pair<ll, ll>>mp;
struct llervals {
ll l, r, cost;
bool operator < (const llervals other) {
return l < other.l;
}
} v[400002];
long long s[400002];
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k >> x;
for (ll i = 1; i <= n; i++) {
ll a, b,c;
cin >> a >> b >> c;
if (a + b - 1 < c) {
mp[a + b].second++;
mp[c + 1].second--;
}
mp[a].first++;
mp[c + 1].first--;
}
pair<ll, ll>sum;
ll last = 0;
ll nr = 0;
for (auto it2 : mp) {
if (sum.first >= k && sum.second) {
v[++nr] = {last, it2.first-1, sum.second};
}
auto it = it2.second;
sum.first += it.first;
sum.second += it.second;
last = it2.first;
}
sort(v + 1,v + nr + 1);
ll ans = 0;
for (ll i = 1; i <= nr; i++) {
s[i] = s[i - 1] + 1ll * (v[i].r - v[i].l + 1) * v[i].cost;
}
for (ll i = 1; i <= nr; i++) {
ll idk = i, st = i, dr = nr;
while (st <= dr) {
ll mij = (st + dr) / 2;
if (v[mij].l <= v[i].l + x - 1) {
idk = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
ll val = s[idk] - s[i - 1];
if (v[i].l + x - 1 <= v[idk].r)
val -= 1ll * (v[idk].r - v[i].l - x + 1) * v[idk].cost;
ans = max(ans, val);
}
for (ll i = 1; i <= nr; i++) {
ll idk = 1, st = 1, dr = i;
while (st <= dr) {
ll mij = (st + dr) / 2;
if (v[mij].r >= v[i].r - x + 1) {
idk = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
ll val = s[i] - s[idk - 1];
if (v[i].r - x + 1 >= v[idk].l)
val -= 1ll * (v[i].r - x + 1 - v[idk].l) * v[idk].cost;
ans = max(ans, val);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
243 ms |
24340 KB |
Output is correct |
| 22 |
Correct |
254 ms |
24212 KB |
Output is correct |
| 23 |
Correct |
239 ms |
26956 KB |
Output is correct |
| 24 |
Correct |
250 ms |
27048 KB |
Output is correct |
| 25 |
Correct |
245 ms |
26884 KB |
Output is correct |
| 26 |
Correct |
234 ms |
26768 KB |
Output is correct |
| 27 |
Correct |
254 ms |
26868 KB |
Output is correct |
| 28 |
Correct |
233 ms |
26924 KB |
Output is correct |
| 29 |
Correct |
233 ms |
26984 KB |
Output is correct |
