| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114886 |
2019-06-03T19:15:36 Z |
mrboorger |
Bank (IZhO14_bank) |
C++14 |
|
1000 ms |
512 KB |
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <iostream>
//#pragma GCC optimize("Ofast")
#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
//mt19937 gen(time(0));
const ll inf = 1e18 + 18;
vector <int> a, b;
main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("divide.in", "r", stdin);
// freopen("divide.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
if (n > m)
{
cout << "NO";
return 0;
}
a.resize(n, 0);
b.resize(m, 0);
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < m; i++)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (n == m)
{
bool f = true;
for(int i = 0; i < n; i++)
if (a[i] != b[i]) f = false;
if (f)
{
cout << "YES";
}
else
{
cout << "NO";
}
return 0;
}
if (n == m - 1)
{
int u = -1;
int kk = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < int(b.size()); j++)
{
if (a[i] == a[j])
{
b.erase(b.begin() + j);
break;
}
kk++;
u = i;
}
if (kk == 0 || (kk == 1 && b[0] + b[1] == a[u]))
{
cout << "YES";
}
else
{
cout << "NO";
}
return 0;
}
if (n == m - 2)
{
vector <int> u;
for(int i = 0; i < n; i++)
for(int j = 0; j < int(b.size()); j++)
{
if (a[i] == a[j])
{
b.erase(b.begin() + j);
break;
}
u.pb(i);
}
if (int(u.size()) == 0)
{
cout << "YES";
return 0;
}
if (int(u.size()) == 1)
{
for(int i = 0; i < (1 << int(b.size())); i++)
{
int sum = 0;
for(int j = 0; j < int(b.size()); j++)
{
if ((i & (1 << j)) > 0) sum += b[j];
}
if (sum == a[u[0]])
{
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
if (int(u.size()) == 2)
{
vector <int> kek(int(b.size()) + 1);
for(int i = 0; i < int(kek.size()); i++)
kek[i] = 0;
while(kek.back() == 0)
{
int sum[2];
sum[0] = 0;
sum[1] = 0;
for(int j = 0; j < int(b.size()); j++)
{
if (kek[j] > 0)
{
sum[kek[j] - 1] += b[j];
}
}
if (sum[0] == a[u[0]] && sum[1] == a[u[1]])
{
cout << "YES";
return 0;
}
kek[0]++;
int j = 0;
while(kek[j] == 3)
{
kek[j + 1]++;
kek[j] = 0;
j++;
}
}
cout << "NO";
return 0;
}
return 0;
}
if (n == 1)
{
//O(2 ^ m * m)
for(int i = 0; i < int(1 << m); i++)
{
int sum = 0;
for(int j = 0; j < m; j++)
{
if ((i & (1 << j)) > 0) sum += b[j];
}
if (a[0] == sum)
{
cout << "YES";
return 0;
}
}
}
else
{
// O(m! * (n + m))
while(next_permutation(b.begin(), b.end()))
{
vector <int> c = a;
int i = 0;
int j = 0;
bool f = true;
while(i < n && j < m)
{
if (c[i] > 0)
{
c[i] -= b[j];
j++;
}
if (c[i] == 0)
{
i++;
}
if (c[i] < 0)
{
f = false;
break;
}
}
if (f && i == n)
{
cout << "YES";
return 0;
}
}
}
cout << "NO";
return 0;
}
Compilation message
bank.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
70 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
384 KB |
Output is correct |
| 9 |
Correct |
71 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| 2 |
Correct |
23 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
21 ms |
384 KB |
Output is correct |
| 5 |
Correct |
148 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
9 ms |
384 KB |
Output is correct |
| 9 |
Correct |
160 ms |
384 KB |
Output is correct |
| 10 |
Correct |
31 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
70 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
384 KB |
Output is correct |
| 9 |
Correct |
71 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
356 KB |
Output is correct |
| 11 |
Correct |
23 ms |
512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
21 ms |
384 KB |
Output is correct |
| 14 |
Correct |
148 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
9 ms |
384 KB |
Output is correct |
| 18 |
Correct |
160 ms |
384 KB |
Output is correct |
| 19 |
Correct |
31 ms |
384 KB |
Output is correct |
| 20 |
Execution timed out |
1071 ms |
384 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
