https://ac.nowcoder.com/acm/contest/331/H

 

题解：

std

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int mn = 5005;
 
int n;
ll k;
int a[mn];
char s[mn];
 
struct node {
    int value, id;
    bool operator<(const node& r) const {
        if (value != r.value)
            return value < r.value;
        else
            return id < r.id;
    }
};
 
priority_queue<node> q;
 
ll d[mn][mn];
 
int main() {
    scanf("%d%lld", &n, &k);
    ll sum = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), q.push({a[i], i}), sum += a[i], s[i] = '0';
    ll nsum = sum - k;
 
    int ans = n;
    while (k < sum) {
        node u = q.top();
        q.pop();
        sum -= u.value;
        ans--;
    }
 
    for (int i = n; i; i--) {
        for (int j = 1; j <= n - i + 1; j++) {
            d[i][j] = max(d[i + 1][j - 1] + a[i], d[i + 1][j]);
        }
    }
 
    int nans = n - ans;
    for (int i = 1; i <= n; i++) {
        if (nsum > d[i + 1][nans]) {
            s[i] = '1';
            nsum -= a[i];
            nans--;
        }
    }
 
    printf("%d\n", ans);
    printf("%s\n", s + 1);
}