Submission #5848772


Source Code Expand

Copy
#define DEBUG 0

/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 6/9/2019, 9:09:02 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

/*
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}

void No()
{
  cout << "No" << endl;
  exit(0);
}
*/

/*
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
*/

// const ll MOD = 1000000007;

int H, W;
string S[2010];
bool X[2010][2010];
ll A[2010][2010];
ll B[2010][2010];

ll solve()
{
  for (auto i = 0; i < H; i++)
  {
    ll t = 0;
    for (auto j = 0; j < W; j++)
    {
      if (X[i][j])
      {
        t++;
      }
      else
      {
        for (auto k = j - 1; k >= j - t; k--)
        {
          A[i][k] = t;
        }
        t = 0;
      }
    }
    for (auto k = W - 1; k >= W - t; k--)
    {
      A[i][k] = t;
    }
  }
  for (auto j = 0; j < W; j++)
  {
    ll t = 0;
    for (auto i = 0; i < H; i++)
    {
      if (X[i][j])
      {
        t++;
      }
      else
      {
        for (auto k = i - 1; k >= i - t; k--)
        {
          B[k][j] = t;
        }
        t = 0;
      }
    }
    for (auto k = H - 1; k >= H - t; k--)
    {
      B[k][j] = t;
    }
  }
  ll ans = 0;
  for (auto i = 0; i < H; i++)
  {
    for (auto j = 0; j < W; j++)
    {
      ans = max(ans, A[i][j] + B[i][j]);
    }
  }
  return ans;
}

int main()
{
  cin >> H >> W;
  for (auto i = 0; i < H; i++)
  {
    cin >> S[i];
  }
  for (auto i = 0; i < H; i++)
  {
    for (auto j = 0; j < W; j++)
    {
      X[i][j] = (S[i][j] == '.');
    }
  }
  solve();
#if DEBUG == 1
  cerr << "A" << endl;
  for (auto i = 0; i < H; i++)
  {
    for (auto j = 0; j < W; j++)
    {
      cerr << A[i][j];
    }
    cerr << endl;
  }
  cerr << "B" << endl;
  for (auto i = 0; i < H; i++)
  {
    for (auto j = 0; j < W; j++)
    {
      cerr << B[i][j];
    }
    cerr << endl;
  }
#endif
  cout << solve() - 1 << endl;
}

Submission Info

Submission Time
Task D - Lamp
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2415 Byte
Status
Exec Time 241 ms
Memory 71424 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 400 / 400 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
Case Name Status Exec Time Memory
01.txt 2 ms 4352 KB
02.txt 2 ms 4352 KB
11.txt 223 ms 71424 KB
12.txt 180 ms 71424 KB
13.txt 227 ms 71424 KB
14.txt 231 ms 71424 KB
15.txt 208 ms 70912 KB
16.txt 221 ms 71424 KB
17.txt 241 ms 71424 KB
18.txt 234 ms 71424 KB
19.txt 199 ms 71424 KB
20.txt 2 ms 4352 KB
21.txt 2 ms 4352 KB
22.txt 5 ms 8576 KB
23.txt 168 ms 36608 KB
24.txt 2 ms 4352 KB
25.txt 15 ms 65920 KB