Submission #122993


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>
#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;

#ifdef _MSC_VER
#include "_lib_msc.h"
#endif

#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)            __typeof__((c).rbegin())
#define RFOREACH(it, c)     for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define REPEAT(i, k, n)     for(int(i)=(k);(i)<((k)+(n));++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
#define RREPEAT(i, k, n)    for(int(i)=(k)+(n)-1;(i)>=(k);--(i))
#define FROMTO(i,f,t)       for(int(i)=(f);(i)<(t);(++i))
#define ALL(c)              (c).begin(), (c).end()
#define ESIZEOF(A)          (sizeof(A)/sizeof((A)[0]))
#define CIN_NO_SYNC         do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)           fgets((p), sizeof(p), stdin)
#define CHOMP(p)            do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n' || *_q == '\r') *_q = 0; } while(0)
#define FILL(m,v)           memset(m, v, sizeof(m))
#define mp                  make_pair
#define pb                  push_back
template<class _T> _T MAX(_T p1,_T p2){return (p2<p1)?p1:p2;} 
template<class _T> _T MIN(_T p1,_T p2){return (p1<p2)?p1:p2;} 
template <class _Tv> inline string join(const _Tv &v,string sep=" "){
    ostringstream s;FOREACH(it,v){if(it!=v.begin())s<<sep;s<<*it;};return s.str();
}
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
inline int clz(ui n){return n==0?32:__builtin_clz(n);}
inline int clz(ull n){return n==0?64:__builtin_clzll(n);}
inline int crz(ui n){return n==0?32:__builtin_ctz(n);}
inline int crz(ull n){return n==0?64:__builtin_ctzll(n);}
inline int bitc(ui n){return __builtin_popcount(n);}
inline int bitc(ull n){return __builtin_popcountll(n);} 
#ifdef _DEBUG
#include "_lib_dbg.h"
#else
#define pf(...) /* */
#define pr(...) /* */
#define prfe(...) /* */
#define prfep(...) /* */
#define dbgchk(...) /* */
#endif

const int MOD = 1000000007;

int dp[900][900][2][2][2][2];

vector<vector<ll> > c;
void combination_gen(int n, vector<vector<ll> > &c){
    c.resize(n+1); REP(i,n+1) c[i].resize(n+1); c[0][0] = 1;
    REPEAT(i,1,n) REP(j,i+1) c[i][j] = (c[i-1][j] + (j > 0 ? c[i-1][j-1] : 0)) % MOD;
}

int R,C,X,Y,D,L,M;
ll dfs(int i, int b, int f1, int f2, int f3, int f4){
    if(i == M){
        if(b||!f1||!f2||!f3||!f4) return 0;
        return 1;
    }
    int x = i%X, y = i/X;
    if(dp[i][b][f1][f2][f3][f4] >= 0) return dp[i][b][f1][f2][f3][f4];
    ll res = 0;
    
    res += dfs(i+1, b-1, f1|(x==0), f2|(y==0), f3|(x==X-1), f4|(y==Y-1));
    res += dfs(i+1, b, f1, f2, f3, f4);
    res %= MOD;

    return (dp[i][b][f1][f2][f3][f4] = res);
}

int main(){
    cin >>R>>C>>X>>Y>>D>>L;
    M = X*Y;
    FILL(dp,-1);
    ll p = dfs(0,D+L,0,0,0,0);

    combination_gen(901, c);

    p = (p * c[L+D][L]) % MOD;
    p = (p * (R-X+1)) % MOD;
    p = (p * (C-Y+1)) % MOD;
    cout << p << endl;
}

Submission Info

Submission Time
Task D - AtCoder社の冬
User naoki
Language C++ (G++ 4.6.4)
Score 101
Code Size 3588 Byte
Status AC
Exec Time 354 ms
Memory 57992 KB

Judge Result

Set Name sub All
Score / Max Score 100 / 100 1 / 1
Status
AC × 25
AC × 52
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 126 ms 57768 KB
00_sample_02E.txt AC 123 ms 57780 KB
00_sample_03E.txt AC 132 ms 57776 KB
00_sample_04.txt AC 191 ms 57772 KB
test_01.txt AC 126 ms 57772 KB
test_02.txt AC 128 ms 57772 KB
test_03E.txt AC 123 ms 57752 KB
test_04E.txt AC 172 ms 57764 KB
test_05.txt AC 121 ms 57772 KB
test_06.txt AC 226 ms 57772 KB
test_07E.txt AC 123 ms 57776 KB
test_08E.txt AC 130 ms 57764 KB
test_09.txt AC 132 ms 57768 KB
test_10.txt AC 171 ms 57748 KB
test_11E.txt AC 133 ms 57836 KB
test_12E.txt AC 145 ms 57776 KB
test_13.txt AC 125 ms 57748 KB
test_14.txt AC 340 ms 57772 KB
test_15E.txt AC 173 ms 57832 KB
test_16E.txt AC 342 ms 57768 KB
test_17.txt AC 120 ms 57772 KB
test_18.txt AC 123 ms 57768 KB
test_19E.txt AC 124 ms 57768 KB
test_20E.txt AC 128 ms 57772 KB
test_21.txt AC 125 ms 57772 KB
test_22.txt AC 194 ms 57768 KB
test_23E.txt AC 133 ms 57776 KB
test_24E.txt AC 256 ms 57768 KB
test_25.txt AC 126 ms 57764 KB
test_26.txt AC 125 ms 57768 KB
test_27E.txt AC 149 ms 57760 KB
test_28E.txt AC 207 ms 57816 KB
test_29.txt AC 317 ms 57992 KB
test_30.txt AC 352 ms 57764 KB
test_31E.txt AC 138 ms 57760 KB
test_32E.txt AC 354 ms 57776 KB
test_33.txt AC 122 ms 57760 KB
test_34.txt AC 126 ms 57780 KB
test_35.txt AC 119 ms 57772 KB
test_36E.txt AC 126 ms 57760 KB
test_37E.txt AC 128 ms 57772 KB
test_38E.txt AC 125 ms 57764 KB
test_39E.txt AC 124 ms 57776 KB
test_40.txt AC 125 ms 57772 KB
test_41.txt AC 125 ms 57764 KB
test_42.txt AC 125 ms 57776 KB
test_43.txt AC 129 ms 57856 KB
test_44.txt AC 122 ms 57764 KB
test_45E.txt AC 121 ms 57768 KB
test_46.txt AC 123 ms 57772 KB
test_47E.txt AC 128 ms 57764 KB
test_48.txt AC 125 ms 57780 KB