제출 #229894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229894		mohamedsobhi777	Rima (COCI17_rima)	C++14	28 / 140	815 ms	10072 KiB

rima

#include<bits/stdc++.h>

using namespace std ; 


const int N = 1e5 + 7 ; 

int n ; 
int dp[N] ; 
int ans ; 
string ss[N] ; 
bool katch(int i , int j){
    if( abs( (int) ss[i].size() - (int) ss[j].size()) > 1 )  return 0 ; 
    string s1 = ss[i] .substr(0 , ss[j].size() -1 ) ; 
    string s2 = ss[j] .substr(0 , ss[j].size()-1) ; 
    return (s1 == s2) ; 
}

bool match(int i , int j){
    return katch(i , j ) ; 
}

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    cin>>n ; 
    for(int i = 0 ; i < n ;i++){
        cin>>ss[i] ;
        reverse( ss[i] .begin() , ss[i].end()) ; 
    }
    sort(ss , ss + n) ;
    for(int i = 0 ;i < n ;i++){ 
        dp[i] = 1 ; 
        for(int j = 0 ; j < i ; j++){
            if(match(j , i)){
                dp[i] = max(dp[i] , dp[j]+1) ; 
            }
        }
        ans = max(ans , dp[i]) ; 
    }
    cout<< ans ; 
    return 0 ;
}

• Subtask 1: 28 / 140