結果
| 問題 |
No.1405 ジグザグロボット
|
| コンテスト | |
| ユーザー |
 SSRS
|
| 提出日時 | 2021-02-18 01:25:47 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,291 bytes |
| コンパイル時間 | 2,754 ms |
| コンパイル使用メモリ | 193,656 KB |
| 実行使用メモリ | 40,960 KB |
| 最終ジャッジ日時 | 2024-09-16 23:40:10 |
| 合計ジャッジ時間 | 23,669 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 TLE * 1 -- * 2 |
ソースコード
#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++){
for (int j = i + 1; j <= K; j++){
for (int k = i; k < j; k++){
int sz = T[k].size();
for (int l = 0; l < sz; l++){
if (T[k][l] == 'L'){
a[i][j]--;
} else {
a[i][j]++;
}
a[i][j] = max(a[i][j], 0);
}
}
}
}
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;
}
}
}
}
}