Submission #3425702
Source Code Expand
// g++ -std=c++11 a.cpp #include<iostream> #include<vector> #include<string> #include<algorithm> #include<map> #include<set> #include<unordered_map> #include<utility> #include<cmath> #include<random> #include<cstring> #include<queue> #include<stack> #include<bitset> #include<cstdio> #include<sstream> #include<iomanip> #include<assert.h> #include<typeinfo> #define loop(i,a,b) for(int i=a;i<b;i++) #define rep(i,a) loop(i,0,a) #define FOR(i,a) for(auto i:a) #define pb push_back #define all(in) in.begin(),in.end() #define shosu(x) fixed<<setprecision(x) #define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl; #define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl; using namespace std; //kaewasuretyuui typedef long long ll; #define int ll typedef int Def; typedef pair<Def,Def> pii; typedef vector<Def> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<vp> vvp; typedef vector<string> vs; typedef vector<double> vd; typedef vector<vd> vvd; typedef pair<Def,pii> pip; typedef vector<pip>vip; //#define mt make_tuple //typedef tuple<int,int,int> tp; //typedef vector<tp> vt; template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;} template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;} //template<class C>constexpr int size(const C &c){return (int)c.size();} //template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;} const double PI=acos(-1); const double EPS=1e-9; Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int n; string s; string f(int l,int r){ vvi pos((r-l)/2,vi(2)); int q; q=0;loop(i,l,r)if(s[i]=='a')pos[q++][0]=i; q=0;loop(i,l,r)if(s[i]=='b')pos[q++][1]=i; string t=""; if(s[l]=='a'){ q=-1; rep(i,pos.size()){ if(pos[i][0]>q){ t+="ab"; q=pos[i][1]; } } }else{ vi used(r-l); rep(i,pos.size()){ string w=""; used[pos[pos.size()-1-i][0]-l]=1; used[pos[pos.size()-1-i][1]-l]=1; rep(j,used.size())if(used[j])w+=s[l+j]; cmax(t,w); } } return t; } signed main(){ cin>>n>>s; vs dp; int t=0,p=0; rep(i,s.size()){ if(s[i]=='a')t++; else t--; if(!t){ dp.pb(f(p,i+1)); p=i+1; } } int N=dp.size(); for(int i=N-1;i>=0;i--){ string w=dp[i]; loop(j,i+1,N)cmax(w,dp[i]+dp[j]); if(i!=N-1)cmax(w,dp[i+1]); dp[i]=w; } cout<<dp[0]<<endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Synchronized Subsequence |
User | ixmel_rd |
Language | C++14 (GCC 5.4.1) |
Score | 1600 |
Code Size | 2570 Byte |
Status | AC |
Exec Time | 799 ms |
Memory | 10496 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 1600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example_0, example_1, example_2, example_3 |
All | bigrand_0, bigrand_1, bigrand_10, bigrand_11, bigrand_12, bigrand_13, bigrand_14, bigrand_2, bigrand_3, bigrand_4, bigrand_5, bigrand_6, bigrand_7, bigrand_8, bigrand_9, bigtoken_0, bigtoken_1, bigtoken_2, bigtoken_3, bigtoken_4, bigtoken_5, bigtoken_6, bigtoken_7, bigtoken_8, bigtoken_9, example_0, example_1, example_2, example_3, koredetanomu_0, koredetanomu_1, koredetanomu_2, koredetanomu_3, koredetanomu_4, koredetanomu_5, koredetanomu_6, koredetanomu_7, lowheight_0, lowheight_1, lowheight_2, lowheight_3, lowheight_4, lowheight_5, lowheight_6, lowheight_7, lowheight_8, lowheight_9, midtoken_0, midtoken_1, midtoken_2, midtoken_3, midtoken_4, midtoken_5, midtoken_6, midtoken_7, midtoken_8, midtoken_9, midtoken_sorted_0, midtoken_sorted_1, midtoken_sorted_2, midtoken_sorted_3, midtoken_sorted_4, midtoken_sorted_5, midtoken_sorted_6, midtoken_sorted_7, midtoken_sorted_8, midtoken_sorted_9, smallrand_0, smallrand_1, smallrand_2, smallrand_3, smallrand_4, smalltoken_0, smalltoken_1, smalltoken_2, smalltoken_3, smalltoken_4, smalltoken_5, smalltoken_6, smalltoken_7, smalltoken_8, smalltoken_9, smalltoken_sorted_0, smalltoken_sorted_1, smalltoken_sorted_2, smalltoken_sorted_3, smalltoken_sorted_4, smalltoken_sorted_5, smalltoken_sorted_6, smalltoken_sorted_7, smalltoken_sorted_8, smalltoken_sorted_9, specialtoken_0, specialtoken_1, specialtoken_2, specialtoken_3, specialtoken_4, specialtoken_5, specialtoken_sorted_0, specialtoken_sorted_1, specialtoken_sorted_2, specialtoken_sorted_3, specialtoken_sorted_4, specialtoken_sorted_5 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
bigrand_0 | AC | 2 ms | 384 KB |
bigrand_1 | AC | 2 ms | 384 KB |
bigrand_10 | AC | 9 ms | 384 KB |
bigrand_11 | AC | 4 ms | 256 KB |
bigrand_12 | AC | 2 ms | 384 KB |
bigrand_13 | AC | 7 ms | 256 KB |
bigrand_14 | AC | 3 ms | 256 KB |
bigrand_2 | AC | 13 ms | 384 KB |
bigrand_3 | AC | 2 ms | 384 KB |
bigrand_4 | AC | 8 ms | 256 KB |
bigrand_5 | AC | 2 ms | 384 KB |
bigrand_6 | AC | 2 ms | 384 KB |
bigrand_7 | AC | 11 ms | 384 KB |
bigrand_8 | AC | 5 ms | 256 KB |
bigrand_9 | AC | 21 ms | 384 KB |
bigtoken_0 | AC | 34 ms | 512 KB |
bigtoken_1 | AC | 2 ms | 384 KB |
bigtoken_2 | AC | 33 ms | 512 KB |
bigtoken_3 | AC | 2 ms | 384 KB |
bigtoken_4 | AC | 31 ms | 512 KB |
bigtoken_5 | AC | 2 ms | 384 KB |
bigtoken_6 | AC | 37 ms | 512 KB |
bigtoken_7 | AC | 2 ms | 384 KB |
bigtoken_8 | AC | 36 ms | 512 KB |
bigtoken_9 | AC | 2 ms | 384 KB |
example_0 | AC | 1 ms | 256 KB |
example_1 | AC | 1 ms | 256 KB |
example_2 | AC | 1 ms | 256 KB |
example_3 | AC | 1 ms | 256 KB |
koredetanomu_0 | AC | 8 ms | 384 KB |
koredetanomu_1 | AC | 7 ms | 384 KB |
koredetanomu_2 | AC | 7 ms | 384 KB |
koredetanomu_3 | AC | 7 ms | 384 KB |
koredetanomu_4 | AC | 7 ms | 384 KB |
koredetanomu_5 | AC | 7 ms | 384 KB |
koredetanomu_6 | AC | 7 ms | 384 KB |
koredetanomu_7 | AC | 7 ms | 384 KB |
lowheight_0 | AC | 33 ms | 512 KB |
lowheight_1 | AC | 2 ms | 384 KB |
lowheight_2 | AC | 37 ms | 512 KB |
lowheight_3 | AC | 2 ms | 384 KB |
lowheight_4 | AC | 33 ms | 512 KB |
lowheight_5 | AC | 2 ms | 384 KB |
lowheight_6 | AC | 37 ms | 512 KB |
lowheight_7 | AC | 2 ms | 384 KB |
lowheight_8 | AC | 35 ms | 512 KB |
lowheight_9 | AC | 2 ms | 384 KB |
midtoken_0 | AC | 13 ms | 256 KB |
midtoken_1 | AC | 5 ms | 256 KB |
midtoken_2 | AC | 4 ms | 256 KB |
midtoken_3 | AC | 3 ms | 256 KB |
midtoken_4 | AC | 3 ms | 256 KB |
midtoken_5 | AC | 3 ms | 256 KB |
midtoken_6 | AC | 3 ms | 256 KB |
midtoken_7 | AC | 3 ms | 256 KB |
midtoken_8 | AC | 2 ms | 256 KB |
midtoken_9 | AC | 3 ms | 256 KB |
midtoken_sorted_0 | AC | 29 ms | 1024 KB |
midtoken_sorted_1 | AC | 8 ms | 640 KB |
midtoken_sorted_2 | AC | 6 ms | 512 KB |
midtoken_sorted_3 | AC | 4 ms | 384 KB |
midtoken_sorted_4 | AC | 3 ms | 384 KB |
midtoken_sorted_5 | AC | 3 ms | 384 KB |
midtoken_sorted_6 | AC | 3 ms | 384 KB |
midtoken_sorted_7 | AC | 3 ms | 384 KB |
midtoken_sorted_8 | AC | 3 ms | 256 KB |
midtoken_sorted_9 | AC | 3 ms | 256 KB |
smallrand_0 | AC | 1 ms | 256 KB |
smallrand_1 | AC | 1 ms | 256 KB |
smallrand_2 | AC | 1 ms | 256 KB |
smallrand_3 | AC | 1 ms | 256 KB |
smallrand_4 | AC | 1 ms | 256 KB |
smalltoken_0 | AC | 685 ms | 2304 KB |
smalltoken_1 | AC | 215 ms | 640 KB |
smalltoken_2 | AC | 110 ms | 384 KB |
smalltoken_3 | AC | 50 ms | 384 KB |
smalltoken_4 | AC | 36 ms | 256 KB |
smalltoken_5 | AC | 27 ms | 256 KB |
smalltoken_6 | AC | 20 ms | 256 KB |
smalltoken_7 | AC | 19 ms | 256 KB |
smalltoken_8 | AC | 22 ms | 256 KB |
smalltoken_9 | AC | 11 ms | 256 KB |
smalltoken_sorted_0 | AC | 799 ms | 10496 KB |
smalltoken_sorted_1 | AC | 340 ms | 5248 KB |
smalltoken_sorted_2 | AC | 164 ms | 3328 KB |
smalltoken_sorted_3 | AC | 146 ms | 2560 KB |
smalltoken_sorted_4 | AC | 113 ms | 2048 KB |
smalltoken_sorted_5 | AC | 52 ms | 1664 KB |
smalltoken_sorted_6 | AC | 42 ms | 1408 KB |
smalltoken_sorted_7 | AC | 33 ms | 1280 KB |
smalltoken_sorted_8 | AC | 25 ms | 1024 KB |
smalltoken_sorted_9 | AC | 23 ms | 1024 KB |
specialtoken_0 | AC | 9 ms | 512 KB |
specialtoken_1 | AC | 6 ms | 256 KB |
specialtoken_2 | AC | 4 ms | 256 KB |
specialtoken_3 | AC | 4 ms | 256 KB |
specialtoken_4 | AC | 4 ms | 256 KB |
specialtoken_5 | AC | 4 ms | 256 KB |
specialtoken_sorted_0 | AC | 11 ms | 1280 KB |
specialtoken_sorted_1 | AC | 8 ms | 1024 KB |
specialtoken_sorted_2 | AC | 6 ms | 896 KB |
specialtoken_sorted_3 | AC | 5 ms | 640 KB |
specialtoken_sorted_4 | AC | 5 ms | 640 KB |
specialtoken_sorted_5 | AC | 4 ms | 512 KB |