NDCCARD - Các lá bài Blackjack
Tác giả: skyvn97
Ngôn ngữ: C++
#include<set>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MAX 10101
using namespace std;
const int INF=(int)1e9;
int m,n;
set<int> sa,sb;
int a[MAX];
int best;
int max(const int &x,const int &y) {
if (x>y) return (x); else return (y);
}
void init(void) {
scanf("%d",&n);
scanf("%d",&m);
int i;
for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
sort(&a[1],&a[n+1]);
if (n<3) {
printf("0");
exit(0);
}
if (a[1]+a[2]+a[3]>m) {
printf("0");
exit(0);
}
if (a[n]+a[n-1]+a[n-2]<=m) {
printf("%d",a[n]+a[n-1]+a[n-2]);
exit(0);
}
best=0;
}
int maxlower(const set<int> &s,const int &val) {
set<int>::iterator it;
it=s.begin();
if (s.empty()) return (-INF);
if (*it>val) return (-INF);
it=s.end();
it--;
if (*it<=val) return (*it);
else {
it=s.upper_bound(val);
it--;
return (*it);
}
}
void process(void) {
int i,j;
sa.clear();sb.clear();
for (i=1;i<=n/2;i=i+1) {
if (i>2) best=max(best,maxlower(sa,m-a[i])+a[i]);
if (best==m) {
printf("%d",m);
return;
}
for (j=1;j<i;j=j+1)
if (a[i]+a[j]<=m && sa.find(a[i]+a[j])==sa.end()) sa.insert(a[i]+a[j]);
}
for (i=n/2+1;i<=n;i=i+1) {
if (i-n/2>2) best=max(best,maxlower(sb,m-a[i])+a[i]);
if (best==m) {
printf("%d",m);
return;
}
for (j=n/2+1;j<i;j=j+1)
if (a[i]+a[j]<=m && sb.find(a[i]+a[j])==sb.end()) sb.insert(a[i]+a[j]);
}
for (i=1;i<=n;i=i+1) {
if (i<=n/2) best=max(best,maxlower(sb,m-a[i])+a[i]);
else best=max(best,maxlower(sa,m-a[i])+a[i]);
if (best==m) {
printf("%d",m);
return;
}
}
printf("%d",best);
}
int main(void) {
init();
process();
return 0;
}