Submission #1142807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142807		floppy	Bank (IZhO14_bank)	C++17	100 / 100	98 ms	8628 KiB

bank

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
 
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define pb push_back
#define eb emplace_back
#define ff first 
#define ss second
#define mp make_pair
 
template <class T>
void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "\b}"; }

template <class T> 
istream& operator>>(istream& in, vector<T>& v)
{
    for(auto&i:v)
        cin>>i; 
    return in; 
}
 
#define MOD 1000000007
#define EPS 1e-6f 
#define PI 3.1415926535897932384626433832795
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }
 
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;

const int MAX_N = 20; 
int dp[1 << MAX_N]; 
int dp2[1 << MAX_N]; 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //freopen("radio.in","r",stdin); 
    //freopen("radio.out","w",stdout);
    
    int n, m; 
    cin >> n >> m; 
    vi v(n), w(m); 
    cin >> v >> w; 
    
    f(i,1,(1<<m))  
    {
        f(j,0,m)
        {
            if (i & (1 << j))
            {
                int mask = i & ~(1 << j); 
                int idx = dp[mask]; 
                int r = dp2[mask]; 
                    
                if (r + w[j] <= v[idx])
                    r += w[j]; 

                if (r == v[idx])
                {
                    r = 0; 
                    idx++; 
                }

                if (idx > dp[i])
                {
                    dp[i] = idx; 
                    dp2[i]=r; 
                }
                else if (idx == dp[i])
                {
                    dp2[i]=max(dp2[i], r); 
                }
            }
        }
        if (dp[i] == n)
        {
            cout << "YES" << endl; 
            return 0; 
        }
    }

    cout << "NO" << endl; 

    return 0; 
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29