Submission #475901

#	Time	Username	Problem	Language	Result	Execution time	Memory
475901		mat_v	Bank (IZhO14_bank)	C++14	100 / 100	343 ms	16836 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
int a[25];
int b[25];
int dp[(1<<20) + 5];
int ost[(1<<20) + 5];
int kol[(1<<20) + 5];
int niz[(1<<20) + 5];
bool cmp(int a, int b){return kol[a] < kol[b];}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    ff(i,0,n - 1)cin >> a[i];
    ff(i,0,m - 1)cin >> b[i];
    ff(i,0,(1<<m) - 1){
        niz[i] = i;
        ff(j,0,m - 1){
            if((1<<j)&i)kol[i]++;
        }
    }
    sort(niz, niz + (1<<m), cmp);
    dp[0] = -1;
    ff(r,1,(1<<m) - 1){
        int i = niz[r];
        dp[i] = -1;
        int sum = 0;
        ff(j,0,m - 1){
            if((1<<j)&i){
                sum += b[j];
            }
        }
        ost[i] = sum;
        ff(j,0,m - 1){
            if((1<<j)&i){
                int dkl = dp[i^(1<<j)];
                int kol = ost[i^(1<<j)] + b[j];
                if(a[dkl + 1] == kol){
                    dkl++;
                    kol = 0;
                }
                if(dkl > dp[i]){
                    dp[i] = dkl;
                    ost[i] = kol;
                }
            }
        }
    }
    if(dp[(1<<m) - 1] >= n-1)cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:37:5: note: in expansion of macro 'ff'
   37 |     ff(i,0,n - 1)cin >> a[i];
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:38:5: note: in expansion of macro 'ff'
   38 |     ff(i,0,m - 1)cin >> b[i];
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:39:5: note: in expansion of macro 'ff'
   39 |     ff(i,0,(1<<m) - 1){
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:41:9: note: in expansion of macro 'ff'
   41 |         ff(j,0,m - 1){
      |         ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'r' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:47:5: note: in expansion of macro 'ff'
   47 |     ff(r,1,(1<<m) - 1){
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:51:9: note: in expansion of macro 'ff'
   51 |         ff(j,0,m - 1){
      |         ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:57:9: note: in expansion of macro 'ff'
   57 |         ff(j,0,m - 1){
      |         ^~

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