Submission #601051

#TimeUsernameProblemLanguageResultExecution timeMemory
601051MohammadAghilKitchen (BOI19_kitchen)C++17
100 / 100
685 ms91260 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); // #ifndef ONLINE_JUDGE // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); // #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 300 + 5, lg = 22, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} int a[maxn], b[maxn], dp[maxn][maxn*maxn], nxt[maxn*maxn]; bitset<maxn*maxn> can; int main(){ IOS(); int n, m, k; cin >> n >> m >> k; rep(i,0,n) cin >> a[i]; rep(i,0,m) cin >> b[i]; rep(i,0,n) if(a[i] < k) return cout << "Impossible\n", 0; int s = 0; rep(i,0,n) s += a[i]; vector<int> c; can[0] = true; rep(i,0,m) { if(b[i] >= n) c.pb(b[i]); else can |= can<<b[i]; } er(sz(c)); int lst = -1; per(i,maxn*maxn-1,0){ if(can[i]) lst = i, er(i); nxt[i] = lst; } rep(i,0,sz(c)) rep(j,0,maxn*maxn){ if(!i){ if(c[i] == j) dp[i][j] = 1; continue; } dp[i][j] = dp[i-1][j]; if(j == c[i]) dp[i][j] = max(dp[i][j], 1); else if(j > c[i] && dp[i-1][j-c[i]]) dp[i][j] = max(dp[i][j], dp[i-1][j-c[i]]+1); } rep(i,0,10) er(i, dp[sz(c)-1][i]); int ans = inf; rep(s1,0,maxn*maxn){ if(!s1 || (sz(c) && dp[sz(c)-1][s1])){ int v1 = n*(k-(s1?dp[sz(c)-1][s1]:0)); int v2 = s - s1; int mx = max({v1, v2, 0}); if(nxt[mx] + 1) ans = min(ans, s1 + nxt[mx]); } } if(ans == inf) cout << "Impossible\n"; else cout << ans - s << '\n'; return 0; }
#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...