Submission #3027255
Source Code Expand
#include <iostream> #include <string> #include <queue> #include <vector> #include <set> #include <map> #include <algorithm> #include <utility> #include <iomanip> #define ll long long int #define pb push_back #define mk make_pair #define pq priority_queue using namespace std; typedef pair<int, int> P; typedef pair<ll, int> Pl; const int inf = 1e9; const ll linf = 1LL << 50; const int mod = 1e9+7; int n, m; map<int, int> mpa; map<int, int> mpb; vector<int> veca; vector<int> vecb; ll dp[1001][101]; ll ans[101][1001]; ll ansb[101][1001]; int suma = 0; int sumb = 0; int main(int argc, char const* argv[]) { cin >> n >> m; for(int i = 0; i < n; i++){ int x; cin >> x; mpa[x]++; if(i == 0 || veca[veca.size() - 1] != x)veca.pb(x); sumb += x; } for(int i = 0; i < m; i++){ int x; cin >> x; mpb[x]++; if(i == 0 || vecb[vecb.size() - 1] != x)vecb.pb(x); suma += x; } for(int i = 0; i <= 100; i++){ dp[0][i] = 1; } for(int i = 1; i < 1000; i++){ for(int j = 1; j <= 100; j++){ dp[i][j] = dp[i][j-1]; if(i >= j)dp[i][j] += dp[i-j][j]; dp[i][j] %= mod; } } ans[0][0] = 1; for(int i = 0; i < veca.size(); i++){ ans[i+1][0] = 1; for(int j = 1; j <= suma; j++){ ans[i+1][j] = 0; for(int k = 0; k <= j; k++){ ans[i+1][j] += ans[i][j-k] * dp[k][mpa[veca[i]]]; ans[i+1][j] %= mod; } } } ansb[0][0] = 1; for(int i = 0; i < vecb.size(); i++){ ansb[i+1][0] = 1; for(int j = 1; j <= sumb; j++){ ansb[i+1][j] = 0; for(int k = 0; k <= j; k++){ ansb[i+1][j] += ansb[i][j-k] * dp[k][mpb[vecb[i]]]; ansb[i+1][j] %= mod; } } } cout << ans[veca.size()][suma] * ansb[vecb.size()][sumb] % mod << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Kill/Death |
User | fumiphys |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1827 Byte |
Status | WA |
Exec Time | 246 ms |
Memory | 1536 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 2 ms | 1024 KB |
01_sample01 | AC | 2 ms | 1024 KB |
01_sample02 | AC | 2 ms | 1024 KB |
01_sample03 | AC | 2 ms | 1024 KB |
01_sample04 | AC | 3 ms | 1024 KB |
02_minimal00 | AC | 2 ms | 1024 KB |
02_minimal01 | WA | 5 ms | 1024 KB |
02_minimal02 | WA | 5 ms | 1024 KB |
02_minimal03 | WA | 8 ms | 1024 KB |
03_maximal00 | WA | 14 ms | 1024 KB |
03_maximal01 | WA | 8 ms | 1024 KB |
04_random-easy00 | AC | 2 ms | 1024 KB |
04_random-easy01 | AC | 2 ms | 1024 KB |
04_random-easy02 | AC | 2 ms | 1024 KB |
04_random-easy03 | AC | 2 ms | 1024 KB |
04_random-easy04 | AC | 2 ms | 1024 KB |
04_random-easy05 | AC | 2 ms | 1024 KB |
04_random-easy06 | AC | 2 ms | 1024 KB |
04_random-easy07 | AC | 2 ms | 1024 KB |
04_random-easy08 | AC | 2 ms | 1024 KB |
04_random-easy09 | AC | 2 ms | 1024 KB |
04_random-easy10 | AC | 2 ms | 1024 KB |
04_random-easy11 | AC | 2 ms | 1024 KB |
04_random-easy12 | AC | 2 ms | 1024 KB |
04_random-easy13 | AC | 2 ms | 1024 KB |
04_random-easy14 | AC | 2 ms | 1024 KB |
04_random-easy15 | AC | 2 ms | 1024 KB |
04_random-easy16 | AC | 2 ms | 1024 KB |
04_random-easy17 | AC | 2 ms | 1024 KB |
04_random-easy18 | AC | 2 ms | 1024 KB |
04_random-easy19 | AC | 2 ms | 1024 KB |
05_random-large00 | AC | 199 ms | 1536 KB |
05_random-large01 | WA | 246 ms | 1536 KB |
05_random-large02 | AC | 222 ms | 1536 KB |
05_random-large03 | AC | 200 ms | 1536 KB |
05_random-large04 | AC | 207 ms | 1536 KB |
05_random-large05 | AC | 221 ms | 1536 KB |
05_random-large06 | AC | 218 ms | 1536 KB |
05_random-large07 | AC | 217 ms | 1536 KB |
05_random-large08 | AC | 209 ms | 1536 KB |
05_random-large09 | AC | 199 ms | 1536 KB |
05_random-large10 | AC | 206 ms | 1536 KB |
05_random-large11 | AC | 209 ms | 1536 KB |
05_random-large12 | AC | 215 ms | 1536 KB |
05_random-large13 | AC | 228 ms | 1536 KB |
05_random-large14 | AC | 221 ms | 1536 KB |
05_random-large15 | AC | 183 ms | 1536 KB |
05_random-large16 | AC | 215 ms | 1536 KB |
05_random-large17 | AC | 227 ms | 1536 KB |
05_random-large18 | AC | 217 ms | 1536 KB |
05_random-large19 | AC | 200 ms | 1536 KB |
06_random00 | AC | 96 ms | 1408 KB |
06_random01 | AC | 3 ms | 1152 KB |
06_random02 | AC | 6 ms | 1152 KB |
06_random03 | AC | 116 ms | 1408 KB |
06_random04 | AC | 40 ms | 1152 KB |
06_random05 | AC | 52 ms | 1408 KB |
06_random06 | AC | 16 ms | 1280 KB |
06_random07 | AC | 32 ms | 1280 KB |
06_random08 | AC | 18 ms | 1280 KB |
06_random09 | AC | 108 ms | 1408 KB |
06_random10 | AC | 6 ms | 1152 KB |
06_random11 | AC | 30 ms | 1152 KB |
06_random12 | AC | 113 ms | 1408 KB |
06_random13 | AC | 27 ms | 1280 KB |
06_random14 | AC | 34 ms | 1280 KB |
06_random15 | AC | 2 ms | 1152 KB |
06_random16 | AC | 62 ms | 1408 KB |
06_random17 | AC | 38 ms | 1280 KB |
06_random18 | AC | 16 ms | 1280 KB |
06_random19 | AC | 23 ms | 1280 KB |