Submission #235763

#	Time	Username	Problem	Language	Result	Execution time	Memory
235763		Kalam	Raspad (COI17_raspad)	C++11	100 / 100	407 ms	197880 KiB

raspad

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 77 , NN = 0 + 77;
int n , m , Mnx , Mxx;
char S[N][NN];
bool M[N][NN];
long long A;
bool bad;
void dfs(int x , int y) {
   Mxx = max(Mxx , x);
   Mnx = min(Mnx , x);
   if(y == 1 || y == m)
      bad = 1;
   M[x][y] = 1;
   for(int i = -1;i <= 1;++ i)
      for(int j = -1;j <= 1;++ j) {
         int nx = x + i , ny = y + j;
         if(! M[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m && S[nx][ny] == '0')
            dfs(nx , ny);
      }
}
int main() {
   scanf("%d %d" , & n , & m);
   for(int i = 1;i <= n;++ i)
      scanf("%s" , S[i] + 1);
   for(int i = 1;i <= n;++ i)
      for(int j = 1;j <= m;++ j)
         A += 1ll * (S[i][j] - '0') * i * (n - i + 1);
   for(int i = 1;i <= n;++ i)
      for(int j = 1;j < m;++ j)
         if(S[i][j] == S[i][j + 1] && S[i][j] == '1')
            A -= 1ll * i * (n - i + 1);
   for(int i = 1;i < n;++ i)
      for(int j = 1;j <= m;++ j)
         if(S[i][j] == S[i + 1][j] && S[i][j] == '1')
            A -= 1ll * i * (n - i);

   for(int i = 1;i <= n;++ i)
      for(int j = 1;j <= m;++ j)
         if(! M[i][j] && S[i][j] == '0') {
            Mnx = Mxx = i;
            bad = 0;
            dfs(i , j);
            if(! bad)
               A += 1ll * (Mnx - 1) * (n - Mxx);
         }
   for(int i = 1;i < n;++ i)
      for(int j = 1;j < m;++ j)
         if(S[i][j] == S[i + 1][j] && S[i][j + 1] == S[i][j] && S[i + 1][j + 1] == S[i][j] && S[i][j] == '1')
            A += 1ll * i * (n - i);

   printf("%lld\n" , A);
   return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d" , & n , & m);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
raspad.cpp:28:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%s" , S[i] + 1);
       ~~~~~^~~~~~~~~~~~~~~~~

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