QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226824 | #7567. Joining Cats | ucup-team2307# | WA | 8ms | 107916kb | C++14 | 2.0kb | 2023-10-26 16:51:23 | 2023-10-26 16:51:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
using ll = long long;
const int N = 5050;
int vis[N][N], nxt[N][N];
// vector<ll> L[N], R[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<int> a(n), b(k);
for(auto &i : a) cin >> i;
for(auto &i : b) cin >> i;
memset(vis, -1, sizeof vis);
queue<array<int, 2>> q[N];
auto add = [&](int l, int r, int d) {
if(vis[l][r] == -1) {
vis[l][r] = d;
q[d].push({l, r});
} else {
assert(vis[l][r] <= d);
}
};
for(int i = 0; i < n; i++) {
nxt[i][k] = k;
for(int j = k;j--;) {
nxt[i][j] = b[j] >= a[i] ? j : nxt[i][j + 1];
}
}
vector<ll> suf { 0 }, pref { 0 };
for(int i = 0; i < n; i++) pref.push_back(pref.back() + a[i]);
for(int i = n; i--;) suf.push_back(suf.back() + a[i]);
suf.erase(suf.begin()); reverse(all(suf));
pref.erase(pref.begin());
for(int i = 0; i < n; i++) add(i, i, 0);
for(int D = 0; D < k; D++)
while(!q[D].empty()) {
auto [x, y] = q[D].front();
q[D].pop();
int d = vis[x][y];
if(d < k)
d = min(x ? nxt[x - 1][d] : k, y + 1 < n ? nxt[y + 1][d] : k);
if(d < k) {
int goL = 0;//upper_bound(all(L[x]), b[d]) - L[x].begin();
for(int z = 1<<14; z>>=1;)
if(x - goL - z >= 0 && suf[x - goL - z] - suf[x] <= b[d])
goL += z;
// goL++;
int goR = 0;//upper_bound(all(R[y]), b[d]) - R[y].begin();
for(int z = 1<<14; z>>=1;)
if(y + goR + z < n && pref[y + goR + z] - pref[x] <= b[d])
goR += z;
// goR++;
// cout << x << " " << y << " " << goL << " " << goR << endl;
add(x - goL, y, d + 1);
add(x, y + goR, d + 1);
}
}
cout << (vis[0][n - 1] == -1 ? "No" : "Yes") << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 107584kb
input:
5 2 1 1 1 1 1 2 2
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 7ms
memory: 107916kb
input:
6 7 3 2 1 1 2 3 2 2 2 2 2 2 2
output:
No
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 8ms
memory: 106848kb
input:
7 4 1 2 3 4 3 2 1 3 3 3 3
output:
No
result:
wrong answer expected YES, found NO