oj.uz

Submission #526913

# Submission time Handle Problem Language Result Execution time Memory
526913 2022-02-16T16:18:40 Z eecs Sandcastle 2 (JOI22_ho_t5) C++17
19 / 100
 5000 ms 880 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50010;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int h, w, ans, tim, a[maxn], vis[maxn];

int id(int x, int y) {
    return (x - 1) * w + y;
}

int main() {
    scanf("%d %d", &h, &w);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            scanf("%d", &a[id(i, j)]);
        }
    }
    if (h == 1) {
        static int f[maxn], id[maxn];
        fill(f + 1, f + w + 1, 1);
        iota(id + 1, id + w + 1, 1);
        sort(id + 1, id + w + 1, [&](int x, int y) { return a[x] < a[y]; });
        for (int i = 1; i <= w; i++) {
            int x = id[i];
            if (x > 1 && a[x - 1] < a[x]) f[x] += f[x - 1];
            if (x < w && a[x + 1] < a[x]) f[x] += f[x + 1];
        }
        printf("%lld\n", accumulate(f + 1, f + w + 1, 0LL)), exit(0);
    }
    for (int lx = 1; lx <= h; lx++) for (int rx = lx; rx <= h; rx++) {
        for (int ly = 1; ly <= w; ly++) for (int ry = ly; ry <= w; ry++) {
            int mx = 0, x, y;
            for (int i = lx; i <= rx; i++) {
                for (int j = ly; j <= ry; j++) {
                    if (a[id(i, j)] > mx) mx = a[id(i, j)], x = i, y = j;
                }
            }
            tim++;
            bool flag = 1;
            for (int i = 1; i <= (rx - lx + 1) * (ry - ly + 1); i++) {
                if (vis[id(x, y)] == tim) { flag = 0; break; }
                vis[id(x, y)] = tim, mx = 0;
                int foo = x, bar = y;
                for (int d = 0; d < 4; d++) {
                    int _x = x + dx[d], _y = y + dy[d];
                    if (_x < lx || _x > rx || _y < ly || _y > ry) continue;
                    if (a[id(x, y)] > a[id(_x, _y)] && a[id(_x, _y)] > mx) mx = a[id(_x, _y)], foo = _x, bar = _y;
                }
                x = foo, y = bar;
            }
            if (flag) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:16:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |             scanf("%d", &a[id(i, j)]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:9:26: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 |     return (x - 1) * w + y;
      |                          ^
Main.cpp:33:28: note: 'y' was declared here
   33 |             int mx = 0, x, y;
      |                            ^
Main.cpp:9:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 |     return (x - 1) * w + y;
      |            ~~~^~~~
Main.cpp:33:25: note: 'x' was declared here
   33 |             int mx = 0, x, y;
      |                         ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 10 ms 880 KB Output is correct
3 Correct 13 ms 844 KB Output is correct
4 Correct 11 ms 868 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 9 ms 844 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 3 ms 308 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 3 ms 308 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Execution timed out 5064 ms 204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 3 ms 308 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Execution timed out 5064 ms 204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 3 ms 308 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Execution timed out 5064 ms 204 KB Time limit exceeded
8 Halted 0 ms 0 KB -