Submission #922274

#	Time	Username	Problem	Language	Result	Execution time	Memory
922274		ttamx	Raspad (COI17_raspad)	C++14	100 / 100	390 ms	227568 KiB

raspad

#include<bits/stdc++.h>

using namespace std;

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

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

pair<int,int> dfs(int i,int j){
    if(j==0||j==m-1)return {0,n-1};
    pair<int,int> res(i,i);
    vis[i][j]=true;
    for(int di=-1;di<=1;di++)for(int dj=-1;dj<=1;dj++){
        int ni=i+di,nj=j+dj;
        if(0<=ni&&ni<n&&0<=nj&&nj<m&&!vis[ni][nj]&&s[ni][nj]=='0'){
            auto [x,y]=dfs(ni,nj);
            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 (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39