oj.uz

답안 #222699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222699 2020-04-13T18:16:38 Z BorisBarca Trener (COCI20_trener) C++14
55 / 110
 2000 ms 85600 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
 
using namespace std;
 
#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define si pair<string, int>
#define is pair<int, string>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORP(i, a, b) for ((i) = (a); (i) < (b); ++i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define MSET memset
#define MCPY memcpy
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
 
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<si> vsi;
typedef vector<is> vis;
typedef vector<string> vs;
//((float) t)/CLOCKS_PER_SEC
 
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};
 
inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}
 
inline void add(int &a, int b){
	a = sum(a, b);
}
 
inline int mul(int a, int b){
	return (ll)a * (ll)b % MOD;
}
 
inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}
 
inline int fast_pot(ll pot, int n){
	ll ret = 1;
	while (n){
		if (n & 1)
			ret = (ret * pot) % MOD;
			pot = (pot * pot) % MOD;
			n >>= 1;
		}
	return ret;
}
 
inline int divide(int a, int b){
	return mul(a, fast_pot(b, MOD - 2));
}
 
ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}
 
inline double ccw(pii A, pii B, pii C){
	return (A.X * B.Y) - (A.Y * B.X) + (B.X * C.Y) - (B.Y * C.X) + (C.X * A.Y) - (C.Y * A.X);
}
 
inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}
 
void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}
 
void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}
 
string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}
 
ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

const int N = 55;
const int K = 1505;

unordered_map <string, vi> m;
int n, k, memo[N][K];
vi e[N][K];
 
int dp(int i, int j){
	if (i == 0)
		return 1;
	int &ret = memo[i][j];
	if (~ret)
		return ret;
	ret = 0;
	FORA(nxt, e[i][j])
		add(ret, dp(i - 1, nxt));
	return ret;
}
 
int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> k;
	set <int> tmp;
	REP(i, n){
		REP(j, k){
			string s; cin >> s;
			m[s].PB(j);
			if (i == 0)
				continue;
			string b = s.substr(0, i);
			string k = s.substr(1, i);
			FORA(x, m[b])
				tmp.INS(x);
			FORA(x, m[k])
				tmp.INS(x);
			FORA(x, tmp)
				e[i][j].PB(x);
			tmp.clear();
		}
	}
	
	memset(memo, -1, sizeof memo);
	int sol = 0;
	REP(i, k)
		add(sol, dp(n - 1, i));
	cout << sol << '\n';
 	
	return 0;
}

Compilation message

trener.cpp: In function 'int fast_pot(ll, int)':
trener.cpp:87:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (n & 1)
   ^~
trener.cpp:89:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    pot = (pot * pot) % MOD;
    ^~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2560 KB Output is correct
2 Correct 6 ms 2560 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4224 KB Output is correct
2 Correct 12 ms 4156 KB Output is correct
3 Correct 12 ms 4224 KB Output is correct
4 Correct 69 ms 5240 KB Output is correct
5 Correct 13 ms 3968 KB Output is correct
6 Correct 14 ms 3968 KB Output is correct
7 Correct 75 ms 5496 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2560 KB Output is correct
2 Correct 6 ms 2560 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 12 ms 4224 KB Output is correct
6 Correct 12 ms 4156 KB Output is correct
7 Correct 12 ms 4224 KB Output is correct
8 Correct 69 ms 5240 KB Output is correct
9 Correct 13 ms 3968 KB Output is correct
10 Correct 14 ms 3968 KB Output is correct
11 Correct 75 ms 5496 KB Output is correct
12 Correct 156 ms 27552 KB Output is correct
13 Correct 158 ms 27576 KB Output is correct
14 Correct 155 ms 27692 KB Output is correct
15 Correct 166 ms 27836 KB Output is correct
16 Execution timed out 2099 ms 85600 KB Time limit exceeded
17 Halted 0 ms 0 KB -