QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#730128#5417. Chat ProgramCalculateloveWA 51ms5376kbC++141.2kb2024-11-09 18:49:182024-11-09 18:49:19

Judging History

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

  • [2024-11-09 18:49:19]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:5376kb
  • [2024-11-09 18:49:18]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long s64;

const int N = 200100;

int n, k, m, c, d;
int a[N];

int S[N];

bool check(s64 mid) {
    for (int i = 1; i <= n; i ++) S[i] = 0;

    for (int i = 1; i <= n; i ++) {
        if (a[i] >= mid) { S[1] ++; S[n - m + 2] --; continue; }

        s64 x;
        if (d == 0) {
            if (mid - c - a[i] <= 0)
                x = 0;
            else
                x = m;
        } else {
            x = (mid - c - a[i]) / d;
            if (x < 0) x = 0;
        }

        if (x >= m) continue;
        if (i - x <= 0) continue;

        int l = std::max(1, i - m + 1), r = i - x;
        S[l] ++, S[r + 1] --;
    }

    for (int i = 1; i <= n; i ++) S[i] += S[i - 1];
    for (int i = 1; i <= n; i ++)
        if (S[i] >= k) return 1;
    
    return 0;
}

int main() {
    scanf("%d%d%d%d%d", &n, &k, &m, &c, &d);

    for (int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    
    s64 l = 0, r = 1000000000000000;
    while (l < r) {
        s64 mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid; else r = mid - 1;
    }

    printf("%lld\n", l);

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

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: 0ms
memory: 3904kb

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: 0ms
memory: 3844kb

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: 0
Accepted
time: 45ms
memory: 5376kb

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:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 51ms
memory: 5320kb

input:

200000 1 100000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:

100001999999999

result:

wrong answer 1st numbers differ - expected: '100001000000000', found: '100001999999999'