QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736363 | #6564. Frequent Flier | blackpanther9229 | AC ✓ | 14ms | 7016kb | C++14 | 1.2kb | 2024-11-12 10:27:53 | 2024-11-12 10:27:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 210000, M = 2100000;
int n, m;
long long k;
long long a[N];
long long b[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
long long cur_sum = 0;
deque<int> q;
for (int i = 1; i <= n + m; i ++) {
while (!q.empty() && q.front() <= i - m) {
q.pop_front();
}
if (i - m > 0) {
cur_sum -= b[i - m];
}
if (i <= n) {
q.push_back(i);
}
while (!q.empty() && cur_sum < k) {
int j = q.back();
if ((cur_sum + a[j] - b[j]) >= k) {
b[j] += (k - cur_sum);
cur_sum = k;
}
else {
cur_sum += (a[j] - b[j]);
b[j] = a[j];
}
if (b[j] == a[j]) q.pop_back();
}
}
long long ans = 0;
for (int i = 1; i <= n; i ++) {
//cout << i << " : " << b[i] << "\n";
ans += b[i];
}
cout << ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
8 3 2 3 1 4 1 5 9 2 6
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 14ms
memory: 5760kb
input:
200000 2467 999931035 182548858 69876218 33328350 919486767 739850600 948199964 392292320 39077742 366752074 917496841 246661698 37219034 56677740 188278971 965701828 28059790 13200243 825730775 542597589 320715170 939054378 470563899 914247467 990100491 290827128 903662394 611104879 18631185 412134...
output:
82994275905
result:
ok single line: '82994275905'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 200000 999959273 1255319
output:
1255319
result:
ok single line: '1255319'
Test #4:
score: 0
Accepted
time: 14ms
memory: 7016kb
input:
200000 118880 996878327 993340390 999483057 808153702 337349872 863222189 7495963 995920883 12950768 958082368 993215196 967152406 1388062 949959944 836952150 964071667 5291 139115263 958470154 51295691 175385 925242139 995685554 10895812 12563 55482 479983443 42805 996241239 6228013 302633329 10331...
output:
2990634981
result:
ok single line: '2990634981'
Test #5:
score: 0
Accepted
time: 11ms
memory: 6680kb
input:
200000 15 44049967 999927791 29351 999894087 687373343 518282902 19725626 452930 6701 999697321 27032796 5498 259987 999999980 485673990 805879 315651507 166801295 189865616 999910671 6203805 978801777 41916529 942904087 997589912 17146790 922137016 444882952 999884603 999926345 938979650 18597283 9...
output:
598769574112
result:
ok single line: '598769574112'