#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<pair<int, int>>> g(2*n);
vector<int> s(2*n);
int S = 0;
for (int i = 0; i < 2*n; ++i) {
int l, r;
cin >> l >> r >> s[i];
S += s[i];
--l;
r += n-1;
g[l].eb(mp(r, i));
g[r].eb(mp(l, i));
}
vector<int> last(2*n), st(2*n);
for (int i = 0; i < 2*n; ++i) last[i] = ssize(g[i])-1;
for (int i = 0; i < 2*n; ++i) st[i] = ssize(g[i]);
vector<bool> off(2*n);
int sum = 0;
for (int i = 0; i < 2*n; ++i) {
int j = i;
while (st[j] == 1) {
while (off[g[j][last[j]].se]) --last[j];
auto [v, idx] = g[j][last[j]];
off[idx] = true;
sum += s[idx] * (j < n ? 1 : -1);
--st[j]; --st[v];
j = v;
}
}
for (int i = 0; i < 2*n; ++i) {
sort(all(g[i]), [&](pair<int, int> a, pair<int, int> b) {
return off[a.se] < off[b.se];
});
auto l = g[i].begin();
while (l != g[i].end() && !off[(*l).se]) l++;
g[i].erase(l, g[i].end());
}
vector<bool> odw(2*n);
vector<int> cnt(40 * n + 2);
for (int i = 0; i < 2*n; ++i) {
if (ssize(g[i]) == 0) continue;
int j = i;
int prev = -1;
int x = 0;
while (!odw[j]) {
odw[j] = true;
pair<int, int> nxt = (prev == g[j][0].fi ? g[j][1] : g[j][0]);
x += s[nxt.se] * (j < n ? 1 : -1);
prev = j;
j = nxt.fi;
}
if (prev != -1) {
x = abs(x);
cnt[2*x]++;
sum -= x;
}
}
#ifndef DEBUG
constexpr int SIZE = 1200005;
#else
constexpr int SIZE = 20;
#endif
debug(sum);
bitset<SIZE> b;
debug(cnt);
b[0] = true;
for (int i = 1; i < ssize(cnt); ++i) {
while (cnt[i] >= 3 && 2*i < ssize(cnt)) {
cnt[2*i]++;
cnt[i] -= 2;
}
for (int j = 1; j <= cnt[i]; ++j) b |= (b<<i);
}
debug(b);
for (int x = 0; x < SIZE; ++x) {
if (b[x] && abs(sum+x) <= k) {
cout << "YES \n";
return 0;
}
}
cout << "NO \n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
2 ms |
860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
1 ms |
860 KB |
Output is correct |
| 16 |
Correct |
1 ms |
860 KB |
Output is correct |
| 17 |
Correct |
1 ms |
860 KB |
Output is correct |
| 18 |
Correct |
1 ms |
860 KB |
Output is correct |
| 19 |
Correct |
1 ms |
860 KB |
Output is correct |
| 20 |
Correct |
1 ms |
860 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
2 ms |
860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
1 ms |
860 KB |
Output is correct |
| 16 |
Correct |
1 ms |
860 KB |
Output is correct |
| 17 |
Correct |
1 ms |
860 KB |
Output is correct |
| 18 |
Correct |
1 ms |
860 KB |
Output is correct |
| 19 |
Correct |
1 ms |
860 KB |
Output is correct |
| 20 |
Correct |
1 ms |
860 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
3932 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
3932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
2 ms |
860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
1 ms |
860 KB |
Output is correct |
| 16 |
Correct |
1 ms |
860 KB |
Output is correct |
| 17 |
Correct |
1 ms |
860 KB |
Output is correct |
| 18 |
Correct |
1 ms |
860 KB |
Output is correct |
| 19 |
Correct |
1 ms |
860 KB |
Output is correct |
| 20 |
Correct |
1 ms |
860 KB |
Output is correct |
| 21 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
