Submission #922272

#	Time	Username	Problem	Language	Result	Execution time	Memory
922272		ttamx	Raspad (COI17_raspad)	C++14	0 / 100	119 ms	26528 KiB

raspad

#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 (stderr)

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39