Submission #3018612
Source Code Expand
#include "bits/stdc++.h" #define esc(ret) cout << (ret) << endl,quick_exit(0) #define fcout(d) cout << fixed << setprecision(d) #define repU(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i) #define repD(i,s,t) for(int i = (int)(s); i >= (int)(t); --i) #define rep(i,n) repU(i,0,(n) - 1) #define rep1(i,n) repU(i,1,(n)) #define all(v) begin(v),end(v) #define vct vector #define prique priority_queue #define l_bnd lower_bound #define u_bnd upper_bound #define puf push_front #define pub push_back #define pof pop_front #define pob pop_back #define mkp make_pair #define mkt make_tuple #define fir first #define sec second #define qceil(n,d) ((n) > 0 ? ((n) - 1) / (d) + 1 : (n) / (d)) #define parity(a,b) ((a) & 1 == (b) & 1) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef pair<int,int> pii; typedef pair<db,int> pdi; const pii dir[] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} }; const int mod = 1e9 + 7; const int inf32 = (1 << 30) - 1; const ll inf64 = (1LL << 62) - 1; string S; int X,Y; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> S >> X >> Y; deque<int> x,y; x.pub(0); int t = 0; for(char c : S){ if(c == 'T'){ t = 1 - t; if(t) y.pub(0); else x.pub(0); }else{ if(t){ ++y.back(); }else{ ++x.back(); } } } bool dp[2][2][16002] = {}; dp[0][1][x.front()] = 1; //cout << x.front() << endl; x.pof(); t = 0; while(!x.empty()){ dp[t][1][0] |= dp[t][0][0]; dp[t][0][0] |= dp[t][1][0]; int l = x.front(); x.pof(); //cout << l << endl; rep(i,2)rep(j,8001){ dp[1 - t][i][j + l] |= dp[t][i][j]; if(l < j){ dp[1 - t][i][j - l] |= dp[t][i][j]; }else{ dp[1 - t][1 - i][l - j] |= dp[t][i][j]; } } rep(i,2) fill(all(dp[t][i]),0); t = 1 - t; } dp[t][1][0] |= dp[t][0][0]; dp[t][0][0] |= dp[t][1][0]; bool dp2[2][2][16002] = {}; dp2[0][0][0] = dp2[0][1][0] = 1; t = 0; while(!y.empty()){ int l = y.front(); y.pof(); rep(i,2)rep(j,8001){ dp2[1 - t][i][j + l] |= dp2[t][i][j]; if(l < j){ dp2[1 - t][i][j - l] |= dp2[t][i][j]; }else{ dp2[1 - t][1 - i][l - j] |= dp2[t][i][j]; } } rep(i,2) fill(all(dp[t][i]),0); t = 1 - t; } bool res2 = dp2[t][1][abs(Y)]; bool res1 = X > 0 ? dp[t][1][X] : dp[t][0][-X]; //cout << res1 << ' ' << res2 << endl; if(res1 & res2) cout << "Yes\n"; else cout << "No\n"; }
Submission Info
Submission Time | |
---|---|
Task | D - FT Robot |
User | jell |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2523 Byte |
Status | WA |
Exec Time | 313 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 384 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 | 384 KB |
0_05.txt | AC | 1 ms | 384 KB |
1_00.txt | AC | 1 ms | 384 KB |
1_01.txt | AC | 1 ms | 384 KB |
1_02.txt | WA | 1 ms | 384 KB |
1_03.txt | WA | 1 ms | 384 KB |
1_04.txt | AC | 1 ms | 384 KB |
1_05.txt | AC | 1 ms | 384 KB |
1_06.txt | WA | 152 ms | 384 KB |
1_07.txt | AC | 152 ms | 384 KB |
1_08.txt | WA | 208 ms | 384 KB |
1_09.txt | AC | 208 ms | 384 KB |
1_10.txt | WA | 205 ms | 384 KB |
1_11.txt | AC | 205 ms | 384 KB |
1_12.txt | WA | 103 ms | 384 KB |
1_13.txt | AC | 103 ms | 384 KB |
1_14.txt | WA | 157 ms | 384 KB |
1_15.txt | AC | 157 ms | 384 KB |
1_16.txt | WA | 156 ms | 384 KB |
1_17.txt | AC | 156 ms | 384 KB |
1_18.txt | WA | 152 ms | 384 KB |
1_19.txt | AC | 152 ms | 384 KB |
1_20.txt | WA | 152 ms | 384 KB |
1_21.txt | AC | 155 ms | 384 KB |
1_22.txt | WA | 155 ms | 384 KB |
1_23.txt | AC | 153 ms | 384 KB |
1_24.txt | WA | 156 ms | 384 KB |
1_25.txt | AC | 152 ms | 384 KB |
1_26.txt | WA | 306 ms | 384 KB |
1_27.txt | AC | 313 ms | 384 KB |
1_28.txt | WA | 152 ms | 384 KB |
1_29.txt | AC | 155 ms | 384 KB |
1_30.txt | WA | 79 ms | 384 KB |
1_31.txt | AC | 74 ms | 384 KB |
1_32.txt | WA | 40 ms | 384 KB |
1_33.txt | AC | 39 ms | 384 KB |
1_34.txt | WA | 20 ms | 384 KB |
1_35.txt | AC | 18 ms | 384 KB |
1_36.txt | WA | 11 ms | 384 KB |
1_37.txt | AC | 13 ms | 384 KB |
1_38.txt | WA | 6 ms | 384 KB |
1_39.txt | AC | 6 ms | 384 KB |
1_40.txt | WA | 3 ms | 384 KB |
1_41.txt | AC | 4 ms | 384 KB |
1_42.txt | AC | 103 ms | 384 KB |
1_43.txt | AC | 103 ms | 384 KB |
1_44.txt | AC | 104 ms | 384 KB |
1_45.txt | AC | 104 ms | 384 KB |
1_46.txt | AC | 105 ms | 384 KB |
1_47.txt | AC | 105 ms | 384 KB |
1_48.txt | AC | 105 ms | 384 KB |
1_49.txt | AC | 105 ms | 384 KB |