QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#447017#8780. Training, Round 2ucup-team3702RE 0ms0kbC++231.7kb2024-06-17 20:13:272024-06-17 20:13:28

Judging History

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

  • [2024-06-17 20:13:28]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-06-17 20:13:27]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 5e3 + 5;

int n, a, b, f[N][N];
std::set<int> S1[N], S2[N];
std::vector<std::pair<int, int>> upd;
int cnt;

int main () {
    std::cin >> n >> a >> b;
    f[0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            if (i or j) S1[i].insert(j);
            else S2[i].insert(j);

    for (int al, ar, bl, br, p = 1; p <= n; p++) {
        std::cin >> al >> ar >> bl >> br;
        upd.clear();
        for (int i = std::max(0, al - a); i <= std::min(p, ar - a); i++) {
            auto l = S2[i].lower_bound(std::max(0, bl - b));
            auto r = S2[i].upper_bound(std::min(p, br - b));
            if (l != S2[i].end()) {
                for (auto it = l; it != r; it++) {
                    if (S1[i + 1].find(*it) != S1[i + 1].end()) {
                        f[i + 1][*it] = 1, S1[i + 1].erase(*it),
                        upd.push_back(std::make_pair(i + 1, *it));
                        assert(++cnt <= n * n);
                    }
                    if (S1[i].find((*it) + 1) != S1[i].end()) {
                        f[i][(*it) + 1] = 1, S1[i].erase((*it) + 1),
                        upd.push_back(std::make_pair(i, (*it) + 1));
                        assert(++cnt <= n * n);
                    }       
                }
                S2[i].erase(l, r);
            }
            assert(++cnt <= n * n);
        }
        for (auto x : upd) {
            S2[x.first].insert(x.second);
            assert(++cnt <= n * n);
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            ans = std::max(ans, f[i][j] * (i + j));
    std::cout << ans << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3 0 0
0 1 0 1
1 1 0 1
1 1 1 1

output:


result: