제출 #1141597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141597		KasymK	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	100 ms	43828 KiB

maxcomp

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e3+5;
const ll INF = 1e18;
const int INF_ = 1e9;
int v[N][N];
ll pn[N][N], px[N][N];

void reload(int n, int m){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            pn[i][j]=INF, px[i][j]=-INF;
}

void rev(int x, int m){
    for(int i = 1; i <= m/2; ++i)
        swap(v[x][i], v[x][m-i+1]);
}

struct node {
    int mx, mn, sz;
    ll val;
    node(){
        mx=-INF_, mn=INF_, sz=0;
        val=-INF;
    };
} dp[N][N];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    auto is=[&](int a, int b) -> bool {
        return (a>=1 and a<=n and b>=1 and b<=m);
    };
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            scanf("%d", &v[i][j]);
    ll answer=-INF;
    reload(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            ll val=INF, val2=-INF;
            if(is(i-1, j))
                umin(val, pn[i-1][j]), umax(val2, px[i-1][j]);
            if(is(i, j-1))
                umin(val, pn[i][j-1]), umax(val2, px[i][j-1]);
            umax(answer, max(v[i][j]-val, val2-v[i][j])-i-j-1);
            pn[i][j]=min(val, (v[i][j]-i-j)*1ll), px[i][j]=max(val2, (v[i][j]+i+j)*1ll);
        }
    for(int i = 1; i <= n; ++i)
        rev(i, m);
    reload(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            ll val=INF, val2=-INF;
            if(is(i-1, j))
                umin(val, pn[i-1][j]), umax(val2, px[i-1][j]);
            if(is(i, j-1))
                umin(val, pn[i][j-1]), umax(val2, px[i][j-1]);
            umax(answer, max(v[i][j]-val, val2-v[i][j])-i-j-1);
            pn[i][j]=min(val, (v[i][j]-i-j)*1ll), px[i][j]=max(val2, (v[i][j]+i+j)*1ll);
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            // 1-> up
            if(is(i-1, j)){
                if(umax(dp[i][j].val, (max(dp[i-1][j].mx, v[i][j])-min(dp[i-1][j].mn, v[i][j])-dp[i-1][j].sz-1)*1ll))
                    umax(dp[i][j].mx, max(dp[i-1][j].mx, v[i][j])), umin(dp[i][j].mn, min(dp[i-1][j].mn, v[i][j])), dp[i][j].sz=dp[i-1][j].sz+1;
            }
            // 2-> left
            if(is(i, j-1)){
                if(umax(dp[i][j].val, (max(dp[i][j-1].mx, v[i][j])-min(dp[i][j-1].mn, v[i][j])-dp[i][j-1].sz-1)*1ll))
                    umax(dp[i][j].mx, max(dp[i][j-1].mx, v[i][j])), umin(dp[i][j].mn, min(dp[i][j-1].mn, v[i][j])), dp[i][j].sz=dp[i][j-1].sz+1;
            }
            // 3-> start new
            if(umax(dp[i][j].val, -1*1ll))
                dp[i][j].mx=v[i][j], dp[i][j].mn=v[i][j], dp[i][j].sz=1;
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            umax(answer, dp[i][j].val);
    printf("%lld\n", answer);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
maxcomp.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |             scanf("%d", &v[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40