QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667553#5417. Chat Program1ockhartWA 72ms6208kbC++201.5kb2024-10-23 00:07:582024-10-23 00:08:09

Judging History

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

  • [2024-10-23 00:08:09]
  • 评测
  • 测评结果:WA
  • 用时:72ms
  • 内存:6208kb
  • [2024-10-23 00:07:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

using ll = long long;
//using i128 = __int128_t;
#define endl "\n"
#define int long long
#define db cout << "db" << endl;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 5e5 + 10;
ll inf = 2e18;
void solve() {
    int n, k, m, c, d;
    cin >> n >> k >> m >> c >> d;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    }

    int l = 0, r = 1e18 + 10;
    while (l <= r) {
    	int mid = (l + r) >> 1, cnt = 0;
    	vector<int> s(n + 2, 0);
    	for (int i = 1; i <= n; i++) {
    		cnt += (a[i] >= mid);
    	}
    	for (int i = 1; i <= n; i++) {
    		if (a[i] >= mid) {
    			continue;
    		}
    		int x;
    		if (!d) {
    			x = 0;
    			x = (a[i] + c >= mid ? 0 : 1e15);
    		} else {
    			x = (mid - a[i] - c) / d; 
    		}

    		int p1 = max(i - x + 1, 0LL), p2 = max(i - m + 1, 0LL);
    		p1 = max(p1, p2);
    		s[p1]--;
    		s[p2]++;
    	}
    	int mx = 0, res = 0;
    	for (int i = 0; i <= n; i++) {
    		res += s[i];
    		mx = max(mx, res);
    	}
    	if (mx + cnt >= k) {
    		l = mid + 1;
    	} else {
    		r = mid - 1;
    	}
    }
    cout << r << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int q = 1;
    //cin >> q;
    while (q --) {
        solve();
    }
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 59ms
memory: 6208kb

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: 72ms
memory: 6200kb

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'