結果
問題 | No.398 ハーフパイプ(2) |
ユーザー |
![]() |
提出日時 | 2016-07-15 23:53:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 1,212 bytes |
コンパイル時間 | 1,552 ms |
コンパイル使用メモリ | 160,668 KB |
実行使用メモリ | 40,448 KB |
最終ジャッジ日時 | 2024-06-27 14:34:44 |
合計ジャッジ時間 | 3,785 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(int)(b);i++) #define REP(i,b) FOR(i,0,b) #define ALL(c) c.begin(),c.end() #define PB push_back #define TT second.second #define SS second.first #define FF first using namespace std; typedef long double ld; typedef long long LL; typedef int ut; typedef vector<ut> VI; typedef pair<ut,ut> pr; typedef pair<ut,pr> ppr; typedef vector<pr> Vpr; typedef priority_queue<pr,Vpr,greater<pr> > PQ; const int INF=1<<30; const int BITSIZE=1<<12; const int SIZE=10+2*1e4; LL DP[101][101][5][400]; LL solve(int a,int b,int n,LL sum){ if(n==0) return sum==0; if(n*b<sum) return 0; if(sum<n*a) return 0; if(DP[a][b][n][sum]) return DP[a][b][n][sum]; LL answer=0; FOR(i,a,b+1) answer+=solve(a,b,n-1,sum-i); return DP[a][b][n][sum]=answer; } LL nCrDP[100][100]; LL nCr(int n,int r){ if(r==0 || r==n) return 1; if(nCrDP[n][r]) return nCrDP[n][r]; return nCrDP[n][r]=nCr(n-1,r-1)+nCr(n-1,r); } int main(){ ld x; cin >> x; LL sum=x*4; LL answer=0; REP(i,101) REP(j,i){ FOR(k,1,5+1) FOR(l,1,6-k+1){ answer+=nCr(6,k)*nCr(6-k,l)*solve(j+1,i-1,6-k-l,sum-i*(k-1)-j*(l-1)); } } if(sum%4==0) answer++; cout << answer << endl; return 0; }