oj.uz

Submission #79913

# Submission time Handle Problem Language Result Execution time Memory
79913 2018-10-17T09:23:57 Z luckyboy Lozinke (COCI17_lozinke) C++14
65 / 100
 1000 ms 33032 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];
map <string,int> dd;
map <string,bool> ok;
long long 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,1,temp)
            FOR(pos,0,temp - j)
            {
                string ww = s[i].substr(pos,j);
                if (ok[ww]) continue;
                ok[ww] = 1;
                ans += dd[ww];
            }
        ++dd[s[i]];
        FOR(j,1,temp)
            FOR(pos,0,temp - j)
            {
                string ww = s[i].substr(pos,j);
                ok[ww] = 0;
            }
    }
    FOR(i,1,n) dd[s[i]] = 0;
    FORD(i,n,1)
    {
        int temp = s[i].size();
        FOR(j,1,temp)
            FOR(pos,0,temp - j)
            {
                string ww = s[i].substr(pos,j);
                if (ok[ww]) continue;
                ok[ww] = 1;
                ans += dd[ww];
            }
        ++dd[s[i]];
        FOR(j,1,temp)
            FOR(pos,0,temp - j)
            {
                string ww = s[i].substr(pos,j);
                ok[ww] = 0;
            }
    }
    cout << ans;
    return 0;
}

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 5 ms 1196 KB Output is correct
4 Correct 7 ms 1244 KB Output is correct
5 Correct 41 ms 1976 KB Output is correct
6 Correct 66 ms 1976 KB Output is correct
7 Correct 101 ms 3468 KB Output is correct
8 Correct 170 ms 5096 KB Output is correct
9 Correct 408 ms 5152 KB Output is correct
10 Execution timed out 1029 ms 15180 KB Time limit exceeded
11 Correct 726 ms 15180 KB Output is correct
12 Execution timed out 1085 ms 33032 KB Time limit exceeded
13 Execution timed out 1078 ms 33032 KB Time limit exceeded
14 Execution timed out 1079 ms 33032 KB Time limit exceeded
15 Execution timed out 1080 ms 33032 KB Time limit exceeded
16 Execution timed out 1006 ms 33032 KB Time limit exceeded
17 Correct 196 ms 33032 KB Output is correct
18 Correct 132 ms 33032 KB Output is correct
19 Execution timed out 1071 ms 33032 KB Time limit exceeded
20 Correct 491 ms 33032 KB Output is correct