Submission #542574

#	Time	Username	Problem	Language	Result	Execution time	Memory
542574		Zhora_004	Dijamant (COCI22_dijamant)	C++17	70 / 70	70 ms	16680 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
//#include <bit>
//#include <ranges>
//#include <numbers>
#define itn int
#define sacnf scanf
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e6 + 1, inf = 1e9;

int find_sum(vector<vector<int>>& pref, int i, int l, int r)
{
    if (l == 0) return pref[i][r];
    return pref[i][r] - pref[i][l - 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> v(n, vector<bool>(m));
    vector<vector<int>> pref(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            if (s[j] == '#') v[i][j] = 1;
            if (j == 0) pref[i][j] = v[i][j];
            else pref[i][j] = pref[i][j - 1] + v[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n - 2; i++)
    {
        for (int j = 1; j < m - 1; j++)
        {
            if (v[i][j])
            {
                if (v[i + 1][j]) continue;
                if (!v[i + 1][j - 1] || !v[i + 1][j + 1]) continue;
                int k = i + 1, l = j - 1, r = j + 1;
                bool flag = 0;
                while (k + 1 < n)
                {
                    if (v[k + 1][l + 1] && v[k + 1][r - 1])
                    {
                        if (l + 1 == r - 1)
                        {
                            ans++;
                            break;
                        }
                        int sm = find_sum(pref, k + 1, l + 1, r - 1);
                        if (sm != 2) break;
                        flag = 1;
                        k++;
                        l++;
                        r--;
                    }
                    else
                    {
                        if (flag) break;
                        if (l == 0 || r == m - 1) break;
                        if (!v[k + 1][l - 1] || !v[k + 1][r + 1]) break;
                        int sm = find_sum(pref, k + 1, l - 1, r + 1);
                        if (sm != 2) break;
                        k++;
                        l--;
                        r++;
                    }
                }
            }
        }
    }
    cout << ans;

    return 0;
}

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