oj.uz

Submission #593643

# Submission time Handle Problem Language Result Execution time Memory
593643 2022-07-11T13:09:41 Z oleh1421 Sandcastle 2 (JOI22_ho_t5) C++17
10 / 100
 5000 ms 852 KB 
//#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5055 ms 852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Execution timed out 5069 ms 340 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Execution timed out 5069 ms 340 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Execution timed out 5069 ms 340 KB Time limit exceeded
8 Halted 0 ms 0 KB -