oj.uz

Submission #341543

# Submission time Handle Problem Language Result Execution time Memory
341543 2020-12-30T00:23:15 Z A_D Trener (COCI20_trener) C++14
55 / 110
 2000 ms 8940 KB 
/*
ID: antwand1
TASK: pprime
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define du long double
#define F first
#define S second
#define FOR(a,b) for(int a=1;a<=b;a++)
#define FORl(a,b) for(a=1;a<=b;a++)
#define FOR0(a,b) for(int a=1;a<b;a++)
#define FORl0(a,b) for(a=0;a<b;a++)
#define ii pair<int,int>
using namespace std;
const int MOD=1e9+7;
const int N=55;
const int M=1511;
string a[N][M];
int dp[N][M];
int n,m;
vector<string> vec;
bool ok(string a,string b)
{
    string ret;
    for(int i=0;i<b.size()-1;i++)ret+=b[i];
    if(ret==a)return 1;
    ret="";
    for(int i=1;i<b.size();i++)ret+=b[i];
    return ret==a;
}
int bc(int i,int j)
{
    int&ret=dp[i][j];
    if(ret!=-1)return ret;
    if(i==n+1){
        //for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";cout<<endl;
        return ret=1;
    }
    ret=0;
    for(int x=1;x<=m;x++){
        if(i==1){
            vec.push_back(a[i][x]);
            ret+=bc(i+1,x);
            vec.pop_back();
        }
        else{
            vec.push_back(a[i][x]);
            if(ok(a[i-1][j],a[i][x]))ret+=bc(i+1,x)%MOD;
            ret%=MOD;
            vec.pop_back();
        }
    }
    ret%=MOD;
    return ret;
}
main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    cout<<bc(1,1)%MOD;
}

Compilation message

trener.cpp: In function 'bool ok(std::string, std::string)':
trener.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<b.size()-1;i++)ret+=b[i];
      |                 ~^~~~~~~~~~~
trener.cpp:31:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=1;i<b.size();i++)ret+=b[i];
      |                 ~^~~~~~~~~
trener.cpp: At global scope:
trener.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main()
      |      ^

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 3820 KB Output is correct
2 Correct 219 ms 3820 KB Output is correct
3 Correct 217 ms 3948 KB Output is correct
4 Correct 152 ms 3864 KB Output is correct
5 Correct 217 ms 3948 KB Output is correct
6 Correct 235 ms 4076 KB Output is correct
7 Correct 151 ms 3948 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3564 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct
3 Correct 2 ms 3564 KB Output is correct
4 Correct 2 ms 3564 KB Output is correct
5 Correct 205 ms 3820 KB Output is correct
6 Correct 219 ms 3820 KB Output is correct
7 Correct 217 ms 3948 KB Output is correct
8 Correct 152 ms 3864 KB Output is correct
9 Correct 217 ms 3948 KB Output is correct
10 Correct 235 ms 4076 KB Output is correct
11 Correct 151 ms 3948 KB Output is correct
12 Execution timed out 2021 ms 8940 KB Time limit exceeded
13 Halted 0 ms 0 KB -