QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726102#5417. Chat ProgramMoemi_WA 49ms8032kbC++202.8kb2024-11-08 21:37:332024-11-08 21:37:33

Judging History

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

  • [2024-11-08 21:37:33]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:8032kb
  • [2024-11-08 21:37:33]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <numeric>

#define sc_int(x) scanf("%d", &x)

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10, M = 5010, MOD = 1e9 + 7;
const int inf = 1e9;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<char, int> PCI;
typedef pair<string, string> PSS;

LL n, m, k, c, d;

void solve()
{
    cin >> n >> k >> m >> c >> d;

    vector<LL> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];

    auto check = [&](LL t)
    {
        vector<LL> cnt(n + 10);
        vector<LL> cnt2(n + 10);
        for(int i = 1; i <= n; i ++) 
        {
            cnt[i] = cnt[i - 1];
            if(a[i] >= t) cnt[i] ++;
        }
        for(int i = 1; i <= m; i ++)
        {
            if(a[i] >= t) cnt2[1] ++;
            else 
            {
                if(a[i] + (i - 1) * d + c >= t) cnt2[1] ++;
                if(a[i] + (i - 1) * d + c < t) continue;
                if(a[i] + c >= t) cnt2[i + 1] --;
                else 
                {
                    LL pos = (t - c - a[i]) / d;
                    if((t - c - a[i]) % d == 0) pos --;
                    if(i + (m - pos) <= i - m + 1) cnt2[i + (m - pos)] --;
                }
            }
        }
        
        LL sum = c + (m - 1) * d;
        for(int i = m + 1; i <= n; i ++)
        {
            if(a[i] >= t) cnt2[i - m + 1] ++;
            else 
            {
                if(a[i] + sum >= t) cnt2[i - m + 1] ++;
                if(a[i] + sum < t) continue;
                if(a[i] + c >= t) cnt2[i + 1] --;
                else 
                {
                    LL pos = (t - c - a[i]) / d;
                    if((t - c - a[i]) % d == 0) pos --;
                    if(i + (m - pos) <= i - m + 1) cnt2[i + (m - pos)] --;
                }
            }
        }

        LL ans = 0;
        for(int i = 1; i + m - 1 <= n; i ++)
        {
            cnt2[i] += cnt2[i - 1];
            ans = max(ans, cnt2[i] + cnt[n] - cnt[i + m - 1]);
        }
        return ans >= k;
    };

    LL l = 1, r = 1e18;
    while(l < r)
    {
        LL mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}


int main()
{
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --)
    {
        solve();
    }
}

详细

Test #1:

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

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: 3548kb

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: 3772kb

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: 49ms
memory: 8032kb

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'