제출 #79576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79576		atoiz	Tug of War (BOI15_tug)	C++14	18 / 100	48 ms	14916 KiB

tug

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
#include <cstring>
#include <map>

using namespace std;

const int MAX = 100007, MAX_K = 500007, INF = 1e8;
int n, k, l[MAX], r[MAX], s[MAX], total = 0;
bool used[MAX], sack[MAX_K];
set<int> inV[MAX];
map<int, int> packs;

void kill() { cout << "NO"; exit(0); }

signed main()
{
	// IO
	memset(used, 0, sizeof used);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < 2 * n; ++i) {
		cin >> l[i] >> r[i] >> s[i]; --l[i], --r[i], r[i] += n;
        inV[l[i]].insert(i);
        inV[r[i]].insert(i);
    }

    // remove singles
    stack<int> st;
    for (int p = 0; p < 2 * n; ++p) {
		if (inV[p].size() == 1) st.push(p);
    }

    int cur = 0;
    while (!st.empty()) {
        int p = st.top(); st.pop();
        used[p] = 1;
        int i = (*inV[p].begin()); inV[p].clear();

        int nxt;
        if (l[i] == p) cur += s[i], nxt = r[i];
        else cur -= s[i], nxt = l[i];

        inV[nxt].erase(inV[nxt].find(i));
        if (inV[nxt].size() == 1) st.push(nxt);
	}


	// check
    for (int p = 0; p < 2 * n; ++p) {
        if (used[p]) continue;
        if (inV[p].size() != 2) kill();
    }

    if (cur != 0) packs[abs(cur)] = 1;

	// initialize knapsack
    for (int p = 0; p < 2 * n; ++p) {
        if (used[p]) continue;

        int sgn = 1, cur = 0;
        int prv = (*inV[p].begin()), nxt = (*inV[p].rbegin());
        cur += sgn * s[prv]; sgn = -sgn; used[p] = 1;
		int p1 = (l[nxt] == p) ? r[nxt] : l[nxt];

        while (p1 != p) {
            prv = nxt;
            nxt = ((*inV[p1].begin()) == prv) ? (*inV[p1].rbegin()) : (*inV[p1].begin());
			cur += sgn * s[prv]; sgn = -sgn; used[p1] = 1;
            p1 = (l[nxt] == p1) ? r[nxt] : l[nxt];
        }

        cur = abs(cur);
        if (cur == 0) continue;
        if (packs.find(cur) == packs.end()) packs[cur] = 1;
        else ++ packs[cur];
	}

    memset(sack, 0, sizeof sack);
    sack[0] = 1;

    // total
    total = 0;
	for (map<int, int>::iterator it = packs.begin(); it != packs.end(); ++it) total += it->first * it->second;

    for (map<int, int>::iterator it = packs.begin(); it != packs.end(); ++it) {
        int val = it->first, cnt = it->second;
//        cerr << val << ' ' << cnt << endl;

        for (int start = 0; start < val; ++start) {
            int last = -INF;
            for (int i = start; i <= total / 2; i += val) {
                if (sack[i]) { last = i; continue; }
                if (last + val * cnt >= i) sack[i] = 1;
            }
        }
    }

    int i = total / 2;
    while (!sack[i]) --i;
    int ans = total - 2 * i;

    if (ans <= k) cout << "YES";
    else cout << "NO";
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29