Submission #5631559
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef vector<pll> vpll;
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
inline void IN(void){
return;
}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
cin >> first;
IN(rest...);
return;
}
inline void OUT(void){
cout << "\n";
return;
}
template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
cout << first << " ";
OUT(rest...);
return;
}
template <typename T>
void vec_print(vector<T> VEC){
REP(i, VEC.size()){
cout << VEC[i] << " ";
}
cout << "\n";
};
template <typename T>
void mat_print(vector<vector<T> > MAT){
REP(i, MAT.size()){
REP(j, MAT[i].size()){
cout << MAT[i][j] << " ";
}
cout << "\n";
}
};
template <typename CLASS1, typename CLASS2>
class HOGE{
public:
CLASS1 key;
CLASS2 value;
HOGE(void){
return;
};
HOGE(CLASS1 key, CLASS2 value){
this->key = key;
this->value = value;
};
~HOGE(void){
return;
};
void print(void){
cout << "key : " << key << ", value : " << value << "\n";
return;
};
bool operator==(const HOGE &obj){
return (this->value == obj.value);
};
bool operator<(const HOGE &obj){
return (this->value < obj.value);
};
bool operator>(const HOGE &obj){
return (this->value > obj.value);
};
};
template <typename CLASS1, typename CLASS2>
bool operator==(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value == hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator<(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value < hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator>(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value > hoge2.value;
};
constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);
map<string, ll> mp;
ll search(string str){
ll ans = 0;
if(mp.find(str)!=mp.end()) return mp[str];
vector<string> vec_str;
string tmp1 = "";
for(int i=0; i+1<str.size(); ++i){
tmp1 += str[i];
if(str[i]=='w' && str[i+1]=='w'){
vec_str.pb(tmp1);
tmp1 = "";
}
}
tmp1 += str[str.size()-1];
vec_str.pb(tmp1);
for(auto str_now : vec_str){
ll ans_tmp = 0;
for(int i=0; i+2<str_now.size(); ++i){
if(str_now[i]=='i' && str_now[i+1]=='w' && str_now[i+2]=='i'){
string str_now_tmp = str_now;
REP(j,3) str_now_tmp.erase(str_now_tmp.begin() + i);
ans_tmp = max(ans_tmp, search(str_now_tmp)+1);
}
}
ans += ans_tmp;
mp[str_now] = ans_tmp;
}
return mp[str] = ans;
}
int main(){
cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)
string str;
IN(str);
vector<string> vec_str;
string str_tmp = "";
for(int i=0; i+1<str.size(); ++i){
str_tmp += str[i];
if(str[i] == 'w' && str[i+1] == 'w'){
vec_str.pb(str_tmp);
str_tmp = "";
}
}
str_tmp += str[str.size()-1];
vec_str.pb(str_tmp);
ll ans = 0;
REP(i, vec_str.size()){
ans += search(vec_str[i]);
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
I - イウィ |
User |
fockl |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4219 Byte |
Status |
TLE |
Exec Time |
2105 ms |
Memory |
28416 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 5 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
1 ms |
256 KB |
01 |
AC |
1 ms |
256 KB |
02 |
AC |
6 ms |
384 KB |
03 |
AC |
4 ms |
384 KB |
04 |
TLE |
2105 ms |
28416 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |