Submission #366032

#TimeUsernameProblemLanguageResultExecution timeMemory
366032YomapeedKitchen (BOI19_kitchen)C++17
100 / 100
185 ms216172 KiB
#include<bits/stdc++.h> #define pi 3.141592653589793238 #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define MOD 1000000007 #define INF 999999999999999999 #define pb push_back #define ff first #define ss second #define mt make_tuple #define ll long long #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// const int N = 3e2 + 2; ll dp[N][N * N]; void chmax(ll& a, ll b){ a = max(a, b); } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); fast; ll T = 1, i, j; //cin >> T; while (T--) { ll n, m, k; cin >> n >> m >> k; vector<ll> a(n), b(m); bool flag = true; ll sum = 0; ll sa = 0; for(i = 0; i < n; i++){ cin >> a[i]; if(a[i] < k){ flag = false; } sum += a[i]; } sa = sum; for(i = 0; i < m; i++){ cin >> b[i]; sum -= b[i]; } if(sum > 0){ flag = false; } if(m < k){ flag = false; } if(!flag){ cout << "Impossible\n"; return 0; } for(i = 0; i < N; i++){ for(j = 0; j < N * N; j++){ dp[i][j] = -INF; } } dp[0][0] = 0; for(i = 0; i < m; i++){ ll B = min(b[i], n); for(ll x = 0; x < N * N; x++){ if(x - b[i] >= 0 && dp[i][x - b[i]] != -INF){ chmax(dp[i + 1][x], dp[i][x - b[i]] + B); } chmax(dp[i + 1][x], dp[i][x]); } } ll ans = INF; //cout << sa << endl; for(i = sa; i < N * N; i++){ if(dp[m][i] >= n * k){ //cout << i << " " << dp[m][i] << endl; ans = i - sa; break; } } if(ans == INF){ cout << "Impossible\n"; return 0; } cout << ans << endl; } return 0; }

Compilation message (stderr)

kitchen.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
kitchen.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...