Drying
http://geocities.yahoo.co.jp/gl/nanagyou/view/20070129/1170065075
ACM/ICPCの対策をバリバリやっておられる方は結構感じてらっしゃるかもしれませんが、テストデータに大きな数が含まれている場合オーバーフローについては常に意識しておかねばなりません。
この手の解法は何度か目にした記憶があるのですが、単純に足し算を行っている部分でも扱う数値が大きいわけですから、正しいはずなのに通らない場合はオーバーフローを起こさないような大きいサイズのものを使うとか、計算の過程でキャストを有効に使うなどの気遣いが必要です。
#include<stdio.h> int i,k,m,l,r,v[100000]; long long t; main(n) { scanf("%d",&n); for(i=0;i<n;++i) { scanf("%d",v+i); v[i]>r?r=v[i]:0; } scanf("%d",&k); if(k!=1) for(;r-l>1;) { m=(l+r)/2; // ここは大丈夫 for(t=i=0;i<n;i++) if(v[i]>m) // 4バイト数だとここでオーバーフローの可能性アリ t+=(v[i]-m+(k-2))/(k-1); t>m?l:r=m; } printf("%d",r); }