oj.uz

Submission #845391

# Submission time Handle Problem Language Result Execution time Memory
845391 2023-09-06T13:27:16 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 856 KB 
// Imagine not FFT
#include <bits/stdc++.h>
#define ONLINE_JUDGE
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
#ifndef ONLINE_JUDGE
    #define DEBUG(x) std::cerr << #x << ": " << x << std::endl;
    #define DEBUGV(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << ___y << " "; std::cerr << "}" << std::endl;
    #define DEBUGVV(x) std::cerr << #x << ": { \n"; for(int _i=0;_i<sz(x);++_i) {DEBUGV(x[_i]);} std::cerr << "}" << std::endl;
	#define DEBUGVP(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << "{" << ___y.first << "," << ___y.second << "}" << " "; std::cerr << "}" << std::endl;
	#define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
#else
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
    #define DEBUG(...) void(23)
    #define DEBUGV(x) void(23);
    #define DEBUGARR(arr, size) void(23)
    #define DEBUGPRINT(...) void(23)
    #define DEBUGMAP(...) void(23)
    #define DEBUGMAPQUEUE(...) void(23)
    #define DEBUGVV(x) void(23);
    #define DEBUGVP(x) void(23);
    #define files void(23);
#endif

#define int long long
#define ll long long
 
#define pb push_back
#define ff first
#define ss second
#define pii std::pair < int , int >
#define pll std::pair < ll , ll >
#define vi std::vector < ll >
#define vl std::vector < int >
#define vii std::vector < pii >
#define vll std::vector < pll >
#define vvi std::vector < vi >
#define vvii std::vector < vii >
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define forn(i,j) for(int i=0;i<j;i++)
#define forr(i,j,k) for(int i=j;i<k;i++)
 
#define mset multiset
#define pqueue priority_queue
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
 
#define sz(a) (int)(a.size())
     
const int MOD = 1000000007;
const int MOD2 = 998244353;

using namespace std;

bool isSub(string a, string b){
	if((b[0]+a)==b) return true;
	if((a+b[sz(b)-1])==b) return true;
	return false;
}

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

int addd(int& a, int b){
	return (a=((a+b)%MOD));
}

void solve(int _t_case){
	int n,k;
	cin >> n >> k;
	vector < pair < string , int > > old;
	forn(i,k){
		string sur;
		cin >> sur;
		old.pb({sur,1});
	}
	forr(i,1,n){
		vector < pair < string , int > > a;
		forn(j,k){
			string sur;
			cin >> sur;
			int tot=0;
			for(auto o:old){
				if(isSub(o.ff,sur)) addd(tot,o.ss);
			}
			if(tot>0) a.pb({sur,tot});
		}
		DEBUGVP(old)
		old=a;
	}
	int ans = 0;
	for(auto _a:old) addd(ans,_a.ss);
	cout << ans << endl;
	return;
}

signed main(){
    fastio;
    files;
    int t=1,_t=0;
    //std::cin >> t;
    while(_t<t){
        ++_t;
        solve(_t);
    }
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 464 KB Output is correct
2 Correct 56 ms 344 KB Output is correct
3 Correct 66 ms 452 KB Output is correct
4 Correct 40 ms 464 KB Output is correct
5 Correct 56 ms 348 KB Output is correct
6 Correct 59 ms 452 KB Output is correct
7 Correct 41 ms 468 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 54 ms 464 KB Output is correct
6 Correct 56 ms 344 KB Output is correct
7 Correct 66 ms 452 KB Output is correct
8 Correct 40 ms 464 KB Output is correct
9 Correct 56 ms 348 KB Output is correct
10 Correct 59 ms 452 KB Output is correct
11 Correct 41 ms 468 KB Output is correct
12 Execution timed out 2062 ms 856 KB Time limit exceeded
13 Halted 0 ms 0 KB -