oj.uz

Submission #141663

# Submission time Handle Problem Language Result Execution time Memory
141663 2019-08-08T17:07:24 Z mariusnicoli Mate (COCI18_mate) C++14
100 / 100
 549 ms 49456 KB 
///#include <fstream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MOD 1000000007
using namespace std;
char p, u, s[2002];
long long R[2002][26];
long long D[2002][26][26], sol[2002][26][26];
long long C[2002][2002];
vector<long long> poz[26];
long long n, i, j, k, t, L;
///ifstream cin ("mate.in");
///ofstream cout("mate.out");
int  main () {
    scanf("%s", s+1);
    ///cin>>s+1;
    n = strlen(s+1);

    C[0][0] = 1;
    for (i=1;i<=n;i++) {
        C[i][0] = 1;
        for (j=1;j<=i;j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]);
            if (C[i][j] >= MOD)
                C[i][j] -= MOD;
        }
    }


    for (i=1;i<=n;i++)
        poz[s[i]-'a'].push_back(i);

///    for (i=0;i<26;i++)
///        Last[i] = n+1;
    for (i=n;i>=1;i--) {
        for (j=0;j<26;j++)
            if (s[i] == j+'a') {
                R[i][j] = 1 + R[i+1][j];
///                Last[j] = i;
            }
            else {
                R[i][j] = R[i+1][j];
///                Last[j] = Last[j+1];
            }
    }
    for (i=n;i>=1;i--) {
        for (j=0;j<26;j++)
            for (k=0;k<26;k++)
                if (s[i] == j+'a')
                    D[i][j][k] = /**D[i+1][j][k] +**/ R[i+1][k];
                else
                    D[i][j][k] = D[i+1][j][k];
    }

    for (L=2;L<=n;L++)
        for (j=0;j<26;j++)
            for (t=0;t<poz[j].size();t++) {
                i=poz[j][t];
                if (i >= L-1)
                    for (k=0;k<26;k++) {
                        sol[L][j][k] += ((D[i][j][k] * C[i-1][L-2])%MOD);
                        if (sol[L][j][k] >= MOD)
                            sol[L][j][k] -= MOD;
                    }
            }


    ///cin>>t;
    scanf("%lld", &t);
    for (;t--;) {
        scanf("%lld %c %c", &L, &p, &u);
        ///cin>>L>>p>>u;
        printf("%lld\n", sol[L][p-'a'][u-'a']);
        ///cout<<sol[L][p-'a'][u-'a']<<"\n";
    }
    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (t=0;t<poz[j].size();t++) {
                      ~^~~~~~~~~~~~~~
mate.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s+1);
     ~~~~~^~~~~~~~~~~
mate.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t);
     ~~~~~^~~~~~~~~~~~
mate.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %c %c", &L, &p, &u);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1144 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 8 ms 1016 KB Output is correct
4 Correct 12 ms 1144 KB Output is correct
5 Correct 46 ms 4344 KB Output is correct
6 Correct 54 ms 4376 KB Output is correct
7 Correct 45 ms 4216 KB Output is correct
8 Correct 39 ms 4088 KB Output is correct
9 Correct 538 ms 49456 KB Output is correct
10 Correct 549 ms 49400 KB Output is correct