oj.uz

Submission #145073

# Submission time Handle Problem Language Result Execution time Memory
145073 2019-08-18T17:13:47 Z RaresRosca Mate (COCI18_mate) C++14
80 / 100
 2000 ms 52360 KB 
#include <iostream>
#include <vector>
#include <cstring>
#define MOD 1000000007
using namespace std;
int i,j,n,x,t,k,l;
long long C[2010][2010],D[2010][26][26],sol[2010][26][26],R[2010][26];
char a,b,s[2010];
vector<long long> poz[26];
int main(){
    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=n;i>=1;i--)
        for(j=0;j<26;j++)
            if(s[i]==j+'a')
                R[i][j]=1+R[i+1][j];
            else
                R[i][j]=R[i+1][j];

    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]=R[i+1][k];
                else
                    D[i][j][k]=D[i+1][j][k];
    for(i=1;i<=n;i++)
        poz[s[i]-'a'].push_back(i);

    for(i=2;i<=n;i++){
        for(j=0;j<26;j++)
            for(k=0;k<poz[j].size();k++){
                x=poz[j][k];
                if(x>=i-1)
                    for(l=0;l<26;l++){
                        sol[i][j][l]+=(D[x][j][l]*C[x-1][i-2])%MOD;
                        if(sol[i][j][l]>=MOD)
                            sol[i][j][l]-=MOD;
                    }
            }
    }
    cin>>k;
    for(;k--;){
        cin>>x>>a>>b;
        cout<<sol[x][a-'a'][b-'a']<<"\n";
    }
    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(k=0;k<poz[j].size();k++){
                     ~^~~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1272 KB Output is correct
2 Correct 58 ms 1144 KB Output is correct
3 Correct 67 ms 1144 KB Output is correct
4 Correct 115 ms 1372 KB Output is correct
5 Correct 414 ms 5268 KB Output is correct
6 Correct 465 ms 5380 KB Output is correct
7 Correct 356 ms 5112 KB Output is correct
8 Correct 326 ms 4820 KB Output is correct
9 Execution timed out 2071 ms 52356 KB Time limit exceeded
10 Execution timed out 2076 ms 52360 KB Time limit exceeded