Submission #6394981

---

Source Code Expand

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

const int W = 1000;
long judge(const vector<int>& a) {
  const int N = a.size();
  vector<vector<long>> dp(N + 1, vector<long>(W + 1));
  
  dp[0][0] = 1;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= W; ++j) {
      dp[i + 1][j] += dp[i][j];
      if (j + a[i] > W) continue;
      dp[i + 1][j + a[i]] += dp[i][j];
    }
  }
  
  long sum = 0;
  for (int j = 0; j <= W; ++j) {
    sum += dp[N][j];
  }
  return sum;
}


long C[64][64];
void pre() {
  for (int i = 0; i < 64; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (j == 0) {
        C[i][j] = 1;
      } else if (i == j) {
        C[i][j] = 1ll << i;
      } else {
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      }
    }
  }
}

vector<int> solve(long m) {
  pre();
  vector<int> a;
  long base = 1;
  int cnt = 0;
  while (base * 2 < m) {
    base *= 2;
    ++cnt;
    a.push_back(1);
  }
  
  long rem = m - base;
  for (int j = cnt; j >= 0; --j) {
    while (rem >= C[cnt][j]) {
      a.push_back(W - j);
      rem -= C[cnt][j];
    }
  }
  return a;
}

int main() {
  long m;
  cin >> m;
  auto a = solve(m);
  
  cout << a.size() << ' ' << W << endl;
  for (int i = 0; i < a.size(); ++i) {
    cout << a[i] << endl;
  }
}

Submission Info

Judge Result