oj.uz

Submission #145035

# Submission time Handle Problem Language Result Execution time Memory
145035 2019-08-18T13:15:33 Z Mihnea Mate (COCI18_mate) C++14
0 / 100
 638 ms 109640 KB 
#include<iostream>
#include<cstdio>
#include<cstring>
#define MOD 1000000007
using namespace std;
long long I;
long long a[2005][2005],b[2005][30],poz[30][2005],sol[2005][30][30],D[2005][30][30];
char s[2005],X,Y;
int main(){
    scanf("%s", (s+1));
    int n=strlen((s+1));
    a[0][0]=1;
    for(int i=1;i<=n;i++){
        a[i][0]=a[i][i]=1;
        for(int j=1;j<i;j++){
            a[i][j]=a[i-1][j-1]+a[i-1][j];
            if(a[i][j]>=MOD)
                a[i][j]-=MOD;
        }
    }
    for(int i=1;i<=n;i++)
        poz[s[i]-'a'][ ++poz[s[i]-'a'][0] ]=i;
    for(int i=n;i>=1;i--)
        for(int j=0;j<26;j++)
            if(s[i]=='a'+j)
                b[i][j]=1+b[i+1][j];
            else
                b[i][j]=b[i+1][j];
    for(int i=n;i>=1;i--)
        for(int j=0;j<26;j++)
            for(int k=0;k<26;k++)
                if(s[i]=='a'+j)
                    D[i][j][k]=b[i+1][k];
                else
                    D[i][j][k]=D[i+1][j][k];
    for(int i=2;i<=n;i++)
        for(int j=0;j<26;j++)
            for(int t=1;t<=poz[j][0];t++){
                int h=poz[j][t];
                if(h>=i-1)
                    for(int k=0;k<26;k++){
                        sol[i][j][k]+=(D[h][j][k]*a[h-1][i-2])%MOD;
                        if(sol[i][j][k]>=MOD)
                            sol[i][j][k]-=MOD;
                    }
            }
    scanf("%lld",&n);
    while(n!=0){
        scanf("%lld %c %c",&I,&X,&Y);
        printf("%lld\n",sol[I][X-'a'][Y-'a']);
        n--;
    }
    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:47:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
     scanf("%lld",&n);
                  ~~^
mate.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", (s+1));
     ~~~~~^~~~~~~~~~~~~
mate.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
mate.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %c %c",&I,&X,&Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 2428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 13 ms 2424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 14 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 18 ms 2424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 60 ms 9208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 66 ms 9368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 54 ms 9216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 50 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 634 ms 109640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 638 ms 109632 KB Execution killed with signal 11 (could be triggered by violating memory limits)