Submission #1243128

#TimeUsernameProblemLanguageResultExecution timeMemory
1243128fadak-14Bank (IZhO14_bank)C++20
100 / 100
430 ms219296 KiB
//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code ! #include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define endl '\n' #define eb emplace_back #define em emplace #define pb push_back #define pf push_front #define pp pop_back #define fr first #define sc second #define sz size /*vector<bool> f(26 , true) ; bool va[mn][mn] = {false}; bool vb[mn][mn] = {false}; ll dp[mn][mn];*/ /* const ll mn = 1771; ll lch[mn], rch[mn]; vector<ll> ed[mn]; deque<ll> rs[mn]; set<ll> v[mn]; bool us[mn]; pair<ll, ll> ar[mn]; ll prv[mn], rnk[mn]; bool lf[mn]; bool va[mn][mn] = {false}; bool vb[mn][mn] = {false};*/ /* const ll mn = 5e5+10 ; const ll mod = 1e9+7; ll a[mn], fa[mn]; vector<tuple<ll, ll, ll>> ed; ll find(ll x) { return (x == fa[x])? x:(fa[x] = find(fa[x])); }*/ //ll b[400014]; /* string a[]= {"01" , "1" , "23456789", "0123456789"} ; const ll mxn = 1e5 + 14 ; const ll dx[] = {-1 , 0 , 1 , 0} ; const ll dy[] = {0 , 1 , 0 , -1} ; vector <ll> adj[mxn] ; ll p[mxn][2] ; */ /* ll bit(ll n){ for(ll i = 0 ; i < 32 ; i++) {if((! (n& (1 << i))) and n &(1 << ( i + 1))) return(i);} } */ ll n ,m ; vector<vector<ll>> dp ; ll eds(ll i1, ll j1, ll i2, ll j2) { return (ll)(i1 - i2) * (i1 - i2) + (ll)(j1 - j2) * (j1 - j2); } db dou(db x) {return x * x ;} vector<ll> cps(const vector<ll> & arr , ll n) { vector <ll> ps(n + 1 , 0) ; for(ll i =0 ; i <n ; i++) ps[i + 1] = ps[i] + arr[i] ; return ps ; } /* const ll mx = 200014; ll d[mx] ; ll e[mx]; vector<ll> a[mx]; vector <ll> aa[mx]; const ll md = 998244353; ll n , k , u , v ; */ /* ll cvp(ll n , ll k ,ll x , const vector<ll> & arr){ vector <ll> ps = cps(arr , n) ; ll ts = ps[n] ; ll count = 0 ; for(ll s = 0 ; s < n ; s++) { ll sm = 0 ; for(ll c = 0 ; c < k ; c++) { for(ll i = s; i < n ; i++) { sm += arr[i] ; if(sm >= x) { count ++ ; break ; } } } } return count ; }*/ ll nx(string s){ cout << "next" ; cout.flush(); for(auto i: s) cout << " " << i ; cout << endl ; cout.flush() ; ll n ; cin >> n ; for(ll i = 1 ; i <= n ;i++) cin >> s ; return n ; } bool ip(const string& s) { if(s == "1") return false ; if(s.length() <= 18) { ll nm = stoll(s) ; if(nm < 2) return false ; for(ll i = 2; i * i <= nm ;i++) if(nm % i == 0) return false ; return true; } vector<ll> prm = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541}; for(ll i : prm){ ll rm = 0 ; for(char c:s) rm = (rm *10 + (c - '0')) % i ; if(rm == 0) return false ; } return true; } /* double cc(const string& num) { ll sod = 0; for (char i : num) sod += i - '0'; double vl = 0; for (char i : num) vl = vl * 10 + (i - '0'); double c = vl / sod; return c; } */ /* ll mmdtv(const string& n) { ll len = n.size() ; ll mnr = len - 1; double mc = 1e18; for(ll m = 1 ; m < (1 << len) ; m++) { string r ; for(ll i = 0 ; i < len ; i++) if(m & (1 << i)) r += n[i] ; if(!r.empty()) { double c = cc(r) ; ll rv = len - r.size(); if(c < mc || (abs(c - mc) < 1e-9 && rv < mnr)) {mc = c;mnr = rv; } } } return mnr; } */ bool sv(ll c , ll i , vector <ll> &arr, vector<vector<ll>> &sm) { if(i == n) return true ; if(dp[c][i] != -1) return dp[c][i] ; for(ll &j : sm[arr[i]]) { if(j & c) continue ; if(sv(j | c , i +1 , arr , sm)){ return dp[c][i] = 1 ; return true;} } dp[c][i] = 0 ; return false ; } ll gp(ll lv, ll rw, ll cl) { if (lv == 1) { if (rw == 1 && cl == 1) return 1; if (rw == 2 && cl == 2) return 2; if (rw == 2 && cl == 1) return 3; return 4; } ll hf = 1 << (lv - 1); ll bc = 1LL << (2 * (lv - 1)); if (rw <= hf && cl <= hf)return gp(lv - 1, rw, cl); if (rw > hf && cl > hf)return bc + gp(lv - 1, rw - hf, cl - hf); if (rw > hf && cl <= hf)return 2 * bc + gp(lv - 1, rw - hf, cl); return 3 * bc + gp(lv - 1, rw, cl - hf); } pair<ll , ll> getp(ll lv, ll ps) { if (lv == 1) { if (ps == 1) return {1, 1}; if (ps == 2) return {2, 2}; if (ps == 3) return {2, 1}; return {1, 2}; } ll hf = 1 << (lv - 1); ll bs = 1LL << (2 * (lv - 1)); if (ps <= bs)return getp(lv - 1, ps); if (ps <= 2 * bs) {auto p = getp(lv - 1, ps - bs);return {p.fr + hf, p.sc + hf};} if (ps <= 3 * bs) { auto p = getp(lv - 1, ps - 2 * bs);return {p.fr + hf, p.sc}; } auto p = getp(lv - 1, ps - 3 * bs); return {p.fr, p.sc + hf}; } bool prime(ll n) { if(n < 2) return false ; for(ll i =2; i*i <= n ; i++) if(n % i == 0) return false ; return true ; } signed main() { cin.tie(0)->sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(0) ; cout.tie(0); /*ll n, k; cin >> n >> k; vector<ll> a(n); for (ll i = 0; i < n; i++)cin >> a[i]; if (k == 1) { ll tt = 0; for (ll nm : a) tt += nm; cout << tt << endl; return 0; } ll lm = n -k + 1; vector<ll> pr(n + 1, 0); for (ll i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i]; deque<ll> dq; ll ms = 1e18; for (ll i = 0; i < n; i++) { ll cs = max(0LL, i - lm + 1); while (!dq.empty() && dq.front() < cs) dq.pop_front(); while (!dq.empty() && pr[i] >= pr[dq.back()])dq.pp(); dq.pb(i); ll cmp = pr[dq.front()]; ll css = pr[i + 1] - cmp; if (css < ms) ms = css; } cout << ms << endl;*/ cin >> n >> m ; vector <ll> arr(n) ; vector<ll> b (m) ; ll mx = 0 ; for(ll &i : arr) cin >> i ; for(ll &i : b) {cin >> i ; mx += i;} vector<vector<ll>> sm (mx +1) ; dp.resize((1 << m) , vector<ll> (n + 1 , -1)) ; for(ll i = 0 ; i < (1 << m) ;i++) { ll c= 0 ; for(ll j = 0 ; j < m ; j++) if(i & (1 << j)) c += b[j] ; if(c >mx) continue ; sm[c].pb(i) ; } //char s[200014] ; /*ll t; cin >>t ; while(t--) { ll n ; cin >> n ; } */ /*while(true){ll ans = nx(a[0]) ; ans = nx(a[1]) ; if(ans == 2) break;} while(true) {ll ans = nx(a[3]) ;if(ans == 1) break ;} cout << "done" << endl ; cout.flush() ;*/ //ll t; cin >> t ; //while(t--){ /*ll n ; cin >> n ; ll q ; cin >> q ; while(q--) { string s; cin >> s ; if(s == "->") {ll x ,y ; cin >> x >>y ; cout << gp(n , x ,y) << endl ;} else {ll d ; cin >> d ; pair<ll , ll> p = getp(n , d) ; cout << p.fr << " " << p.sc << endl;} }*/ /*string n ; cin >> n ; //cout << mmdtv(n) << endl ; //i'll try another bad idea //ok ll mx = 0 ; ll count = 0 ; for(auto i : n) { if(i == '0') count ++ ; else mx = max(mx, count + 1) ; } cout << n.sz() - mx << endl;*/ for(ll &i :arr) { if(i > mx) {cout << "NO" << endl ; return 0;} if(sm[i].empty()) {cout << "NO" << endl ; return 0 ;} } if(sv(0 , 0 , arr, sm)) {cout << "YES" << endl;} else cout << "NO" << endl; 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...