oj.uz

Submission #489450

# Submission time Handle Problem Language Result Execution time Memory
489450 2021-11-23T02:33:36 Z wiwiho Remittance (JOI19_remittance) C++14
55 / 100
 1000 ms 89752 KB 
#include<bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n";\
}

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<ll> a(n), b(n);

    set<pll, greater<>> s;

    auto rmv = [&](int i){
        if(a[i] >= 2 && a[i] - b[i] != 0) s.erase(mp(a[i] - b[i], i));
    };
    auto add = [&](int i){
        if(a[i] >= 2 && a[i] - b[i] != 0) s.insert(mp(a[i] - b[i], i));
    };

    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        add(i);
    }

    while(!s.empty()){
        pll now = *s.begin();
        int id = now.S;
        s.erase(s.begin());
        //cerr << "test " << now.F << " " << now.S << "\n";

        ll cnt = now.F;
        if(cnt < 0) break;
        cnt = max(cnt / 2, 1LL);
        int nxt = (id + 1) % n;
        //cerr << cnt << " " << nxt << "\n";
        rmv(nxt);
        a[id] -= cnt * 2;
        a[nxt] += cnt;
        add(nxt);
        add(id);
        //printv(a, cerr);
        //printv(b, cerr);
    }

    for(int i = 0; i < n; i++){
        if(a[i] != b[i]){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 0 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 0 ms 320 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 0 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 1 ms 316 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 0 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 0 ms 320 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 0 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Correct 0 ms 208 KB Output is correct
35 Correct 0 ms 208 KB Output is correct
36 Correct 0 ms 208 KB Output is correct
37 Correct 1 ms 208 KB Output is correct
38 Correct 1 ms 208 KB Output is correct
39 Correct 1 ms 208 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 208 KB Output is correct
42 Correct 1 ms 208 KB Output is correct
43 Correct 1 ms 208 KB Output is correct
44 Correct 1 ms 208 KB Output is correct
45 Correct 0 ms 208 KB Output is correct
46 Correct 0 ms 208 KB Output is correct
47 Correct 1 ms 208 KB Output is correct
48 Correct 1 ms 208 KB Output is correct
49 Correct 1 ms 208 KB Output is correct
50 Correct 0 ms 208 KB Output is correct
51 Correct 1 ms 208 KB Output is correct
52 Correct 1 ms 208 KB Output is correct
53 Correct 0 ms 208 KB Output is correct
54 Correct 1 ms 208 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Correct 1 ms 316 KB Output is correct
57 Correct 0 ms 208 KB Output is correct
58 Correct 0 ms 224 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 0 ms 208 KB Output is correct
61 Correct 0 ms 208 KB Output is correct
62 Correct 1 ms 208 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 0 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 0 ms 320 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 0 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Correct 0 ms 208 KB Output is correct
35 Correct 0 ms 208 KB Output is correct
36 Correct 0 ms 208 KB Output is correct
37 Correct 1 ms 208 KB Output is correct
38 Correct 1 ms 208 KB Output is correct
39 Correct 1 ms 208 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 208 KB Output is correct
42 Correct 1 ms 208 KB Output is correct
43 Correct 1 ms 208 KB Output is correct
44 Correct 1 ms 208 KB Output is correct
45 Correct 0 ms 208 KB Output is correct
46 Correct 0 ms 208 KB Output is correct
47 Correct 1 ms 208 KB Output is correct
48 Correct 1 ms 208 KB Output is correct
49 Correct 1 ms 208 KB Output is correct
50 Correct 0 ms 208 KB Output is correct
51 Correct 1 ms 208 KB Output is correct
52 Correct 1 ms 208 KB Output is correct
53 Correct 0 ms 208 KB Output is correct
54 Correct 1 ms 208 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Correct 1 ms 316 KB Output is correct
57 Correct 0 ms 208 KB Output is correct
58 Correct 0 ms 224 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 0 ms 208 KB Output is correct
61 Correct 0 ms 208 KB Output is correct
62 Correct 1 ms 208 KB Output is correct
63 Execution timed out 1088 ms 89752 KB Time limit exceeded
64 Halted 0 ms 0 KB -