oj.uz

Submission #546280

# Submission time Handle Problem Language Result Execution time Memory
546280 2022-04-07T03:38:35 Z truc12a2cvp Raspad (COI17_raspad) C++14
0 / 100
 98 ms 28756 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int N = 1e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;

int n, m, vis[N][55], minx, miny, maxx, maxy, dirs[] = {0, 1, 0, -1, 0};
char a[N][55];
bool check = true;

inline bool inside(int x, int y){
       return x >= 1 && x <= n && y >= 1 && y <= m;
}

void dfs(int x, int y){
       vis[x][y] = true;
       check &= (a[x - 1][y - 1] != '0');
       check &= (a[x - 1][y + 1] != '0');
       check &= (a[x + 1][y - 1] != '0');
       check &= (a[x + 1][y + 1] != '0');
       minx = min(minx, x);
       miny = min(miny, y);
       maxx = max(maxx, x);
       maxy = max(maxy, y);
       for(int i = 0; i < 4; i ++){
              int nx = x + dirs[i], ny = y + dirs[i + 1];
              if(inside(nx, ny) && !vis[nx][ny] && a[nx][ny] == '0') dfs(nx, ny);
       }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
       for(int j = 1; j <= m; j ++) cin >> a[i][j];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
       for(int j = 1; j <= m; j ++){
              if(a[i][j] == '1'){
                     ans += i * 1ll * (n - i + 1);
                     if(a[i - 1][j] == '1') ans -= (i - 1) * 1ll * (n - i + 1);
                     if(a[i][j - 1] == '1') ans -= i * 1ll * (n - i + 1);
                     if(a[i - 1][j] == a[i][j - 1] && a[i - 1][j] == '1' && a[i - 1][j - 1] == '1') ans += (i - 1) * 1ll * (n - i + 1);
              }
       }
    }
    for(int i = 1; i <= n; i ++){
       for(int j = 1; j <= m; j ++){
              if(!vis[i][j] && a[i][j] == '0'){
                     minx = miny = INF;
                     maxx = maxy = -INF;
                     check = true;
                     dfs(i, j);
                     if(minx > 1 && maxx < n && miny > 1 && maxy < m && check) ans += (minx - 1) * 1ll * (n - maxx);
              }
       }
    }
    cout << ans << endl;
    return 0;
}
/*
5 7
0100010
0111110
0101001
1111011
0100100
*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3668 KB Output is correct
2 Incorrect 98 ms 28756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -