結果

問題 No.412 花火大会
ユーザー te-sh
提出日時 2017-10-25 16:26:06
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,025 bytes
コンパイル時間 1,268 ms
コンパイル使用メモリ 110,896 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 22:06:52
合計ジャッジ時間 1,810 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto s = readln.split.to!(int[]), ns = s.length;
  auto n = readln.chomp.to!size_t;
  auto e = readln.split.to!(int[]);

  s.sort();
  auto b = s[0], c = s[1], d = s[2];

  auto s1 = e.count!(ei => b <= ei && ei < c);
  auto s2 = e.count!(ei => c <= ei && ei < d);
  auto s3 = e.count!(ei => d <= ei);

  auto pt = pascalTriangle!int(n), ans = 0;

  foreach (i1; 0..s1+1)
    foreach (i2; 0..s2+1)
      foreach (i3; 0..s3+1) {
        if (i3 >= 3 ||
            i3 == 2 && (i2 >= 1 || i1 >= 1) ||
            i3 == 1 && (i2 >= 2 || i2 == 1 && i1 >= 1)) {
          ans += pt[s3][i3] * pt[s2][i2] * pt[s1][i1] * 2 ^^ (n-s1-s2-s3);
        }
      }

  writeln(ans);
}

pure T[][] pascalTriangle(T)(size_t n)
{
  auto t = new T[][](n + 1);
  t[0] = new T[](1);
  t[0][0] = 1;
  foreach (i; 1..n+1) {
    t[i] = new T[](i + 1);
    t[i][0] = t[i][$-1] = 1;
    foreach (j; 1..i)
      t[i][j] = t[i - 1][j - 1] + t[i - 1][j];
  }
  return t;
}
0