oj.uz

답안 #544645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544645 2022-04-02T14:11:27 Z pokmui9909 전봇대 (KOI13_pole) C++17
100 / 100
 21 ms 2056 KB 
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <climits>
#include <set>
#include <map>
#include <cassert>
#include <cmath>
using namespace std;

using ll = long long;

ll n;
ll ar[100005];

ll f(ll d)
{
	ll ans = 0;
	for (ll i = 0; i < n; i++)
		ans += abs(d * i - ar[i]);
	return ans;
}

signed main()
{
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> ar[i];
	ll l = 0, r = ar[n - 1];
	while (r - l >= 3)
	{
		ll p = (l * 2 + r) / 3, q = (l + r * 2) / 3;
		if (f(p) <= f(q)) r = q;
		else l = p;
	}
	ll ans = 1e15;
	for (int i = l; i <= r; i++) ans = min(ans, f(i));
	cout << ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2004 KB Output is correct
2 Correct 20 ms 1924 KB Output is correct
3 Correct 21 ms 2056 KB Output is correct
4 Correct 20 ms 1876 KB Output is correct
5 Correct 20 ms 1940 KB Output is correct
6 Correct 18 ms 1856 KB Output is correct