Submission #593643

#	Time	Username	Problem	Language	Result	Execution time	Memory
593643		oleh1421	Sandcastle 2 (JOI22_ho_t5)	C++17	10 / 100	5069 ms	852 KiB

Main

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const ll inf=1e18;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=510;
const int Lg=16;
vector<vector<int> >a;
bool ok(int x1,int y1,int x2,int y2){
    int cnt=0;
    for (int i=x1;i<=x2;i++){
        for (int j=y1;j<=y2;j++){
            int x=-1,y=-1;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=i+dx,ny=j+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]<a[i][j]) continue;
                    if (x==-1 || a[x][y]>a[nx][ny]){
                        x=nx;
                        y=ny;
                    }
                }
            }
            if (x==-1) continue;
            cnt++;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=x+dx,ny=y+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]<a[x][y] && a[i][j]<a[nx][ny]) return false;
                }
            }
        }
    }

    for (int i=x1;i<=x2;i++){
        for (int j=y1;j<=y2;j++){
            int x=-1,y=-1;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=i+dx,ny=j+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]>a[i][j]) continue;
                    if (x==-1 || a[x][y]<a[nx][ny]){
                        x=nx;
                        y=ny;
                    }
                }
            }
            if (x==-1) continue;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=x+dx,ny=y+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]>a[x][y] && a[i][j]>a[nx][ny]) return false;
                }
            }
        }
    }
    return (cnt==((x2-x1+1)*(y2-y1+1)-1));
}
void solve(){
    int n,m;cin>>n>>m;
    a.resize(n);
    for (int i=0;i<n;i++){
        a[i].resize(m);
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int res=0;
    for (int x1=0;x1<n;x1++){
        for (int y1=0;y1<m;y1++){
            for (int x2=x1;x2<n;x2++){
                for (int y2=y1;y2<m;y2++){
                    if (ok(x1,y1,x2,y2)) {
                        res++;
//                        cout<<y1<<" "<<y2<<endl;
                    }
                }
            }
        }
    }
    cout<<res<<endl;
}
int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

• Subtask 1: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 0 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20