QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#501436 | #6130. Plants vs. Zombies | WTR2007# | WA | 81ms | 5364kb | C++20 | 1.4kb | 2024-08-02 18:28:53 | 2024-08-02 18:28:54 |
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 = 0; i < n; i++) {
if (i == n - 1) sum += 2 * max(d[i], d[i + 1]) - (d[i + 1] > d[i]);
else {
sum += 2 * d[i] + 1;
d[i + 1] = max(0ll, d[i + 1] - d[i] - 1);
}
if (sum > m) return false;
}
return true;
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
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: 81ms
memory: 5364kb
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 20 3 2 14 1 4 1 4 2 6 1 2 24 3 30 10 1 2 3 1 1 2 6 1 1 6 24 28 1 4 3 1 4 10 6 4 1 5 1 2 1 7 30 2 1 1 16 8 1 30 2 30 4 2 1 1 2 1 2 1 5 2 1 1 1 1 5 1 4 6 28 1 1 21 3 1 2 4 1 1 14 4 6 1 1 5 14 3 8 1 4 1 10 12 5 8 1 6 12 1 725 1 17 132 676 588 110 1 163 5910826 1000000000000 16561021906
result:
wrong answer 1st numbers differ - expected: '0', found: '1'