oj.uz

Submission #340396

# Submission time Handle Problem Language Result Execution time Memory
340396 2020-12-27T13:48:45 Z Hazem Trener (COCI20_trener) C++14
110 / 110
 386 ms 24988 KB 
/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 2e5 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

string s[55][2000];
LL ans[55][2000];
map<string,LL>mp;

LL add(LL a,LL b){
    return (a+b)%MOD;
}

string sub(string s,int l,int r){

    string ret = "";
    for(int i=l;i<=r;i++)
        ret += s[i];
    
    return ret;
}

bool check(string s,string r){

    bool q = 0;
    for(int i=0;i<2;i++)
        q |= sub(r,i,i+s.size()-1)==s;
    
    return q;
}

int main()
{
    //freopen("out.txt","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
        cin>>s[i][j];

    for(int i=1;i<=k;i++)
        ans[n][i] = 1;

    for(int i=1;i<=k;i++){
        string r1 = sub(s[n][i],0,n-2);
        string r2 = sub(s[n][i],1,n-1);  
        mp[r1]++;
        if(r2!=r1)mp[r2]++;
    }
    
    for(int i=n-1;i>=2;i--){
        for(int j=1;j<=k;j++){
            
            string r1 = sub(s[i][j],0,i-2);
            string r2 = sub(s[i][j],1,i-1);
            mp[r1] = add(mp[r1],mp[s[i][j]]);

            if(r2!=r1)
            mp[r2] = add(mp[r2],mp[s[i][j]]);
        }
    }

    LL ans1 = 0;
    for(int i=1;i<=k;i++)
        ans1 = add(ans1,mp[s[1][i]]);

    printf("%lld\n",ans1);
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3820 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5228 KB Output is correct
2 Correct 20 ms 5228 KB Output is correct
3 Correct 20 ms 5228 KB Output is correct
4 Correct 10 ms 4076 KB Output is correct
5 Correct 21 ms 4844 KB Output is correct
6 Correct 21 ms 4844 KB Output is correct
7 Correct 10 ms 4076 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 3 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3820 KB Output is correct
5 Correct 20 ms 5228 KB Output is correct
6 Correct 20 ms 5228 KB Output is correct
7 Correct 20 ms 5228 KB Output is correct
8 Correct 10 ms 4076 KB Output is correct
9 Correct 21 ms 4844 KB Output is correct
10 Correct 21 ms 4844 KB Output is correct
11 Correct 10 ms 4076 KB Output is correct
12 Correct 386 ms 24988 KB Output is correct
13 Correct 384 ms 24812 KB Output is correct
14 Correct 356 ms 24940 KB Output is correct
15 Correct 358 ms 24812 KB Output is correct
16 Correct 104 ms 9196 KB Output is correct
17 Correct 339 ms 19564 KB Output is correct
18 Correct 341 ms 19692 KB Output is correct
19 Correct 343 ms 19692 KB Output is correct
20 Correct 351 ms 19692 KB Output is correct
21 Correct 343 ms 19692 KB Output is correct
22 Correct 109 ms 9196 KB Output is correct