#include <bits/stdc++.h> using namespace std; #define KungFlu "I don't care where are you from let's destroy this fucking kung flu" /* data type*/ #define ld long double #define ll long long int #define ull unsigned long long int #define fl float #define dou double #define cst const /* For loop*/ #define FORUP(i, star, end) for (ll i = star; i <= end; ++i) #define FORDOWN(i, star, end) for (ll i = star; i >= end; --i) #define FORAUTO(item, m) for (auto item : m) #define foreach(vector) \ for (auto it : vector) cout << it << ' '; #define foreachEndLine(vector) \ for (auto it : vector) cout << it << '\n'; #define foreach_nospace(vector) \ for (auto it : vector) cout << it; #define Map_Foreach(map) \ for (auto it : map) cout << it.fi << ' ' << it.se << endl; #define fur(i, a, b, c) for (int i = a; i <= b; i += c) /* Numeric and Calculate */ #define SUM(a, b) a + b #define SUB(a, b) a - b #define MUL(a, b) a* b #define DIV(a, b) a / b #define MODMAGIC(a, b) a % b #define MAXIMON ((ll)1e8 + 9) #define maxn ((ll)1e7 + 9) #define nn ((ll)1e6) #define MAXx 100009 #define mmax 100009 #define PI 3.14159265358979323846 #define PINor 3.14 #define mod 1000000007 #define nmax 1009 #define MaTrixSize 6009 #define INF (ll)1e9 * 2 + 10 #define EPS 1e - 9 #define INT_SIZE 32 #define maxsz (ll)1e5 + 3 /* string construc*/ #define UpCase(s) transform(s.begin(), s.end(), s.begin(), ::toupper); #define LowCase(s) transform(s.begin(), s.end(), s.begin(), ::tolower); /* maxspeed i_o*/ #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); /* Array and Vector*/ #define AutoInputArray(a, b, x) FORUP(a, 1, b) cin >> x[i]; #define ArrayInputFR0(a, b, x) FORUP(a, 0, b - 1) cin >> x[i]; #define outPutFormat(number, digit) cout << fixed << setprecision(digit) << number << endl; #define outPutNumber(num) cout << num << endl; #define VctUniq(vector) \ sort(vector.begin(), vector.end()); \ vector.erase(unique(vector.begin(), vector.end()), vector.end()); #define VctUniqGreater(vector) \ sort(vector.begin(), vector.end(), greater<ll>()); \ vector.erase(unique(vector.begin(), vector.end()), vector.end()); #define SortAsc(a) sort(a + 1, a + 1 + n); #define SortDesc(a) sort(a + 1, a + 1 + n, greater<ll>()); #define SortAscFR0(a) sort(a, a + n); #define SortDescFR0(a) sort(a, a + n, greater<ll>()); #define VectorSortASC(vector) sort(vector.begin(), vector.end()); #define VectorSortDESC(vector) sort(vector.begin(), vector.end(), greater<ll>()); #define all(vector) vector.begin(), vector.end() #define Rall(x) x.rbegin(), x.rend() #define ArrAll(a) a + 1, a + 1 + n #define max_Of_Arr(vector) *max_element(vector.begin(), vector.end()) #define min_Of_Arr(vector) *min_element(vector.begin(), vector.end()) /* FIle input, output*/ #define File_IO \ freopen("input.txt", "rt", stdin); \ freopen("output.txt", "w", stdout); #define File_InPut freopen("input.txt", "r", stdin) #define File_Out freopen("output.txt", "w", stdin) /* Short typing*/ #define pb push_back #define eb emplace_back #define emt empty #define emp emplace #define pob pop_back #define add insert #define clr clear #define mp make_pair #define mt make_tuple #define vct vector #define ss set #define M map #define stk stack #define qee queue #define dqq deque #define ok true #define wr false #define fi first #define se second #define back return #define len(vector) vector.size() #define B back /* Endline or breakpage if you like*/ #define endl "\n" #define Endl "\n" #define ENdl "\n" #define ENDl "\n" #define ENDL "\n" #define PageBreak cout << "\n"; /* Using the pair or the map, stack, queue*/ #define dii <int, int> #define dll <ll, ll> #define dcl <char, ll> #define dsl <string, ll> #define dul <ull, ull> /* Convert anything*/ #define to_s to_string #define to_i stoi #define to_I64 stoll #define to_UI64 stoull #define maxN 1000000007 /* System event*/ #define con continue #define stop system("pause"); #define whatIs(x) cout << "Line " << __LINE__ << ": " << #x << " = " << (x) << endl #define ShowTime() cerr << "Executed in " << clock() * 1000 / CLOCKS_PER_SEC << " ms"; /* Template class*/ template <class T> bool Larger(T a, T b) { back a > b ? (a = b, ok) : wr; } template <class T> bool Smaller(T& a, T& b) { back a < b ? (a = b, ok) : wr; } template <class T> bool Equal(T& a, T& b) { back a == b ? (a != b, ok) : wr; } template <class T> void SwapXor(T& a, T& b) { a ^= b; b ^= a; a ^= b; } template <class T> T findMax(T a, T b) { back(a > b) ? a : b; } template <class T> T findMin(T a, T b) { back(a < b) ? a : b; } // C++ 17 fast template // template<typename... Args> // void readLine(Args&... args) { // ((cin >> args), ...); // } // template<typename... Args> // void getString(Args&... args) { // ((getline(cin, args)), ...); // } // template<typename... Args> // void writeInLine(Args... args) { // ((cout << args << " "), ...); // } // template<typename... Args> // void writeLine(Args... args) { // ((cout << args << " "), ...); // PageBreak; // } // template<typename... Args> // void writeNextLine(Args... args) { // ((cout << args << "\n"), ...); // } // template<typename T> void scan(T& x) { // x = 0; // bool neg = 0; // register T c = getchar(); // if (c == '-') // neg = 1, c = getchar(); // while ((c < 48) || (c > 57)) // c = getchar(); // for (; c < 48 || c > 57; c = getchar()); // for (; c > 47 && c < 58; c = getchar()) // x = (x << 3) + (x << 1) + (c & 15); // if (neg) x *= -1; // } // template<typename T> void print(T n) { // bool neg = 0; // if (n < 0) // n *= -1, neg = 1; // char snum[65]; // int i = 0; // do { // snum[i++] = n % 10 + '0'; // n /= 10; // } // while (n); // --i; // if (neg) // putchar('-'); // while (i >= 0) // putchar(snum[i--]); // putchar('\n'); // } // template<typename... Args> // auto sumOf(Args... args) { // back(args + ...); // } // template<typename T, typename... Args> // void pushToVector(vector<T>& v, Args&&... args) { // (v.eb(forward<Args>(args)), ...); // } /* typedef tefdype*/ typedef pair<int, int> pii; typedef pair<ll, ll> plr; typedef pair<char, ll> pcr; typedef pair<string, ll> psr; typedef pair<ll, string> prs; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<plr> vpl; typedef vector<pii> vil; typedef vector<pcr> vcr; typedef vector<psr> vsr; typedef vector<prs> vrs; typedef vector<string> vs; typedef vector<pii> VII; typedef vector<vi> VVI; typedef M dii MPII; typedef ss<int> SETI; typedef multiset<int> MSETI; #define fw(a, b, c) for (ll c = a; c <= b; c++) ll n, m, a[1001][1001], res; string s[1001]; int32_t main() { fast_io; cin >> m >> n; fw(1, m, r) cin >> s[r]; memset(a, 0, sizeof(a)); fw(1, m, r) { fw(1, n, c) { if (s[r][c - 1] == '1') a[r][c] = 0; else a[r][c] = min(a[r - 1][c], min(a[r][c - 1], a[r - 1][c - 1])) + 1; res += a[r][c]; } } cout << res << endl; } // g++ -static -m64 -O2 -std=gnu++17 code.cpp -o code.exe && code.exe