Submission #87291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87291	2018-11-30T07:42:08 Z	Yaroslaff	Bomb (IZhO17_bomb)	C++14	Compilation error	0 ms	0 KB

bomb

#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);
//#else
//    freopen("bomb.in","r",stdin);
//    freopen("bomb.out","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

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:55: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:55: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:55: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:55: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:55: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:59: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:59: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:59: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:59: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:59:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
bomb.cpp:74: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:74: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:74: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:74: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:74: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:78: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:78: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:78: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:78: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:78:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
                 res[len] = min(res[len], tl + tr - 1);
                                                     ^
bomb.cpp:92: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:92: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:92: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:92: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:92:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
         ans = max(ans, i*res[i]);
                                ^