Submission #18299403


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'){
                chmax(res, calc(l+1, mid-1) + calc(mid+1, r-1) + 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 0
Code Size 3062 Byte
Status WA
Exec Time 51 ms
Memory 3976 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 2
WA × 5
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 WA 50 ms 3932 KB
01 WA 43 ms 3932 KB
02 WA 51 ms 3976 KB
03 WA 49 ms 3892 KB
04 WA 41 ms 3912 KB
90 AC 8 ms 3528 KB
91 AC 2 ms 3468 KB