제출 #980911

#제출 시각아이디문제언어결과실행 시간메모리
980911Hadi_Alhamed은행 (IZhO14_bank)C++17
100 / 100
99 ms8792 KiB
//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)); vpi dp((1 << M) + 10); for(int Set = 0 ; Set < (1 << M) ; Set++) { for(int bill = 0; bill < M ; bill++) { if(Set & (1 << bill)) { if(dp[Set ^ (1 << bill)].S + B[bill] == A[ dp[Set ^ (1 << bill)].F]) { //adding this bill will cause an increase in covered elements dp[Set] = max(dp[Set] , {dp[Set ^ (1 << bill)].F + 1 , 0}); }else { //no increase in covered elements but //we might be able to enhance the available sum dp[Set] = max(dp[Set] , { dp[Set ^ (1 << bill)].F , dp[Set ^ ( 1 << bill)].S + B[bill] } ); } } } if(dp[Set].F == N) { YES; return; } } 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 */

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...