oj.uz

Submission #239024

# Submission time Handle Problem Language Result Execution time Memory
239024 2020-06-14T07:10:25 Z VEGAnn Mate (COCI18_mate) C++14
0 / 100
 2000 ms 36804 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define i2 array<int,2>
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 2010;
const ll OO = 1e18;
const int md = int(1e9) + 7;
unordered_map<string, int> mem[N];
string s, st;
int n, C[N][N];
ll cnt[N][26], ans;

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

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

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

    cin >> s;
    n = sz(s);

    for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        cnt[i][s[j] - 'a']++;

    C[0][0] = 1;

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

        for (int j = 1; j < n; j++)
            C[i][j] = sum(C[i - 1][j], C[i - 1][j - 1]);
    }

    int qq; cin >> qq;

    for (; qq; qq--){
        int d; cin >> d >> st;

        if (mem[d].find(st) != mem[d].end()){
            cout << mem[d][st] << '\n';
            continue;
        }

        d -= 2;

        int ch = (st[1] - 'a');

        ans = 0;

        for (int i = 0; i < n; i++)
            if (s[i] == st[0]) {
                if (cnt[i][ch] == 0) break;

                (ans += cnt[i][ch] * C[i][d]) %= md;
            }

        mem[d][st] = ans;

        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1664 KB Output isn't correct
2 Incorrect 13 ms 1536 KB Output isn't correct
3 Incorrect 14 ms 1536 KB Output isn't correct
4 Incorrect 21 ms 1920 KB Output isn't correct
5 Incorrect 92 ms 6648 KB Output isn't correct
6 Incorrect 103 ms 6992 KB Output isn't correct
7 Incorrect 93 ms 6264 KB Output isn't correct
8 Incorrect 82 ms 6068 KB Output isn't correct
9 Execution timed out 2092 ms 36652 KB Time limit exceeded
10 Execution timed out 2080 ms 36804 KB Time limit exceeded