Submission #5541757
Source Code Expand
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <limits.h> #include <math.h> #include <functional> #include <bitset> #include <iomanip> #include <cassert> #include <float.h> #include <random> #define repeat(i,n) for (int i = 0; (i) < (n); ++ (i)) #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' #define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> Pii; typedef vector<int> vint; typedef vector<ll> vll; const ll INF = LLONG_MAX/10; const ll MOD = 1e9+7; int N; double dp[1<<16][20]; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N; int s=0; repeat(i,N){ int x;cin>>x; s |= 1<<x; } for(int b=1;b<(1<<16);b++){ for(int x=1;x<15;x++){ double tmp=0; int cnt=0; repeat(i,3){ if((b>>(x-1+i))&1){ double a =dp[b^(1<<(x-1+i))][1]; for(int y=2;y<15;y++){ a = min(a,dp[b^(1<<(x-1+i))][y]); } tmp += a; }else{ cnt++; } } if(cnt==3)dp[b][x] = INF; else dp[b][x] = (tmp+3)/(3-cnt); } } double ans = dp[s][1]; for(int x=2;x<15;x++){ ans = min(ans,dp[s][x]); } printf("%.7lf\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - ボール |
User | hashiryo |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 1707 Byte |
Status | AC |
Exec Time | 24 ms |
Memory | 10496 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 5 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 24 ms | 10496 KB |
01 | AC | 24 ms | 10496 KB |
02 | AC | 24 ms | 10496 KB |
03 | AC | 24 ms | 10496 KB |
90 | AC | 24 ms | 10496 KB |
91 | AC | 24 ms | 10496 KB |