Submission #209938

#	Time	Username	Problem	Language	Result	Execution time	Memory
209938		EntityIT	Sandwich (JOI16_sandwich)	C++14	100 / 100	2703 ms	8440 KiB

sandwich

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n, m;
vector<vector<int> > a;

bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

array<int, 4> dx{ -1, 0, 1, 0 }, dy{ 0, -1, 0, 1 };
vector<vector<int> > f;
int F(int x, int y, int dir) {
  if (!valid(x, y) ) return 0;

  if (dir & 1) dir ^= a[x][y];

  if (~f[x][y]) return f[x][y] ^ inf ? 0 : inf;
  f[x][y] = inf;

  int tmp1 = F(x + dx[dir], y + dy[dir], dir),
      tmp2 = F(x + dx[dir ^ a[x][y] ], y + dy[dir ^ a[x][y] ], dir ^ a[x][y]);
  if (tmp1 ^ inf && tmp2 ^ inf) f[x][y] = 2 + tmp1 + tmp2;

  return f[x][y];
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n >> m;
  a.assign(n, vector<int>(m) );
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      char c; cin >> c;
      a[i][j] = c == 'N' ? 3 : 1;
    }
  }

  vector<vector<int> > ans(n, vector<int>(m, inf) );
  for (int j = 0; j < m; ++j) {
    for (const auto &dir : array<int, 2>{ 0, 2 }) {
      int sum = 0;
      f.assign(n, vector<int>(m, -1) );
      if (!dir) {
        for (int i = 0; i < n; ++i) {
          int tmp = F(i, j, dir);
          if (tmp == inf) break ;
          sum += tmp;
          asMn(ans[i][j], sum);
        }
      }
      else {
        for (int i = n - 1; ~i; --i) {
          int tmp = F(i, j, dir);
          if (tmp == inf) break ;
          sum += tmp;
          asMn(ans[i][j], sum);
        }
      }
    }
  }

  for (const auto &i : ans) {
    for (const auto &j : i) cout << (j ^ inf ? j : -1) << ' ';
    cout << '\n';
  }

  return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65