Submission #1221311

#TimeUsernameProblemLanguageResultExecution timeMemory
1221311aasrstagBank (IZhO14_bank)C++20
71 / 100
1095 ms8520 KiB
#pragma GCC optimize("O3") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define ll long long using namespace std; void setIO(string prob) { freopen((prob + ".in").c_str(), "r", stdin); freopen((prob + ".out").c_str(), "w", stdout); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); //setIO("txt"); int n, m; cin >> n >> m; vector <int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } vector <int> coins(m); for (int i = 0; i < m; i++){ cin >> coins[i]; } //dp[s] -> represents current salary paying + overflow //s represents subset //this is an ordering problem, because given some salaries we need to pay //if it is possible, some order exists of the bank notes where we can just pay the salaries //if no order exists, then it is impossible //vector <vector <bool>> dp(n, vector <bool>(1 << m, false)); vector <pair <int, int>> dp(1 << m, {-1, -1}); dp[0] = {0, 0}; for (int i = 0; i < n; i++){ for (int s = 1; s < (1 << m); s++){ for (int j = 0; j < m; j++){ if (s & (1 << j)){ //okay, we are adding coin j to s / {j} //dp[s / {j}] should have current count of salaries paid, and what is "overflow" //make sure not transitions from bad states if (dp[s ^ (1 << j)].first < i) continue; if (dp[s ^ (1 << j)].first == i + 1){ dp[s] = max(dp[s], make_pair(dp[s ^ (1 << j)].first, dp[s ^ (1 << j)].second + coins[j])); } else if (dp[s ^ (1 << j)].second + coins[j] == a[i]){ dp[s] = max(dp[s], make_pair(dp[s ^ (1 << j)].first + 1, 0)); } else if (dp[s ^ (1 << j)].second + coins[j] < a[i]){ dp[s] = max(dp[s], make_pair(dp[s ^ (1 << j)].first, dp[s ^ (1 << j)].second + coins[j])); } //otherwise, adding this coins goes above salary, so pretty useless } } } } bool pos = false; for (int s = 0; s < (1 << m); s++){ if (dp[s].first == n){ pos = true; } } cout << (pos ? "YES" : "NO"); }

Compilation message (stderr)

bank.cpp: In function 'void setIO(std::string)':
bank.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen((prob + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen((prob + ".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...