Submission #10342197


Source Code Expand

#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;
int org_grid[30][30];
int grid[30][30];
int tmp_col[30];

void show(int H, int W){
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cout << grid[i][j];
    }
    cout << endl;
  }
  return;
}


void slide(int H, int W){
  for(int i = 0; i < W; i++){
    int real_height = 0;
    for(int j = 0; j < H; j++){
      if(grid[j][i] != 0){
        tmp_col[real_height] = grid[j][i];
        real_height ++;
      }
    }
    for(int j = 0; j < H; j++){
      grid[j][i] = 0;
    }
    for(int j = 0; j < real_height; j++){
      grid[j][i] = tmp_col[j];
    }
  }
}

void update(int H, int W, int K, int &score, int coeff, bool &updated){
  for(int i = 0; i < H; i++){
    int range_begin = -1;
    int range_color = -1;
    for(int j = 0; j < W; j++){
      if(range_color != grid[i][j]){
        if(j - range_begin >= K && range_color > 0){
          updated = true;
          for(int k = range_begin; k < j; k++){
            score += coeff * grid[i][k];
            grid[i][k] = 0;
          }
        }
        range_begin = j;
        range_color = grid[i][j];
      }
    }
    if(W - range_begin >= K && range_color > 0){
      updated = true;
      for(int k = range_begin; k < W; k++){
        score += coeff * grid[i][k];
        grid[i][k] = 0;
      }
    }
  }
}

int main(void){
  int H;
  int W;
  int K;
  cin >> H >> W >> K;
  for(int i = 0; i < H; i++){
    string tmp;
    cin >> tmp;
    for(int j = 0; j < W; j++){
      org_grid[H - i - 1][j] = (int) (tmp[j] - '0');
    }
  }

  int ans = 0;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      for(int k = 0; k < H; k++){
        for(int l = 0; l < W; l++){
          grid[k][l] = org_grid[k][l];
        }
      }
      grid[i][j] = 0;
      int cur_score = 0;
      int cur_coeff = 1;
      while(true){
        bool updated = false;
        slide(H, W);
        update(H, W, K, cur_score, cur_coeff, updated);
        if(!updated){
          break;
        }
        cur_coeff *= 2;
      }
      ans = max(ans, cur_score);
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task B - Falling Stone Game
User katom
Language C++14 (GCC 5.4.1)
Score 300
Code Size 2474 Byte
Status AC
Exec Time 15 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 2 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 1 ms 256 KB
sub2_in3.txt AC 1 ms 256 KB
sub2_in4.txt AC 2 ms 256 KB
sub2_in5.txt AC 3 ms 256 KB
sub2_in6.txt AC 6 ms 256 KB
sub2_in7.txt AC 15 ms 256 KB