Submission #2766423


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n;
ll a[1000005];
ll Abs(ll x){
	return x > 0 ? x : -x;
}
ll check(ll x){
	ll ret = 0;
	for(int i = 1; i <= n; i ++){
		ret = ret + Abs(a[i] - x - i);
	}
	return ret;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%lld", &a[i]);
	}
	ll ans = 1e18;
	ll L = -1e9, R = 1e9;
	while(R - L >= 3){
		ll m1 = (L + L + R) / 3;
		ll m2 = (R + L + R) / 3;
		if(check(m1) < check(m2)){
			R = m2;
		} else L = m1;
	}
	for(ll i = L; i <= R; i ++){
		ans = min(ans, check(i));
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task C - Linear Approximation
User falundafa
Language C++14 (GCC 5.4.1)
Score 300
Code Size 635 Byte
Status AC
Exec Time 46 ms
Memory 1792 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:18:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:20:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 4
AC × 19
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 9 ms 512 KB
subtask_1_03.txt AC 8 ms 512 KB
subtask_1_04.txt AC 23 ms 1024 KB
subtask_1_05.txt AC 40 ms 1536 KB
subtask_1_06.txt AC 44 ms 1792 KB
subtask_1_07.txt AC 46 ms 1792 KB
subtask_1_08.txt AC 46 ms 1792 KB
subtask_1_09.txt AC 46 ms 1792 KB
subtask_1_10.txt AC 45 ms 1792 KB
subtask_1_11.txt AC 45 ms 1792 KB