Submission #1231457

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
lli MOD = 1e9 + 7;

bool dp[5100][5510] = {};
int main()
{
    //つまり考えるべきことはi以外でもっともSに近いものを作るてその総和+a_iがKを超えれば不必要ではない
    //これはk>=a_i + S つまり(k-a_i)<=s&&s<kなるsの存在判定
    //iで毎回dpすればn^2kで部分点
    lli n, k;

    lli a[100005];
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    sort(a, a + n);
    int cnt = 0;
    int u = n;
    int L = 0;
    while (u - L > 1) {
        rep(i, 5100) rep(j, 5510) dp[i][j] = false;
        int i = (u + L) / 2;
        dp[0][0] = true;
        rep(j, n) rep(l, k)
        {
            if (dp[j][l])
                dp[j + 1][l] = true;
            if (i == j)
                continue;
            if (dp[j][l] && a[j] + l < k) {
                dp[j + 1][a[j] + l] = true;
            }
        }
        bool flag = false;
        rrep(l, k)
        {
            if (dp[n][l]) {
                if (l + a[i] >= k) {
                    flag = true;
                    u = i;
                    break;
                }
            }
        }
        if (!flag)
            L = i;
    }
    cout << u << endl;
}

Submission Info

Judge Result