Submission #628643

#	Time	Username	Problem	Language	Result	Execution time	Memory
628643		a_aguilo	Tug of War (BOI15_tug)	C++17	18 / 100	3091 ms	2004 KiB

tug

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

vi leftSpots, rightSpots;

struct contestant{
    int left, right, force;
    contestant(int l, int r, int f){
        left = l;
        right = r;
        force = f;
    }
};

vector<contestant*> people;

int n, k;
int sLeft, sRight;

bool possible(int pos){
    if(pos == 2*n) return (abs(sLeft-sRight)<= k);
    if(!leftSpots[people[pos]->left]){
        sLeft += people[pos]->force;
        leftSpots[people[pos]->left] = 1;
        if(possible(pos+1)) return true;
        sLeft -= people[pos]->force;
        leftSpots[people[pos]->left] = 0;
    }
    if(!rightSpots[people[pos]->right]){
        sRight += people[pos]->force;
        rightSpots[people[pos]->right] = 1;
        if(possible(pos+1)) return true;
        sRight -= people[pos]->force;
        rightSpots[people[pos]->right] = 0;
    }
    return false;
}

int main(){
    int l, r, s;
    cin >> n >> k;
    people = vector<contestant*> (2*n);
    for(int i = 0; i < 2*n; ++i){
        cin >> l >> r >> s; l--; r--;
        contestant* act = new contestant(l, r, s);
        people[i] = act;
    }
    sLeft = 0;
    sRight = 0;
    leftSpots = vi(n, 0); rightSpots = vi(n, 0);
    if(possible(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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