Submission #239013

#	Time	Username	Problem	Language	Result	Execution time	Memory
239013		NONAME	Mate (COCI18_mate)	C++17	80 / 100	2093 ms	27376 KiB

mate

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

const int N = 2e5 + 10;
const int base = 1e9 + 7;

string s;
int c[2500][2500], res[2500][2500];

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

//    freopen("in.txt", "r", stdin);

    cin >> s;
    int n = int(s.size());

    for (int i = 0; i < 2500; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % base;
    }

    for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
        char c1 = s[i], c2 = s[j];
        int v = (c1 - 'a' + 1) + 29 * (c2 - 'a' + 1);

        for (int l = -1; l < i; ++l)
            res[v][l + 1] = (res[v][l + 1] + c[i][l + 1]) % base;
    }

    int q;
    cin >> q;
    while (q--) {
        int d;
        string t;
        cin >> d >> t;

        cout << res[(t[0] - 'a' + 1) + 29 * (t[1] - 'a' + 1)][d - 2] << "\n";
    }
}

• Subtask 1: 80 / 100