QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#447017 | #8780. Training, Round 2 | ucup-team3702 | RE | 0ms | 0kb | C++23 | 1.7kb | 2024-06-17 20:13:27 | 2024-06-17 20:13:28 |
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