oj.uz

Submission #79935

# Submission time Handle Problem Language Result Execution time Memory
79935 2018-10-17T12:37:18 Z luckyboy Lozinke (COCI17_lozinke) C++14
40 / 100
 1000 ms 12780 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 20005
#define maxm 500005
#define pii pair <int,int>
#define Task "Lozinke"
using namespace std;
int n;
string s[maxn];
long long a[maxn][100],top[maxn],b[maxn],top1,ans;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n;
    FOR(i,1,n)
    {
        cin >> s[i];
        int temp = s[i].size();
        FOR(j,0,temp-1)
           {
                long long cur = 0;
                FOR(k,1,temp - j)
                {
                    cur = cur * 27 + (s[i][j+k-1] - 'a' + 1);
                    a[i][++top[i]] = cur;
                }
           }
        sort(a[i] + 1,a[i] + top[i] + 1);
        top[i] = unique(a[i]+1 , a[i] + top[i] + 1) - a[i] - 1;
        FOR(j,1,top[i])
        {
            ans += upper_bound(b+1,b+top1+1,a[i][j]) - lower_bound(b+1,b+top1+1,a[i][j]);
        }
        b[++top1] = a[i][top[i]];
        sort(b+1,b+top1+1);
    }
    top1 = 0;
    FORD(i,n,1)
    {
        FOR(j,1,top[i])
        {
            ans += upper_bound(b+1,b+top1+1,a[i][j]) - lower_bound(b+1,b+top1+1,a[i][j]);
        }
        b[++top1] = a[i][top[i]];
        sort(b+1,b+top1+1);
    }
    cout << ans;
    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1088 KB Output is correct
4 Correct 11 ms 1492 KB Output is correct
5 Correct 43 ms 1924 KB Output is correct
6 Correct 95 ms 2464 KB Output is correct
7 Correct 241 ms 2848 KB Output is correct
8 Correct 172 ms 2976 KB Output is correct
9 Execution timed out 1076 ms 6712 KB Time limit exceeded
10 Execution timed out 1074 ms 6712 KB Time limit exceeded
11 Execution timed out 1085 ms 6768 KB Time limit exceeded
12 Execution timed out 1072 ms 6768 KB Time limit exceeded
13 Execution timed out 1058 ms 6768 KB Time limit exceeded
14 Execution timed out 1075 ms 6768 KB Time limit exceeded
15 Execution timed out 1078 ms 6816 KB Time limit exceeded
16 Execution timed out 1069 ms 6816 KB Time limit exceeded
17 Execution timed out 1081 ms 12780 KB Time limit exceeded
18 Execution timed out 1068 ms 12780 KB Time limit exceeded
19 Execution timed out 1082 ms 12780 KB Time limit exceeded
20 Execution timed out 1083 ms 12780 KB Time limit exceeded