oj.uz

Submission #733130

# Submission time Handle Problem Language Result Execution time Memory
733130 2023-04-30T06:53:22 Z ac2hu The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 624 ms 70688 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int H, W;cin >> H >> W;
    int v = -1, x = -1, y = -1;
    vector<vector<int>> a(H, vector<int>(W));
    for(int i = 0;i<H;i++){
        for(int j = 0;j<W;j++){
            cin >> a[i][j];
            if(a[i][j] > v)v = a[i][j], x = i, y = j;
        }
    }
    auto check2 = [&](vector<int> v, int siz){
        int mn = 1e9, mx = -1e9;
        for(int i = 0;i<H;i++){
            for(int j = W - 1;j>v[i];j--){
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        if(mx - mn <= siz)return true;
        else return false;
    };
    auto check3 = [&](vector<int> v, int siz){
        int mn = 1e9, mx = -1e9;
        for(int i = 0;i<H;i++){
            for(int j = 0;j<v[i];j++){
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        if(mx - mn <= siz)return true;
        else return false;
    };
    auto check = [&](int siz){
        int maximum = v;
        {
            // Case1: build it from 0 onwards
            vector<int> c;
            for(int i = 0;i<H;i++){
                bool used = false;
                for(int j = 0;j<W;j++){
                    if(maximum - a[i][j] > siz){
                        c.push_back(j - 1);
                        used = true;
                        break;
                    }
                }
                if(!used)c.push_back(W - 1);
            } 
            if(c[x] >= y){
                vector<int> f = c;
                for(int i = 1;i<H;i++)f[i] = min(f[i],f[i - 1]);
                if(check2(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)f[i] = min(f[i], f[i + 1]);
                if(check2(f, siz)){
                    return true;
                }
            }
        }
        {

            // Case2: build it fron W - 1
            vector<int> c;
            for(int i = 0;i<H;i++){
                bool used = false;
                for(int j = W - 1;j>=0;j--){
                    if(maximum - a[i][j] > siz){
                        c.push_back(j + 1);
                        used = true;
                        break;
                    }
                }
                if(!used)c.push_back(0);
            } 
            if(c[x] <= y){
                vector<int> f = c;
                for(int i = 1;i<H;i++)f[i] = max(f[i],f[i - 1]);
                if(check3(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)f[i] = max(f[i], f[i + 1]);
                if(check3(f, siz)){
                    return true;
                }
            }
        }
        return false;
    };
    int l = 0, r = 1e9 + 1e8;
    while(l < r){
        int mid = (l + r - 1)/2;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
}

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 5 ms 852 KB Output is correct
19 Correct 5 ms 912 KB Output is correct
20 Correct 4 ms 852 KB Output is correct
21 Correct 8 ms 1016 KB Output is correct
22 Correct 9 ms 1008 KB Output is correct
23 Correct 8 ms 972 KB Output is correct
24 Correct 6 ms 948 KB Output is correct
25 Correct 10 ms 980 KB Output is correct
26 Correct 15 ms 980 KB Output is correct
27 Correct 7 ms 1008 KB Output is correct
28 Correct 7 ms 1008 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 5 ms 852 KB Output is correct
19 Correct 5 ms 912 KB Output is correct
20 Correct 4 ms 852 KB Output is correct
21 Correct 8 ms 1016 KB Output is correct
22 Correct 9 ms 1008 KB Output is correct
23 Correct 8 ms 972 KB Output is correct
24 Correct 6 ms 948 KB Output is correct
25 Correct 10 ms 980 KB Output is correct
26 Correct 15 ms 980 KB Output is correct
27 Correct 7 ms 1008 KB Output is correct
28 Correct 7 ms 1008 KB Output is correct
29 Correct 443 ms 52280 KB Output is correct
30 Correct 427 ms 50932 KB Output is correct
31 Correct 492 ms 54852 KB Output is correct
32 Correct 395 ms 54736 KB Output is correct
33 Correct 431 ms 47800 KB Output is correct
34 Correct 411 ms 54980 KB Output is correct
35 Correct 602 ms 70528 KB Output is correct
36 Correct 587 ms 61476 KB Output is correct
37 Correct 624 ms 70688 KB Output is correct