oj.uz

Submission #759064

# Submission time Handle Problem Language Result Execution time Memory
759064 2023-06-15T17:52:58 Z harut_13 Dijamant (COCI22_dijamant) C++14
70 / 70
 114 ms 22088 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = pv(a, b / 2);
    if (b % 2) {
        return (res * res) * a;
    }
    else {
        return (res * res);
    }
}

vector < vector<char>> v;
bool vand(int i, int j) {
    if (v[i][j] == '#')return 1;
    else return 0;
}

void solve() {
    int n, m; cin >> n >> m;
    v = vector < vector<char>>(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    vector<vec> right(n, vec(m, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                for (int k = j + 1; k < m; k++) {
                    if (vand(i, k)) {
                        right[i][j] = k; break;
                    }
                }
                if (right[i][j] != -1)j = right[i][j]-1;
                else break;
            }
        }
    }

    vector<vector<bool>> a(n, vector<bool>(m)), b(n, vector<bool>(m)), c(n, vector<bool>(m)), d(n, vector<bool>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                if (right[i][j] != -1  ) {
                    if ((right[i][j] - j) == 2 && i != 0) {
                        if (vand(i - 1, j + 1)) {
                            a[i][j] = 1;
                            b[i][right[i][j]] = 1;
                        }
                    }
                    else {
                        if (i != 0) {
                            if (a[i - 1][j + 1] && b[i - 1][right[i][j] - 1] && right[i-1][j+1]==right[i][j]-1) {
                                a[i][j] = 1;
                                b[i][right[i][j]] = 1;
                            } 
                        }
                    }
                }
            }
        }
    }
    for (int i = n - 1; i >= 0;i--) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                if (right[i][j] != -1 && ((right[i][j] - j) % 2 == 0)) {
                    if ((right[i][j] - j) == 2 && i != n-1) {
                        if (vand(i + 1, j + 1)) {
                            c[i][j] = 1;
                            d[i][right[i][j]] = 1;
                        }
                    }
                    else {
                        if (i != n - 1) {
                            if (c[i + 1][j + 1] && d[i + 1][right[i][j] - 1] && right[i+1][j+1]==right[i][j]-1) {
                                c[i][j] = 1;
                                d[i][right[i][j]] = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j) && right[i][j] != -1) {
                if (a[i][j] && c[i][j] && b[i][right[i][j]] && d[i][right[i][j]]) {
                    cnt++;
                   // cout << i << " " << j << i << " " << right[i][j] << endl;
                }
            }
           // cout << a[i][j];
        }
        //cout << endl;
    }
    cout << cnt << endl;
}
int main() {
    FASTIO

        //int t; cin >> t;
    //while (t--)
        solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 47 ms 20488 KB Output is correct
15 Correct 61 ms 21100 KB Output is correct
16 Correct 114 ms 19460 KB Output is correct
17 Correct 73 ms 19384 KB Output is correct
18 Correct 85 ms 22088 KB Output is correct
19 Correct 46 ms 18732 KB Output is correct
20 Correct 54 ms 22012 KB Output is correct
21 Correct 45 ms 18736 KB Output is correct
22 Correct 75 ms 19952 KB Output is correct
23 Correct 65 ms 19020 KB Output is correct
24 Correct 77 ms 20440 KB Output is correct
25 Correct 43 ms 18608 KB Output is correct
26 Correct 64 ms 19376 KB Output is correct