oj.uz

Submission #953626

# Submission time Handle Problem Language Result Execution time Memory
953626 2024-03-26T10:57:37 Z Darren0724 Cultivation (JOI17_cultivation) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=42;
const int INF=1e9;
vector v(N,vector(N,0));
vector<int> dx={1,-1,0,0},dy={0,0,-1,1};
int r,c;
int solve(vector<int> a){
    vector v1=v;
    vector v2=v;
    for(int k=0;k<2;k++){
        for(int times=0;times<a[k];times++){
            for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    int c=i+dx[k];
                    int d=j+dy[k];
                    if(v1[i][j])v2[c][d]=1;
                }
            }   
            v1=v2;
        }
    }
    vector<int> mx(r+2,-INF),mn(r+2,INF);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(v1[i][j]){
                mx[i]=max(mx[i],j);
                mn[i]=min(mn[i],j);
            }
        }
    }
    int a1=0,b1=0;
    for(int i=1;i<=r;i++){
        if(mn[i]==INF){
            return -1;
        }
        a1=max(a1,mn[i]-1);
        b1=max(b1,c-mx[i]);
    }
    a.push_back(a1);
    a.push_back(b1);
    for(int k=2;k<3;k++){
        for(int times=0;times<a[k];times++){
            for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    int c=i+dx[k];
                    int d=j+dy[k];
                    if(v1[i][j])v2[c][d]=1;
                }
            }   
            v1=v2;
        }
    }
    int mx5=0;
    for(int i=1;i<=r;i++){
        int cnt5=0;
        for(int j=1;j<=c;j++){
            if(v1[i][j]==0){
                cnt5++;
            }
            else{
                cnt5=0;
            }
            mx5=max(cnt5,mx5);
        }
    }
    //cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<' '<<a[3]<<' '<<mx5<<endl;
    return a1+b1+mx5;
}
int32_t main() {
    LCBorz;
    cin>>r>>c;
    int n;cin>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        v[a[i]][b[i]]=1;
    }
    int ans=INF;
    for(int i=0;i<r;i++){
        for(int j=0;j<r;j++){
            int tmp=solve({i,j});
            if(tmp!=-1){
                ans=min(ans,i+j+tmp);
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

Subtask #1
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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -