oj.uz

Submission #826532

# Submission time Handle Problem Language Result Execution time Memory
826532 2023-08-15T16:29:11 Z detroiddh Dijamant (COCI22_dijamant) C++17
0 / 70
 4 ms 2004 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 2003;
const ll mod = 1e9 + 7;

int m , n;
int table[maxn * 2 + 3][maxn * 2 + 3] , pfs[maxn * 2 + 3][maxn * 2 + 3];

void sub1()
{
   int ans = 0;

   for(int i = 1 ; i <= n + m - 1 ; ++i)
   {
       for(int j = 1 ; j <= n + m - 1 ; ++j)
       {
           pfs[i][j] = pfs[i - 1][j] + pfs[i][j - 1] - pfs[i - 1][j - 1] + table[i][j];
       }
   }

//   for(int i = 1 ; i <= n + m - 1 ; ++i)
//   {
//       for(int j = 1 ; j <= n + m - 1 ; ++j)
//       {
//           cout<<table[i][j]<<" ";
//       }
//       cout<<'\n';
//   }

   for(int i = 1 ; i <= n + m - 1 ; ++i)
   {
       for(int j = 1 ; j <= n + m - 1 ; ++j)
       {
           for(int k = 3 ; i - k >= 0 && j - k >= 0 ; k += 2)
           {
               int sum1 = pfs[i][j] - pfs[i - k][j] - pfs[i][j - k] + pfs[i - k][j - k];
               int sum2 = pfs[i - 1][j - 1] - pfs[i - k + 1][j - 1] - pfs[i - 1][j - k + 1] + pfs[i - k + 1][j - k + 1];
               int so = sum1 - sum2;
               if(so == (k + 1) * 2 - 4 && sum1 - sum2 == sum1)
               {
                   //cout<<i<<" "<<j<<" "<<sum1<<" "<<sum2<<'\n';
                   ++ans;
               }
           }
       }
   }

   cout<<ans;
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
//   freopen("DIAMOND.INP","r",stdin);
//   freopen("DIAMOND.OUT","w",stdout);

   cin>>m>>n;

   char a;
   for(int i = 1 ; i <= m ; ++i)
   {
       for(int j = 1 ; j <= n ; ++j)
       {
           cin>>a;
           if(a == '#') table[i + j - 1][m - i + j] = 1;
       }
   }

   sub1();
}

/*
##.#.#.#.##
#.#.#.#.#.#
.#.#.#.#.#.
#.#.#.#.#.#
##.#.#.#.##
*/

Subtask #1
0 / 20.0

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

Subtask #2
0 / 50.0

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