답안 #245002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245002	2020-07-05T10:52:14 Z	VEGAnn	Rima (COCI17_rima)	C++14	56 / 140	257 ms	19164 KB

rima

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 500100;
const int NN = 18;
string s[N];
int n, ans = 0;
bool mem[NN][NN], f[(1 << NN)][NN];

bool ok(int i, int j){
    int ned = max(sz(s[i]), sz(s[j])) - 1;

    int lf = 0;

    while (lf < min(sz(s[i]), sz(s[j])) && s[i][lf] == s[j][lf])
        lf++;

    return bool(lf >= ned);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s[i];

        reverse(all(s[i]));
    }

    if (n <= 18){
        for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            mem[i][j] = mem[j][i] = ok(i, j);

        for (int i = 0; i < n; i++)
            f[(1 << i)][i] = 1;

        for (int msk = 1; msk < (1 << n); msk++)
        for (int lst = 0; lst < n; lst++){
            if (!f[msk][lst]) continue;

            int cnt = __builtin_popcount(msk);

            ans = max(ans, cnt);

            for (int i = 0; i < n; i++)
                if (!(msk & (1 << i)) && mem[lst][i])
                    f[msk + (1 << i)][i] = 1;
        }

        cout << ans;

        return 0;
    }

    sort(s, s + n);

    for (int i = 0; i < n; ){
        int j = i + 1;

        while (j < n && ok(j - 1, j))
            j++;

        ans = max(ans, j - i);

        i = j;
    }

    cout << ans;

    return 0;
}

Subtask #1

56.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	16000 KB	Output is correct
2	Correct	19 ms	16256 KB	Output is correct
3	Correct	18 ms	16384 KB	Output is correct
4	Incorrect	257 ms	16120 KB	Output isn't correct
5	Correct	26 ms	18944 KB	Output is correct
6	Incorrect	19 ms	16664 KB	Output isn't correct
7	Incorrect	17 ms	16600 KB	Output isn't correct
8	Incorrect	16 ms	16496 KB	Output isn't correct
9	Incorrect	34 ms	19164 KB	Output isn't correct
10	Incorrect	17 ms	16708 KB	Output isn't correct