oj.uz

Submission #182408

# Submission time Handle Problem Language Result Execution time Memory
182408 2020-01-09T18:04:37 Z awlintqaa Rima (COCI17_rima) C++14
42 / 140
 86 ms 75512 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n;
string s[20];
int dp[(1<<19)+9][18];
int check(int x,int y){
        if(x==0)x=y;
        string a=s[x];
        string b=s[y];
        if(a.size()-b.size()>1)return 0;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        for(int i=0;i<b.size()-((int)a.size()==(int)b.size());i++){
                if(a[i]!=b[i])return 0;
        }
        return 1;
}
int bt(int mask,int last){
        int N=__builtin_popcount(mask);
        if(N==n)return 0;
        int &ret=dp[mask][last];
        if(ret!=-1)return ret;
        ret=0;
        for(int i=1;i<=n;i++){
                if((mask&(1<<i)))C;
                if(!check(last,i))C;
                ret=max(ret,bt((mask|(1<<i)),i)+1);
        }
        return ret;
}
int main(){
        mem(dp,-1);
        cin>>n;
        for(int i=1;i<=n;i++)cin>>s[i];
        cout<<bt(0,0)<<endl;
}

Compilation message

rima.cpp: In function 'int check(int, int)':
rima.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<b.size()-((int)a.size()==(int)b.size());i++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37240 KB Output is correct
2 Correct 35 ms 37240 KB Output is correct
3 Correct 34 ms 37240 KB Output is correct
4 Runtime error 83 ms 75384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 85 ms 75512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 82 ms 75384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 86 ms 75356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 81 ms 75272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 81 ms 75256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 83 ms 75268 KB Execution killed with signal 11 (could be triggered by violating memory limits)