Submission #145073

#	Time	Username	Problem	Language	Result	Execution time	Memory
145073		RaresRosca	Mate (COCI18_mate)	C++14	80 / 100	2076 ms	52360 KiB

mate

#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 (stderr)

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 / 100