Submission #308924

#	Time	Username	Problem	Language	Result	Execution time	Memory
308924		shrek12357	Mate (COCI18_mate)	C++14	100 / 100	1904 ms	39416 KiB

mate

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
//cin.tie(0);
//ios_base::sync_with_stdio(0);

const int MOD = 1e9 + 7;
const int MAXN = 2005;

int main() {
	ll bin[MAXN + 5][MAXN + 5];
    for (int i = 0; i <= MAXN; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
                bin[i][j] = 1;

            else
                bin[i][j] = (bin[i - 1][j - 1] +
                bin[i - 1][j])%MOD;
        }
    }
    string s;
    cin >> s;
    ll dp[MAXN][26][26];
    ll counts[MAXN][26];
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < 26; j++) {
            for (int k = 0; k < 26; k++) {
                dp[i][j][k] = 0;
            }
            counts[i][j] = 0;
        }
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        counts[i][s[i] - 97]++;
        if (i == s.size() - 1) {
            continue;
        }
        for (int j = 0; j < 26; j++) {
            counts[i][j] = (counts[i][j] + counts[i + 1][j])%MOD;
        }
    }
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < 26; k++) {
                dp[j+2][s[i] - 97][k] = (dp[j + 2][s[i] - 97][k] + ((counts[i + 1][k]) * bin[i][j]) % MOD)%MOD;
            }
        }
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int len;
        cin >> len;
        char a, b;
        cin >> a >> b;
        cout << dp[len][a - 97][b - 97] << endl;
    }
}

Compilation message (stderr)

mate.cpp: In function 'int main()':
mate.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (i == s.size() - 1) {
      |             ~~^~~~~~~~~~~~~~~
mate.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 100 / 100