oj.uz

Submission #493158

# Submission time Handle Problem Language Result Execution time Memory
493158 2021-12-10T07:34:47 Z Biaz The Kingdom of JOIOI (JOI17_joioi) C++17
15 / 100
 4000 ms 348 KB 
#include <bits/stdc++.h>
//#define int long long
//#define double long double
#define Nanase_Kurumi_aka_menhera_chan_is_mine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pi pair<double,int>
#define ALL(i) i.begin(),i.end()
#define gcd(i,j) __gcd(i,j)
#define fi first
#define se second
#define eps 0.00000001
#define ist insert
#define DNE nullptr
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC optimize("O2")
int max(int x,int y){return x>=y?x:y;}
int min(int x,int y){return x>=y?y:x;}
using namespace std;
typedef int ll;
const int N=2005;
const int M=1000005;
const int MOD=1000000007;//998244353;
const int INF=2147483647;//1000000000000000000;

int n,m,ans;
int a[N][N];
int premx[N][N],sufmx[N][N],premn[N][N],sufmn[N][N];
vector<int> vc,res;
int calc(){
    int mx=0,mn=INF,sum=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=vc[i];j++)
            mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
        /*mx=max(mx,premx[i][vc[i]]);
        mn=min(mn,premn[i][vc[i]]);*/
    }
    sum+=mx-mn;
    mx=0;mn=INF;
    for (int i=1;i<=n;i++){
        for (int j=vc[i]+1;j<=m;j++)
            mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
        /*mx=max(mx,sufmx[i][vc[i]+1]);
        mn=min(mn,sufmn[i][vc[i]+1]);*/
    }
    //sum+=mx-mn;
    return max(sum,mx-mn);
}
int _calc(vector<int> &t){
    int mx=0,mn=INF,sum=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=t[i];j++)
            mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
        /*mx=max(mx,premx[i][t[i]]);
        mn=min(mn,premn[i][t[i]]);*/
    }
    sum+=mx-mn;
    mx=0;mn=INF;
    for (int i=1;i<=n;i++){
        for (int j=t[i]+1;j<=m;j++)
            mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);

        /*mx=max(mx,sufmx[i][t[i]+1]);
        mn=min(mn,sufmn[i][t[i]+1]);*/
    }
    //sum+=mx-mn;
    return max(sum,mx-mn);
}
void dfs(int i){
    if (i==n){
        ans=min(ans,calc());
        vector<int> t(ALL(vc));t.pb(0);
        reverse(ALL(t));
        ans=min(ans,_calc(t));
        return;
    }
    for (int k=vc.back();k<=m;k++){
        vc.pb(k);
        dfs(i+1);
        vc.pop_back();
    }
}
inline void sol(){
    cin >>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin >>a[i][j];
    /*for (int i=1;i<=n;i++){
        fill(premn[i],premn[i]+m+1,INF);
        fill(sufmn[i],sufmn[i]+m+1,INF);
        for (int j=1;j<=m;j++){
            premx[i][j]=max(a[i][j],premx[i][j-1]);
            premn[i][j]=min(a[i][j],premn[i][j-1]);
        }
        for (int j=m;j>=1;j--){
            sufmx[i][j]=max(a[i][j],sufmx[i][j+1]);
            sufmn[i][j]=min(a[i][j],sufmn[i][j+1]);
        }
    }*/
    ans=INF;
    vc.pb(0);
    for (int i=0;i<=m;i++){
        vc.pb(i);
        dfs(1);
        vc.pop_back();
    }
    cout <<ans<<'\n';
    //for (int &i:res) cout <<i<<' ';
}

signed main(){
    Nanase_Kurumi_aka_menhera_chan_is_mine
    int _=1;
    //cin >>_;
    while (_--) sol();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 77 ms 336 KB Output is correct
4 Correct 37 ms 336 KB Output is correct
5 Correct 75 ms 324 KB Output is correct
6 Correct 18 ms 336 KB Output is correct
7 Correct 76 ms 336 KB Output is correct
8 Correct 78 ms 348 KB Output is correct
9 Correct 76 ms 336 KB Output is correct
10 Correct 79 ms 336 KB Output is correct
11 Correct 81 ms 344 KB Output is correct
12 Correct 76 ms 336 KB Output is correct
13 Correct 79 ms 348 KB Output is correct
14 Correct 76 ms 348 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 77 ms 336 KB Output is correct
4 Correct 37 ms 336 KB Output is correct
5 Correct 75 ms 324 KB Output is correct
6 Correct 18 ms 336 KB Output is correct
7 Correct 76 ms 336 KB Output is correct
8 Correct 78 ms 348 KB Output is correct
9 Correct 76 ms 336 KB Output is correct
10 Correct 79 ms 336 KB Output is correct
11 Correct 81 ms 344 KB Output is correct
12 Correct 76 ms 336 KB Output is correct
13 Correct 79 ms 348 KB Output is correct
14 Correct 76 ms 348 KB Output is correct
15 Execution timed out 4058 ms 336 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 77 ms 336 KB Output is correct
4 Correct 37 ms 336 KB Output is correct
5 Correct 75 ms 324 KB Output is correct
6 Correct 18 ms 336 KB Output is correct
7 Correct 76 ms 336 KB Output is correct
8 Correct 78 ms 348 KB Output is correct
9 Correct 76 ms 336 KB Output is correct
10 Correct 79 ms 336 KB Output is correct
11 Correct 81 ms 344 KB Output is correct
12 Correct 76 ms 336 KB Output is correct
13 Correct 79 ms 348 KB Output is correct
14 Correct 76 ms 348 KB Output is correct
15 Execution timed out 4058 ms 336 KB Time limit exceeded
16 Halted 0 ms 0 KB -