QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #526214 | #7277. Bring Down the | skittles1412# | 0 | 0ms | 3548kb | C++17 | 2.6kb | 2024-08-21 12:21:20 | 2024-08-21 12:21:20 |
answer
// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
inline void init_io() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
}
template <typename T>
vector<T> iota(int n, const T& x) {
vector<T> arr(n);
iota(begin(arr), end(arr), x);
return arr;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
out << "[";
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << ", ";
}
out << arr[i];
}
return out << "]";
}
template <typename T>
int c_lb(const vector<T>& arr, const T& x) {
return int(lower_bound(begin(arr), end(arr), x) - begin(arr));
}
template <typename T>
int c_ub(const vector<T>& arr, const T& x) {
return int(upper_bound(begin(arr), end(arr), x) - begin(arr));
}
template <typename T>
T reversed(T arr) {
reverse(begin(arr), end(arr));
return arr;
}
template <typename T>
T sorted(T arr) {
sort(begin(arr), end(arr));
return arr;
}
template <typename T>
bool on(T mask, int bit) {
return (mask >> bit) & 1;
}
template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
long kv;
map<array<long, 4>, bool> dp_memo;
bool dp(long x1, long f1, long x2, long f2) {
if (x1 < 0) {
assert(x2 >= 0);
return false;
}
if (x2 <= 0) {
return true;
}
long a1 = max(long(0), x1 - kv * f2);
auto [it, inserted] = dp_memo.insert({{x1, f1, x2, f2}, false});
bool& ans = it->second;
if (!inserted) {
return ans;
}
if (f2) {
ans = ans || !dp(x2, f2 - 1, x1, f1);
}
ans = ans || !dp(x2 - a1, f2, x1, f1);
return ans;
}
void solve() {
long x1, f1, x2, f2;
cin >> x1 >> f1 >> x2 >> f2;
if (dp(x1, f1, x2, f2)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
int main() {
init_io();
int q;
cin >> kv >> q;
while (q--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 5
Accepted
time: 0ms
memory: 3548kb
input:
17 2 42 1 33 1 42 1 33 7
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: 0
Time Limit Exceeded
input:
2 250000 75 16 56 55 50 9 49 60 18 67 62 5 30 54 61 39 22 39 42 31 26 30 55 1 23 30 53 16 55 13 6 44 69 8 58 72 53 7 60 12 29 14 26 34 37 64 24 71 19 3 40 1 64 13 33 65 67 24 68 3 64 17 50 66 71 6 62 13 15 29 26 24 51 30 34 45 46 5 40 72 54 52 60 49 35 21 18 30 39 31 35 34 30 74 72 5 74 12 6 15 11 4...
output:
NO NO YES YES NO YES NO NO NO YES NO NO NO NO YES NO YES NO NO NO YES NO NO YES YES NO YES YES NO YES YES NO NO YES NO NO YES YES YES NO NO NO NO YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO NO NO YES NO NO NO YES YES NO YES NO YES NO YES YES YES YES NO YES YES YES NO YES NO NO NO NO YES ...
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Memory Limit Exceeded
Test #28:
score: 0
Memory Limit Exceeded
input:
1 250000 554333015044 833858497873 833858497874 554333015044 655160857180 306396306924 306396306917 655160857187 374728598365 176680698490 176680698490 374728598365 764650258714 835600427315 835600427309 764650258720 521594231110 318048536486 318048536482 521594231115 273627794040 449769302710 10899...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%