Submission #229520

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229520	2020-05-04T22:13:38 Z	MohamedAhmed04	Rima (COCI17_rima)	C++14	42 / 140	68 ms	79608 KB

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

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	39296 KB	Output is correct
2	Correct	22 ms	39296 KB	Output is correct
3	Correct	22 ms	39288 KB	Output is correct
4	Runtime error	63 ms	79480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	68 ms	79608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	64 ms	79480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	65 ms	79484 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	65 ms	79480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	66 ms	79480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	66 ms	79480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)