oj.uz

Submission #93942

# Submission time Handle Problem Language Result Execution time Memory
93942 2019-01-13T16:10:49 Z ahmedie404 Pohlepko (COCI16_pohlepko) C++14
80 / 80
 157 ms 8184 KB 
#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> point;
#define x first
#define y second

const int MAX = 2010;

int n, m;
char grid[MAX][MAX];
bool vis[MAX][MAX];

int main(void) {

  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> grid[i];

  vector< point > curr, next;
  for (curr.push_back({0, 0}); !curr.empty(); curr = next) {
    point p = curr.back();
    cout << grid[p.x][p.y];

    char mn = 'z';
    for (point pt : curr) {
      int dx = 1, dy = 0;
      for (int i = 0; i < 2; ++i) {
        swap(dx, dy);
        int nx = pt.x + dx;
        int ny = pt.y + dy;
        if (nx >= n || ny >= m) continue;
        mn = min(mn, grid[nx][ny]);
      }
    }

    next.clear();
    for (point pt : curr) {
      int dx = 1, dy = 0;
      for (int i = 0; i < 2; ++i) {
        swap(dx, dy);
        int nx = pt.x + dx;
        int ny = pt.y + dy;
        if (nx >= n || ny >= m) continue;
        if (vis[nx][ny]) continue;
        if (grid[nx][ny] == mn) {
          next.push_back({nx, ny});
          vis[nx][ny] = 1;
        }
      }
    }
  }

  cout << endl;

  return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 9 ms 1656 KB Output is correct
7 Correct 41 ms 5624 KB Output is correct
8 Correct 157 ms 8176 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 13 ms 4216 KB Output is correct
13 Correct 13 ms 8184 KB Output is correct
14 Correct 110 ms 8156 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 57 ms 6264 KB Output is correct