QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263157#7567. Joining CatsDateTree#RE 1ms3468kbC++171.2kb2023-11-24 16:10:492023-11-24 16:10:49

Judging History

你现在查看的是最新测评结果

  • [2023-11-24 16:10:49]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3468kb
  • [2023-11-24 16:10:49]
  • 提交

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

output:


result: