| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 980817 |
2024-05-12T13:11:06 Z |
Hadi_Alhamed |
Bank (IZhO14_bank) |
C++17 |
|
68 ms |
456 KB |
//to live is to die
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n) \
for (int i = 0; i <= n; i++) \
{ \
a[i] = 0; \
}
#define clearMat(a, n, m, d) \
for (int i = 0; i <= n; i++) \
{ \
for (int j = 0; j <= m; j++) \
a[i][j] = d; \
}
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)
#define db(x) cerr << #x <<" "; _print(x); cerr << endl;
#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void _print(int x)
{
cerr << x;
}
void _print(ll x)
{
cerr << x;
}
void _print(string x)
{
cerr << x;
}
void _print(char x)
{
cerr << x;
}
void _print(double x)
{
cerr << x;
}
void _print(ull x)
{
cerr << x;
}
void _print(vl x)
{
for(auto e : x)
{
cerr << e << " ";
}
cerr << "\n";
}
void print(vpi x)
{
for(auto e : x)
{
cerr << e.F << " " << e.S << "\n";
}
cerr << "\n";
}
void _print(vi x)
{
for(auto e : x)
{
cerr << e << " ";
}
cerr << "\n";
}
void _print(deque<ll>x)
{
for(auto e : x)
{
cerr << e << " ";
}
cerr << "\n";
}
//order_of_key(k): # of elements less than k (which is the index of x = k)
//find_by_order(k); iterator of the k-th element
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> bool ckmin(T& a, const T& b)
{
return b<a?a=b,1:0;
}
template<class T> bool ckmax(T& a, const T& b)
{
return a<b?a=b,1:0;
}
template<typename T> istream& operator>>(istream& in, vector<T>& a)
{
for(auto &x : a) in >> x;
return in;
};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a)
{
for(auto &x : a) out << x << ' ';
return out;
};
// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
return (char)(num + '0');
}
ll const MAX = 1e18+1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
ll const SIZE = 2e5 + 900;
const int LOG = 20;
template<typename T, typename T2>
void add(T & X, T2 Y)
{
X = (X + Y + MOD)%MOD;
}
template<typename T, typename T2>
T mult(T X, T2 Y)
{
return X * Y % MOD;
}
void setIO(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
//x & (-x) give me the minBit of x
// x & (x - 1) turns off rightmost bit
const ll MAX_N = 1000006;
ll const P = 10000003;
ll const _P = 998244353;
ll const M = 1e9 + 9;
void solve()
{
int N, M;
cin >> N >> M;
vi A(N);
vi B(M);
cin >> A;
cin >> B;
sort(all(A));
int cnt{};
vi vis(100);
for(int j = 0 ; j < N ; j++)
{
for(int Set = 1 ; Set < (1 << M) ; Set++)
{
int sum = 0;
bool flag = 1;
for(int i = 0 ; i < M ; i++)
{
if(Set & (1 << i))
{
if(vis[i])
{
flag = 0;
break;
}
else{
sum += B[i];
}
}
}
if(flag && sum == A[j])
{
// db(sum);
cnt++;
for(int i = 0 ;i < M ; i++)
{
if(Set & (1 << i))
{
vis[i] = 1;
}
}
break;
}
}
}
cnt == N ? YES : NO;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// setIO("movie");
int T = 1;
// cin >> T;
while(T--)
{
solve();
}
return 0;
}
/* stuff you should look for
* WRITE STUFF DOWN, ON PAPER
* BFS THEN DFS
* int overflow, array bounds
* special cases (n=1?)
* do sm th instead of nothing and stay organized
* DON'T GET STUCK ON ONE APPROACH
* (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
* 1- problem to subProblem
* 2- from simple to complex: start with a special
* problem and then try to update the solution for general case
* -(constraints - > solve it with none , one,two ... of them till you reach the given problem
-(no constraints - > try to give it some)
-how a special case may be incremented
* 3-Simplification by Assumptions
* REVERSE PROBLEM
* PROBLEM ABSTRACTION
* SMALL O BSERVATIONS MIGHT HELP ALOT
* WATCH OUT FOR TIME
* RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
* CORRECT IDEA, NEED MORE OBSERVATIONS
* CORRECT APPROACH, WRONG IDEA
* WRONG APPROACH
* THINK CONCRETE THEN SYMBOL,
* having the solution for the first m state , can we solve it for m + 1 ?
* in many cases incremental thinking needs data sorting
*/
Compilation message
bank.cpp: In function 'void setIO(std::string)':
bank.cpp:165:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
68 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
62 ms |
428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
456 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
68 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
62 ms |
428 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
456 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
