QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #410407 | #6178. 区间子集问题 | A_programmer | Compile Error | / | / | C++17 | 3.8kb | 2024-05-13 23:21:05 | 2024-05-13 23:21:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct node { int l, r; } p[2005];
vector<int> g[2005];
stack<int> stk;
pii b[4005];
int n, size[2005];
ll dp[2005][2005][2][2];
ll tmp[2005][2][2];
void dfs(int u)
{
size[u] = 1;
if (!g[u].size())
{
dp[u][0][0][0] = dp[u][0][0][1] = dp[u][0][1][0] = p[u].r - p[u].l;
dp[u][0][1][1] = -inf;
return;
}
for (int v : g[u]) dfs(v);
dp[u][0][0][0] = 0;
int siz = g[u].size();
for (int id = 0; id < siz; id++)
{
int v = g[u][id];
for (int i = 0; i <= size[u] + size[v]; i++) tmp[i][0][0] = tmp[i][0][1] = -inf;
for (int j = 0; j <= size[u]; j++)
for (int k = 0; k < size[v]; k++)
{
tmp[j + k][0][0] = max(tmp[j + k][0][0], max(dp[u][j][0][0] + dp[v][k][0][0], dp[u][j][0][1] + dp[v][k][1][0]));
tmp[j + k][0][1] = max(tmp[j + k][0][1], max(dp[u][j][0][0] + dp[v][k][0][1], dp[u][j][0][1] + dp[v][k][1][1]));
}
size[u] += size[v];
if (id == siz - 1)
{
for (int j = 0; j <= size[u]; j++) tmp[j][0][1] += p[u].r - p[v].r;
for (int j = size[u]; j; j--) tmp[j][0][0] = max(tmp[j][0][0], tmp[j - 1][0][0] + p[u].r - p[v].r);
}
else
{
for (int j = size[u]; j; j--) tmp[j][0][1] = tmp[j - 1][0][1] + p[g[u][id + 1]].l - p[v].r;
tmp[0][0][1] = -inf;
}
for (int i = 1; i <= size[u]; i++) dp[u][i][0][0] = tmp[i][0][0], dp[u][i][0][1] = tmp[i][0][1];
}
for (int i = 0; i < size[u]; i++) dp[u][i][0][0] = dp[u][i + 1][0][0], dp[u][i][0][1] = dp[u][i + 1][0][1];
dp[u][0][1][1] = p[g[u][0]].l - p[u].l; size[u] = 1;
for (int id = 0; id < siz; id++)
{
int v = g[u][id];
for (int i = 0; i <= size[u] + size[v]; i++) tmp[i][1][0] = tmp[i][1][1] = -inf;
for (int j = 0; j <= size[u]; j++)
for (int k = 0; k <= size[v]; k++)
{
tmp[j + k][1][0] = max(tmp[j + k][1][0], max(dp[u][j][1][0] + dp[v][k][0][0], dp[u][j][1][1] + dp[v][k][1][0]));
tmp[j + k][1][1] = max(tmp[j + k][1][1], max(dp[u][j][1][0] + dp[v][k][0][1], dp[u][j][1][1] + dp[v][k][1][1]));
}
size[u] += size[v];
if (id == siz - 1)
{
for (int j = 0; j <= size[u]; j++) tmp[j][1][1] += p[u].r - p[v].r;
for (int j = size[u]; j; j--) tmp[j][1][0] = max(tmp[j][1][0], tmp[j - 1][1][0] + p[u].r - p[v].r);
}
else
{
for (int j = size[u]; j; j--) tmp[j][1][1] = tmp[j - 1][1][1] + p[g[u][id + 1]].l - p[v].r;
tmp[0][1][1] = -inf;
}
for (int i = 1; i <= size[u]; i++) dp[u][i][1][0] = tmp[i][1][0], dp[u][i][1][1] = tmp[i][1][1];
}
for (int i = 0; i < size[u]; i++) dp[u][i][0][0] = dp[u][i + 1][0][0], dp[u][i][0][1] = dp[u][i + 1][0][1];
// cout << u << " ---------------\n";
// for (int i = 0; i <= n; i++) cout << dp[u][i][0][0] << " " << dp[u][i][0][1] << " " << dp[u][i][1][0] << " " << dp[u][i][1][1] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i].l >> p[i].r;
b[2 * i - 1] = make_pair(p[i].l, i);
b[2 * i] = make_pair(p[i].r, i);
}
sort(b + 1, b + 2 * n + 1);
memset(dp, -0x3f, sizeof(dp));
ll ans = 0;
for (int i = 1; i <= 2 * n; i++)
{
int x = b[i].second;
if (stk.size() && stk.top() == x) stk.pop();
else
{
if (stk.size()) g[stk.top()].emplace_back(x);
stk.push(x);
}
if (!stk.size())
{
dfs(x);
ans += dp[x][0][0][0];
}
}
cout << ans;
return 0;
}
Details
answer.code: In function ‘void dfs(int)’:
answer.code:19:5: error: reference to ‘size’ is ambiguous
19 | size[u] = 1;
| ^~~~
In file included from /usr/include/c++/13/string:53,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from answer.code:1:
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:33:30: error: reference to ‘size’ is ambiguous
33 | for (int i = 0; i <= size[u] + size[v]; i++) tmp[i][0][0] = tmp[i][0][1] = -inf;
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:33:40: error: reference to ‘size’ is ambiguous
33 | for (int i = 0; i <= size[u] + size[v]; i++) tmp[i][0][0] = tmp[i][0][1] = -inf;
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:34:30: error: reference to ‘size’ is ambiguous
34 | for (int j = 0; j <= size[u]; j++)
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:35:33: error: reference to ‘size’ is ambiguous
35 | for (int k = 0; k < size[v]; k++)
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:40:9: error: reference to ‘size’ is ambiguous
40 | size[u] += size[v];
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:13:8: note: ‘int size [2005]’
13 | int n, size[2005];
| ^~~~
answer.code:40:20: error: reference to ‘size’ is ambiguous
40 | size[u] += size[v];
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::...