#include #include #include #include #include #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) //#define CALC_TIME #if defined(CALC_TIME) static void show_timediff(struct timespec *start, struct timespec *end, const char *msg){ if (start->tv_nsec > end->tv_nsec){ end->tv_sec--; end->tv_nsec = end->tv_nsec + 1000*1000*1000; } printf("[%s] %2ld.%06ld sec\n", msg, end->tv_sec - start->tv_sec, (end->tv_nsec - start->tv_nsec)/1000); } #endif static int my_atoi(char *p){ int result = 0; char tmp; while (1){ tmp = *p; if (tmp >= '0' && tmp <= '9'){ result = 10*result + (tmp-'0'); p++; } else { break; } } return result; } int max_N; int max_D; int num_for_price[1000001]; int prev_price_for_price[1000001]; char big_buffer[64*1024+1]; int g_cur_buf_pos; #define BIG_BUFFER_SIZE (sizeof(big_buffer)-1) static char *my_fill_first(){ fread (big_buffer, 1, BIG_BUFFER_SIZE, stdin); return &big_buffer[0]; } static int my_read_one(){ char *p; char tmp; int result = 0; int cur_buf_pos = g_cur_buf_pos; p = &big_buffer[0]; retry: result = 0; while (cur_buf_pos < BIG_BUFFER_SIZE){ tmp = p[cur_buf_pos]; if (tmp >= '0' && tmp <= '9'){ result = 10*result + (tmp-'0'); cur_buf_pos++; } else { g_cur_buf_pos = cur_buf_pos + 1; return result; } } /* we reached the end of buffer, */ cur_buf_pos = g_cur_buf_pos; memcpy (p, p+cur_buf_pos, BIG_BUFFER_SIZE-cur_buf_pos); fread (p+BIG_BUFFER_SIZE-cur_buf_pos, 1, cur_buf_pos, stdin); cur_buf_pos = 0; goto retry; } static void parse_and_get_maxnum(){ char *buf; char *p; buf = my_fill_first(); p = strchr(buf, ' '); max_N = my_atoi(buf); max_D = my_atoi(p+1); g_cur_buf_pos = strchr(p+1, '\n') - &big_buffer[0] + 1; return; } static void parse_and_get_array(){ int i, p, tmp; for( i=max_N; i>0; i--){ tmp = my_read_one(); num_for_price[tmp]++; } p = 0; for( i=0; likely(i<=sizeof(prev_price_for_price)/sizeof(prev_price_for_price[0]) - 1); i++) { if (unlikely(num_for_price[i])){ p = i; } prev_price_for_price[i] = p; } } static int calc_campaign_one(int target){ int i; int max_price = 0; int tmp_prev_price_for_price; // int tmp_min_end_price = target - prev_price_for_price[target]; int tmp_min_end_price = 10; #if 1 for( i=prev_price_for_price[(target+1)/2]; likely(i>=tmp_min_end_price); i=prev_price_for_price[i-1]){ __builtin_prefetch(&prev_price_for_price[i-1]); tmp_prev_price_for_price = prev_price_for_price[target-i]; if (unlikely(max_price < i + tmp_prev_price_for_price) && (i != tmp_prev_price_for_price || num_for_price[i] >1)){ max_price = i + tmp_prev_price_for_price; if (unlikely(max_price >= target)){ break; } } } #else /* loop unrolling 4 */ int tmp_prev_price_for_price2, tmp_prev_price_for_price3, tmp_prev_price_for_price4; for( i=prev_price_for_price[(target+1)/2]; likely(i>=tmp_min_end_price); i=prev_price_for_price[i-1]){ __builtin_prefetch(&prev_price_for_price[i-1]); tmp_prev_price_for_price = prev_price_for_price[target-i]; if (unlikely(max_price < i + tmp_prev_price_for_price) && (i != tmp_prev_price_for_price || num_for_price[i] >1)){ max_price = i + tmp_prev_price_for_price; if (max_price >= target){ break; } } i = prev_price_for_price[i-1]; if (unlikely(i1)){ max_price = i + tmp_prev_price_for_price2; if (max_price >= target){ break; } } i = prev_price_for_price[i-1]; if (unlikely(i1)){ max_price = i + tmp_prev_price_for_price3; if (max_price >= target){ break; } } i = prev_price_for_price[i-1]; if (unlikely(i1)){ max_price = i + tmp_prev_price_for_price4; if (max_price >= target){ break; } } } #endif return max_price; } static void calc_campaign(){ int i, target,result; for( i=max_D; i>0; i--){ target = my_read_one(); result = calc_campaign_one(target); printf("%d\n", result); } } int main(int argc, char* argv[]){ #if defined(CALC_TIME) struct timespec start, end; #endif #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &start); #endif parse_and_get_maxnum(); #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &end); show_timediff (&start, &end, "1"); #endif #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &start); #endif parse_and_get_array(); #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &end); show_timediff (&start, &end, "2"); #endif #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &start); #endif calc_campaign(); #if defined(CALC_TIME) clock_gettime(CLOCK_REALTIME, &end); show_timediff (&start, &end, "3"); #endif return 0; }