Submission #123048
Source Code Expand
#include <string> #include <vector> #include <cmath> #include <ctime> #include <iostream> #include <cstdio> #include <set> #include <map> #include <queue> #include <sstream> #include <algorithm> #include <numeric> #include <cstring> using namespace std; typedef long long ll; const ll MOD = 1000000007; ll C[1000][1000]; void init(){ for(int n=0;n<1000;n++){ for(int k=0;k<=n;k++){ if(k == 0 || k == n){ C[n][k] = 1; } else { C[n][k] = (C[n-1][k] + C[n-1][k-1]) % MOD; } } } } ll sub(int N, int D, int L){ if(N < 0 || D < 0 || L < 0 || D + L > N)return 0; ll res = 1; res = (res * C[N][D]) % MOD; res = (res * C[N - D][L]) % MOD; return res; } ll solve(int X, int Y, int D, int L){ if(X > Y){ swap(X, Y); } int N = X * Y; ll res = 0; if(X == 1 && Y == 1){ if(D == 1)++res; if(L == 1)++res; return res; } if(X == 1){ res = (res + sub(N - 2, D - 2, L)) % MOD; res = (res + sub(N - 2, D, L - 2)) % MOD; res = (res + sub(N - 2, D - 1, L - 1) * 2) % MOD; return res; } for(int a=1;a<=X;a++)for(int b=1;b<=Y;b++)for(int c=1;c<=X;c++)for(int d=1;d<=Y;d++){ if(a < X && b == 1)continue; if(b < Y && c == 1)continue; if(c < X && d == 1)continue; if(d < Y && a == 1)continue; int cnt = 4; if(a == X && b == 1)--cnt; if(b == Y && c == 1)--cnt; if(c == X && d == 1)--cnt; if(d == Y && a == 1)--cnt; for(int m=0;m<1<<cnt;m++){ int dd = D, ll = L; for(int i=0;i<cnt;i++){ if((m >> i) & 1){ --dd; } else { --ll; } } int rest = X * Y; rest -= (X - a); rest -= (Y - b); rest -= (X - c); rest -= (Y - d); rest -= cnt; res = (res + sub(rest, dd, ll)) % MOD; } } return res; } int main(){ init(); int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; ll sub = solve(X, Y, D, L); ll p = (R - X + 1) * (C - Y + 1); ll res = (sub * p) % MOD; cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | kroton |
Language | C++ (G++ 4.6.4) |
Score | 101 |
Code Size | 2018 Byte |
Status | AC |
Exec Time | 366 ms |
Memory | 7712 KB |
Judge Result
Set Name | sub | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 100 / 100 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sub | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, test_03E.txt, test_04E.txt, test_07E.txt, test_08E.txt, test_11E.txt, test_12E.txt, test_15E.txt, test_16E.txt, test_19E.txt, test_20E.txt, test_23E.txt, test_24E.txt, test_27E.txt, test_28E.txt, test_31E.txt, test_32E.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_45E.txt, test_47E.txt |
All | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03E.txt, test_04E.txt, test_05.txt, test_06.txt, test_07E.txt, test_08E.txt, test_09.txt, test_10.txt, test_11E.txt, test_12E.txt, test_13.txt, test_14.txt, test_15E.txt, test_16E.txt, test_17.txt, test_18.txt, test_19E.txt, test_20E.txt, test_21.txt, test_22.txt, test_23E.txt, test_24E.txt, test_25.txt, test_26.txt, test_27E.txt, test_28E.txt, test_29.txt, test_30.txt, test_31E.txt, test_32E.txt, test_33.txt, test_34.txt, test_35.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45E.txt, test_46.txt, test_47E.txt, test_48.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01E.txt | AC | 33 ms | 7576 KB |
00_sample_02E.txt | AC | 33 ms | 7588 KB |
00_sample_03E.txt | AC | 47 ms | 7588 KB |
00_sample_04.txt | AC | 139 ms | 7588 KB |
test_01.txt | AC | 35 ms | 7672 KB |
test_02.txt | AC | 35 ms | 7652 KB |
test_03E.txt | AC | 33 ms | 7672 KB |
test_04E.txt | AC | 88 ms | 7588 KB |
test_05.txt | AC | 33 ms | 7588 KB |
test_06.txt | AC | 192 ms | 7668 KB |
test_07E.txt | AC | 37 ms | 7656 KB |
test_08E.txt | AC | 47 ms | 7596 KB |
test_09.txt | AC | 58 ms | 7712 KB |
test_10.txt | AC | 123 ms | 7588 KB |
test_11E.txt | AC | 44 ms | 7592 KB |
test_12E.txt | AC | 78 ms | 7588 KB |
test_13.txt | AC | 35 ms | 7712 KB |
test_14.txt | AC | 343 ms | 7584 KB |
test_15E.txt | AC | 107 ms | 7584 KB |
test_16E.txt | AC | 352 ms | 7588 KB |
test_17.txt | AC | 33 ms | 7584 KB |
test_18.txt | AC | 35 ms | 7592 KB |
test_19E.txt | AC | 33 ms | 7596 KB |
test_20E.txt | AC | 34 ms | 7588 KB |
test_21.txt | AC | 35 ms | 7584 KB |
test_22.txt | AC | 122 ms | 7668 KB |
test_23E.txt | AC | 33 ms | 7596 KB |
test_24E.txt | AC | 202 ms | 7588 KB |
test_25.txt | AC | 41 ms | 7592 KB |
test_26.txt | AC | 34 ms | 7592 KB |
test_27E.txt | AC | 79 ms | 7588 KB |
test_28E.txt | AC | 141 ms | 7580 KB |
test_29.txt | AC | 320 ms | 7652 KB |
test_30.txt | AC | 366 ms | 7588 KB |
test_31E.txt | AC | 48 ms | 7592 KB |
test_32E.txt | AC | 349 ms | 7592 KB |
test_33.txt | AC | 35 ms | 7660 KB |
test_34.txt | AC | 36 ms | 7584 KB |
test_35.txt | AC | 33 ms | 7580 KB |
test_36E.txt | AC | 33 ms | 7596 KB |
test_37E.txt | AC | 34 ms | 7588 KB |
test_38E.txt | AC | 33 ms | 7580 KB |
test_39E.txt | AC | 34 ms | 7600 KB |
test_40.txt | AC | 36 ms | 7584 KB |
test_41.txt | AC | 33 ms | 7592 KB |
test_42.txt | AC | 35 ms | 7596 KB |
test_43.txt | AC | 33 ms | 7708 KB |
test_44.txt | AC | 37 ms | 7652 KB |
test_45E.txt | AC | 34 ms | 7648 KB |
test_46.txt | AC | 34 ms | 7592 KB |
test_47E.txt | AC | 33 ms | 7588 KB |
test_48.txt | AC | 33 ms | 7584 KB |