QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#501328 | #6130. Plants vs. Zombies | WTR2007# | WA | 70ms | 5316kb | C++20 | 1.2kb | 2024-08-02 16:48:23 | 2024-08-02 16:48:23 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define MULT_TEST 1
using namespace std;
typedef long double ldb;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 100005;
int n, m, a[N], d[N];
inline int read() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
w = (w << 1) + (w << 3) + ch - 48;
ch = getchar();
}
return w * f;
}
inline bool Check(int x) {
int sum = 0;
d[0] = d[n + 1] = 0;
for (int i = 1; i <= n; i++) d[i] = (x + a[i] - 1) / a[i];
for (int i = 1; i <= n; i++)
sum += max(0ll, d[i] - d[i - 1] - d[i + 1]) + d[i];
return sum <= m;
}
inline void Solve() {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
int l = 1, r = 1E18;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (Check(mid)) l = mid;
else r = mid - 1;
}
printf("%lld\n", l);
}
signed main() {
int _ = 1;
#if MULT_TEST
_ = read();
#endif
while (_--) Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
2 4 8 3 2 6 6 3 9 10 10 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #2:
score: -100
Wrong Answer
time: 70ms
memory: 5316kb
input:
116 4 0 3 2 6 6 4 1 3 2 6 6 10 19 10 2 8 4 2 4 9 3 3 3 4 8 3 9 3 6 2 19 2 10 11 15 3 1 1 4 3 7 10 8 6 7 10 10 14 8 7 1 1 10 9 2 8 10 7 2 13 2 3 10 10 8 1 6 6 9 4 7 1 8 8 7 14 6 7 4 5 3 1 3 11 6 8 1 10 9 7 2 6 6 1 3 9 4 10 6 1 3 8 7 7 10 6 2 10 4 7 2 5 11 9 10 5 9 2 9 1 2 4 8 6 2 8 8 1 6 4 5 7 2 9 8 ...
output:
1 1 4 6 18 3 2 12 1 4 1 4 2 6 1 4 24 3 35 12 1 2 4 1 1 2 6 1 2 6 24 28 1 4 3 1 4 10 6 4 1 5 1 2 1 7 32 3 1 1 16 8 1 30 3 25 4 2 1 1 2 1 2 1 5 2 1 1 1 1 5 1 5 4 28 1 1 24 4 1 2 4 1 1 14 4 6 1 1 5 14 3 9 1 4 1 12 12 6 8 1 6 9 1 780 1 19 147 720 675 120 1 173 70067381857739449 1000000000000 74872380575...
result:
wrong answer 1st numbers differ - expected: '0', found: '1'