oj.uz

Submission #244844

# Submission time Handle Problem Language Result Execution time Memory
244844 2020-07-05T07:16:19 Z VEGAnn Rima (COCI17_rima) C++14
14 / 140
 1000 ms 19284 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 500100;
string s[N];
int n, ans = 0, f[N];

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]));
    }

    sort(s, s + n);

    for (int i = 0; i < n; i++){
        f[i] = max(f[i], 1);
        ans = max(ans, f[i]);

        for (int j = i + 1; j < n; j++)
            if (ok(i, j))
                f[j] = max(f[j], f[i] + 1);
    }

    cout << ans;

    return 0;
}

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 16000 KB Output isn't correct
2 Correct 15 ms 16000 KB Output is correct
3 Incorrect 15 ms 16000 KB Output isn't correct
4 Execution timed out 1087 ms 16248 KB Time limit exceeded
5 Execution timed out 1090 ms 18944 KB Time limit exceeded
6 Incorrect 191 ms 16664 KB Output isn't correct
7 Incorrect 100 ms 16548 KB Output isn't correct
8 Incorrect 60 ms 16496 KB Output isn't correct
9 Execution timed out 1086 ms 19284 KB Time limit exceeded
10 Incorrect 69 ms 16708 KB Output isn't correct