Submission #6406966
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
// typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
// container util
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
// repetition
#define FOR(i,m,n) for(ll (i) = ((ll) m); (i) < ((ll) n); ++(i))
#define RFOR(i,m,n) for(ll (i) = ((ll) (m)-1); (i) >= ((ll) n); --(i))
#define REP(i,n) FOR(i,0,n)
// i/o
#define TFOUT(b,t,f) cout << ((b)? (t) : (f)) << endl
//constant
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INFTY = (1<<21);
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
bool is_iwi(char x, char y, char z) {
return x == 'i' && y == 'w' && z == 'i';
}
int main() {
string s; cin >> s;
vvi dp;
REP(i, s.length()) dp.emplace_back(s.length(), 0);
for (int len = 1; len <= s.length(); ++len) {
for (int l = 0; l < s.length()-len+1; ++l) {
int r = l + len - 1;
if (len < 3) {
dp[l][r] = 0;
continue;
}
if (
len % 3 == 0 &&
(
(dp[l+1][r-2] == len/3-1 && is_iwi(s[l], s[r-1], s[r])) ||
(dp[l+2][r-1] == len/3-1 && is_iwi(s[l], s[l+1], s[r]))
)
) {
dp[l][r] = len/3;
continue;
}
int val = 0;
for (int m = l; m < r; ++m) {
val = max(val, dp[l][m] + dp[m+1][r]);
}
dp[l][r] = val;
}
}
cout << dp[0][s.length()-1] << endl;
return 0;
}
//
// dp[l][r] = s[l:r+1]において削除できる回数
// 削除パターンは以下の2通りである :
// 1. s[l:m]s[m+1:r+1]が独立に消える
// 2. s[l+2:r]が全て消えてs[l]s[l+1]s[r]=iwi
// またはs[l+1:r-1]が全て消えてs[l]s[r-1]s[r]=iwi
// N=len(s) <= 300なので O(N^3)でも十分に間に合っちゃう!
//
Submission Info
Submission Time |
|
Task |
I - イウィ |
User |
kumachan_atcoder |
Language |
C++14 (GCC 5.4.1) |
Score |
5 |
Code Size |
2566 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
640 KB |
Judge Result
Set Name |
All |
Score / Max Score |
5 / 5 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
7 ms |
640 KB |
01 |
AC |
7 ms |
640 KB |
02 |
AC |
7 ms |
640 KB |
03 |
AC |
7 ms |
640 KB |
04 |
AC |
6 ms |
512 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |