Submission #824461

#	Time	Username	Problem	Language	Result	Execution time	Memory
824461		PoonYaPat	Sandcastle 2 (JOI22_ho_t5)	C++14	19 / 100	5061 ms	6428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int h,w,c[5000][5000],val[50005];
ll ans,dp1[50005],dp2[50005];
map<int,int> mp;

int cc=0;
void dfs(int x, int y) {
    ++cc;
    if (mp[c[x-1][y]]==cc+1) dfs(x-1,y);
    else if (mp[c[x+1][y]]==cc+1) dfs(x+1,y);
    else if (mp[c[x][y-1]]==cc+1) dfs(x,y-1);
    else if (mp[c[x][y+1]]==cc+1) dfs(x,y+1);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>h>>w;
    if (h==1) {
        
        for (int i=1; i<=w; ++i) cin>>val[i];
        
        for (int i=1; i<=w; ++i) {
            if (i && val[i]>val[i-1]) dp1[i]=dp1[i-1]+1;
            else dp1[i]=1;
            ans+=dp1[i];
        }

        for (int i=w; i>=1; --i) {
            if (i!=w && val[i]>val[i+1]) dp2[i]=dp2[i+1]+1;
            else dp2[i]=1;
            ans+=dp2[i]-1;
        }

        cout<<ans;

    } else {
        for (int i=1; i<=h; ++i) for (int j=1; j<=w; ++j) cin>>c[i][j];
        for (int x1=1; x1<=h; ++x1) {
            for (int y1=1; y1<=w; ++y1) {
                for (int x2=x1; x2<=h; ++x2) {
                    for (int y2=y1; y2<=w; ++y2) {

                        mp.clear();
                        cc=0;
                        int mi=INT_MAX,X,Y;

                        for (int x=x1; x<=x2; ++x) {
                            for (int y=y1; y<=y2; ++y) {
                                mp[c[x][y]]=0;
                                if (c[x][y]<mi) {
                                    mi=c[x][y];
                                    X=x;
                                    Y=y;
                                }
                            }
                        }

                        int cnt=0;
                        for (auto s : mp) mp[s.first]=++cnt;
                        dfs(X,Y);
                        if (cc==(x2-x1+1)*(y2-y1+1)) ++ans;
                    }
                }
            }
        }
        cout<<ans;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:63:28: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |                         dfs(X,Y);
      |                         ~~~^~~~~
Main.cpp:63:28: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]

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