Submission #2434840


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
#define ZERO(a) memset(a,0,sizeof(a))
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
#define exists find_if
#define forall all_of

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 
using vi = vector<int>; using vvi = vector<vi>; vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }
using Pos = complex<double>;

template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const stack<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const unordered_set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U, typename V>  ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
string bits_to_string(ll input, ll n=64) { string s; rep(i, n) s += '0' + !!(input & (1ll << i)); reverse(all(s)); return s; }

template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
string substr(string s, P x) {return s.substr(x.fi, x.se - x.fi); }
struct ci : public iterator<forward_iterator_tag, ll> { ll n; ci(const ll n) : n(n) { } bool operator==(const ci& x) { return n == x.n; } bool operator!=(const ci& x) { return !(*this == x); } ci &operator++() { n++; return *this; } ll operator*() const { return n; } };

size_t random_seed; namespace std { using argument_type = P; template<> struct hash<argument_type> { size_t operator()(argument_type const& x) const { size_t seed = random_seed; seed ^= hash<ll>{}(x.fi); seed ^= (hash<ll>{}(x.se) << 1); return seed; } }; }; // hash for various class
namespace myhash{ const int Bsizes[]={3,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81}; const int xor_nums[]={0x100007d1,0x5ff049c9,0x14560859,0x07087fef,0x3e277d49,0x4dba1f17,0x709c5988,0x05904258,0x1aa71872,0x238819b3,0x7b002bb7,0x1cf91302,0x0012290a,0x1083576b,0x76473e49,0x3d86295b,0x20536814,0x08634f4d,0x115405e8,0x0e6359f2}; const int hash_key=xor_nums[rand()%20]; const int mod_key=xor_nums[rand()%20]; template <typename T> struct myhash{ std::size_t operator()(const T& val) const { return (hash<T>{}(val)%mod_key)^hash_key; } }; };
template <typename T> class uset:public std::unordered_set<T,myhash::myhash<T>> { using SET=std::unordered_set<T,myhash::myhash<T>>; public: uset():SET(){SET::rehash(myhash::Bsizes[rand()%20]);} };
template <typename T,typename U> class umap:public std::unordered_map<T,U,myhash::myhash<T>> { public: using MAP=std::unordered_map<T,U,myhash::myhash<T>>; umap():MAP(){MAP::rehash(myhash::Bsizes[rand()%20]);} };    

struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
struct init_{init_(){ gettimeofday(&start, NULL); ios::sync_with_stdio(false); cin.tie(0); srand((unsigned int)time(NULL)); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;

static const double EPS = 1e-14;
static const long long INF = 1e18;
static const long long mo = 1e9+7;
#define ldout fixed << setprecision(40) 

int main(void) {
    ll n, m; cin >> n >> m;
    vector<string> bb(n);
    rep(i, n) cin >> bb[i];
    vector<string> org = bb;
    vvll b(n,vll(m));
    rep(i,n)rep(j,m)b[i][j]=(bb[i][j]=='#'?1:0);
//    cout << b << endl;

    vvll a(n,vll(m));
    rep(j, m) a[0][j] = 1;
    rep(j,m-1)repi(i,1,n) {
        if ((b[i][j]+b[i-1][j]+b[i][j+1]+b[i-1][j+1]) % 2 == 1) {
            a[i][j] = 1;
        }
    }
    rep(i,n)a[i][m-1]=-1;
//    cout <<  a << endl;

    rep(j,m-1)rep(i,n) {
        if (a[i][j] == 0) a[i][j] = a[i-1][j] + 1;
    }
//    cout <<  a << endl;

    ll ans = max(n,m);
    repi(i, 0, n) {
        ll ret = 0;
        stack<P> s;
        rep(j, m) {
            chmax(ret, a[i][j]*2);
            ll next_j = j;
            while (s.size() && s.top().fi >= a[i][j]) {
                ll tmp = (j-s.top().se+1)*(s.top().fi);
//                cout << j << " " << s.top() << " " << a[i][j] << " " << tmp <<" ###"  << endl;
                chmax(ret, tmp);
                next_j = s.top().se;
                s.pop();
            }
            s.push(P(a[i][j], next_j));
        }
        chmax(ans, ret);
    }
    cout << ans << endl;

    /*
    ll br = 0;
    rep(i, n) rep(j, m) repi(ii,i+1,n+1) repi(jj,j+1,m+1) {
//        cout << "########" << endl;
        repi(x,i,ii-1)repi(y,j,jj-1) {
//            cout << b[x][y];
//            if (y==jj-1-1) cout << endl;
            if ((b[x][y] + b[x+1][y] + b[x][y+1] + b[x+1][y+1])%2==1) {
                goto SKIP;
            }
        }
        chmax(br, (ii-i)*(jj-j));

        SKIP:;
    }
    cout << br << endl;
    if (br != ans) {
        cout <<"HIT"<<endl;
        rep(i,n)
        cout << org[i] << endl;
    }
    */

    return 0;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User hamko
Language C++14 (GCC 5.4.1)
Score 700
Code Size 7384 Byte
Status
Exec Time 304 ms
Memory 71168 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 700 / 700 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 2 ms 640 KB
10.txt 214 ms 71168 KB
11.txt 100 ms 37248 KB
12.txt 197 ms 70656 KB
13.txt 200 ms 71168 KB
14.txt 198 ms 70656 KB
15.txt 199 ms 71168 KB
16.txt 200 ms 71168 KB
17.txt 199 ms 71168 KB
18.txt 219 ms 70656 KB
19.txt 202 ms 71168 KB
2.txt 1 ms 384 KB
20.txt 204 ms 70656 KB
21.txt 206 ms 71168 KB
22.txt 205 ms 71168 KB
23.txt 207 ms 71168 KB
24.txt 197 ms 71168 KB
25.txt 197 ms 71168 KB
26.txt 231 ms 71168 KB
27.txt 231 ms 71168 KB
28.txt 268 ms 71168 KB
29.txt 251 ms 71168 KB
3.txt 304 ms 71040 KB
30.txt 223 ms 71168 KB
31.txt 216 ms 71168 KB
32.txt 201 ms 71168 KB
33.txt 200 ms 71168 KB
34.txt 200 ms 71168 KB
4.txt 303 ms 71168 KB
5.txt 2 ms 768 KB
6.txt 1 ms 384 KB
7.txt 224 ms 71168 KB
8.txt 223 ms 71168 KB
9.txt 213 ms 71168 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB