제출 #342124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342124		chenwz	비스킷 담기 (IOI20_biscuits)	C++14	100 / 100	20 ms	1408 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
using namespace std;
typedef long long LL;
const int NN = 63;
LL count_tastiness(LL x, vector<LL> a) {
  vector <LL> S(NN, 0), D(NN, 0);
  LL s = 0;
  for (size_t i = 0; i < NN; i++) {
    if (i < a.size()) s += a[i] << i;
    S[i] = s;
  } // S = ∑a(i)2^i
  D[0] = 1; // D(i): # of valid y, y ≤2^i
  for (int i = 1; i < NN; i++) {
    LL cur = s; D[i] = 1;
    for (int j = i; j--;) { // j <= i
      cur = min(cur, S[j]);
      if (x <= (cur >> j)) cur -= x << j, D[i] += D[j];
    }
  }
  return D.back();
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23