Submission #15839

#	Time	Username	Problem	Language	Result	Execution time	Memory
15839		jihoon	전봇대 (KOI13_pole)	C++98	100 / 100	32 ms	3816 KiB

pole

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

class su{
public:
	double gap;int gae;
	bool operator < (const su &ss) const{
		return gap < ss.gap;
	}
};

int n;
int wichi[100001];
long long int res[100001];
long long int mn=-1;
su midd[100001];
long long int whole;
long long int mid1,mid2;
double mi1,mi2;
int lb1,ub1,lb2,ub2;

long long int calc(int obj){
	long long int dap=0,gg=0;
	for(int i=1;i<n;i++){
		gg+=obj;
		dap+=abs(gg-wichi[i]);
	}
	//printf("%d %lld\n",obj,dap);
	return dap;
}

int main(){
	long long int cnt=0;
	scanf("%d",&n);
	scanf("%d",&wichi[0]);
	for(int i=1;i<n;i++){
		scanf("%d",&wichi[i]);
		midd[i-1].gap=wichi[i]/(double)i;
		midd[i-1].gae=i;
	}
	whole=(n-1);
	whole*=n;
	whole/=2;
	mid1=whole+1;mid1/=2;
	mid2=mid1+((whole%2)==0);
	sort(midd,midd+(n-1));
	for(int i=0;i<n-1;i++){
	//	printf("%f %d\n",midd[i].gap,midd[i].gae);
		if(cnt<mid1&&mid1<=cnt+midd[i].gae){
			mi1=midd[i].gap;
		}
		if(cnt<mid2&&mid2<=cnt+midd[i].gae){
			mi2=midd[i].gap;
			break;
		}
		cnt+=midd[i].gae;
	}
	lb1=(int)mi1;ub1=lb1+1;
	lb2=(int)mi2;ub2=lb2+1;
	printf("%lld",min(calc(lb1),min(calc(ub1),min(calc(lb2),calc(ub2)))));
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37