QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207993 | #7567. Joining Cats | cardinal_city# | WA | 1ms | 3544kb | C++23 | 1.8kb | 2023-10-09 02:36:32 | 2023-10-09 02:36:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b);
#define smn(a, b) a = min(a, b);
#define pb push_back
#define endl '\n'
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
mt19937 rng(time(0));
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vector<ll> w(n), s(k);
rep(i,0,n) cin >> w[i];
rep(i,0,k) cin >> s[i];
vector<ll> pfx(n+1);
rep(i,0,n) pfx[i+1] = pfx[i] + w[i];
auto bs_left = [&](int j, int l) { // find min i s.t. sum w_i + ... + w_j <= s_k
ll tot = pfx[j + 1] - s[l];
if (tot <= 0) { // s[k] >= sum w_0 through w_j
return 0;
}
int pos = lower_bound(pfx.begin(), pfx.end(), tot) - pfx.begin();
return pos;
};
auto bs_right = [&](int j, int l) { // find max i s.t. sum w_j + ... + w_i <= s_k
// cout << j << ", " << l << ", " << pfx[j] + s[l] << "\n";
int pos = upper_bound(pfx.begin(), pfx.end(), pfx[j] + s[l]) - pfx.begin();
return pos - 1;
};
vector save(n, vector<int>(n, k + 1));
for (int i = 0; i < n; i++) save[i][i] = 0;
function<bool(int, int, int)> dfs = [&](int i, int j, int l) {
if (save[i][j] <= l) return true;
if (l < 0) return false;
// cout << "solving case " << i << ", " << j << ", " << l << "\n";
int p1 = bs_left(j, l - 1);
// cout << "bs_left gives " << p1 - 1 << "\n";
int p2 = bs_right(i, l - 1);
// cout << "bs_right gives " << p2 << "\n";
if (p1 - 1 <= i || p2 >= j || dfs(i, p1 - 1, l - 1) || dfs(p2, j, l - 1)) {
save[i][j] = min(save[i][j], l);
return true;
}
return false;
};
cout << (dfs(0, n - 1, k) ? "Yes\n" : "No\n");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
input:
5 2 1 1 1 1 1 2 2
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3544kb
input:
6 7 3 2 1 1 2 3 2 2 2 2 2 2 2
output:
Yes
result:
wrong answer expected NO, found YES