oj.uz

Submission #847779

# Submission time Handle Problem Language Result Execution time Memory
847779 2023-09-10T12:04:34 Z Essa2006 The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 1711 ms 56872 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m;
    cin>>n>>m;
    vector<vector<int>>A(n, vector<int>(m));
    int mn=1e9, mx=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>A[i][j];
            mn=min(mn, A[i][j]);
            mx=max(mx, A[i][j]);
        }
    }
    int l=0, r=1e9, ans;
    while(l<=r){
        int md=(l+r)/2;
        vector<vector<bool>>B(n, vector<bool>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mx-A[i][j]>md)
                    B[i][j]=1;
            }
        }
        bool can=0, cur;
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=0;i<n;i++){
                for(int j=m-1;j>=0;j--){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i!=n-1){
                            B2[i+1][j]=1;
                        }
                        if(j){
                            B2[i][j-1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i!=n-1){
                            B2[i+1][j]=1;
                        }
                        if(j!=m-1){
                            B2[i][j+1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=n-1;i>=0;i--){
                for(int j=m-1;j>=0;j--){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i){
                            B2[i-1][j]=1;
                        }
                        if(j){
                            B2[i][j-1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=n-1;i>=0;i--){
                for(int j=0;j<m;j++){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i){
                            B2[i-1][j]=1;
                        }
                        if(j!=m-1){
                            B2[i][j+1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        if(can)
            ans=md, r=md-1;
        else
            l=md+1;
    }
    cout<<ans<<endl;
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:4:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define endl '\n'
      |              ^~~~
joioi.cpp:22:21: note: 'ans' was declared here
   22 |     int l=0, r=1e9, ans;
      |                     ^~~

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 704 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 448 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 10 ms 600 KB Output is correct
17 Correct 11 ms 856 KB Output is correct
18 Correct 15 ms 856 KB Output is correct
19 Correct 15 ms 936 KB Output is correct
20 Correct 14 ms 1016 KB Output is correct
21 Correct 15 ms 856 KB Output is correct
22 Correct 19 ms 856 KB Output is correct
23 Correct 18 ms 860 KB Output is correct
24 Correct 15 ms 860 KB Output is correct
25 Correct 18 ms 856 KB Output is correct
26 Correct 17 ms 856 KB Output is correct
27 Correct 15 ms 856 KB Output is correct
28 Correct 14 ms 856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 704 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 448 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 10 ms 600 KB Output is correct
17 Correct 11 ms 856 KB Output is correct
18 Correct 15 ms 856 KB Output is correct
19 Correct 15 ms 936 KB Output is correct
20 Correct 14 ms 1016 KB Output is correct
21 Correct 15 ms 856 KB Output is correct
22 Correct 19 ms 856 KB Output is correct
23 Correct 18 ms 860 KB Output is correct
24 Correct 15 ms 860 KB Output is correct
25 Correct 18 ms 856 KB Output is correct
26 Correct 17 ms 856 KB Output is correct
27 Correct 15 ms 856 KB Output is correct
28 Correct 14 ms 856 KB Output is correct
29 Correct 1201 ms 38712 KB Output is correct
30 Correct 1203 ms 37908 KB Output is correct
31 Correct 1295 ms 40860 KB Output is correct
32 Correct 1181 ms 40708 KB Output is correct
33 Correct 1063 ms 35480 KB Output is correct
34 Correct 1275 ms 40900 KB Output is correct
35 Correct 1596 ms 56612 KB Output is correct
36 Correct 1450 ms 49328 KB Output is correct
37 Correct 1711 ms 56872 KB Output is correct