Submission #1232489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232489		peyman_sf	Dijamant (COCI22_dijamant)	C++20	70 / 70	141 ms	189412 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;

const ll maxn = 2010;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

#define TextIO ifstream fileIn("input.txt"); cin.rdbuf(fileIn.rdbuf()); ofstream fileOut("output.txt"); cout.rdbuf(fileOut.rdbuf());
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define print(x) for (auto i : x) cout << i << ' '; cout << endl
#define out(x) {cout << x << endl; return;}
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'

ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll pw(ll a, ll b, ll md = mod) {ll res = 1; b = max(b, 0ll); while(b) {if (b & 1){res = (a * res) % md;} a = (a * a) % md; b >>= 1;} return (res % md);}

ll n, m;
ll a[maxn][maxn];
ll dp[maxn][maxn][4];
vll row[maxn];

void solve() {
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        s = "_" + s;
        for (ll j = 1; j <= m; j++) {
            a[i][j] = (s[j] == '#');
            if (s[j] == '#') {
                row[i].pb(j);
                dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = dp[i][j][3] = 1;
            }
        }
    }


    for (ll i = 2; i <= n; i++) {
        for (ll j = 1; j < row[i].size(); j++) {
            ll r = row[i][j];
            ll l = row[i][j - 1];
            dp[i][r][0] = max(dp[i][r][0], min(dp[i - 1][r - 1][0] + 1, (r - l) / 2 + 1));
            dp[i][l][1] = max(dp[i][l][1], min(dp[i - 1][l + 1][1] + 1, (r - l) / 2 + 1));
        }
    }

    for (ll i = n - 1; i >= 1; i--) {
        for (ll j = 1; j < row[i].size(); j++) {
            ll r = row[i][j];
            ll l = row[i][j - 1];
            dp[i][r][2] = max(dp[i][r][2], min(dp[i + 1][r - 1][2] + 1, (r - l) / 2 + 1));
            dp[i][l][3] = max(dp[i][l][3], min(dp[i + 1][l + 1][3] + 1, (r - l) / 2 + 1));
        }
    }


    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j < row[i].size(); j++) {
            ll r = row[i][j];
            ll l = row[i][j - 1];
            if (dp[i][l][1] == dp[i][r][0] && dp[i][r][0] == dp[i][r][2] && dp[i][r][2] == dp[i][l][3] && dp[i][l][1] >= (r - l) / 2 + 1 && (r - l) % 2 == 0)
                ans++;
        }
    }

    cout << ans << endl;
}

int main() {
    FastIO
    ll t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50