oj.uz

답안 #143332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143332 2019-08-13T16:45:49 Z nicolaalexandra Mate (COCI18_mate) C++14
0 / 100
 2000 ms 24284 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#define DIM 2010
#define MOD 1000000007
using namespace std;

//ifstream cin ("date.in");
//ofstream cout ("date.out");
int v[DIM],c[DIM][DIM],f[DIM],dp[DIM][30][30];
vector <int> pozx,pozy;
set <int> L;
char s[DIM],l1,l2;
int n,i,j,x,y,q,lg;
int main (){

    cin>>s+1;
    n = strlen(s+1);
    for (i=1;i<=n;i++)
        v[i] = s[i] - 'a' + 1;

    c[0][0] = c[1][0] = c[1][1] = 1;
    for (i=2;i<=n;i++){
        c[i][0] = 1;
        for (j=1;j<=i;j++)
            c[i][j] = (c[i-1][j] + c[i-1][j-1])%MOD;
    }

    for (x=1;x<=26;x++)
        for (y=1;y<=26;y++){
            if (x == 14 && y == 14)
                x = 14;
            pozy.clear(), pozx.clear(), L.clear();
            memset (f,0,sizeof f);
            for (i=1;i<=n;i++)
                if (v[i] == y)
                    pozy.push_back(i);
            int idx = 0;
            for (i=1;i<=n;i++){
                if (pozy[idx] == i){
                    for (j=0;j<pozx.size();j++){
                        L.insert(pozx[j]-1); /// pana unde pot selecta caractere
                        f[pozx[j]-1]++;
                    }
                    if (idx == pozy.size()-1)
                        break;
                    idx++;
                }
                if (v[i] == x)
                    pozx.push_back(i);
            }
            /// dp[i][x][y] - cate siruri de lungime i care se termina cu xy pot obtine
            for (i=2;i<=n;i++)
                for (set<int>:: iterator it=L.begin();it!=L.end();it++){
                    int lg = *it;
                    dp[i][x][y] = (dp[i][x][y] + c[lg][i-2]*f[lg]%MOD)%MOD;
                }}

    cin>>q;
    for (;q--;){
        cin>>lg>>l1>>l2;
        x = l1-'a'+1, y = l2-'a'+1;
        cout<<dp[lg][x][y]<<"\n";
    }



    return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>s+1;
          ~^~
mate.cpp:42:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (j=0;j<pozx.size();j++){
                              ~^~~~~~~~~~~~
mate.cpp:46:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (idx == pozy.size()-1)
                         ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 760 KB Output isn't correct
2 Incorrect 58 ms 760 KB Output isn't correct
3 Incorrect 68 ms 760 KB Output isn't correct
4 Incorrect 115 ms 760 KB Output isn't correct
5 Incorrect 422 ms 2876 KB Output isn't correct
6 Incorrect 488 ms 3040 KB Output isn't correct
7 Incorrect 360 ms 2936 KB Output isn't correct
8 Incorrect 329 ms 2604 KB Output isn't correct
9 Execution timed out 2056 ms 24284 KB Time limit exceeded
10 Execution timed out 2064 ms 24256 KB Time limit exceeded