QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726249 | #5417. Chat Program | Moemi_ | WA | 68ms | 7820kb | C++20 | 2.8kb | 2024-11-08 22:33:55 | 2024-11-08 22:33:56 |
Judging History
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 - 1 <= n - m + 1) cnt2[i + (m - pos) - 1] --;
}
}
}
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 - 1 <= n - m + 1) cnt2[i + m - pos - 1] --;
}
}
}
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: 3608kb
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: 3528kb
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: 3616kb
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: 68ms
memory: 7820kb
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'