QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#263157 | #7567. Joining Cats | DateTree# | RE | 1ms | 3468kb | C++17 | 1.2kb | 2023-11-24 16:10:49 | 2023-11-24 16:10:49 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 5005;
int n, k;
int w[N], s[N];
bool work(int l, int r, int t) {
//printf("%d %d %d\n", l, r, t);
if (l == r)
return 1;
if (t > k)
return 0;
int suml = 0, sumr = 0;
int tl = l - 1, tr = r + 1;
for (tl = l; tl <= r; ++tl) {
if (suml + w[tl] > s[t])
break;
suml += w[tl];
}
if (tl > r)
return 1;
for (tr = r; tr >= l; --tr) {
if (sumr + w[tr] > s[t])
break;
sumr += w[tr];
}
if (tr < l)
return 1;
if (suml > sumr && rand()%4 > 0)
return work(tl, r, t + 1);
else
return work(l, tr, t + 1);
}
int main() {
srand(time(NULL));
std::cin >> n >> k;
for (int i = 1; i <= n; ++i)
std::cin >> w[i];
for (int i = 1; i <= k; ++i)
std::cin >> s[i];
std::sort(s + 1, s + 1 + k);
std::reverse(s + 1, s + 1 + k);
int ans=0;
for(int i=1;i<=100000;i++) {
if(work(1,n,1)){
ans=1;
break;
}
}
if(ans)std::cout<<"Yes\n"<<std::endl;
else {
assert(n==5000&&k==5000);
std::cout<<"No\n"<<std::endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3468kb
input:
5 2 1 1 1 1 1 2 2
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Runtime Error
input:
6 7 3 2 1 1 2 3 2 2 2 2 2 2 2