Submission #5848106


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; k > j - t; k--)
        {
          A[i][k] = t;
        }
        t = 0;
      }
    }
    for (auto k = W - 1; k > W - 1 - 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; k > i - t; k--)
        {
          B[k][j] = t;
        }
        t = 0;
      }
    }
    for (auto k = H - 1; k > H - 1 - 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] == '.');
    }
  }
  cout << solve() - 1 << endl;
}

Submission Info

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

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 0 / 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 204 ms 71424 KB
12.txt 176 ms 71424 KB
13.txt 199 ms 71424 KB
14.txt 209 ms 71424 KB
15.txt 192 ms 70912 KB
16.txt 204 ms 71424 KB
17.txt 213 ms 71424 KB
18.txt 204 ms 71424 KB
19.txt 184 ms 71424 KB
20.txt 3 ms 4352 KB
21.txt 2 ms 4352 KB
22.txt 5 ms 8576 KB
23.txt 162 ms 36608 KB
24.txt 3 ms 4352 KB
25.txt 22 ms 65920 KB