結果
問題 | No.93 ペガサス |
ユーザー | hirose_golf |
提出日時 | 2014-12-07 21:50:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,454 bytes |
コンパイル時間 | 836 ms |
コンパイル使用メモリ | 94,948 KB |
実行使用メモリ | 35,584 KB |
最終ジャッジ日時 | 2024-06-11 17:35:53 |
合計ジャッジ時間 | 2,026 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 10 ms
35,328 KB |
testcase_02 | AC | 11 ms
35,328 KB |
testcase_03 | AC | 11 ms
35,328 KB |
testcase_04 | AC | 18 ms
35,440 KB |
testcase_05 | AC | 13 ms
35,456 KB |
testcase_06 | AC | 12 ms
35,264 KB |
testcase_07 | AC | 35 ms
35,296 KB |
testcase_08 | AC | 23 ms
35,456 KB |
testcase_09 | AC | 57 ms
35,504 KB |
testcase_10 | AC | 11 ms
35,312 KB |
testcase_11 | WA | - |
testcase_12 | AC | 51 ms
35,404 KB |
testcase_13 | AC | 21 ms
35,236 KB |
testcase_14 | AC | 13 ms
35,240 KB |
testcase_15 | AC | 46 ms
35,556 KB |
testcase_16 | AC | 16 ms
35,456 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 10 ms
35,328 KB |
testcase_19 | AC | 61 ms
35,584 KB |
ソースコード
#include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <cstring> #include <assert.h> #include <sys/time.h> #include <fstream> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) #define REP(i,n) FOR(i,0,n) #define each(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i) #define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i) #define exist(s,e) ((s).find(e)!=(s).end()) #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #define deb(x) cerr << #x << " = " << (x) << " , "; #define debl cerr << " (L" << __LINE__ << ")"<< endl; #define sz(s) (int)((s).size()) #define clr(a) memset((a),0,sizeof(a)) #define nclr(a) memset((a),-1,sizeof(a)) #define pb push_back #define INRANGE(x,s,e) ((s)<=(x) && (x)<(e)) #define MP(x,y) make_pair((x),(y)) double pi=3.14159265358979323846; using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<string> vs; template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){ os << "[ "; REP(i,z.size())os << z[i] << ", " ; return ( os << "]" << endl); } template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){ os << "set( "; EACH(p,z)os << (*p) << ", " ; return ( os << ")" << endl); } template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){ os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ; return ( os << "}" << endl); } template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){ return ( os << "(" << z.first << ", " << z.second << ",)" ); } double get_time(){ struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + tv.tv_usec*1e-6; } typedef unsigned int uint32_t; struct RND{ uint32_t x; uint32_t y; uint32_t z; uint32_t w; RND(){ x=123456789; y=362436069; z=521288629; w=88675123; } void init(int seed){ x=123456789; y=362436069; z=521288629; w=seed+100; REP(i,10)get(); } uint32_t get(){ uint32_t t; t=x^(x<<11); x=y;y=z;z=w; w=(w^(w>>19))^(t^(t>>8)); return w; } }; RND rnd; ll n; ll mod = 1000000007LL; ll memo[1010][1010][2][2]; ll brute(ll n){ vl a(n); rep(i,n)a[i]=i; ll cnt = 0; do{ bool ok = true; rep(i,n-1) if(abs(a[i+1]-a[i])==2)ok=false; if(ok) cnt++; }while(next_permutation(a.begin(), a.end())); return cnt; } ll rec(ll i, ll dame, int f1, int f2){ if(dame==-1)return 0; //既にi個置いた。 if(i==n)return dame==0; ll &ret = memo[i][dame][f1][f2]; if(ret != -1) return ret; ll ans = 0; if(f1==0){ if(f2==0){ ans += dame*rec(i+1, dame-1, f2, 0); //既にダメな場所においた。 } else{ ans += (dame-1)*rec(i+1, dame-1, f2, 0); //既にダメな場所においた。 ans += rec(i+1, dame-1, 0, 0); //既にダメな場所においた。 } ans += (i+1-2-dame) * rec(i+1, dame, f2, 0) ; // すでにOKかつ普通の場所においた。 ans += 2*rec(i+1, dame+1, f2, 1); //やばい場所においた。 } else{ if(f2==0){ ans += (dame-1)*rec(i+1,dame-1,f2,0) ; //すでにダメな場所かつ、普通の場所 } else{ ans += (dame-2)*rec(i+1, dame-1, f2, 0); //既にダメな場所においた。 ans += rec(i+1, dame-1, 0, 0); //既にダメな場所においた。 } ans += (i+1-1-dame)*rec(i+1,dame,f2,0) ; // すでにOKかつ普通の場所。 ans += rec(i+1,dame+1,f2,1) + rec(i+1,dame,f2,1); //やばい場所。 } return ret = ans%mod; } void _main(istream &inp){ inp >> n; if(n==1){ cout << 1 << endl; return; } if(n==2){ cout << 2 << endl; return; } nclr(memo); cout << 2*rec(2,0,0,0) << endl; } int main(){ if(0){ ifstream ifs("test.txt"); _main(ifs); } else{ _main(cin); } return 0; }