Pagini recente » Cod sursa (job #1984405) | Cod sursa (job #880110) | Cod sursa (job #517910) | Cod sursa (job #1992167) | Cod sursa (job #1411910)
#include<cstdio>
#include<deque>
#define INF 2000000000
using namespace std;
deque<int>q;
int n,m,a,b,k,i,j,vmax,v[20500],x[250],y[250],d[2][76000],t[2][76000];
FILE *f,*g;
int minim(int a,int b){
if(a<b)
return a;
return b;
}
void rez(int st,int dr,int m){
/*while(x[st]==0&&st<=dr)
st++;
while(x[dr]==0&&dr>=st)
dr--;
*/
if(st==dr){
if(x[st]==0)
return;
for(i=1;i<=x[st];i++){
if(i*st<=m)
fprintf(g,"%d\n",st);
else
break;
}
return;
}
int nr=0;
for(i=0;i<=m;i++){
t[0][i]=i;
if( i%st==0 && i/st<=x[st] )
d[0][i]=i/st;
else
d[0][i]=INF;
if(d[0][i]!=INF)
nr=i;
}
int mid=(st+dr)/2;
for(i=1;i<=m;i++){
d[1][i]=INF;
}
for(i=st+1;i<=dr;i++){
if(x[i]){
for(k=0;k<i;k++){
q.clear();
for(j=k;j<=m;j+=i){
while(!q.empty()&&d[0][j]<d[0][ q.back() ]+( j - q.back() ) /i){
q.pop_back();
}
q.push_back(j);
while( (j-q.front())/i > x[i] && !q.empty() ){
q.pop_front();
}
d[1][j]=minim(INF,d[0][q.front()]+(j-q.front())/i);
if(i<=mid)
t[1][j]=j;
else
t[1][j]=t[0][ q.front() ];
if(d[1][j]!=INF && j>nr)
nr=j;
}
}
for(k=0;k<=m;k++){
d[0][k]=d[1][k];
d[1][k]=INF;
t[0][k]=t[1][k];
}
}
}
if(st==1&&dr==200)
fprintf(g,"%d %d\n",nr,d[0][nr]);
int a=t[0][nr];
rez(st,mid,a);
rez(mid+1,dr,nr-a);
}
int main(){
f=fopen("ghiozdan.in","r");
g=fopen("ghiozdan.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++){
fscanf(f,"%d",&v[i]);
x[ v[i] ]++;
}
rez(1,200,m);
fclose(f);
fclose(g);
return 0;
}