Codeforces755F.PolandBallandGifts多重背包+贪心

#include
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 1e6+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;

int a[N],b[N],n,k,vis[N],H[N],cnt;
int main() {
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
    for(int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        int j = a[i],cnts = 0;
        while(!vis[j]) {
            cnts++;
            vis[j] = 1;
            j = a[j];
        }
        b[++cnt] = cnts;
    }
    sort(b+1,b+cnt+1);
    int ans2 = 0,kk = k;
    for(int i = 1; i <= cnt; ++i) {
        if(kk >= b[i]/2) kk-=b[i]/2,ans2 += b[i]/2*2;
        else {
            ans2 += 2*kk;
            kk = 0;
            break;
        }
    }
    ans2 += kk;
    ans2 = min(n,ans2);
    for(int i = 1; i <= cnt; ++i) H[b[i]]++;
    bitset dp;
    dp.set(0);
    for(int i = 1; i <= n; ++i) {
        if(H[i] == 0) continue;
        int t = H[i],l = 1;
        while(t) {
            int w = min(t,l);
            t -= w;
            dp |= dp<<(w*i);
            l <<= 1;
        }
        if(dp[k] == 1) {
            printf("%d %d\n",k,ans2);
            return 0;
        }
    }
    printf("%d %d\n",1+k,ans2);
    return 0;
}