oj.uz

Submission #145072

# Submission time Handle Problem Language Result Execution time Memory
145072 2019-08-18T17:09:29 Z RaresRosca Mate (COCI18_mate) C++14
20 / 100
 2000 ms 53816 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]=D[i][j+1][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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 1400 KB Output is correct
2 Incorrect 59 ms 1148 KB Output isn't correct
3 Correct 70 ms 1144 KB Output is correct
4 Incorrect 116 ms 1400 KB Output isn't correct
5 Incorrect 416 ms 5368 KB Output isn't correct
6 Incorrect 483 ms 5624 KB Output isn't correct
7 Incorrect 357 ms 5160 KB Output isn't correct
8 Incorrect 326 ms 4856 KB Output isn't correct
9 Execution timed out 2055 ms 53572 KB Time limit exceeded
10 Execution timed out 2073 ms 53816 KB Time limit exceeded