Submission #229520

#	Time	Username	Problem	Language	Result	Execution time	Memory
229520		MohamedAhmed04	Rima (COCI17_rima)	C++14	42 / 140	68 ms	79608 KiB

rima

//bruteforce to make sure that I understood the problem right.
 
#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 19 ;
 
string arr[MAX] ;
bool mark[MAX][MAX] ;
int n ;
 
int dp[MAX][(1 << MAX)] ;
 
int solve(int last , int mask)
{
    int &ret = dp[last][mask] ;
    if(ret != -1)
        return ret ;
    ret = 0 ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(mark[i][last] == 0 || (mask & (1 << i)))
            continue ;
        ret = max(ret , solve(i , mask | (1 << i)) + 1) ;
    }
    return ret ;
}
 
int main()
{
    memset(dp , -1 , sizeof(dp)) ;
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin>>n ;
    for(int i = 0 ; i < n ; ++i)
        cin>>arr[i] ;
    for(int i = 0 ; i < n ; ++i)
    {
        for(int j = i+1 ; j < n ; ++j)
        {
            if(max(arr[i].size() , arr[j].size()) - min(arr[i].size() , arr[j].size()) >= 2)
                continue ;
            bool flag = true ;
            int idx1 = arr[i].size()-1 , idx2 = arr[j].size()-1 ;
            for(int k = 0 ; k < max(arr[i].size() , arr[j].size())-1 ; ++k)
            {
                if(arr[i][idx1] != arr[j][idx2])
                {
                    flag = false ;
                    break ;
                }
                --idx1 , --idx2 ;
            }
            mark[i][j] = mark[j][i] = flag ;
        }
    }
    int ans = 0 ;
    for(int i = 0 ; i < n ; ++i)
        ans = max(ans , solve(i , 1 << i)+1) ;
    return cout<<ans<<"\n" , 0 ;
} 

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:46:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = 0 ; k < max(arr[i].size() , arr[j].size())-1 ; ++k)
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 42 / 140