Submission #1970634
Source Code Expand
// 基本テンプレート #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define int long long int template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} typedef pair<int, int> pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; int N, M; int cnt_A[1010], cnt_B[1010]; vector<int> val_A, val_B; // 何人の人に何デス配るときの場合の数 int rec[110][1010]; void pre_func() { rec[0][0] = 1; repq(n,1,100) repq(k,0,1000) { for(int i=0; i<=k/n; i++) { (rec[n][k] += rec[n-1][k-i*n]) %= MOD; } } } // i 番目までの種類で何デス使ったか int dp[110][1010]; int solve(vector<int> &vec, int sum) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; int S = vec.size(); rep(i,0,S) repq(j,0,sum) repq(k,0,j) { (dp[i+1][j] += (dp[i][k] * rec[vec[i]][j-k])) %= MOD; } return dp[S][sum]; } signed main() { cin >> N >> M; int sum_A = 0, sum_B = 0; rep(i,0,N) { int p; cin >> p; cnt_A[p]++; sum_B += p; } rep(i,0,M) { int p; cin >> p; cnt_B[p]++; sum_A += p; } repq(i,0,1000) { if(cnt_A[i]) val_A.push_back(cnt_A[i]); if(cnt_B[i]) val_B.push_back(cnt_B[i]); } pre_func(); int ans_A = solve(val_A, sum_A); int ans_B = solve(val_B, sum_B); printf("%lld\n", (ans_A * ans_B) % MOD); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Kill/Death |
User | tsutaj |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2279 Byte |
Status | AC |
Exec Time | 136 ms |
Memory | 1920 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 500 / 500 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 01_sample00, 01_sample01, 01_sample02, 01_sample03, 01_sample04, 02_minimal00, 02_minimal01, 02_minimal02, 02_minimal03, 03_maximal00, 03_maximal01, 04_random-easy00, 04_random-easy01, 04_random-easy02, 04_random-easy03, 04_random-easy04, 04_random-easy05, 04_random-easy06, 04_random-easy07, 04_random-easy08, 04_random-easy09, 04_random-easy10, 04_random-easy11, 04_random-easy12, 04_random-easy13, 04_random-easy14, 04_random-easy15, 04_random-easy16, 04_random-easy17, 04_random-easy18, 04_random-easy19, 05_random-large00, 05_random-large01, 05_random-large02, 05_random-large03, 05_random-large04, 05_random-large05, 05_random-large06, 05_random-large07, 05_random-large08, 05_random-large09, 05_random-large10, 05_random-large11, 05_random-large12, 05_random-large13, 05_random-large14, 05_random-large15, 05_random-large16, 05_random-large17, 05_random-large18, 05_random-large19, 06_random00, 06_random01, 06_random02, 06_random03, 06_random04, 06_random05, 06_random06, 06_random07, 06_random08, 06_random09, 06_random10, 06_random11, 06_random12, 06_random13, 06_random14, 06_random15, 06_random16, 06_random17, 06_random18, 06_random19 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01_sample00 | AC | 13 ms | 1920 KB |
01_sample01 | AC | 13 ms | 1920 KB |
01_sample02 | AC | 13 ms | 1920 KB |
01_sample03 | AC | 13 ms | 1920 KB |
01_sample04 | AC | 14 ms | 1920 KB |
02_minimal00 | AC | 13 ms | 1920 KB |
02_minimal01 | AC | 15 ms | 1920 KB |
02_minimal02 | AC | 15 ms | 1920 KB |
02_minimal03 | AC | 17 ms | 1920 KB |
03_maximal00 | AC | 21 ms | 1920 KB |
03_maximal01 | AC | 17 ms | 1920 KB |
04_random-easy00 | AC | 13 ms | 1920 KB |
04_random-easy01 | AC | 13 ms | 1920 KB |
04_random-easy02 | AC | 13 ms | 1920 KB |
04_random-easy03 | AC | 13 ms | 1920 KB |
04_random-easy04 | AC | 13 ms | 1920 KB |
04_random-easy05 | AC | 13 ms | 1920 KB |
04_random-easy06 | AC | 13 ms | 1920 KB |
04_random-easy07 | AC | 13 ms | 1920 KB |
04_random-easy08 | AC | 13 ms | 1920 KB |
04_random-easy09 | AC | 13 ms | 1920 KB |
04_random-easy10 | AC | 13 ms | 1920 KB |
04_random-easy11 | AC | 13 ms | 1920 KB |
04_random-easy12 | AC | 13 ms | 1920 KB |
04_random-easy13 | AC | 13 ms | 1920 KB |
04_random-easy14 | AC | 13 ms | 1920 KB |
04_random-easy15 | AC | 13 ms | 1920 KB |
04_random-easy16 | AC | 13 ms | 1920 KB |
04_random-easy17 | AC | 13 ms | 1920 KB |
04_random-easy18 | AC | 13 ms | 1920 KB |
04_random-easy19 | AC | 13 ms | 1920 KB |
05_random-large00 | AC | 114 ms | 1920 KB |
05_random-large01 | AC | 136 ms | 1920 KB |
05_random-large02 | AC | 124 ms | 1920 KB |
05_random-large03 | AC | 115 ms | 1920 KB |
05_random-large04 | AC | 118 ms | 1920 KB |
05_random-large05 | AC | 125 ms | 1920 KB |
05_random-large06 | AC | 124 ms | 1920 KB |
05_random-large07 | AC | 123 ms | 1920 KB |
05_random-large08 | AC | 118 ms | 1920 KB |
05_random-large09 | AC | 117 ms | 1920 KB |
05_random-large10 | AC | 118 ms | 1920 KB |
05_random-large11 | AC | 119 ms | 1920 KB |
05_random-large12 | AC | 123 ms | 1920 KB |
05_random-large13 | AC | 126 ms | 1920 KB |
05_random-large14 | AC | 123 ms | 1920 KB |
05_random-large15 | AC | 107 ms | 1920 KB |
05_random-large16 | AC | 122 ms | 1920 KB |
05_random-large17 | AC | 127 ms | 1920 KB |
05_random-large18 | AC | 124 ms | 1920 KB |
05_random-large19 | AC | 116 ms | 1920 KB |
06_random00 | AC | 62 ms | 1920 KB |
06_random01 | AC | 14 ms | 1920 KB |
06_random02 | AC | 16 ms | 1920 KB |
06_random03 | AC | 75 ms | 1920 KB |
06_random04 | AC | 34 ms | 1920 KB |
06_random05 | AC | 40 ms | 1920 KB |
06_random06 | AC | 21 ms | 1920 KB |
06_random07 | AC | 31 ms | 1920 KB |
06_random08 | AC | 22 ms | 1920 KB |
06_random09 | AC | 71 ms | 1920 KB |
06_random10 | AC | 16 ms | 1920 KB |
06_random11 | AC | 30 ms | 1920 KB |
06_random12 | AC | 73 ms | 1920 KB |
06_random13 | AC | 27 ms | 1920 KB |
06_random14 | AC | 31 ms | 1920 KB |
06_random15 | AC | 13 ms | 1920 KB |
06_random16 | AC | 45 ms | 1920 KB |
06_random17 | AC | 33 ms | 1920 KB |
06_random18 | AC | 21 ms | 1920 KB |
06_random19 | AC | 25 ms | 1920 KB |