oj.uz

Submission #922272

# Submission time Handle Problem Language Result Execution time Memory
922272 2024-02-05T10:46:02 Z ttamx Raspad (COI17_raspad) C++14
0 / 100
 119 ms 26528 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=100005;
const int M=55;

int n,m,cnt;
string s[N];
long long ans;
bool vis[N][M];

pair<int,int> dfs(int i,int j){
    if(i<0||n<=i||j<0||m<=j||vis[i][j]||s[i][j]=='1')return {n-1,0};
    vis[i][j]=true;
    if(j==0||j==m-1)return {0,n-1};
    pair<int,int> res(i,i);
    for(int di=-1;di<=1;di++)for(int dj=-1;dj<=1;dj++){
        auto [x,y]=dfs(i+di,j+dj);
        res.first=min(res.first,x);
        res.second=max(res.second,y);
    }
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<n;i++)cin >> s[i];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='1')ans+=1LL*(i+1)*(n-i);
    for(int i=1;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='1'&&s[i-1][j]=='1')ans-=1LL*i*(n-i);
    for(int i=0;i<n;i++)for(int j=1;j<m;j++)if(s[i][j]=='1'&&s[i][j-1]=='1')ans-=1LL*(i+1)*(n-i);
    for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(s[i][j]=='1'&&s[i][j-1]=='1'&&s[i-1][j]=='1'&&s[i-1][j-1]=='1')ans+=1LL*i*(n-i);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='0'&&!vis[i][j]){
        auto [x,y]=dfs(i,j);
        ans+=1LL*x*(n-y-1);
    }
    cout << ans;
}

Compilation message

raspad.cpp: In function 'std::pair<int, int> dfs(int, int)':
raspad.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |         auto [x,y]=dfs(i+di,j+dj);
      |              ^
raspad.cpp: In function 'int main()':
raspad.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [x,y]=dfs(i,j);
      |              ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Incorrect 2 ms 4700 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 4696 KB Output is correct
2 Incorrect 2 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5464 KB Output is correct
2 Incorrect 119 ms 26528 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 4696 KB Output is correct
2 Incorrect 2 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -