제출 #1259328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259328		nicolo_010	축제 (IOI25_festival)	C++20	5 / 100	327 ms	197920 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

const ll INF = 1e17;

std::vector<int> max_coupons(int AA, std::vector<int> P, std::vector<int> T) {
  ll A = AA;
  v<v<int>> order;
  v<v<int>> ones;
  int N = P.size();
  rep(i, 0, N) {
    if (T[i] != 1) order.push_back({P[i], T[i], i});
    else ones.push_back({P[i], i});
  }
  sort(order.begin(), order.end(), [&](v<int> a, v<int> b) {
    ll v1 = -a[0]*a[1]*b[1] - b[0]*b[1];
    ll v2 = -b[0]*b[1]*a[1] - a[0]*a[1];
    return v1 > v2;
  });

  sort(ones.begin(), ones.end());

  v<v<ll>> dp(N+1, v<ll>(71, -1));
  v<v<int>> par(N+1, v<int>(71, -1));

  int beg=0;
  for (auto x : order) {
    ll p = x[0], t = x[1];
    if ((A-p)*t >= A) {
      A = (A-p)*t;
      A = min(A, INF);
      beg++;
    }
  }

  rep(i, 0, N+1) {
    dp[i][0] = A;
  }
  int M = order.size();

  rep(i, beg+1, M+1) {
    ll p = order[i-1][0];
    ll t = order[i-1][1];

    rep(j, 0, 71) {
      if (dp[i-1][j] >= 0) {
        dp[i][j] = dp[i-1][j];
        par[i][j] = 0;
      }
    }

    rep(j, 0, 70) {
      if (dp[i-1][j] >= p) {
        ll val = (dp[i-1][j]-p)*t;
        val = min(val, INF);
        if (val > dp[i][j+1]) {
          dp[i][j+1] = val;
          par[i][j+1] = 1;
        }
      }
    }
  }

  int K = ones.size();

  v<ll> pref(K+1, 0);

  rep(i, 1, K+1) {
    pref[i] = pref[i-1] + ones[i-1][0];
  }

  int mx = -1, id=-1, one=-1;
  rep(j, 0, 70) {
    if (dp[M][j] >= 0) {
      int val = j;
      int l = 1, r = K;
      int anss=0;
      while (l <= r) {
        int m = (l+r)/2;
        if (pref[m] <= dp[M][j]) {
          l = m+1;
          anss = m;
        }
        else r=m-1;
      }

      val += anss;
      if (val > mx) {
        mx = val;
        id = j;
        one = anss;
      }
    }
  }

  v<int> ans;
  rep(i, 0, one) {
    ans.push_back(ones[i][1]);
  }

  for (int i = M; i >= beg; i--) {
    if (par[i][id] == 1) {
      id--;
      ans.push_back(order[i-1][2]);
    }
  }

  for (int i = beg-1; i >= 0; i--) {
    ans.push_back(order[i][2]);
  }
  reverse(ans.begin(), ans.end());

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18