oj.uz

Submission #1064228

# Submission time Handle Problem Language Result Execution time Memory
1064228 2024-08-18T10:39:39 Z Unforgettablepl Cultivation (JOI17_cultivation) C++17
15 / 100
 725 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int r,c,n;
    cin >> r >> c >> n;
    vector<pair<int,int>> points(n);
    for(auto&[a,b]:points)cin>>a>>b;
    int tar = r*c;
    auto check = [&](int chosenR,int chosenC){
        vector grid(4*r+1,vector(4*c+1,0ll));
        for(auto&[x,y]:points) {
            grid[x][y]++;
            grid[x+chosenR][y]--;
            grid[x][y+chosenC]--;
            grid[x+chosenR][y+chosenC]++;
        }
        for(int i=1;i<=4*r;i++) {
            for(int j=1;j<=4*c;j++) {
                grid[i][j]+=grid[i][j-1];
            }
        }
        for(int i=1;i<=4*c;i++) {
            for(int j=1;j<=4*r;j++) {
                grid[j][i]+=grid[j-1][i];
            }
        }
        for(int i=1;i<=4*r;i++) {
            for(int j=1;j<=4*c;j++) {
                grid[i][j]=min(1ll,grid[i][j])+grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1];
            }
        }
        auto get = [&](int x1,int y1,int x2,int y2) {
            return grid[x2][y2]-grid[x1-1][y2]-grid[x2][y1-1]+grid[x1-1][y1-1];
        };
        for(int i=1;i<=2*r;i++) {
            for(int j=1;j<=2*c;j++) {
                if(get(i,j,i+r-1,j+c-1)==tar)return true;
            }
        }
        return false;
    };
    int ans = r+c;
    for(int R=1;R<=2*r;R++) {
        for(int C=1;C<=2*c;C++) {
            if(check(R,C)) {
                ans=min(ans,R+C-2);
            }
        }
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 15 ms 484 KB Output is correct
18 Correct 96 ms 348 KB Output is correct
19 Correct 473 ms 632 KB Output is correct
20 Correct 38 ms 348 KB Output is correct
21 Correct 386 ms 616 KB Output is correct
22 Correct 656 ms 752 KB Output is correct
23 Correct 666 ms 652 KB Output is correct
24 Correct 673 ms 668 KB Output is correct
25 Correct 661 ms 652 KB Output is correct
26 Correct 661 ms 772 KB Output is correct
27 Correct 652 ms 668 KB Output is correct
28 Correct 706 ms 660 KB Output is correct
29 Correct 541 ms 648 KB Output is correct
30 Correct 667 ms 652 KB Output is correct
31 Correct 667 ms 652 KB Output is correct
32 Correct 725 ms 772 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 15 ms 484 KB Output is correct
18 Correct 96 ms 348 KB Output is correct
19 Correct 473 ms 632 KB Output is correct
20 Correct 38 ms 348 KB Output is correct
21 Correct 386 ms 616 KB Output is correct
22 Correct 656 ms 752 KB Output is correct
23 Correct 666 ms 652 KB Output is correct
24 Correct 673 ms 668 KB Output is correct
25 Correct 661 ms 652 KB Output is correct
26 Correct 661 ms 772 KB Output is correct
27 Correct 652 ms 668 KB Output is correct
28 Correct 706 ms 660 KB Output is correct
29 Correct 541 ms 648 KB Output is correct
30 Correct 667 ms 652 KB Output is correct
31 Correct 667 ms 652 KB Output is correct
32 Correct 725 ms 772 KB Output is correct
33 Runtime error 124 ms 262144 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 15 ms 484 KB Output is correct
18 Correct 96 ms 348 KB Output is correct
19 Correct 473 ms 632 KB Output is correct
20 Correct 38 ms 348 KB Output is correct
21 Correct 386 ms 616 KB Output is correct
22 Correct 656 ms 752 KB Output is correct
23 Correct 666 ms 652 KB Output is correct
24 Correct 673 ms 668 KB Output is correct
25 Correct 661 ms 652 KB Output is correct
26 Correct 661 ms 772 KB Output is correct
27 Correct 652 ms 668 KB Output is correct
28 Correct 706 ms 660 KB Output is correct
29 Correct 541 ms 648 KB Output is correct
30 Correct 667 ms 652 KB Output is correct
31 Correct 667 ms 652 KB Output is correct
32 Correct 725 ms 772 KB Output is correct
33 Runtime error 124 ms 262144 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -