QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685078 | #5417. Chat Program | Vegetog | WA | 50ms | 8332kb | C++20 | 1.7kb | 2024-10-28 17:29:34 | 2024-10-28 17:29:35 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "_my_utils.h"
#endif
#define int long long
using namespace std;
using ll = long long;
using PII = std::pair<int, int>;
constexpr ll INF = 2E18 + 10;
constexpr int N = 2E5 + 10;
int n, k, m, c, d;
int a[N];
int b[N], pr[N];
bool check(int x) {
for (int i = 1; i <= n; i++) {
a[i] = b[i];
pr[i] = 0;
}
for (int i = 1; i <= n; i++) {
if (a[i] >= x) {
pr[1]++;
pr[n + 1]--;
} else if (a[i] + c + d * (min(i, m) - 1) >= x) {
if (d == 0) {
pr[max(1LL, i - m + 1)]++;
pr[i + 1]--;
continue;
}
pr[max(1LL, i - m + 1)]++;
int mx = a[i] + c + d * (min(i, m) - 1);
int cnt = (mx - (x - 1) + d - 1) / d;
pr[min(n + 1, max(1LL, i - m + 1) + cnt - 1 + 1)]--;
}
}
int t = 0;
for (int i = 1; i + m - 1 <= n; i++) {
t += pr[i];
if (t >= k) {
return 1;
}
}
return 0;
}
void SINGLE_TEST() {
cin >> n >> k >> m >> c >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
int l = 1, r = INF;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int SAMPLES = 1;
// cin >> SAMPLES;
for (int CUR = 1; CUR <= SAMPLES; CUR++) {
SINGLE_TEST();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5708kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Wrong Answer
time: 50ms
memory: 8332kb
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1
result:
wrong answer 1st numbers differ - expected: '0', found: '1'