Submission #2009570
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
const int32_t inf = 1001001001;
const int64_t infll = 1001001001001001001ll;
const int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
template <typename T> using vector2d = vector<vector<T>>;
// clang-format off
template <typename T> void sort(vector<T> &v) { sort(all(v)); }
// ostream &operator<<(ostream &os, __int128_t value) { if (ostream::sentry(os)) { __uint128_t tmp = value < 0 ? -value : value; char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __int128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } if (in[0] == '-') value *= -1; return is; }
// ostream &operator<<(ostream &os, __uint128_t value) { if (ostream::sentry(os)) { char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[value % 10]; value /= 10; } while (value != 0); int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __uint128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } return is; }
template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }
struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;
inline int64_t in() { int64_t x = 0; cin >> x; return x; }
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on
string s;
// int x, y;
int x[2];
vector<int> a[2];
vector<vector<int>> dp;
int dfs(int i, int t, int idx) {
if (i == a[idx].size()) {
return (t - 8000) == x[idx];
}
if (~dp[i][t]) return dp[i][t];
return dp[i][t] = dfs(i + 1, t + a[idx][i], idx) | dfs(i + 1, t - a[idx][i], idx);
}
signed main(int argc, char *argv[]) {
cin >> s >> x[0] >> x[1];
s += "T";
int cnt = 0, idx = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'T') {
a[idx & 1].push_back(cnt);
cnt = 0;
idx++;
} else {
cnt++;
}
}
dp.assign(a[0].size(), vector<int>(16010, -1));
if (dfs(1, a[0][0] + 8000, 0)) {
dp.assign(a[1].size(), vector<int>(16010, -1));
if (dfs(0, 8000, 1)) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}
Submission Info
Submission Time |
|
Task |
D - FT Robot |
User |
Luzhiled |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3433 Byte |
Status |
AC |
Exec Time |
215 ms |
Memory |
248960 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
512 KB |
0_01.txt |
AC |
1 ms |
384 KB |
0_02.txt |
AC |
1 ms |
384 KB |
0_03.txt |
AC |
1 ms |
384 KB |
0_04.txt |
AC |
1 ms |
512 KB |
0_05.txt |
AC |
1 ms |
512 KB |
1_00.txt |
AC |
1 ms |
384 KB |
1_01.txt |
AC |
1 ms |
384 KB |
1_02.txt |
AC |
1 ms |
384 KB |
1_03.txt |
AC |
1 ms |
384 KB |
1_04.txt |
AC |
1 ms |
512 KB |
1_05.txt |
AC |
1 ms |
512 KB |
1_06.txt |
AC |
191 ms |
125696 KB |
1_07.txt |
AC |
117 ms |
125696 KB |
1_08.txt |
AC |
212 ms |
167424 KB |
1_09.txt |
AC |
191 ms |
167424 KB |
1_10.txt |
AC |
212 ms |
167424 KB |
1_11.txt |
AC |
75 ms |
167424 KB |
1_12.txt |
AC |
99 ms |
83968 KB |
1_13.txt |
AC |
99 ms |
83968 KB |
1_14.txt |
AC |
140 ms |
125696 KB |
1_15.txt |
AC |
142 ms |
125696 KB |
1_16.txt |
AC |
141 ms |
125696 KB |
1_17.txt |
AC |
140 ms |
125696 KB |
1_18.txt |
AC |
207 ms |
122880 KB |
1_19.txt |
AC |
123 ms |
123136 KB |
1_20.txt |
AC |
211 ms |
122880 KB |
1_21.txt |
AC |
127 ms |
125056 KB |
1_22.txt |
AC |
214 ms |
124928 KB |
1_23.txt |
AC |
210 ms |
123648 KB |
1_24.txt |
AC |
213 ms |
126080 KB |
1_25.txt |
AC |
215 ms |
123008 KB |
1_26.txt |
AC |
139 ms |
243584 KB |
1_27.txt |
AC |
114 ms |
248960 KB |
1_28.txt |
AC |
215 ms |
123008 KB |
1_29.txt |
AC |
128 ms |
124928 KB |
1_30.txt |
AC |
108 ms |
63744 KB |
1_31.txt |
AC |
62 ms |
61952 KB |
1_32.txt |
AC |
45 ms |
32512 KB |
1_33.txt |
AC |
46 ms |
31232 KB |
1_34.txt |
AC |
20 ms |
15744 KB |
1_35.txt |
AC |
13 ms |
14720 KB |
1_36.txt |
AC |
11 ms |
8320 KB |
1_37.txt |
AC |
9 ms |
9856 KB |
1_38.txt |
AC |
6 ms |
4096 KB |
1_39.txt |
AC |
5 ms |
4480 KB |
1_40.txt |
AC |
4 ms |
2176 KB |
1_41.txt |
AC |
3 ms |
2560 KB |
1_42.txt |
AC |
62 ms |
84352 KB |
1_43.txt |
AC |
50 ms |
84224 KB |
1_44.txt |
AC |
195 ms |
84480 KB |
1_45.txt |
AC |
114 ms |
84352 KB |
1_46.txt |
AC |
72 ms |
84096 KB |
1_47.txt |
AC |
60 ms |
84352 KB |
1_48.txt |
AC |
61 ms |
84224 KB |
1_49.txt |
AC |
60 ms |
84352 KB |