oj.uz

Submission #15839

# Submission time Handle Problem Language Result Execution time Memory
15839 2015-07-30T15:27:45 Z jihoon 전봇대 (KOI13_pole) C++
100 / 100
 32 ms 3816 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3816 KB Output is correct
2 Correct 0 ms 3816 KB Output is correct
3 Correct 0 ms 3816 KB Output is correct
4 Correct 0 ms 3816 KB Output is correct
5 Correct 0 ms 3816 KB Output is correct
6 Correct 0 ms 3816 KB Output is correct
7 Correct 0 ms 3816 KB Output is correct
8 Correct 0 ms 3816 KB Output is correct
9 Correct 0 ms 3816 KB Output is correct
10 Correct 0 ms 3816 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3816 KB Output is correct
2 Correct 0 ms 3816 KB Output is correct
3 Correct 0 ms 3816 KB Output is correct
4 Correct 0 ms 3816 KB Output is correct
5 Correct 0 ms 3816 KB Output is correct
6 Correct 0 ms 3816 KB Output is correct
7 Correct 0 ms 3816 KB Output is correct
8 Correct 0 ms 3816 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3816 KB Output is correct
2 Correct 0 ms 3816 KB Output is correct
3 Correct 2 ms 3816 KB Output is correct
4 Correct 0 ms 3816 KB Output is correct
5 Correct 0 ms 3816 KB Output is correct
6 Correct 3 ms 3816 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3816 KB Output is correct
2 Correct 32 ms 3816 KB Output is correct
3 Correct 27 ms 3816 KB Output is correct
4 Correct 28 ms 3816 KB Output is correct
5 Correct 21 ms 3816 KB Output is correct
6 Correct 32 ms 3816 KB Output is correct