提出 #18299871


ソースコード 拡げる

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";
}

提出情報

提出日時
問題 I - イウィ
ユーザ suta
言語 C++ (GCC 9.2.1)
得点 5
コード長 3211 Byte
結果 AC
実行時間 49 ms
メモリ 4000 KB

ジャッジ結果

セット名 All
得点 / 配点 5 / 5
結果
AC × 7
セット名 テストケース
All 00, 01, 02, 03, 04, 90, 91
ケース名 結果 実行時間 メモリ
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