Submission #1160677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160677		qin	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	320 KiB

joioi

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define mp make_pair
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, ll b){
    int ret = 1;
    while(b){
        if(b & 1) ret = mul(ret, a);
        b >>= 1, a = mul(a, a);
    } return ret;
}
int inv(int a){ return fpow(a, mod-2); }
struct coeff{
    V<int> fac, invfac;
    coeff(int n){
        fac.resize(n+1), invfac.resize(n+1);
        fac[0] = 1, invfac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
        invfac[n] = inv(fac[n]);
        for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
    }
    int get(int n, int k){
        if(n < k) return 0;
        return mul(fac[n], mul(invfac[n-k], invfac[k]));
    }
};
void answer(){
    int n, m; scanf("%d%d", &n, &m);
    V<V<int>> t(n+1, V<int>(m+1, 0));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]);

    int mn = inf, mx = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            mn = min(mn, t[i][j]), mx = max(mx, t[i][j]);
    
    auto calc = [&](){
        int result = inf;
        V<V<pii>> p(n+1, V<pii>(m+2, pii(0, 0)));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j)
                p[i][j].fi = max(p[i][j-1].fi, t[i][j]-mn);
            for(int j = m; j >= 1; --j)
                p[i][j-1].se = max(p[i][j+1].se, mx-t[i][j]);
        }

        V<V<int>> dp(n+1, V<int>(m+2, inf));
        for(int i = 0; i <= m; ++i) dp[0][i] = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= m; ++j){
                for(int l = j; l <= m; ++l) dp[i][j] = min(dp[i][j], dp[i-1][l]);
                dp[i][j] = max(dp[i][j], max(p[i][j].fi, p[i][j].se));
            }
        }
        // pn;
        // // printf("%d %d\n\n", mn, mx);

        // for(int i = 1; i <= n; ++i){
        //     for(int j = 0; j <= m; ++j) printf("%d %d,", p[i][j].fi, p[i][j].se);
        //     pn;
        // }
        // pn;

        for(int i = 0; i <= m; ++i)
            result = min(result, dp[n][i]);

        dp = V<V<int>>(n+1, V<int>(m+2, inf));
        for(int i = 0; i <= m; ++i) dp[0][i] = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j <= m; ++j){
                for(int l = 0; l <= j; ++l) dp[i][j] = min(dp[i][j], dp[i-1][l]);
                dp[i][j] = max(dp[i][j], max(p[i][j].fi, p[i][j].se));
            }
        }
        for(int i = 0; i <= m; ++i)
            result = min(result, dp[n][i]);
        
        // for(int i = 1; i <= n; ++i){
        //     for(int j = 0; j <= m; ++j) printf("%d ", dp[i][j]);
        //     pn;
        // }
        
        return result;
    };

    int result = mx-mn;
    result = min(result, calc());
    for(int i = 1; i <= n; ++i) reverse(1+all(t[i]));
    result = min(result, calc());
    printf("%d\n", result);
}
int main(){
		int T = 1;
		// scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'void answer()':
joioi.cpp:53:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     int n, m; scanf("%d%d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:56:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]);
      |                                     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40