oj.uz

Submission #86060

# Submission time Handle Problem Language Result Execution time Memory
86060 2018-11-24T11:16:08 Z kraljlavova1 Krov (COCI17_krov) C++11
56 / 140
 1500 ms 1700 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
const int MAXN=5010;
const llint inf=1e18;
int n;
int h[MAXN];
llint sol=inf;
llint f(int v,int idx){
	llint ret=0;
	for(int i=0;i<n;i++){
		int eh=v-abs(idx-i);
		ret+=abs(eh-h[i]);
	}
	return ret;
}
llint solve(int idx){
	int lo=max(idx+1,n-idx),hi=1e9,mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		llint f0=f(mid-1,idx);
		llint f1=f(mid,idx);
		llint f2=f(mid+1,idx);
		if(f0<=f1&&f1<=f2) hi=mid-1;
		else if(f0>=f1&&f1>=f2) lo=mid+1;
		else lo=hi=mid;
	}
	return f(lo,idx);
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	for(int i=0;i<n;i++){
		sol=min(sol,solve(i));
	}
	cout<<sol<<"\n";
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 376 KB Output is correct
2 Correct 269 ms 516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 628 KB Output is correct
2 Correct 280 ms 628 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 636 KB Output is correct
2 Correct 519 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 724 KB Output is correct
2 Correct 919 ms 856 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -