제출 #427327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427327		peijar	비스킷 담기 (IOI20_biscuits)	C++17	9 / 100	1096 ms	332 KiB

biscuits

#include <bits/stdc++.h>
#define int long long
using namespace std;

#include "biscuits.h"

// dp[cur][nbNecessaire] = nb de facons de choisir y si il faut nbNecessaire et
// qu'on autorise que ceux avec des bits <= cur
//
// dp[cur][nbNecessaire] = dp[cur-1][2 * (max(0, nbNecessaire - a[cur]))]
// + dp[cur-1][2 * (max(0, x + nbNecessaire - a[cur]))]
// dp[-1][0] = 1
//
//
// dp2[cur][nbSupplements] = dp2[cur+1][ (nbSupplements + a[cur]) / 2]
// + dp2[cur+1][(nbSupplements + a[cur] - x) / 2]
//
// dp2[256][nbSupplements] = 1
//
//
// Si a[i] > x on peut ajouter (a[i] - x) / 2 à a[i+1]
// Donc a[i] <= x pour tout i

const int MAX = 256;
int dfs(const vector<int> &a, int nbRestants, int x, int curBit) {
  if (curBit == MAX)
    return 1;
  if (curBit < (int)a.size())
    nbRestants += a[curBit];
  int sol = dfs(a, nbRestants / 2, x, curBit + 1);
  if (nbRestants >= x)
    sol += dfs(a, (nbRestants - x) / 2, x, curBit + 1);
  return sol;
}

int count_tastiness(int x, vector<int> a) {
  return dfs(a, 0, x, 0);
  if (x > (int)1e5)
    return 1;
  array<vector<int>, 2> arr;
  arr.fill(vector<int>(x + 2, 0));

  for (int i(0); i < (int)a.size(); ++i) {
    if (a[i] > x) {
      if (i + 1 == (int)a.size())
        a.push_back(0);
      a[i + 1] += (a[i] - x) / 2;
      a[i] -= 2 * ((a[i] - x) / 2);
    }
  }

  for (int nbRestants = 0; nbRestants <= x + 1; ++nbRestants)
    arr[(MAX - 1) % 2][nbRestants] = 1;

  for (int i(MAX - 2); i >= 0; --i) {
    int cur = i % 2;
    int prev = !cur;
    for (int nbRestants = 0; nbRestants <= x + 1; ++nbRestants) {
      arr[cur][nbRestants] = 0;
      int tot = nbRestants;
      if (i < (int)a.size())
        tot += a[i];
      if (tot >= x)
        arr[cur][nbRestants] += arr[prev][(tot - x) / 2];
      arr[cur][nbRestants] += arr[prev][tot / 2];
    }
  }
  return arr[0][0];
}

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