oj.uz

Submission #752825

# Submission time Handle Problem Language Result Execution time Memory
752825 2023-06-04T02:09:40 Z guagua0407 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1391 ms 102004 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2e3+5;
int a[mxn][mxn];
vector<int> vec;
int n,m;
int mn=1e9;
int mx=0;

bool check(int mid){
    int best=m;
    int sir[n];
    for(int i=0;i<n;i++){
        int j=0;
        while(j<best and a[i][j]<=mn+mid) j++;
        best=j;
        sir[i]=j;
    }
    int mnn=1e9;
    int mxx=0;
    for(int i=0;i<n;i++){
        for(int j=sir[i];j<m;j++){
            mnn=min(mnn,a[i][j]);
            mxx=max(mxx,a[i][j]);
        }
    }
    return (mxx-mnn)<=mid;
}

bool ok(int mid){
    if(check(mid)) return true;
    reverse(a,a+n);
    if(check(mid)) return true;
    for(int i=0;i<n;i++){
        reverse(a[i],a[i]+m);
    }
    if(check(mid)) return true;
    reverse(a,a+n);
    if(check(mid)) return true;
    return false;
}

signed main() {_
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            vec.push_back(a[i][j]);
            mx=max(mx,a[i][j]);
            mn=min(mn,a[i][j]);
        }
    }
    sort(all(vec));
    int l=0,r=mx-mn;
    while(l<r){
        int mid=(l+r)/2;
        if(ok(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<'\n';
    return 0;
}
//maybe its multiset not set

Compilation message

joioi.cpp: In function 'void setIO(std::string)':
joioi.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 6 ms 3924 KB Output is correct
17 Correct 16 ms 4180 KB Output is correct
18 Correct 16 ms 4180 KB Output is correct
19 Correct 15 ms 4172 KB Output is correct
20 Correct 14 ms 3668 KB Output is correct
21 Correct 21 ms 4308 KB Output is correct
22 Correct 29 ms 4180 KB Output is correct
23 Correct 18 ms 4232 KB Output is correct
24 Correct 18 ms 3796 KB Output is correct
25 Correct 20 ms 4308 KB Output is correct
26 Correct 20 ms 4316 KB Output is correct
27 Correct 27 ms 4312 KB Output is correct
28 Correct 23 ms 4312 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 6 ms 3924 KB Output is correct
17 Correct 16 ms 4180 KB Output is correct
18 Correct 16 ms 4180 KB Output is correct
19 Correct 15 ms 4172 KB Output is correct
20 Correct 14 ms 3668 KB Output is correct
21 Correct 21 ms 4308 KB Output is correct
22 Correct 29 ms 4180 KB Output is correct
23 Correct 18 ms 4232 KB Output is correct
24 Correct 18 ms 3796 KB Output is correct
25 Correct 20 ms 4308 KB Output is correct
26 Correct 20 ms 4316 KB Output is correct
27 Correct 27 ms 4312 KB Output is correct
28 Correct 23 ms 4312 KB Output is correct
29 Correct 926 ms 82064 KB Output is correct
30 Correct 906 ms 82348 KB Output is correct
31 Correct 997 ms 86232 KB Output is correct
32 Correct 1035 ms 86112 KB Output is correct
33 Correct 849 ms 75372 KB Output is correct
34 Correct 923 ms 86416 KB Output is correct
35 Correct 1391 ms 101948 KB Output is correct
36 Correct 1179 ms 92688 KB Output is correct
37 Correct 1359 ms 102004 KB Output is correct