Submission #145184

# Submission time Handle Problem Language Result Execution time Memory
145184 2019-08-19T08:27:44 Z solimm4sks Watching (JOI13_watching) C++14
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;

long long n, p, q;
long long a[200005];
long long dp[2005][2005];

long long smallReach[2005];
long long bigReach[2005];

#define INF 1000000

bool check(long long w){
    for(long long i = 0; i <= n; ++i){
        for(long long j = 0; j <= n; ++j){
            dp[i][j] = INF;
        }
    }

    for(long long i = 1; i <= n; ++i){
        long long ind1 = lower_bound(a, a + n, a[i] - w + 1) - a;
        long long ind2 = lower_bound(a, a + n, a[i] - 2 * w + 1) - a;

        smallReach[i] = max(ind1, 1);
        bigReach[i] = max(ind2, 1);
    }

    for(long long i = 0; i <= n; ++i){
        dp[0][i] = 0;
    }

    for(long long i = 1; i <= n; ++i){
        for(long long j = 0; j <= n; ++j){
            if(j){
                dp[i][j] = min(dp[bigReach[i] - 1][j] + 1, dp[smallReach[i] - 1][j - 1]);
            }else{
                dp[i][0] = dp[bigReach[i] - 1][0] + 1;
            }
        }
    }

    if(dp[n][p] <= q){
        return true;
    }
    return false;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> p >> q;
    for(long long i = 1; i <= n; ++i){
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    p = min(p, n);
    q = min(q, n);

    long long l = 0;
    long long r = 1000000010;
    long long lc = -1;
    while(l <= r){
        long long mid = (l + r) / 2;
        bool ch = check(mid);
        if(ch){
            r = mid - 1;
            lc = mid;
        }else{
            l = mid + 1;
        }
    }

    if(lc == -1){
        while(1);
    }

    cout << lc << "\n";
    return 0;
}

Compilation message

watching.cpp: In function 'bool check(long long int)':
watching.cpp:24:36: error: no matching function for call to 'max(long long int&, int)'
         smallReach[i] = max(ind1, 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 watching.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:
watching.cpp:24:36: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         smallReach[i] = max(ind1, 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 watching.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:
watching.cpp:24:36: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         smallReach[i] = max(ind1, 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 watching.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:
watching.cpp:24:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         smallReach[i] = max(ind1, 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 watching.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:
watching.cpp:24:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         smallReach[i] = max(ind1, 1);
                                    ^
watching.cpp:25:34: error: no matching function for call to 'max(long long int&, int)'
         bigReach[i] = max(ind2, 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 watching.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:
watching.cpp:25:34: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         bigReach[i] = max(ind2, 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 watching.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:
watching.cpp:25:34: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         bigReach[i] = max(ind2, 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 watching.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:
watching.cpp:25:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         bigReach[i] = max(ind2, 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 watching.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:
watching.cpp:25:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         bigReach[i] = max(ind2, 1);
                                  ^