oj.uz

Submission #692031

# Submission time Handle Problem Language Result Execution time Memory
692031 2023-02-01T05:22:13 Z Cookie197 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 832 ms 227176 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl
#define mp make_pair
#define mt(a,b,c,d) mp(mp(a,b),mp(c,d)) 

int arr[8][3003][3003],n,m,s=2e9,sx[8],sy[8];
bool check(int num){

    for (int z=0;z<=7;z++){
        if (z==1 || z==2 || z==5 || z==7) swap(n,m);
        int am = 0,an = 1e9,bm = 0,bn = 1e9, ok = true;
        
        int lim = m, safe = false;
        for (int i=1;i<=n;i++){
            int cut = 0;
            for (int j=1;j<=lim;j++){
                if (max(am, arr[z][i][j]) - s > num) break;
                cut++;
                am = max(am, arr[z][i][j]);
                if (arr[z][i][j] == s) safe = true;
            }
            lim = cut;

            //if (i == sx[z] && cut < sy[z] && !safe) {ok = false; break;}

            for (int j=cut+1;j<=m;j++){
                bm = max(bm, arr[z][i][j]), bn = min(bn, arr[z][i][j]);
            }
            if (bm - bn > num) {ok = false; break;}
        }
        if (z==1 || z==2 || z==5 || z==7) swap(n,m);
        if (ok && safe) return true;
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int x; cin>>x;
            arr[0][i][j] = x;
            arr[1][j][i] = x;
            arr[2][m-j+1][n-i+1] = x;
            arr[3][n-i+1][m-j+1] = x;
            arr[4][n-i+1][j] = x;
            arr[5][m-j+1][i] = x;
            arr[6][i][m-j+1] = x;
            arr[7][j][n-i+1] = x;
            s = min(s, x);
        }
    }

    for (int z=0;z<=7;z++) for (int i=1;i<=n;i++) for (int j=n;j>=1;j--) if (arr[z][i][j] == s) sx[z] = i, sy[z] = j;


    int left = 0, right = 1000000005;
    while(left < right){
        int mid = (left + right) >> 1;
        if (!check(mid)) left = mid+1;
        else right = mid;
    }
    cout<<left<<endl;
}

Compilation message

joioi.cpp: In function 'bool check(int)':
joioi.cpp:19:20: warning: unused variable 'an' [-Wunused-variable]
   19 |         int am = 0,an = 1e9,bm = 0,bn = 1e9, ok = true;
      |                    ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 584 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 584 KB Output is correct
15 Correct 2 ms 3788 KB Output is correct
16 Correct 8 ms 7764 KB Output is correct
17 Correct 11 ms 8276 KB Output is correct
18 Correct 8 ms 8148 KB Output is correct
19 Correct 9 ms 8272 KB Output is correct
20 Correct 7 ms 7632 KB Output is correct
21 Correct 12 ms 8428 KB Output is correct
22 Correct 10 ms 8276 KB Output is correct
23 Correct 10 ms 8376 KB Output is correct
24 Correct 8 ms 7764 KB Output is correct
25 Correct 9 ms 8404 KB Output is correct
26 Correct 13 ms 8404 KB Output is correct
27 Correct 11 ms 8404 KB Output is correct
28 Correct 12 ms 8392 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 584 KB Output is correct
15 Correct 2 ms 3788 KB Output is correct
16 Correct 8 ms 7764 KB Output is correct
17 Correct 11 ms 8276 KB Output is correct
18 Correct 8 ms 8148 KB Output is correct
19 Correct 9 ms 8272 KB Output is correct
20 Correct 7 ms 7632 KB Output is correct
21 Correct 12 ms 8428 KB Output is correct
22 Correct 10 ms 8276 KB Output is correct
23 Correct 10 ms 8376 KB Output is correct
24 Correct 8 ms 7764 KB Output is correct
25 Correct 9 ms 8404 KB Output is correct
26 Correct 13 ms 8404 KB Output is correct
27 Correct 11 ms 8404 KB Output is correct
28 Correct 12 ms 8392 KB Output is correct
29 Correct 680 ms 203300 KB Output is correct
30 Correct 618 ms 199084 KB Output is correct
31 Correct 741 ms 211304 KB Output is correct
32 Correct 711 ms 211332 KB Output is correct
33 Correct 601 ms 189260 KB Output is correct
34 Correct 764 ms 211500 KB Output is correct
35 Correct 832 ms 227012 KB Output is correct
36 Correct 686 ms 202984 KB Output is correct
37 Correct 815 ms 227176 KB Output is correct