# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
87290 | Yaroslaff | Bomb (IZhO17_bomb) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]); ^