oj.uz

Submission #824461

# Submission time Handle Problem Language Result Execution time Memory
824461 2023-08-14T06:34:47 Z PoonYaPat Sandcastle 2 (JOI22_ho_t5) C++14
19 / 100
 5000 ms 6428 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1632 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct
4 Correct 4 ms 1620 KB Output is correct
5 Correct 4 ms 1600 KB Output is correct
6 Correct 4 ms 1620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 8 ms 388 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 380 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 8 ms 388 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Execution timed out 5061 ms 6428 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 8 ms 388 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Execution timed out 5061 ms 6428 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 8 ms 388 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Execution timed out 5061 ms 6428 KB Time limit exceeded
8 Halted 0 ms 0 KB -