oj.uz

Submission #23068

# Submission time Handle Problem Language Result Execution time Memory
23068 2017-05-02T15:14:54 Z model_code Pohlepko (COCI16_pohlepko) C++11
80 / 80
 146 ms 9908 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 0 ms 9908 KB Output is correct
2 Correct 0 ms 9908 KB Output is correct
3 Correct 0 ms 9908 KB Output is correct
4 Correct 0 ms 9908 KB Output is correct
5 Correct 0 ms 9908 KB Output is correct
6 Correct 13 ms 9908 KB Output is correct
7 Correct 46 ms 9908 KB Output is correct
8 Correct 146 ms 9908 KB Output is correct
9 Correct 0 ms 9908 KB Output is correct
10 Correct 3 ms 9908 KB Output is correct
11 Correct 3 ms 9908 KB Output is correct
12 Correct 16 ms 9908 KB Output is correct
13 Correct 16 ms 9908 KB Output is correct
14 Correct 139 ms 9908 KB Output is correct
15 Correct 0 ms 9908 KB Output is correct
16 Correct 73 ms 9908 KB Output is correct