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
AC × 7
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