Pagini recente » Cod sursa (job #1365437) | Cod sursa (job #826337) | Cod sursa (job #2082683) | Cod sursa (job #955580) | Cod sursa (job #779265)
Cod sursa(job #779265)
#include<stdio.h>
#define maxg 200
#define maxG 75005
#define b 50
using namespace std;
FILE*f=fopen("ghiozdan.in","r");
FILE*g=fopen("ghiozdan.out","w");
int n,G;
int fr[maxg+1],A[maxG],B[maxG],T[b][maxG+1];
int front[maxg+1],back[maxg+1],deq[maxG+maxg+1];
const int inf = 1<<29;
inline void dinamica ( int lim ){
for ( int i = 1 ; i <= G ; ++i ){
A[i] = inf;
}
int last_line = 0;
for ( int i = 1 ; i <= lim ; ++i ){
int line = last_line+1; if ( line == b ) line = 0;
last_line = line;
for ( int j = 0 ; j < i ; ++j ){
int pos = (G/i+1)*j + 1;
front[j] = back[j] = pos;
deq[pos] = j;
}
for ( int j = 0 ; j <= G ; ++j ){
B[j] = A[j];
T[line][j] = j;
}
if ( !fr[i] ) continue ;
int last = i-1;
for ( int j = i ; j <= G ; ++j ){
int list = last+1; if ( list == i ) list = 0;
int pos = deq[front[list]];
last = list;
if ( (j-pos)/i > fr[i] ){
++front[list];
pos = deq[front[list]];
}
if ( A[pos] + (j-pos)/i < B[j] ){
B[j] = A[pos] + (j-pos)/i;
T[line][j] = pos;
}
while ( front[list] <= back[list] ){
int pos = deq[back[list]];
if ( A[pos]+(j-pos)/i > A[j] ){
--back[list];
}
else{
break ;
}
}
deq[++back[list]] = j;
}
for ( int j = 0 ; j <= G ; ++j ){
A[j] = B[j];
}
}
}
int main () {
fscanf(f,"%d %d",&n,&G);
int x;
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%d",&x);
++fr[x];
}
dinamica(200);
int sol;
for ( int i = G ; i >= 0 ; --i ){
if ( A[i] != inf ){
fprintf(g,"%d %d\n",i,A[i]);
sol = i;
break ;
}
}
if ( G <= 50000 ){
int lim = 199;
for ( int i = 200 ; i >= 200 ; --i ){
for ( int j = sol - T[i%b][sol] ; j > 0 ; j -= i ){
fprintf(g,"%d\n",i);
}
sol = T[i%b][sol];
}
while ( lim > 0 ){
dinamica(lim);
for ( int i = lim ; i >= lim-b && i >= 0 ; --i ){
for ( int j = sol - T[i%b][sol] ; j > 0 ; j -= i ){
fprintf(g,"%d\n",i);
}
sol = T[i%b][sol];
}
lim -= b;
}
}
fclose(f);
fclose(g);
return 0;
}