Submission #1248890

#TimeUsernameProblemLanguageResultExecution timeMemory
1248890kitsuneBank (IZhO14_bank)C++20
100 / 100
175 ms10696 KiB
#include <bits/stdc++.h> /// kitsune using namespace std; #define fi first #define se second #define mp make_pair //#define int long long #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++) #define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--) typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; } template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; } const int siz = 1e5 + 2; const int SIZ = 1e6 + 2; const int mod = 1e9 + 7; const int maxx = 2e9; const ll MAXX = 1e18; const string file = "1"; int n, m; int a[20], b[20]; int s[1 << 20], p[1 << 20]; bool f[1 << 20]; bool g[1 << 20]; bool dp(int mask) { int pos = p[mask]; if (pos == n) { return true; } bool& res = f[mask]; bool& cal = g[mask]; if (cal) { return res; } res = false; rep (i, 0, m - 1) { if (mask & (1 << i)) { continue; } int new_mask = mask ^ (1 << i); int sum = s[new_mask]; if (sum <= a[pos]) { res |= dp(new_mask); } } cal = true; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (fopen((file + ".inp").c_str(), "r")) { freopen((file + ".inp").c_str(), "r", stdin); freopen((file + ".out").c_str(), "w", stdout); } cin >> n >> m; rep (i, 0, n - 1) { cin >> a[i]; a[i] += (i == 0 ? 0 : a[i - 1]); } rep (i, 0, m - 1) { cin >> b[i]; } rep (mask, 0, (1 << m) - 1) { rep (i, 0, m - 1) { if (mask & (1 << i)) { s[mask] += b[i]; } } p[mask] = upper_bound(a, a + n, s[mask]) - a; } cout << (dp(0) ? "YES" : "NO") << "\n"; // cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n"; return 0; }

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen((file + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen((file + ".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...