結果
| 問題 | No.1405 ジグザグロボット |
| ユーザー |
 SSRS
|
| 提出日時 | 2021-02-18 23:10:05 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,242 bytes |
| コンパイル時間 | 2,318 ms |
| コンパイル使用メモリ | 196,764 KB |
| 実行使用メモリ | 6,584 KB |
| 最終ジャッジ日時 | 2023-10-16 23:58:29 |
| 合計ジャッジ時間 | 15,753 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | WA | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | WA | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | AC | 66 ms
6,460 KB |
| testcase_18 | WA | - |
| testcase_19 | TLE | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
vector<int> dy = {1, 0, 0};
vector<int> dx = {0, 1, -1};
int main(){
int N, X, Y;
cin >> N >> X >> Y;
string S;
cin >> S;
vector<string> T(1);
for (int i = 0; i < N; i++){
if (S[i] == 'S'){
T.push_back("");
} else {
T.back() += S[i];
}
}
int K = T.size();
if (Y >= K){
cout << -1 << endl;
} else {
vector<vector<int>> a(K + 1, vector<int>(K + 1, 0));
for (int i = 0; i < K; i++){
int c = 0;
for (int j = i + 1; j <= K; j++){
int sz = T[j].size();
for (int k = 0; k < sz; k++){
if (T[j][k] == 'L'){
c--;
c = max(c, 0);
} else {
c++;
}
}
a[i][j] = c;
}
}
vector<vector<int>> dp(Y + 2, vector<int>(K + 1, -INF));
dp[0][0] = 0;
for (int i = 0; i <= Y; i++){
for (int j = 0; j < K; j++){
for (int k = j + 1; k <= K; k++){
dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[j][k]);
}
}
}
if (dp[Y + 1][K] < X){
cout << -1 << endl;
} else {
vector<int> P(Y + 2);
P[Y + 1] = K;
for (int i = Y; i >= 0; i--){
for (int j = 0; j < P[i + 1]; j++){
if (dp[i + 1][P[i + 1]] == dp[i][j] + a[j][P[i + 1]]){
P[i] = j;
break;
}
}
}
vector<int> L(Y + 1);
for (int i = 0; i <= Y; i++){
L[i] = dp[i][P[i]];
}
vector<string> T2(Y + 1);
for (int i = 0; i <= Y; i++){
for (int j = P[i]; j < P[i + 1]; j++){
T2[i] += T[j];
T2[i] += 'S';
}
}
T2[Y].pop_back();
vector<int> R = L;
for (int i = 0; i <= Y; i++){
int x = L[i];
int l = T2[i].size();
for (int j = 0; j < l; j++){
if (T2[i][j] == 'L'){
x--;
}
if (T2[i][j] == 'R'){
x++;
}
x = max(x, L[i]);
R[i] = max(R[i], x);
}
}
set<pair<int, int>> st;
for (int i = 0; i <= Y; i++){
for (int j = L[i]; j <= R[i]; j++){
st.insert(make_pair(i, j));
}
}
vector<vector<int>> ans(Y + 2);
for (auto P : st){
int y = P.first;
int x = P.second;
for (int i = 0; i < 3; i++){
int y2 = y + dy[i];
int x2 = x + dx[i];
if (st.count(make_pair(y2, x2)) == 0){
ans[y2].push_back(x2);
}
}
}
for (int i = 0; i < Y + 2; i++){
sort(ans[i].begin(), ans[i].end());
ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
}
while (true){
set<pair<int, int>> st2;
for (int i = 0; i < Y + 2; i++){
int cnt = ans[i].size();
for (int j = 0; j < cnt; j++){
st2.insert(make_pair(i, ans[i][j]));
}
}
int cx = 0, cy = 0;
vector<int> up(Y + 1);
vector<int> id(Y);
for (int i = 0; i < N; i++){
int x2 = cx, y2 = cy;
if (S[i] == 'L'){
x2--;
}
if (S[i] == 'R'){
x2++;
}
if (S[i] == 'S'){
y2++;
}
if (st2.count(make_pair(y2, x2)) == 1){
x2 = cx;
y2 = cy;
}
if (y2 != cy){
id[cy] = i;
up[cy] = x2;
}
cx = x2;
cy = y2;
}
up[Y] = cx;
if (cx == X){
break;
}
vector<int> d(Y + 1);
d[0] = up[0];
for (int j = 1; j <= Y; j++){
d[j] = up[j] - up[j - 1];
}
int p = 0;
while (d[p] == 0){
p++;
}
ans[p].back()--;
set<pair<int, int>> st3;
for (int i = 0; i < Y + 2; i++){
int cnt = ans[i].size();
for (int j = 0; j < cnt; j++){
st3.insert(make_pair(i, ans[i][j]));
}
}
vector<int> px(N + 1), py(N + 1);
px[0] = 0;
py[0] = 0;
for (int i = 0; i < N; i++){
px[i + 1] = px[i];
py[i + 1] = py[i];
if (S[i] == 'L'){
px[i + 1]--;
}
if (S[i] == 'R'){
px[i + 1]++;
}
if (S[i] == 'S'){
py[i + 1]++;
}
if (st3.count(make_pair(py[i + 1], px[i + 1])) == 1 || py[i + 1] > p){
px[i + 1] = px[i];
py[i + 1] = py[i];
}
}
if (px[id[p]] != up[p]){
for (int i = p + 1; i < Y + 2; i++){
int cnt = ans[i].size();
for (int j = 0; j < cnt; j++){
ans[i][j]--;
}
}
}
}
for (int i = 0; i < Y + 2; i++){
ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
}
int M = 0;
for (int i = 0; i < Y + 2; i++){
M += ans[i].size();
}
cout << M << endl;
for (int i = 0; i < Y + 2; i++){
int cnt = ans[i].size();
for (int j = 0; j < cnt; j++){
cout << ans[i][j] << ' ' << i << endl;
}
}
}
}
}