Submission #5848772

Source Code Expand

Copy
```#define DEBUG 0

/**
* File    : D.cpp
* Author  : Kazune Takahashi
* Created : 6/9/2019, 9:09:02 PM
*/

#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 2019-06-09 21:46:59+0900 D - Lamp kazunetakahashi C++14 (GCC 5.4.1) 400 2415 Byte AC 241 ms 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