QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667619#5417. Chat Program1ockhartWA 66ms6260kbC++201.5kb2024-10-23 00:53:512024-10-23 00:54:04

Judging History

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

  • [2024-10-23 00:54:04]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:6260kb
  • [2024-10-23 00:53:51]
  • 提交

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;
    	vector<int> s(n + 2, 0);
    	for (int i = 1; i <= n; i++) {
    		if (a[i] >= mid) {
    			s[0]++;
    			continue;
    		}
    		int x;
    		if (!d) {
    			x = (a[i] + c >= mid ? 0 : 1e15);
    		} else {
    			int dis = (mid - a[i] - c);
    			x = (dis <= 0 ? 0 : dis % d + (dis % d != 0));
    			//x = ((a[i] + c >= mid ? 0 : mid - a[i] - c + d - 1) / 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 >= 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: 3600kb

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

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

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: 54ms
memory: 6180kb

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: 66ms
memory: 6260kb

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:

998046875000099998

result:

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