oj.uz

Submission #490208

# Submission time Handle Problem Language Result Execution time Memory
490208 2021-11-26T10:01:34 Z kaxzert Bank (IZhO14_bank) C++17
100 / 100
 489 ms 82500 KB 
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)

void setIO(string s) {
    if (sz(s) != 0) {
        freopen((s+".inp").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

void setIOusaco(string s) {
    if (sz(s) != 0) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

int f[27][(1<<(21))-1];
int n, m;
vt<int> ke[27];

int dp(int i, int bitmask) {
	if (i == n) return 1;

	if (f[i][bitmask] != -1) return f[i][bitmask];

	trav(u, ke[i]) {
		if ((bitmask&u)==0) {
			if (dp(i+1, bitmask|u)) return f[i][bitmask] = 1;
		}
	}
	return f[i][bitmask] = 0;
}

int main() {
    #ifndef TAP 
    setIO("");
    //setIOusaco("bank2014");
    #endif

    fast;
    cin >> n >> m;
    vt<int> a(n);
    trav(i, a) cin >> i;
    vt<int> b(m);
    trav(i, b) cin >> i;

    fto(i, 0, n-1) {
    	fto(j, 1, (1<<m)-1) {
    		int li = j;
    		int sum = 0;
    		int pos = 0;
    		while(li > 0) {
    			sum += b[pos]*(li&1);
    			++pos;
    			li >>= 1;
    		}
    		if (sum == a[i]) ke[i].pb(j);
    	}
    }

    fto(i, 0, n-1) {
    	fto(j, 0, (1<<m)-1) f[i][j] = -1;
    }

    cout << (dp(0, 0) ? "YES": "NO") << '\n';

    return 0;
}

Compilation message

bank.cpp: In function 'void setIO(std::string)':
bank.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp: In function 'void setIOusaco(std::string)':
bank.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 17 ms 4412 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 24 ms 4420 KB Output is correct
9 Correct 20 ms 4272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 4 ms 1228 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 17 ms 4412 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 24 ms 4420 KB Output is correct
9 Correct 20 ms 4272 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 716 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 3 ms 972 KB Output is correct
23 Correct 3 ms 1228 KB Output is correct
24 Correct 3 ms 972 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 2 ms 844 KB Output is correct
29 Correct 3 ms 844 KB Output is correct
30 Correct 4 ms 1228 KB Output is correct
31 Correct 33 ms 8516 KB Output is correct
32 Correct 51 ms 12624 KB Output is correct
33 Correct 122 ms 28972 KB Output is correct
34 Correct 180 ms 41404 KB Output is correct
35 Correct 198 ms 45480 KB Output is correct
36 Correct 329 ms 82476 KB Output is correct
37 Correct 34 ms 8516 KB Output is correct
38 Correct 67 ms 16708 KB Output is correct
39 Correct 145 ms 33068 KB Output is correct
40 Correct 168 ms 41388 KB Output is correct
41 Correct 338 ms 82472 KB Output is correct
42 Correct 92 ms 20796 KB Output is correct
43 Correct 135 ms 33076 KB Output is correct
44 Correct 250 ms 61992 KB Output is correct
45 Correct 51 ms 12608 KB Output is correct
46 Correct 101 ms 24888 KB Output is correct
47 Correct 244 ms 61876 KB Output is correct
48 Correct 22 ms 4428 KB Output is correct
49 Correct 22 ms 4336 KB Output is correct
50 Correct 332 ms 82488 KB Output is correct
51 Correct 170 ms 41424 KB Output is correct
52 Correct 165 ms 41396 KB Output is correct
53 Correct 167 ms 41424 KB Output is correct
54 Correct 336 ms 82476 KB Output is correct
55 Correct 329 ms 82500 KB Output is correct
56 Correct 340 ms 82480 KB Output is correct
57 Correct 489 ms 82484 KB Output is correct
58 Correct 313 ms 78396 KB Output is correct