ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 12.05.2019 11:31:57

ამოცანა: კიბე

მომხმარებელი: Niko2019

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <bits/stdc++.h>
using namespace std;

int n, w, e, z, b, a[122][2], d[122][2];

int main() {
    cin >> n >> w;
    for(int i = 0; i < w; ++i) {
        cin >> z >> b;
        a[z][0] = b;
    }
    cin >> e;
    for(int i = 0; i < e; ++i) {
        cin >> z >> b;
        a[z][1] = b;
    }
    d[1][0] = 1;
    for(int i = 2; i <= n; ++i) {
        d[i][0] = d[i - 1][0] + 1;
        d[i][1] = d[i - 1][1];
        for(int j = i - 2; j >= 1; --j) {
            if(a[j][0] + j >= i) {
                if(d[j][0] + 1 < d[i][0]) {
                    d[i][0] = d[j][0] + 1;
                    d[i][1] = d[j][1];
                } else if(d[j][0] + 1 == d[i][0] && d[j][1] < d[i][1]) {
                    d[i][1] = d[j][1];
                }
            }
            if(a[j][1] * 2 + j >= i) {
                int c = (i - j + 1) / 2;
                if(d[j][0] + 1 < d[i][0]) {
                    d[i][0] = d[j][0] + 1;
                    d[i][1] = d[j][1] + c;
                } else if(d[j][0] + 1 == d[i][0] && d[j][1] + c < d[i][1]) {
                    d[i][1] = d[j][1] + c;
                }
            }
        }
    }
    cout << d[n][0] << " " << d[n][1] << endl;
}

ტესტები

შემავალი მონაცემები
77
8
1 1
23 1
24 5
36 4
47 19
19 9
8 14
38 1
38
12 13
46 12
56 15
15 7
64 13
62 13
31 10
45 9
37 11
8 7
9 11
32 8
38 6
59 4
13 7
47 3
44 10
1 12
19 7
26 6
39 10
54 5
23 7
17 7
4 8
66 1
28 2
5 4
24 7
14 3
51 14
61 12
36 1
33 9
60 14
3 9
35 10
52 4
გამომავალი მონაცემები
5 38
თქვენი პასუხი
5 38
ჩეკერის პასუხი
YES
შემავალი მონაცემები
6
1
1 1
2
2 1
1 3
გამომავალი მონაცემები
2 3
თქვენი პასუხი
2 3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
1
1 1
3
3 1
2 5
6 8
გამომავალი მონაცემები
3 4
თქვენი პასუხი
3 4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
49
7
1 1
14 1
9 11
8 15
38 6
18 3
28 12
14
2 3
32 11
30 13
38 4
17 15
33 14
18 10
26 9
22 11
5 7
27 8
20 9
14 14
11 3
გამომავალი მონაცემები
6 17
თქვენი პასუხი
6 17
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50
9
1 1
14 1
15 5
22 4
29 19
11 9
5 14
23 1
7 17
7
28 12
34 15
9 7
39 13
37 13
19 10
27 9
გამომავალი მონაცემები
8 16
თქვენი პასუხი
8 16
ჩეკერის პასუხი
YES
შემავალი მონაცემები
103
10
1 1
32 1
34 5
50 4
66 19
26 9
11 14
53 1
16 17
64 16
6
77 15
21 7
89 13
86 13
42 10
62 9
გამომავალი მონაცემები
20 38
თქვენი პასუხი
20 38
ჩეკერის პასუხი
YES
შემავალი მონაცემები
107
5
2 1
33 1
35 5
53 4
68 19
16
27 7
11 11
55 1
17 13
67 12
81 15
22 7
93 13
90 13
44 10
65 9
54 11
12 7
66 8
48 9
34 14
გამომავალი მონაცემები
17 41
თქვენი პასუხი
17 41
ჩეკერის პასუხი
YES
შემავალი მონაცემები
112
12
2 1
35 1
37 5
55 4
72 19
29 9
12 14
58 1
17 17
70 16
85 20
23 9
21
98 13
95 13
47 10
68 9
57 11
12 7
13 11
49 8
58 6
89 4
19 7
71 3
55 10
64 1
81 5
48 6
39 9
62 5
18 13
31 6
42 4
გამომავალი მონაცემები
19 34
თქვენი პასუხი
19 34
ჩეკერის პასუხი
YES
შემავალი მონაცემები
117
6
2 1
36 1
39 5
58 4
75 19
30 9
30
12 11
61 1
18 13
74 12
89 15
24 7
102 13
99 13
49 10
71 9
59 11
13 7
72 8
53 9
37 14
29 3
46 11
58 10
67 1
85 5
50 6
41 9
65 5
19 13
32 6
44 4
45 1
106 1
8 2
28 15
გამომავალი მონაცემები
14 48
თქვენი პასუხი
14 48
ჩეკერის პასუხი
YES
შემავალი მონაცემები
120
10
2 1
37 1
40 5
60 4
78 19
31 9
12 14
63 1
19 17
76 16
20
92 15
25 7
105 13
102 13
50 10
73 9
61 11
13 7
14 11
53 8
63 6
96 4
20 7
77 3
60 10
69 1
87 5
51 6
42 9
67 5
გამომავალი მონაცემები
20 31
თქვენი პასუხი
20 31
ჩეკერის პასუხი
YES