oj.uz

Submission #494605

# Submission time Handle Problem Language Result Execution time Memory
494605 2021-12-15T20:28:09 Z Nimbostratus Anagramistica (COCI21_anagramistica) C++17
110 / 110
 11 ms 14240 KB 
#include "bits/stdc++.h"
#define fi first
#define se second
constexpr int maxn = 2e3 + 5;
constexpr int inf = 2e9;
constexpr int mod = 1e9 + 7;
using namespace std;
using lint = long long;
using pii = pair<int, int>;

int n, k;
int knap[2][maxn];
int c[maxn][maxn];
map<string, int> mp;
int m;
int sz[maxn];
vector<pii> p[maxn];

void precalc() {
	for(int i = 0; i <= n; i++)
		c[i][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	m = mp.size();
	for(int i = 1; i <= m; i++) {
		sz[i] = mp.begin()->se;
		mp.erase(mp.begin());
		for(int j = 1; j <= sz[i]; j++)
			p[i].push_back({c[sz[i]][j], c[j][2]});
	}
}

void solve() {
	knap[1][0] = 1;
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j <= k; j++)
			knap[0][j] = knap[1][j];
		for(auto [num, cnt] : p[i])
			for(int j = k - cnt; j >= 0; j--) {
				knap[1][j + cnt] += 1ll * num * knap[0][j] % mod;
				knap[1][j + cnt] %= mod;
			}
	}
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		sort(str.begin(), str.end());
		mp[str]++;
	}
	precalc();
	solve();
	cout << knap[1][k] << endl;

}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8244 KB Output is correct
2 Correct 7 ms 10316 KB Output is correct
3 Correct 7 ms 12272 KB Output is correct
4 Correct 10 ms 14156 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 5 ms 8244 KB Output is correct
7 Correct 7 ms 10316 KB Output is correct
8 Correct 7 ms 12272 KB Output is correct
9 Correct 10 ms 14156 KB Output is correct
10 Correct 3 ms 3404 KB Output is correct
11 Correct 2 ms 3404 KB Output is correct
12 Correct 4 ms 6348 KB Output is correct
13 Correct 4 ms 6372 KB Output is correct
14 Correct 7 ms 10260 KB Output is correct
15 Correct 7 ms 10288 KB Output is correct
16 Correct 11 ms 14240 KB Output is correct
17 Correct 11 ms 14156 KB Output is correct
18 Correct 10 ms 14156 KB Output is correct