Submission #18299871


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define DEBUG
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) { os << ','; }
        os << v[i];
    }
    os << '}';
    return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
    cerr << " " << x;
    debugg(args...);
}
#define debug(...)                                                             \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,-1,0,1,1,-1,-1,1};
ll dx[8] = {-1,0,1,0,1,-1,1,-1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    int sz = a.size();
    for(auto itr = a.begin(); itr != a.end(); itr++){
		cout << *itr;
        sz--;
        if(sz) cout << " ";
	}
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){
	cout << a << " " << b << "\n";
}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
void mark() {cout << "#" << "\n";}
ll pcount(ll x) {return __builtin_popcountll(x);}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int dp[303][303];
bool vi[303][303];
string s;

int calc(int l, int r){
    if(vi[l][r]) return dp[l][r];
    if(r-l < 2) return 0;
    vi[l][r] = true;
    int res = 0;
    for(int mid=l; mid<r; mid++){
        chmax(res, calc(l,mid) + calc(mid+1,r));
    }
    if(s[l] == 'i' && s[r] == 'i'){
        for(int mid=l+1; mid<r; mid++){
            if(s[mid] == 'w'){
                int left = calc(l+1,mid-1);
                int right = calc(mid+1,r-1);
                if(left*3 == mid-l-1 && right*3 == r-mid-1){
                    chmax(res, left+right+1);
                }
            }
        }
    }
    return dp[l][r] = res;
}

int main(){
    cin >> s;
    int n = s.size();
    cout << calc(0,n-1) << "\n";
}

Submission Info

Submission Time
Task I - イウィ
User suta
Language C++ (GCC 9.2.1)
Score 5
Code Size 3211 Byte
Status AC
Exec Time 49 ms
Memory 4000 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 49 ms 3972 KB
01 AC 42 ms 3876 KB
02 AC 48 ms 4000 KB
03 AC 48 ms 3980 KB
04 AC 42 ms 3964 KB
90 AC 8 ms 3472 KB
91 AC 2 ms 3548 KB