| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 681928 | 2023-01-14T22:24:39 Z | MilosMilutinovic | Tug of War (BOI15_tug) | C++14 | 381 ms | 5476 KB |
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
typedef long long ll;
const int N = 30333;
int n, k;
int l[2 * N];
int r[2 * N];
int s[2 * N];
vector<int> g[4 * N];
int ver;
int pos;
bool was[4 * N];
ll sum[2];
void addEdge(int v, int u) {
g[v].push_back(u);
g[u].push_back(v);
}
void dfs(int v) {
if (v < 2 * n) {
sum[ver & 1] += s[v];
ver++;
} else pos++;
was[v] = true;
for (int u : g[v])
if (!was[u])
dfs(u);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d", &n, &k);
assert(k >= 0);
for (int i = 0; i < 2 * n; i++) {
scanf("%d%d%d", &l[i], &r[i], &s[i]);
--l[i];--r[i];
addEdge(i, 2 * n + l[i]);
addEdge(i, 3 * n + r[i]);
}
vector<int> diff;
for (int i = 0; i < 2 * n; i++) if (!was[i]) {
ver = 0;
pos = 0;
sum[0] = 0;
sum[1] = 0;
dfs(i);
diff.push_back(sum[0] - sum[1]);
if (ver > pos) {
printf("NO\n");
return 0;
}
}
bitset<40 * N + 1> dp;
dp[20 * N] = 1;
for (int x : diff) {
x = abs(x);
dp = ((dp >> x) | (dp << x));
}
bool ok = false;
for (int i = 0; i <= k; i++)
if (dp[20 * N + i] || dp[20 * N - i])
ok = true;
if (ok)
printf("YES\n");
else
printf("NO\n");
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3668 KB | Output is correct |
| 2 | Correct | 3 ms | 3668 KB | Output is correct |
| 3 | Correct | 2 ms | 3668 KB | Output is correct |
| 4 | Correct | 3 ms | 3668 KB | Output is correct |
| 5 | Correct | 3 ms | 3668 KB | Output is correct |
| 6 | Correct | 2 ms | 3668 KB | Output is correct |
| 7 | Correct | 2 ms | 3668 KB | Output is correct |
| 8 | Correct | 3 ms | 3764 KB | Output is correct |
| 9 | Correct | 3 ms | 3756 KB | Output is correct |
| 10 | Correct | 3 ms | 3760 KB | Output is correct |
| 11 | Correct | 3 ms | 3756 KB | Output is correct |
| 12 | Correct | 2 ms | 3668 KB | Output is correct |
| 13 | Correct | 2 ms | 3756 KB | Output is correct |
| 14 | Correct | 2 ms | 3668 KB | Output is correct |
| 15 | Correct | 3 ms | 3668 KB | Output is correct |
| 16 | Correct | 3 ms | 3668 KB | Output is correct |
| 17 | Correct | 3 ms | 3668 KB | Output is correct |
| 18 | Correct | 2 ms | 3668 KB | Output is correct |
| 19 | Correct | 3 ms | 3764 KB | Output is correct |
| 20 | Correct | 3 ms | 3668 KB | Output is correct |
| 21 | Correct | 2 ms | 3668 KB | Output is correct |
| 22 | Correct | 2 ms | 3756 KB | Output is correct |
| 23 | Incorrect | 2 ms | 3760 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3668 KB | Output is correct |
| 2 | Correct | 3 ms | 3668 KB | Output is correct |
| 3 | Correct | 2 ms | 3668 KB | Output is correct |
| 4 | Correct | 3 ms | 3668 KB | Output is correct |
| 5 | Correct | 3 ms | 3668 KB | Output is correct |
| 6 | Correct | 2 ms | 3668 KB | Output is correct |
| 7 | Correct | 2 ms | 3668 KB | Output is correct |
| 8 | Correct | 3 ms | 3764 KB | Output is correct |
| 9 | Correct | 3 ms | 3756 KB | Output is correct |
| 10 | Correct | 3 ms | 3760 KB | Output is correct |
| 11 | Correct | 3 ms | 3756 KB | Output is correct |
| 12 | Correct | 2 ms | 3668 KB | Output is correct |
| 13 | Correct | 2 ms | 3756 KB | Output is correct |
| 14 | Correct | 2 ms | 3668 KB | Output is correct |
| 15 | Correct | 3 ms | 3668 KB | Output is correct |
| 16 | Correct | 3 ms | 3668 KB | Output is correct |
| 17 | Correct | 3 ms | 3668 KB | Output is correct |
| 18 | Correct | 2 ms | 3668 KB | Output is correct |
| 19 | Correct | 3 ms | 3764 KB | Output is correct |
| 20 | Correct | 3 ms | 3668 KB | Output is correct |
| 21 | Correct | 2 ms | 3668 KB | Output is correct |
| 22 | Correct | 2 ms | 3756 KB | Output is correct |
| 23 | Incorrect | 2 ms | 3760 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 363 ms | 5364 KB | Output is correct |
| 2 | Correct | 11 ms | 5204 KB | Output is correct |
| 3 | Correct | 351 ms | 5300 KB | Output is correct |
| 4 | Correct | 10 ms | 5248 KB | Output is correct |
| 5 | Correct | 381 ms | 5384 KB | Output is correct |
| 6 | Correct | 11 ms | 5224 KB | Output is correct |
| 7 | Correct | 359 ms | 5332 KB | Output is correct |
| 8 | Correct | 10 ms | 5204 KB | Output is correct |
| 9 | Correct | 353 ms | 5476 KB | Output is correct |
| 10 | Correct | 13 ms | 5200 KB | Output is correct |
| 11 | Correct | 346 ms | 5332 KB | Output is correct |
| 12 | Correct | 11 ms | 5204 KB | Output is correct |
| 13 | Correct | 353 ms | 5372 KB | Output is correct |
| 14 | Correct | 362 ms | 5368 KB | Output is correct |
| 15 | Correct | 18 ms | 5204 KB | Output is correct |
| 16 | Correct | 355 ms | 5368 KB | Output is correct |
| 17 | Correct | 10 ms | 5204 KB | Output is correct |
| 18 | Correct | 362 ms | 5372 KB | Output is correct |
| 19 | Correct | 11 ms | 5204 KB | Output is correct |
| 20 | Correct | 350 ms | 5372 KB | Output is correct |
| 21 | Correct | 11 ms | 5332 KB | Output is correct |
| 22 | Correct | 297 ms | 5324 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3668 KB | Output is correct |
| 2 | Correct | 3 ms | 3668 KB | Output is correct |
| 3 | Correct | 2 ms | 3668 KB | Output is correct |
| 4 | Correct | 3 ms | 3668 KB | Output is correct |
| 5 | Correct | 3 ms | 3668 KB | Output is correct |
| 6 | Correct | 2 ms | 3668 KB | Output is correct |
| 7 | Correct | 2 ms | 3668 KB | Output is correct |
| 8 | Correct | 3 ms | 3764 KB | Output is correct |
| 9 | Correct | 3 ms | 3756 KB | Output is correct |
| 10 | Correct | 3 ms | 3760 KB | Output is correct |
| 11 | Correct | 3 ms | 3756 KB | Output is correct |
| 12 | Correct | 2 ms | 3668 KB | Output is correct |
| 13 | Correct | 2 ms | 3756 KB | Output is correct |
| 14 | Correct | 2 ms | 3668 KB | Output is correct |
| 15 | Correct | 3 ms | 3668 KB | Output is correct |
| 16 | Correct | 3 ms | 3668 KB | Output is correct |
| 17 | Correct | 3 ms | 3668 KB | Output is correct |
| 18 | Correct | 2 ms | 3668 KB | Output is correct |
| 19 | Correct | 3 ms | 3764 KB | Output is correct |
| 20 | Correct | 3 ms | 3668 KB | Output is correct |
| 21 | Correct | 2 ms | 3668 KB | Output is correct |
| 22 | Correct | 2 ms | 3756 KB | Output is correct |
| 23 | Incorrect | 2 ms | 3760 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |