oj.uz

답안 #229943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229943 2020-05-07T08:15:15 Z mohamedsobhi777 Rima (COCI17_rima) C++14
56 / 140
 26 ms 2340 KB 
#pragma comment(linker, "/STACK: 3000000")

#include<bits/stdc++.h>

using namespace std ; 


const int N = 3e3 + 7 ; 

int n  ; 
string ss[N] ; 

struct trie{
    int nxt[N][27] ; 
    int cnt[N] ; 
    int t = 1 ; 
    int dp[N][2] ; 
    void add(string &add_ ){
        int cur = 1 ; 
        int sz = add_.size() ; 
        for(int i = 0 ;i < sz ;i++ ){
            int c = add_[i] - 'a' ; 
            if(!nxt[cur][c])nxt[cur][c] = ++t ;
            cur = nxt[cur][c] ;
        }
        cnt[cur] ++ ; 
    }

    int solve(int i , bool flag){
        if(dp[i][flag]!=-1) return dp[i][flag] ;
        if(flag && !cnt[i]) return 0 ; 
        int ret = 0 ; 
        int kids = 0 ;  
        
        for(int j = 0 ;j < 26 ;j ++){
            kids +=cnt[nxt[i][j]] ; 
        }
        vector<int> res = {0 , 0}; 
        for(int j = 0 ;j < 26 ; j++){
            if(nxt[i][j]){
                ret = max(ret ,  solve(nxt[i][j] , flag )  ) ; 
                ret = max(ret , solve(nxt[i][j] , 1) + kids ) ;
                res.push_back(solve(nxt[i][j] , 1) + kids) ; 
                
            }
        }   
        sort(res.begin() , res.end()) ; 
        ret = max(ret , res.back() + res[res.size()-2] - kids ) ; 
        return dp[i][flag] =ret ; 
    }

} tr; 

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ; 
    memset(tr.dp , -1 , sizeof tr.dp) ; 
    cin>>n ; 
    for(int i = 0 ; i < n ;i++){
        string x ; 
        cin>>x ; 
        reverse( x .begin() , x.end()) ; 
        tr.add(x) ; 
    }
    int ans = max(tr.solve(1 , 0 ) , tr.solve(1 , 1)) ; 
    cout<< ans;  
    return 0 ;
}

Compilation message

rima.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK: 3000000")

Subtask #1
56.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Runtime error 6 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 26 ms 1272 KB Output is correct
6 Runtime error 8 ms 2196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 2340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 2272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 7 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 8 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)