Submission #123228
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 S = 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(S-2, D-2, L)) % MOD; res = (res + sub(S-2, D, L-2)) % MOD; res = (res + sub(S-2, D-1, L-1) * 2) % MOD; return res; } for(int m=0;m<1<<4;m++){ int N = S; bool f[4]; f[0] = (m >> 0) & 1; f[1] = (m >> 1) & 1; f[2] = (m >> 2) & 1; f[3] = (m >> 3) & 1; int cnt = 0; if(f[0])N -= X, ++cnt; if(f[1])N -= Y, ++cnt; if(f[2])N -= X, ++cnt; if(f[3])N -= Y, ++cnt; if(f[0] && f[1])++N; if(f[1] && f[2])++N; if(f[2] && f[3])++N; if(f[3] && f[0])++N; if(cnt % 2 == 0)res = (res + sub(N, D, L)) % MOD; else res = (res - sub(N, D, L) + MOD) % 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 | 1803 Byte |
Status | AC |
Exec Time | 36 ms |
Memory | 7672 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 | 7596 KB |
00_sample_02E.txt | AC | 32 ms | 7588 KB |
00_sample_03E.txt | AC | 33 ms | 7588 KB |
00_sample_04.txt | AC | 34 ms | 7592 KB |
test_01.txt | AC | 35 ms | 7592 KB |
test_02.txt | AC | 34 ms | 7592 KB |
test_03E.txt | AC | 35 ms | 7584 KB |
test_04E.txt | AC | 34 ms | 7596 KB |
test_05.txt | AC | 34 ms | 7592 KB |
test_06.txt | AC | 32 ms | 7576 KB |
test_07E.txt | AC | 32 ms | 7580 KB |
test_08E.txt | AC | 35 ms | 7672 KB |
test_09.txt | AC | 34 ms | 7592 KB |
test_10.txt | AC | 34 ms | 7588 KB |
test_11E.txt | AC | 35 ms | 7592 KB |
test_12E.txt | AC | 34 ms | 7588 KB |
test_13.txt | AC | 33 ms | 7576 KB |
test_14.txt | AC | 35 ms | 7592 KB |
test_15E.txt | AC | 34 ms | 7644 KB |
test_16E.txt | AC | 34 ms | 7592 KB |
test_17.txt | AC | 34 ms | 7584 KB |
test_18.txt | AC | 34 ms | 7672 KB |
test_19E.txt | AC | 35 ms | 7672 KB |
test_20E.txt | AC | 34 ms | 7584 KB |
test_21.txt | AC | 34 ms | 7584 KB |
test_22.txt | AC | 34 ms | 7592 KB |
test_23E.txt | AC | 35 ms | 7592 KB |
test_24E.txt | AC | 34 ms | 7584 KB |
test_25.txt | AC | 36 ms | 7652 KB |
test_26.txt | AC | 35 ms | 7592 KB |
test_27E.txt | AC | 34 ms | 7672 KB |
test_28E.txt | AC | 33 ms | 7584 KB |
test_29.txt | AC | 33 ms | 7588 KB |
test_30.txt | AC | 32 ms | 7580 KB |
test_31E.txt | AC | 32 ms | 7672 KB |
test_32E.txt | AC | 33 ms | 7580 KB |
test_33.txt | AC | 33 ms | 7584 KB |
test_34.txt | AC | 33 ms | 7592 KB |
test_35.txt | AC | 34 ms | 7588 KB |
test_36E.txt | AC | 34 ms | 7596 KB |
test_37E.txt | AC | 33 ms | 7592 KB |
test_38E.txt | AC | 33 ms | 7588 KB |
test_39E.txt | AC | 34 ms | 7652 KB |
test_40.txt | AC | 33 ms | 7596 KB |
test_41.txt | AC | 32 ms | 7592 KB |
test_42.txt | AC | 33 ms | 7580 KB |
test_43.txt | AC | 34 ms | 7588 KB |
test_44.txt | AC | 33 ms | 7584 KB |
test_45E.txt | AC | 32 ms | 7672 KB |
test_46.txt | AC | 34 ms | 7644 KB |
test_47E.txt | AC | 33 ms | 7580 KB |
test_48.txt | AC | 36 ms | 7596 KB |