oj.uz

Submission #308924

# Submission time Handle Problem Language Result Execution time Memory
308924 2020-10-02T09:56:41 Z shrek12357 Mate (COCI18_mate) C++14
100 / 100
 1904 ms 39416 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 34296 KB Output is correct
2 Correct 72 ms 34224 KB Output is correct
3 Correct 80 ms 34176 KB Output is correct
4 Correct 120 ms 34176 KB Output is correct
5 Correct 388 ms 35192 KB Output is correct
6 Correct 428 ms 35192 KB Output is correct
7 Correct 331 ms 34972 KB Output is correct
8 Correct 301 ms 34936 KB Output is correct
9 Correct 1904 ms 39288 KB Output is correct
10 Correct 1897 ms 39416 KB Output is correct