QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557112#360. Cultivationmakrav15 970ms3880kbC++202.4kb2024-09-11 03:22:552024-09-11 03:22:55

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 03:22:55]
  • 评测
  • 测评结果：15
  • 用时：970ms
  • 内存：3880kb
查看
  • [2024-09-11 03:22:55]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

void solve() {
    int h, w, n; cin >> h >> w >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {cin >> a[i].first >> a[i].second; a[i].first--; a[i].second--; }
    int ans = 1e9;
    vector<int> ups, dwns;
    for (int i = 0; i < n; i++) ups.pb(a[i].first);
    sort(all(ups));
    for (int up : ups) {
         if (up>ans)continue;
        for (int down=0;down<h;down++){
            for (int left=0;left<w;left++) {
                if (up+left+down>ans)continue;
                for (int right = 0;right<w;right++) {
                    if (up+left+right+down>ans)continue;
                    vector<vector<int>> us(h+1, vector<int>(w+1));
                    for (int i = 0; i < n; i++) {
                        int I1 = max(0, a[i].first - up), I2 = min(h - 1, a[i].first + down), J1 = max(0, a[i].second - left), J2 = min(w - 1, a[i].second + right);
                        us[I1][J1]++;
                        us[I1][J2 + 1]--;
                        us[I2 + 1][J1]--;
                        us[I2 + 1][J2 + 1]++;
                    }
                    bool good = true;
                    if (!us[0][0]) continue;
                    for (int i = 0; i < h; i++) {
                        if(!good)break;
                        for (int j = 0; j < w; j++) {
                            if (i > 0) us[i][j] += us[i - 1][j];
                            if (j > 0) us[i][j] += us[i][j - 1];
                            if (i>0&&j>0) us[i][j] -= us[i-1][j-1];
                            if (us[i][j]==0) {
                                good=false;break;
                            }
                        }
                    }
                    if(good){
                        ans=min(ans,up+down+left+right);
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out1.txt", "w", stdout);

        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3512kb

input:

2 4
2
1 1
1 4

output:

3

result:

ok single line: '3'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3792kb

input:

4 1
1
2 1

output:

3

result:

ok single line: '3'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3564kb

input:

3 3
3
1 2
1 3
3 3

output:

3

result:

ok single line: '3'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3508kb

input:

2 2
1
1 2

output:

2

result:

ok single line: '2'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3628kb

input:

4 4
10
4 2
2 3
2 4
4 1
1 2
2 1
4 3
3 3
3 1
1 4

output:

2

result:

ok single line: '2'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3572kb

input:

4 4
1
4 1

output:

6

result:

ok single line: '6'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3624kb

input:

4 4
3
2 2
3 3
1 4

output:

5

result:

ok single line: '5'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3564kb

input:

4 4
15
4 3
2 4
4 4
4 1
3 3
1 2
3 1
2 1
3 4
3 2
4 2
2 3
1 3
2 2
1 4

output:

1

result:

ok single line: '1'

Test #9:

score: 5
Accepted
time: 0ms
memory: 3508kb

input:

4 3
3
2 1
2 3
4 1

output:

3

result:

ok single line: '3'

Test #10:

score: 5
Accepted
time: 0ms
memory: 3568kb

input:

4 4
2
3 4
2 4

output:

5

result:

ok single line: '5'

Test #11:

score: 5
Accepted
time: 0ms
memory: 3788kb

input:

2 4
1
1 2

output:

4

result:

ok single line: '4'

Test #12:

score: 5
Accepted
time: 0ms
memory: 3572kb

input:

3 3
4
2 1
1 1
3 2
3 1

output:

2

result:

ok single line: '2'

Test #13:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

3 4
3
1 4
3 3
3 4

output:

4

result:

ok single line: '4'

Test #14:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

3 3
2
2 1
3 3

output:

4

result:

ok single line: '4'

Test #15:

score: 5
Accepted
time: 0ms
memory: 3636kb

input:

4 4
2
2 4
3 1

output:

6

result:

ok single line: '6'

Test #16:

score: 5
Accepted
time: 0ms
memory: 3664kb

input:

4 4
3
2 2
2 1
4 2

output:

4

result:

ok single line: '4'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 10
Accepted
time: 2ms
memory: 3624kb

input:

15 15
20
6 13
14 4
11 13
15 3
12 4
10 4
11 6
8 9
12 12
2 15
4 3
8 15
8 4
3 1
5 10
11 12
8 7
13 10
11 4
1 3

output:

13

result:

ok single line: '13'

Test #18:

score: 10
Accepted
time: 3ms
memory: 3568kb

input:

25 25
66
24 6
12 18
11 2
24 18
6 9
20 6
15 19
17 2
15 9
15 20
18 9
5 19
9 2
6 12
22 16
6 2
1 5
14 24
12 21
17 24
10 15
21 1
20 22
11 24
11 4
6 21
18 12
25 20
16 3
18 16
6 4
20 9
6 15
24 14
3 20
9 9
25 9
18 6
4 16
12 7
14 22
20 25
24 10
11 14
17 6
23 23
21 12
18 22
8 23
1 11
17 18
8 5
3 7
1 17
8 12
4...

output:

9

result:

ok single line: '9'

Test #19:

score: 10
Accepted
time: 108ms
memory: 3632kb

input:

36 38
28
30 5
4 23
29 20
1 36
8 28
8 9
5 26
23 16
26 1
24 38
22 36
4 26
9 7
10 24
20 11
31 5
24 30
26 30
18 15
14 1
23 31
20 7
23 30
33 9
27 33
8 7
9 16
33 5

output:

30

result:

ok single line: '30'

Test #20:

score: 10
Accepted
time: 6ms
memory: 3564kb

input:

10 40
19
7 5
8 38
4 7
8 5
4 30
1 33
1 16
2 21
8 33
4 36
6 20
6 27
4 14
10 15
9 30
8 13
4 15
10 9
5 22

output:

17

result:

ok single line: '17'

Test #21:

score: 10
Accepted
time: 545ms
memory: 3640kb

input:

40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14

output:

50

result:

ok single line: '50'

Test #22:

score: 10
Accepted
time: 60ms
memory: 3800kb

input:

40 40
120
23 22
31 36
2 4
2 32
14 40
23 32
18 11
27 36
7 1
25 33
22 40
34 9
26 20
18 7
35 7
3 17
19 6
5 27
19 30
33 15
2 15
19 15
4 8
27 1
8 27
10 2
11 39
31 27
32 35
17 4
18 22
2 7
7 10
5 14
40 23
3 36
6 6
6 15
21 35
27 39
25 1
40 11
36 16
8 23
35 27
18 21
24 39
13 22
4 3
12 17
31 16
3 6
6 4
3 30
2...

output:

16

result:

ok single line: '16'

Test #23:

score: 10
Accepted
time: 970ms
memory: 3636kb

input:

40 40
33
10 22
10 3
7 11
12 14
11 12
1 21
6 23
3 11
8 24
3 40
8 14
7 25
8 15
12 3
10 7
4 32
7 32
9 32
9 30
4 22
8 22
11 24
6 19
10 16
10 2
9 4
10 15
9 28
7 1
4 31
7 35
4 18
2 35

output:

46

result:

ok single line: '46'

Test #24:

score: 10
Accepted
time: 42ms
memory: 3804kb

input:

40 40
200
10 16
27 15
18 11
16 25
34 7
39 25
26 15
12 20
8 1
20 14
25 27
33 4
29 40
20 33
8 9
32 16
37 25
34 27
31 23
30 8
40 30
35 37
27 7
18 27
36 30
13 30
12 32
32 4
15 21
29 39
4 32
8 7
12 21
35 40
32 29
34 17
22 30
12 34
34 39
23 16
27 16
13 26
28 32
8 31
30 16
13 25
28 13
19 35
38 35
2 40
7 1
...

output:

14

result:

ok single line: '14'

Test #25:

score: 10
Accepted
time: 74ms
memory: 3804kb

input:

40 40
150
8 38
27 32
34 14
29 32
16 36
29 19
40 30
30 22
34 12
4 30
24 37
14 8
31 21
40 17
38 25
16 5
29 5
38 29
28 10
2 5
5 16
20 11
38 6
21 11
5 8
26 13
21 35
27 27
10 11
18 30
30 40
8 18
31 5
16 7
3 1
35 36
40 26
18 39
25 8
19 16
17 26
6 20
13 30
34 4
35 8
33 4
25 29
39 7
22 40
10 36
26 3
30 14
1...

output:

16

result:

ok single line: '16'

Test #26:

score: 10
Accepted
time: 187ms
memory: 3616kb

input:

40 40
300
5 29
4 30
10 5
19 1
11 37
8 26
2 12
29 25
13 33
4 36
15 9
6 39
27 35
34 14
35 27
32 26
14 35
23 35
23 34
12 6
2 21
20 29
20 23
5 21
15 11
7 13
6 23
33 7
19 22
20 31
28 25
7 18
15 39
25 1
2 16
5 23
5 28
7 21
5 31
8 29
16 14
18 29
16 3
3 23
20 35
24 34
14 4
14 30
39 18
25 5
19 37
28 10
7 11
...

output:

18

result:

ok single line: '18'

Test #27:

score: 10
Accepted
time: 112ms
memory: 3520kb

input:

40 40
300
23 5
15 1
34 20
36 22
19 4
31 19
11 34
13 33
3 20
18 4
27 10
37 21
14 11
30 34
8 29
6 26
32 33
8 10
1 14
40 40
4 22
19 31
6 28
37 16
22 34
38 17
16 2
18 36
12 4
38 15
1 24
1 18
32 8
6 18
35 26
12 36
25 2
38 20
19 3
25 12
2 34
35 22
10 36
26 3
10 22
36 8
29 33
3 39
5 10
7 9
36 14
24 5
5 21
...

output:

14

result:

ok single line: '14'

Test #28:

score: 10
Accepted
time: 75ms
memory: 3880kb

input:

39 40
200
9 40
2 33
16 32
14 33
14 27
3 28
5 31
36 30
15 22
23 17
22 28
13 10
4 14
24 35
4 35
12 22
28 32
8 37
7 31
1 37
28 21
39 22
12 17
7 20
35 16
10 12
12 6
27 31
33 15
19 16
13 35
26 35
10 19
15 25
18 19
21 9
11 9
39 4
3 31
20 24
37 26
22 38
13 40
18 12
29 4
31 2
10 26
2 39
2 3
18 9
14 34
39 23...

output:

15

result:

ok single line: '15'

Test #29:

score: 10
Accepted
time: 34ms
memory: 3544kb

input:

38 38
300
30 33
11 38
6 10
19 20
29 30
1 18
30 20
11 19
23 15
32 3
32 30
5 34
7 30
34 1
5 4
20 35
8 13
25 32
12 2
6 3
1 19
38 7
35 16
14 9
37 2
10 4
13 21
37 17
34 4
20 20
14 12
20 13
36 3
10 33
5 8
23 23
9 22
17 19
13 9
20 14
31 4
11 23
17 32
12 10
21 23
31 11
17 35
12 17
31 27
3 6
10 37
2 38
5 15
...

output:

9

result:

ok single line: '9'

Test #30:

score: 10
Accepted
time: 32ms
memory: 3580kb

input:

40 40
300
25 27
25 10
20 19
16 40
29 29
39 20
3 4
6 20
20 6
1 25
39 32
28 26
27 17
30 38
4 33
27 24
21 4
36 32
29 7
4 23
39 2
40 6
14 40
33 39
23 32
23 34
18 6
36 28
40 4
15 28
13 33
34 3
4 35
20 29
38 36
7 24
5 25
20 3
37 13
40 26
5 9
40 36
24 26
16 14
8 28
37 6
24 16
7 3
28 28
34 13
34 36
29 12
13...

output:

10

result:

ok single line: '10'

Test #31:

score: 10
Accepted
time: 21ms
memory: 3584kb

input:

40 40
300
31 12
30 38
21 17
11 12
1 28
10 37
10 13
5 22
18 21
28 37
23 40
29 32
21 33
5 3
21 24
14 15
2 23
9 33
15 31
38 12
37 8
37 26
1 5
28 34
22 10
18 29
30 39
23 34
25 37
35 1
10 7
25 11
10 38
34 30
18 1
12 1
10 25
16 11
35 40
26 30
5 15
23 3
22 22
16 4
8 21
12 23
24 29
4 27
40 5
18 15
35 38
1 1...

output:

9

result:

ok single line: '9'

Test #32:

score: 10
Accepted
time: 36ms
memory: 3580kb

input:

40 40
300
24 6
26 15
30 7
10 12
17 17
7 25
36 26
19 39
32 10
20 1
16 1
34 1
23 19
10 38
40 7
13 39
25 27
28 25
39 18
25 20
17 3
32 28
10 4
6 3
12 16
29 35
13 12
29 16
2 35
6 15
19 7
1 32
18 24
13 18
1 31
28 31
29 12
19 4
20 10
1 3
6 38
1 10
27 14
33 26
1 12
8 31
9 39
22 21
8 39
37 3
26 33
25 10
32 4...

output:

11

result:

ok single line: '11'

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #33:

score: 0
Time Limit Exceeded

input:

2 200000000
300
1 88265857
1 174408185
1 105379902
1 185252998
2 30206021
2 102367431
2 89739523
1 116153736
2 68837704
1 110817136
2 26646126
2 86276690
1 127329134
2 126441765
1 19927577
1 38738747
1 105161585
1 60367988
2 67085969
1 1865971
1 27164731
1 77127255
2 168438218
1 4482768
1 197852914
...

output:

result:

Subtask #4:

score: 0
Memory Limit Exceeded

Test #45:

score: 0
Memory Limit Exceeded

input:

1000000000 1000000000
17
822413671 70423910
260075513 431043546
300945721 793553248
142848049 163787897
392462410 831950868
699005697 111397300
444396260 130450496
642691616 595456084
467968916 463598810
159764248 611476406
929313754 539645102
365153650 964108073
906780716 373514044
970118116 655138...

output:

result:

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 13:33:18 | OpenSource Project