Submission #1267784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267784		enzy	Sandcastle 2 (JOI22_ho_t5)	C++20	10 / 100	5 ms	11076 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int v[maxn][maxn], ma[maxn][maxn][maxn], id[maxn][maxn][maxn], marc[maxn][maxn], dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, qtd;
bool in(int x, int y, int lx, int ly, int ux, int uy){
    return lx<=x&&x<=ux&&ly<=y&&y<=uy;
}
void dfs(int x, int y, int c, int lx, int ly, int ux, int uy){
    marc[x][y]=c; qtd++;
    //cout << x << " " << y << endl;
    vector<pair<int,pair<int,int>>>process;
    for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(in(nx,ny,lx,ly,ux,uy)&&marc[nx][ny]!=c&&v[x][y]>v[nx][ny]) process.push_back({-v[nx][ny],{nx,ny}});
    }
    sort(process.begin(),process.end());
    if(!process.size()) return;
    auto p=process[0];
    dfs(p.second.first,p.second.second,c,lx,ly,ux,uy);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int h, w; cin >> h >> w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
            cin >> v[i][j];
            ma[i][j][j]=v[i][j];
            id[i][j][j]=j;
        }
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            for(int k=j+1;k<=w;k++){
                ma[i][j][k]=max(ma[i][j][k-1],v[i][k]);
                if(ma[i][j][k-1]<v[i][k]) id[i][j][k]=k;
                else id[i][j][k]=id[i][j][k-1];
            }
    int resp=0, c=0;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            for(int k=i;k<=h;k++)
                for(int l=j;l<=w;l++){
                    int ix, iy, best=0;
                    for(int aux=i;aux<=k;aux++){
                        if(best<ma[aux][j][l]){
                            best=ma[aux][j][l];
                            ix=aux; iy=id[aux][j][l];
                        }
                    }
                    qtd=0;
                    dfs(ix,iy,++c,i,j,k,l);
                    int need=(k-i+1)*(l-j+1);
                    //cout << j << " " << l << " " << qtd << " " << need << " " << iy << endl << endl;
                    if(qtd==need){
                        //cout << j << " " << l << endl;
                        resp++;
                    }
                }
    cout << resp << endl;
}

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