QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785615 | #5417. Chat Program | wlkmok369 | WA | 64ms | 7832kb | C++14 | 1.8kb | 2024-11-26 18:32:40 | 2024-11-26 18:32:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define PII pair<ll, ll>
const ll mod = 1e9 + 7;
const ll MAXN = 500005;
const ll base1 = 131;
const ll base2 = 127;
ll _ = 1, n, m, ans = 0, a[MAXN]; // f[MAXN];
ll c, k, d;
bool check(ll x)
{
vector<ll> f(n + 10, 0);
ll sum = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= x)
{
sum++;
}
}
if (sum >= x)
{
return 1;
}
for (int i = 1; i <= n; i++)
{
if (a[i] < x)
{
ll l = max(0ll, i - m + 1);
ll maxn = a[i] + c + d * (i - l);
if (maxn < x)
{
continue;
}
ll minn = a[i] + c;
ll p = 0;
if (d == 0)
{
p = 0;
}
else
{
p = max(0ll, (ll)ceil(1.0 * (x - minn) / d));
}
ll r = i - p;
f[l]++;
f[r + 1]--;
}
}
ll res = 0;
for (int i = 1; i <= n; i++)
{
f[i] += f[i - 1];
res = max(res, f[i]);
if (sum + res >= k)
{
return 1;
}
}
return 0;
}
void solve()
{
cin >> n >> k >> m >> c >> d;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
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 << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// cin>>_;
while (_--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3640kb
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: 3552kb
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: 64ms
memory: 7832kb
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'