oj.uz

Submission #594200

# Submission time Handle Problem Language Result Execution time Memory
594200 2022-07-12T08:17:30 Z 박상훈(#8431) Sandcastle 2 (JOI22_ho_t5) C++17
19 / 100
 5000 ms 1152 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int n, m, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<int>> a;

void solve1(){
    int pt = 0;
    ll ans = 0;
    bool flag;
    for (int i=1;i<=m;i++){
        if (i==m) {ans++; break;}
        if (pt<=i){
           pt = i+1;
           flag = (a[1][i] < a[1][pt]);
        }

        while(pt<m && flag==(a[1][pt] < a[1][pt+1])) pt++;
        ans += pt - i + 1;

        //printf("%d: %d\n", i, pt);
    }
    printf("%lld\n", ans);
    exit(0);
}

int calc(int x1, int x2, int y1, int y2){
    vector<int> V;
    for (int i=x1;i<=x2;i++){
        for (int j=y1;j<=y2;j++){
            V.push_back(a[i][j]);
        }
    }

    sort(V.begin(), V.end());

    int x = 0, y = 0, idx = 0;
    for (int i=x1;i<=x2;i++){
        for (int j=y1;j<=y2;j++){
            if (V[0]==a[i][j]){
                x = i, y = j;
            }
        }
    }

    while(idx+1<(int)V.size()){
        for (int k=0;k<4;k++){
            int nx = x + dx[k], ny = y + dy[k];
            if (a[nx][ny]==V[idx+1]) {x = nx, y = ny; break;}
        }
        if (a[x][y]==V[idx]) return 0;
        idx++;
    }
    return 1;
}

int main(){
    scanf("%d %d", &n, &m);
    a.resize(n+2, vector<int>(m+2, 0));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            scanf("%d", &a[i][j]);
        }
    }

    if (n==1) solve1();

    ll ans = 0;
    for (int i1=1;i1<=n;i1++){
        for (int i2=i1;i2<=n;i2++){
            for (int j1=1;j1<=m;j1++){
                for (int j2=j1;j2<=m;j2++){
                    ans += calc(i1, i2, j1, j2);
                }
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve1()':
Main.cpp:19:20: warning: 'flag' may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |         while(pt<m && flag==(a[1][pt] < a[1][pt+1])) pt++;
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 9 ms 1112 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 224 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Execution timed out 5021 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 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 224 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Execution timed out 5021 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 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 224 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Execution timed out 5021 ms 340 KB Time limit exceeded
8 Halted 0 ms 0 KB -