Submission #87290

#TimeUsernameProblemLanguageResultExecution timeMemory
87290YaroslaffBomb (IZhO17_bomb)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second #define ll long long #define int short int #define ld long double #define null nullptr #define endl '\n' using namespace std; mt19937 gen(chrono::system_clock::now().time_since_epoch().count()); const int M = 1e9 + 7; const int N = 2501; int n, m, x[N][N], l[N][N], r[N][N], res[N], ans; string s[N]; main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif cin >> n >> m; for (int i = 0; i < n; i++){ cin >> s[i];res[i + 1] = N; for (int j = 0; j < m; j++) x[i][j] = s[i][j] - '0'; } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){ if (!x[i][j]) l[i][j] = 0; else l[i][j] = (j ? l[i][j - 1] : 0) + 1; } for (int i = n - 1; i >= 0; i--) for (int j = m - 1; j >= 0; j--){ if (!x[i][j]) r[i][j] = 0; else r[i][j] = r[i][j + 1] + 1; } for (int j = 0; j < m; j++){ int tl = N; int tr = N; int p = -1; for (int i = 0; i <= n; i++){ if (i != n && x[i][j] == 1){ res[1] = min(res[1], l[i][j] + r[i][j] - 1); int len = i - p; tl = min(tl, l[i][j]); tr = min(tr, r[i][j]); res[len] = min(res[len], tl + tr - 1); } if (i == n || x[i][j] == 0){ int l = i - p; // cerr << l << endl; if (l != 1) res[l] = 0; tl = tr = N; p = i; } } tl = N; tr = N; p = n; for (int i = n - 1; i >= -1; i--){ if (i != -1 && x[i][j] == 1){ res[1] = min(res[1], l[i][j] + r[i][j] - 1); int len = p - i; tl = min(tl, l[i][j]); tr = min(tr, r[i][j]); res[len] = min(res[len], tl + tr - 1); } if (i == -1 || x[i][j] == 0){ int l = p - i; // cerr << l << endl; if (l != 1) res[l] = 0; tl = tr = N; p = i; } } } for (int i = 2; i <= n; i++) res[i] = min(res[i], res[i - 1]); for (int i = 1; i <= n; i++) ans = max(ans, i*res[i]); cout << ans; return 0; }

Compilation message (stderr)

bomb.cpp:16:19: warning: overflow in implicit constant conversion [-Woverflow]
 const int M = 1e9 + 7;
               ~~~~^~~
bomb.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
bomb.cpp: In function 'int main()':
bomb.cpp:52:59: error: no matching function for call to 'min(short int&, int)'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
bomb.cpp:52:59: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
bomb.cpp:52:59: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
bomb.cpp:52:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
bomb.cpp:52:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
bomb.cpp:56:53: error: no matching function for call to 'min(short int&, int)'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
bomb.cpp:56:53: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
bomb.cpp:56:53: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
bomb.cpp:56:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
bomb.cpp:56:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
bomb.cpp:71:59: error: no matching function for call to 'min(short int&, int)'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
bomb.cpp:71:59: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
bomb.cpp:71:59: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
bomb.cpp:71:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
bomb.cpp:71:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[1] = min(res[1], l[i][j] + r[i][j] - 1);
                                                           ^
bomb.cpp:75:53: error: no matching function for call to 'min(short int&, int)'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
bomb.cpp:75:53: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
bomb.cpp:75:53: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
bomb.cpp:75:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
bomb.cpp:75:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
bomb.cpp:89:32: error: no matching function for call to 'max(short int&, int)'
         ans = max(ans, i*res[i]);
                                ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
bomb.cpp:89:32: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
         ans = max(ans, i*res[i]);
                                ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
bomb.cpp:89:32: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
         ans = max(ans, i*res[i]);
                                ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
bomb.cpp:89:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
         ans = max(ans, i*res[i]);
                                ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from bomb.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
bomb.cpp:89:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
         ans = max(ans, i*res[i]);
                                ^