Submission #10300497
Source Code Expand
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))
#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif
using namespace std;
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T> void puts_all(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void puts_all(const T &value, const Args&... args){std::cout << value << " ";puts_all(args...);}
template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}
struct Init{
Init(){
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(12);
cerr << fixed << setprecision(12);
}
}init;
template <typename T, typename Container = std::vector<T>>
auto run_length_encode(const Container &v){
std::vector<std::pair<T,int64_t>> ret;
for(auto &x : v){
if(ret.empty()) ret.push_back({x,1});
else if(ret.back().fst == x) ++ret.back().snd;
else ret.push_back({x,1});
}
return ret;
}
LLI solve(int H, int W, int K, vector<vector<int>> c){
LLI ret = 0;
auto proc =
[&](){
REP(j,W){
vector<int> temp;
REP(i,H) if(c[i][j] != 0) temp.push_back(c[i][j]);
reverse(ALL(temp));
REP(i,H) c[i][j] = 0;
REP(i,temp.size()){
c[H-1-i][j] = temp[i];
}
}
};
auto check =
[&](){
int ret = 0;
REP(i,H){
auto r = run_length_encode<int>(c[i]);
int p = 0;
for(auto &a : r){
if(a.snd >= K){
ret += a.fst * a.snd;
REP(j,a.snd){
c[i][p] = 0;
++p;
}
}else{
REP(j,a.snd){
c[i][p] = a.fst;
++p;
}
}
}
}
return ret;
};
proc();
int i = 0;
while(1){
LLI t = check();
if(t == 0) break;
ret += (t << i);
++i;
proc();
}
return ret;
}
int main(){
int H, W, K;
while(cin >> H >> W >> K){
auto c = make_vector<int>(H, W, 0);
REP(i,H){
REP(j,W){
char a; cin >> a;
c[i][j] = a - '0';
}
}
LLI ans = 0;
REP(i,H){
REP(j,W){
auto cc = c;
cc[i][j] = 0;
chmax(ans, solve(H, W, K, cc));
}
}
puts_all(ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Falling Stone Game |
User |
you070707 |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
3653 Byte |
Status |
AC |
Exec Time |
116 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
120 / 120 |
180 / 180 |
Status |
|
|
|
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 |
2 ms |
256 KB |
sample_4.txt |
AC |
10 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 |
3 ms |
256 KB |
sub2_in3.txt |
AC |
3 ms |
256 KB |
sub2_in4.txt |
AC |
9 ms |
256 KB |
sub2_in5.txt |
AC |
22 ms |
256 KB |
sub2_in6.txt |
AC |
37 ms |
256 KB |
sub2_in7.txt |
AC |
116 ms |
256 KB |