Submission #123013
Source Code Expand
#include <iostream> #include <iomanip> #include <sstream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <cfloat> #include <vector> #include <string> #include <stack> #include <queue> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <numeric> #include <iterator> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int,int> PII; typedef vector<PII> VPII; typedef istringstream ISS; typedef ostringstream OSS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) #define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it ) #define ALL( c ) (c).begin(), (c).end() #define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end() #define PB( n ) push_back( n )>> d > #define MP( a, b ) make_pair( ( a ), ( b ) ) #define EXIST( c, e ) ( (c).find( e ) != (c).end() ) #define fst first #define snd second #define DUMP( x ) cerr << #x << " = " << ( x ) << endl #define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl const int MOD = 1000000007; int dp[ 30 * 30 + 1 ][ 30 * 30 + 2 ][ 1 << 4 ]; int solve2( const int N, const int A, const int B ) { VVI dp( N + 1, VI( A + 2, 0 ) ); dp[0][0] = 1; REP( i, 0, N ) { REP( a, 0, A + 1 ) { const int b = i - a; if ( a < A ) { ( dp[ i + 1 ][ a + 1 ] += dp[i][a] ) %= MOD; } if ( b < B ) { ( dp[ i + 1 ][a] += dp[i][a] ) %= MOD; } } } return dp[N][A]; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; dp[0][0][0] = 1; //dp[ i 箇所決定 ][ 何かを置いた数 ][ 上下左右のフラグ ] := 場合の数 REP( i, 0, X * Y ) { REP( j, 0, X * Y + 1 ) { REP( k, 0, 1 << 4 ) { int nk = k; nk |= i < Y; nk |= ( i % Y == 0 ) << 1; nk |= ( X * Y - Y <= i ) << 2; nk |= ( i % Y == Y - 1 ) << 3; { // 何も置かない ( dp[ i + 1 ][j][k] += dp[i][j][k] ) %= MOD; } { // 何かを置く ( dp[ i + 1 ][ j + 1 ][ nk ] += dp[i][j][k] ) %= MOD; } } } } LL res = (LL)dp[ X * Y ][ D + L ][ ( 1 << 4 ) - 1 ] * solve2( D + L, D, L ); ( res *= R - X + 1 ) %= MOD; ( res *= C - Y + 1 ) %= MOD; cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | torus711 |
Language | C++11 (GCC 4.8.1) |
Score | 101 |
Code Size | 2595 Byte |
Status | AC |
Exec Time | 268 ms |
Memory | 51556 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 | 22 ms | 804 KB |
00_sample_02E.txt | AC | 21 ms | 804 KB |
00_sample_03E.txt | AC | 35 ms | 4000 KB |
00_sample_04.txt | AC | 112 ms | 20508 KB |
test_01.txt | AC | 21 ms | 988 KB |
test_02.txt | AC | 20 ms | 804 KB |
test_03E.txt | AC | 22 ms | 804 KB |
test_04E.txt | AC | 74 ms | 12456 KB |
test_05.txt | AC | 22 ms | 804 KB |
test_06.txt | AC | 149 ms | 28200 KB |
test_07E.txt | AC | 23 ms | 1696 KB |
test_08E.txt | AC | 35 ms | 4380 KB |
test_09.txt | AC | 44 ms | 6172 KB |
test_10.txt | AC | 98 ms | 17184 KB |
test_11E.txt | AC | 35 ms | 3832 KB |
test_12E.txt | AC | 65 ms | 10396 KB |
test_13.txt | AC | 27 ms | 1696 KB |
test_14.txt | AC | 268 ms | 51496 KB |
test_15E.txt | AC | 89 ms | 15224 KB |
test_16E.txt | AC | 267 ms | 51556 KB |
test_17.txt | AC | 21 ms | 936 KB |
test_18.txt | AC | 24 ms | 1568 KB |
test_19E.txt | AC | 21 ms | 808 KB |
test_20E.txt | AC | 21 ms | 1188 KB |
test_21.txt | AC | 23 ms | 1564 KB |
test_22.txt | AC | 95 ms | 17184 KB |
test_23E.txt | AC | 20 ms | 804 KB |
test_24E.txt | AC | 159 ms | 30748 KB |
test_25.txt | AC | 31 ms | 2856 KB |
test_26.txt | AC | 23 ms | 1196 KB |
test_27E.txt | AC | 66 ms | 10724 KB |
test_28E.txt | AC | 117 ms | 21240 KB |
test_29.txt | AC | 243 ms | 48164 KB |
test_30.txt | AC | 268 ms | 51492 KB |
test_31E.txt | AC | 37 ms | 4396 KB |
test_32E.txt | AC | 267 ms | 51496 KB |
test_33.txt | AC | 21 ms | 936 KB |
test_34.txt | AC | 25 ms | 1952 KB |
test_35.txt | AC | 21 ms | 796 KB |
test_36E.txt | AC | 21 ms | 928 KB |
test_37E.txt | AC | 21 ms | 928 KB |
test_38E.txt | AC | 19 ms | 804 KB |
test_39E.txt | AC | 23 ms | 808 KB |
test_40.txt | AC | 26 ms | 2080 KB |
test_41.txt | AC | 22 ms | 732 KB |
test_42.txt | AC | 25 ms | 1568 KB |
test_43.txt | AC | 21 ms | 1060 KB |
test_44.txt | AC | 26 ms | 1912 KB |
test_45E.txt | AC | 20 ms | 932 KB |
test_46.txt | AC | 21 ms | 1056 KB |
test_47E.txt | AC | 22 ms | 928 KB |
test_48.txt | AC | 20 ms | 804 KB |