이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define con continue
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
vector< pair<int, int> > dir = {
{
-1, 0
},
{
0, 1
},
{
1, 0
},
{
0, -1
}
};
bool valid(int x, int y, int n, int m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937 rng(1999999973);
const int N = 22;
int a[N], b[N], pref[N], n, m;
bool can[1 << (N - 1)];
signed main() {
ifstream cin("bank.in");
ofstream cout("bank.out");
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
pref[0] = a[0];
for (int i = 1; i < n; i++)
pref[i] = a[i] + pref[i - 1];
pref[n] = INF;
for (int i = 0; i < m; i++)
cin >> b[i];
can[0] = true;
for (int mask = 0; mask < (1 << m); mask++) {
if (!can[mask])
continue;
int cur = 0, sum = 0;
for (int i = 0; i < m; i++) {
if (((mask>>i)&1) == 1)
sum += b[i];
}
while(pref[cur] <= sum)
cur++;
if (cur == n) {
cout << "YES";
return 0;
}
for (int i = 0; i < m; i++) {
if (((mask>>i)&1) == 0 && sum + b[i] <= pref[cur])
can[mask | (1 << i)] = true;
}
}
cout << "NO";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |