oj.uz

답안 #88577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88577 2018-12-06T17:52:17 Z aminra Akcija (COCI15_akcija) C++14
80 / 80
 24 ms 3836 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)5e5 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
ll n, a[MAXN], dp[MAXN], p[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	p[0] = a[0];
	for (int i = 1; i < n; i++)
		p[i] = p[i - 1] + a[i];
	
	
	dp[n - 1] = a[n - 1];
	if(n != 1)
		dp[n - 2] = a[n - 2] + a[n - 1];
	ll mn = p[n - 1];
	if(n >= 3)
		mn -= a[n - 3];
	for (int i = n - 3; i >= 0; i--)
	{
		dp[i] = mn;
		if(i)
			dp[i] -= p[i - 1];
		if(i)
		mn = min(mn, dp[i + 2] + p[i + 1] - a[i - 1]);
	}
	cout << dp[0];
}

Subtask #1
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 18 ms 3372 KB Output is correct
7 Correct 13 ms 3712 KB Output is correct
8 Correct 13 ms 3756 KB Output is correct
9 Correct 22 ms 3756 KB Output is correct
10 Correct 24 ms 3836 KB Output is correct