Submission #529462

#	Time	Username	Problem	Language	Result	Execution time	Memory
529462		wiwiho	Sandcastle 2 (JOI22_ho_t5)	C++14	0 / 100	1395 ms	1048580 KiB

Main

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

struct rect{
    int u, d, l, r;
    int cnt = 1;
    int area(){
        return (r - l + 1) * (d - u + 1);
    }
};

rect merge(rect a, rect b){
    rect c;
    c.l = min(a.l, b.l);
    c.r = max(a.r, b.r);
    c.u = min(a.u, b.u);
    c.d = max(a.d, b.d);
    c.cnt = a.cnt + b.cnt;
    return c;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int h, w;
    cin >> h >> w;

    vector<vector<int>> a(h + 2, vector<int>(w + 2, INT_MAX));

    vector<pair<int, pii>> tmp;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
            tmp.eb(mp(a[i][j], mp(i, j)));
        }
    }
    lsort(tmp);

    vector<vector<vector<rect>>> dp(h + 2, vector<vector<rect>>(w + 2));
    
    vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
    for(auto i : tmp){
        int x = i.S.F, y = i.S.S;
        rect r({x, x, y, y});
        dp[x][y].eb(r);
        for(auto d : dir){
            int nx = x + d.F, ny = y + d.S;
            if(a[nx][ny] >= a[x][y]) continue;
            for(rect& j : dp[nx][ny]){
                dp[x][y].eb(merge(r, j));
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            for(rect r : dp[i][j]){
                if(r.area() == r.cnt) ans++;
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

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