QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103310 | #6130. Plants vs. Zombies | evirir# | WA | 157ms | 4688kb | C++20 | 2.4kb | 2023-05-05 07:29:06 | 2023-05-05 07:29:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forn(i,a,b) for(int i = a; i < (b); i++)
#define fore(i,a,b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
void water_ij_until_i_near_target(ll target, const vector<ll> &a, vector<ll> &d, size_t i, size_t j, ll &m) {
if (d[i] >= target) return;
ll waters = (target - d[i] - 1) / a[i];
if (waters == 0) return;
// cout << "watered " << i << " and " << j << ", took " << (waters * 2) << " waters" << endl;
d[i] += waters * a[i];
d[j] += waters * a[j];
m -= 2 * waters;
}
bool canReach(ll target, const vector<ll> &a, ll n, ll m) {
// cout << "target: " << target << endl;
vector<ll> d = a;
m -= n;
forn(i, 0, n - 1) {
water_ij_until_i_near_target(target, a, d, i, i+1, m);
if (m < 0) return false;
}
water_ij_until_i_near_target(target, a, d, n - 1, n - 2, m);
int cur_run = 0;
forn(i, 0, n) {
if (d[i] < target) {
cur_run++;
} else if (cur_run) {
ll waters = 0;
if (i == n - 1) {
waters = cur_run;
} else {
waters = (cur_run + 1) / 2 * 2;
}
m -= waters;
// cout << "run from " << (i - cur_run) << " to " << (i - 1) << " took " << waters << endl;
cur_run = 0;
}
}
if (cur_run != 0) {
ll waters = (cur_run + 1) / 2 * 2;
// cout << "final run from " << (n - cur_run) << " to " << (n - 1) << " took " << waters << endl;
m -= waters;
}
// if (m >= 0) cout << "success" << endl;
return m >= 0;
}
void solve()
{
ll n, m;
cin >> n >> m;
vector<ll> a(n, 0);
forn(i,0,n) cin >> a[i];
if (m < n) {
cout << 0 << endl;
return;
}
ll left = 0;
ll right = (*max_element(all(a)) + n - 1) / n * m;
// cout << "right "<<right <<endl;
while (left < right) {
ll mid = left + (right - left + 1) / 2;
if (canReach(mid, a, n, m)) {
left = mid;
} else {
right = mid - 1;
}
}
cout << right << endl;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t; cin>>t;
forn(i,0,t) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3440kb
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: 157ms
memory: 4688kb
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:
0 0 4 6 20 3 2 14 1 4 0 4 2 6 0 2 24 3 30 10 0 2 3 0 0 2 6 0 1 6 24 28 1 4 3 0 4 10 6 4 1 5 0 2 0 7 30 2 0 0 16 8 0 30 2 30 4 2 0 0 2 0 2 0 5 2 0 0 0 0 5 0 4 6 28 0 0 21 3 0 2 4 0 0 14 4 6 1 0 5 12 3 8 0 4 0 10 12 5 6 1 6 12 0 725 0 17 132 676 588 110 0 163 5910826 1000000000000 16561021906
result:
wrong answer 91st numbers differ - expected: '14', found: '12'