Submission #1482130


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
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#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};

string s[35], t[35];
int h, w, k, cnt[35][35];

int sim() {
  int mul = 1, score = 0;
  bool update = true;
  while(update) {
    update = false;
    //落とす
    FOR(i2, 1, h) {
      for(int i=h-1; i>0; --i) REP(j, w) {
        if(t[i][j] == '-') {
          t[i][j] = t[i-1][j];
          t[i-1][j] = '-';
        }
      }
    }
    // REP(i, h) {
    //   cout << t[i] << endl;
    // }
    // cout << "kesu\n";

    //水平に何個隣り合っているか
    REP(i, h) {
      cnt[i][0] = 1;
      FOR(j, 1, w) {
        if(t[i][j] == t[i][j-1] && t[i][j] != '-') {
          cnt[i][j] = cnt[i][j-1] + 1;
        } else {
          cnt[i][j] = 1;
        }
      }
    }

    //消せるやつを消して空白に&&スコアプラス
    REP(i, h) {
      int tmp = 0;
      for(int j=w-1; j>=0; --j){
        if(tmp == 0 && cnt[i][j] >= k) {
          tmp = cnt[i][j];
          score += mul*(t[i][j]-'0')*cnt[i][j];
          update = true;
        }
        if(tmp > 0) t[i][j] = '-', tmp--;
      }
    }
    mul *= 2;
    // REP(i, h) {
    //   cout << t[i] << endl;
    // }
  }
  return score;
}


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

  int ret = 0;
  REP(i, h) REP(j, w) {
    // cout << i << " " << j << "-------------" << endl;
    REP(i2, h) t[i2] = s[i2];
    t[i][j] = '-';
    ret = max(ret, sim());
    // cout << "ret:" << ret << endl;
  }
  cout << ret << endl;

  return 0;
}

Submission Info

Submission Time
Task B - Falling Stone Game
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 300
Code Size 2269 Byte
Status AC
Exec Time 109 ms
Memory 256 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 120 / 120 180 / 180
Status
AC × 4
AC × 8
AC × 19
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub1_in6.txt, sub1_in7.txt, sub1_in8.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub1_in6.txt, sub1_in7.txt, sub1_in8.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub2_in5.txt, sub2_in6.txt, sub2_in7.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 7 ms 256 KB
sub1_in1.txt AC 1 ms 256 KB
sub1_in2.txt AC 1 ms 256 KB
sub1_in3.txt AC 1 ms 256 KB
sub1_in4.txt AC 1 ms 256 KB
sub1_in5.txt AC 1 ms 256 KB
sub1_in6.txt AC 1 ms 256 KB
sub1_in7.txt AC 1 ms 256 KB
sub1_in8.txt AC 1 ms 256 KB
sub2_in1.txt AC 1 ms 256 KB
sub2_in2.txt AC 2 ms 256 KB
sub2_in3.txt AC 2 ms 256 KB
sub2_in4.txt AC 6 ms 256 KB
sub2_in5.txt AC 15 ms 256 KB
sub2_in6.txt AC 33 ms 256 KB
sub2_in7.txt AC 109 ms 256 KB