# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
493761 |
2021-12-12T20:25:25 Z |
vulpes |
City (BOI06_city) |
C++17 |
|
1000 ms |
77776 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll K = 20007;
ll t, c[K];
bool cmp(const pair<ll,ll> &a, const pair<ll,ll> &b) {
return a.first * t + c[a.second] <
b.first * t + c[b.second];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> t >> k;
for (int i = 0; i < k; i++) {
cin >> c[i];
}
set<pair<ll,ll>, decltype(&cmp)> s(cmp);
ll r = 0; s.insert({0, 0});
map<int,bool> v;
while (n) {
pair<ll,ll> h = *s.begin();
s.erase(s.begin());
ll z = min(n, (h.first + 1) * 4); n -= z;
r += z * (h.first * t + c[h.second]);
if (h.second + 1 < k) {
s.insert({h.first, h.second + 1});
}
if (!v[h.first + 1]) {
v[h.first + 1] = true;
s.insert({h.first + 1, 0});
}
}
cout << r << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
697 ms |
77776 KB |
Output is correct |
3 |
Correct |
5 ms |
1356 KB |
Output is correct |
4 |
Execution timed out |
1093 ms |
320 KB |
Time limit exceeded |
5 |
Correct |
12 ms |
2380 KB |
Output is correct |
6 |
Correct |
6 ms |
1228 KB |
Output is correct |
7 |
Execution timed out |
1092 ms |
1536 KB |
Time limit exceeded |
8 |
Incorrect |
502 ms |
432 KB |
Output isn't correct |
9 |
Incorrect |
336 ms |
576 KB |
Output isn't correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |