Submission #1602700

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAIN

const int h = 30, w = 30;
int board[30][30], d[30][30][30][30];

signed main(void)
{
  REP(i, h) REP(j, w) cin >> board[i][j];

  vector<PII> ans;
  int score = 0;

  bool update = true;
  while(update) {
    int ma = 0, sx, sy, gx, gy;
    REP(i, h) REP(j, w) {
      if(board[i][j] == 0) continue;
      // cout << i << " " << j << endl;
      // (i, j)始点のLISを求める
      queue<PII> que;
      REP(k, h) REP(l, w) d[i][j][k][l] = INF;
      que.push(PII{j, i});
      d[i][j][i][j] = 0;

      while(que.size()) {
        PII p = que.front(); que.pop();
        int y = p.second, x = p.first;
        // if(i == 19 && j == 17) cout << x << " " << y << " " << d[i][j][p.second][p.first] << " " << board[y][x] << endl;
        REP(a, 4) {
          int nx = x + dx[a], ny = y + dy[a];
          if(IN(0, w, nx) && IN(0, h, ny)
            && board[y][x] > board[ny][nx] && d[i][j][ny][nx] == INF
            && board[ny][nx]) {
            // if(i == 19 && j == 17) cout << board[y][x] << " " << board[ny][nx] << endl;
            que.push(PII{nx, ny});
            d[i][j][ny][nx] = d[i][j][y][x] + 1;
            if(ma < d[i][j][ny][nx]) {
              ma = d[i][j][ny][nx];
              sx = j, sy = i, gx = nx, gy = ny;
              // cout << ma << " " << sx << " " << sy << " " << gx << " " << gy << endl;
            }
          }
        }
      }
    }
    if(!ma) break;
    // REP(i, h) {
    //   REP(j, w) {
    //     if(d[sy][sx][i][j] == INF) cout << -1 << " ";
    //     else cout << d[sy][sx][i][j] << " ";
    //   }
    //   cout << endl;
    // }
    // cout << "---------------" << endl;
    // cout << ma << " " << sx << " " << sy << " " << gx << " " << gy << endl;
    // REP(i, h) {
    //   REP(j, w) {
    //     cout << board[i][j] << " ";
    //   }
    //   cout << endl;
    // }
    // maxのLISを消す
    // 連続列をつくる
    int x = gx, y = gy;
    vector<PII> v;
    v.PB({y, x});
    REP(_, ma) {
      // cout << y << " " << x << endl;
      REP(i, 4) {
        int nx = x+dx[i], ny = y+dy[i];
        if(IN(0, w, nx) && IN(0, h, ny) && d[sy][sx][y][x] == d[sy][sx][ny][nx] + 1 && board[ny][nx] > board[y][x]) {
          // cout << ny << " " << nx << endl;
          while(board[ny][nx] > board[y][x]+1) {
            score++, board[ny][nx]--;
            ans.PB({ny, nx});
          }
          y = ny, x = nx;
          if(board[y][x] < 0) return 0;
          v.PB({y, x});
          // cout << y << " " << x << endl;
          break;
        }
      }
    }
    // cout << "a" << endl;
    // if(sx == 0 && sy == 0) {
    // }
    reverse(ALL(v));
    // for(auto i: v) cout << i.first << " " << i.second << endl;
    REP(i, v.size()) {
      int len = v.size()-i;
      score++;
      REP(j, len) {
        ans.PB({v[j].first, v[j].second});
        board[v[j].first][v[j].second]--;
        // cout << v[j].first << " " << v[j].second << " " << board[v[j].first][v[j].second] << endl;
      }
    }
  }

  REP(i, h) {
    REP(j, w) {
      while(board[i][j]) board[i][j]--, ans.PB({i, j}), score++;
    }
  }
  //
  // REP(i, h) {
  //   REP(j, w) {
  //     cout << board[i][j] << " ";
  //   }
  //   cout << endl;
  // }


#ifdef MAIN
  for(PII i: ans) cout << i.first+1 << " " << i.second+1 << endl;
#else
  cout << "score:" << 100000 - score << " " << ans.size() << endl;
#endif

  return 0;
}

Submission Info

Judge Result