QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226824#7567. Joining Catsucup-team2307#WA 8ms107916kbC++142.0kb2023-10-26 16:51:232023-10-26 16:51:23

Judging History

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

  • [2023-10-26 16:51:23]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:107916kb
  • [2023-10-26 16:51:23]
  • 提交

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';
}

詳細信息

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