Submission #771554

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771554	2023-07-03T06:20:30 Z	Wael	Kitchen (BOI19_kitchen)	C++14	Compilation error	0 ms	0 KB

kitchen

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
//#define int long long
#define F first
#define S second
#define endl '\n'
#define INT INT_MAX
int const M = 301 , Mx = 1e5 , N = 4e6 + 2 , lg = 30 , mod = 1e9 + 7;
int dx[] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};
int dy[] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int T , n , m , k , x , ans = 1e9 , y , w , sum , a[M] , b[M] , mx = 9e4 , dp[4][Mx];
bool Dp[2][Mx][M];
int closer[Mx][M] , sum1;

main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);

    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i] , sum += a[i];
    for(int i = 1 ; i <= m ; ++i) cin >> b[i] , sum1 += b[i];

    for(int i = 1 ; i <= n ; ++i) {
        if(a[i] < k) {
            cout << "Impossible" << endl;
            return 0;
        }
    }

    sort(b + 1 , b + m + 1);
    int Index = lower_bound(b + 1 , b + m + 1 , n) - b; --Index;

    dp[0][0] = 1;
    for(int i = 1 ; i <= Index ; ++i) {
        int I = (i % 2);
        dp[I][0] = 1;
        for(int j = 1 ; j <= mx ; ++j) {
            dp[I][j] = dp[!I][j];
            if(j >= b[i]) dp[I][j] = max(dp[I][j] , dp[!I][j - b[i]]);
        }
    }

    Dp[Index % 2][0][0] = 1;
    for(int i = Index + 1 ; i <= m ; ++i) {
        int I = (i % 2);
        Dp[I][0][0] = 1;
        for(int j = 1 ; j <= sum1 ; ++j) {
            for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
                Dp[I][j][cnt] = Dp[!I][j][cnt];
                if(j >= b[i]) Dp[I][j][cnt] = max(Dp[I][j][cnt] , Dp[!I][j - b[i]][cnt - 1]);
            }
        }
    }

    int I = m % 2;
    for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
        for(int j = mx ; j >= 1 ; --j) {
            closer[j][cnt] = closer[j + 1][cnt];
            if(Dp[I][j][cnt]) closer[j][cnt] = j;
        }
    }

    for(int Left = 0 ; Left <= mx ; ++Left) {
        if(dp[Index % 2][Left]) {
            if(Left >= sum) ans = min(ans , Left - sum);
            else {
                int ReqCnt = k - (Left / n);
                ReqCnt = max(ReqCnt , 0ll);
                int ReqJ = sum - Left;
                for(int CurCnt = ReqCnt ; CurCnt <= m - Index ; ++CurCnt)
                    if(closer[ReqJ][CurCnt]) ans = min(ans , (Left + closer[ReqJ][CurCnt]) - sum);
            }
        }
    }

    if(ans == 1e18) cout << "Impossible" << endl;
    else cout << ans << endl;

    return 0;
}

Compilation message

kitchen.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:68:42: error: no matching function for call to 'max(int&, long long int)'
   68 |                 ReqCnt = max(ReqCnt , 0ll);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from kitchen.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
kitchen.cpp:68:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   68 |                 ReqCnt = max(ReqCnt , 0ll);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from kitchen.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
kitchen.cpp:68:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   68 |                 ReqCnt = max(ReqCnt , 0ll);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from kitchen.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
kitchen.cpp:68:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   68 |                 ReqCnt = max(ReqCnt , 0ll);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from kitchen.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
kitchen.cpp:68:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   68 |                 ReqCnt = max(ReqCnt , 0ll);
      |                                          ^