oj.uz

Submission #628643

# Submission time Handle Problem Language Result Execution time Memory
628643 2022-08-13T14:45:03 Z a_aguilo Tug of War (BOI15_tug) C++17
18 / 100
 3000 ms 2004 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 4 ms 596 KB Output is correct
27 Execution timed out 3091 ms 468 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2004 KB Output is correct
2 Execution timed out 3085 ms 1420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 4 ms 596 KB Output is correct
27 Execution timed out 3091 ms 468 KB Time limit exceeded
28 Halted 0 ms 0 KB -