QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685078#5417. Chat ProgramVegetogWA 50ms8332kbC++201.7kb2024-10-28 17:29:342024-10-28 17:29:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 17:29:35]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:8332kb
  • [2024-10-28 17:29:34]
  • 提交

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'