Submission #15180

#	Time	Username	Problem	Language	Result	Execution time	Memory
15180		wad	달리는 게임 (kriii3_E)	C++98	0 / 70	12 ms	9532 KiB

E

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <string.h>
#include <functional>
#include <list>
#include <set>
#include <map>
#include <stdio.h>
#include <math.h>
typedef long long ll;
using namespace std;
/*
int bear[200001];
int maxv[200001];
int main()
{
	int n; cin >> n;
	memset(maxv, 0, sizeof(maxv));
	for (int i = 0; i < n; i++)
	{
		int t; scanf("%d", &t);
		bear[i] = t;
		maxv[0] = max(maxv[0], t);
	}
	int idx = 1;
	for (int i = n - 1; i > 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			bear[j] = min(bear[j], bear[j + 1]);
			maxv[idx] = max(maxv[idx], bear[j]);
		}
		idx++;
	}
	for (int i = 0; i < n; i++)
	{
		cout << maxv[i] << " ";
	}

	return 0;
}
*/
/*
//CF_Round_300.Quasi Binary
int cache[1000000];
vector<int> bv;
void makeBinary(vector<int>& v,int n,int sum)
{
	if (n == -1)
	{
		if (sum!=0)
			v.push_back(sum);
		return;
	}
	makeBinary(v, n - 1, sum);
	makeBinary(v, n - 1, sum + (int)pow(10.0, (double)n));
}
//이번 함수는 정수가 주어지면 최소 몇번이 필요한지 계산한다.
int countFunc(int n)
{
	if (n == 0)
		return 0;
	int& ret = cache[n];
	if (ret != -1)
		return ret;
	ret = 987654321;
	for (int i = 0; i < bv.size(); i++)
	{
		if (bv[i] > n)
			break;
		ret = min(ret, countFunc(n - bv[i]) + 1);
	}
	return ret;
}
//reconstruct는 countFunc를 역추적한다.
void reconstruct(vector<int>& v,int n)
{
	if (n == 0)
		return;
	for (int i = 0; i < bv.size(); i++)
	{
		if (countFunc(n) == countFunc(n - bv[i]) + 1)
		{
			v.push_back(bv[i]);
			reconstruct(v, n - bv[i]);
			return;
		}
	}
}
int main()
{
	memset(cache, -1, sizeof(cache));
	makeBinary(bv, 6, 0);
	sort(bv.begin(), bv.end());
	int k; cin >> k;
	if (k == 1000000)
	{
		cout << "1" << endl;
		cout << "1000000";
		return 0;
	}
	cout << countFunc(k) << endl;
	vector<int> lv;
	reconstruct(lv, k);
	for (int i = 0; i < lv.size(); i++)
	{
		cout << lv[i] << " ";
	}
	return 0;
}
*/
/*
//R_303_Div2_C.WoodCutters
int n;
vector<ll> vx;
vector<ll> vh;
int maxTree(ll lb, int idx) //lb means left boundary and idx means index
{
	ll curX = vx[idx];
	ll curH = vh[idx];
	if (idx == n - 1)
		return 1;
	if (lb < curX - curH)
		return maxTree(curX, idx + 1) + 1;
	else if (vx[idx + 1] > curX + curH)
		return maxTree(curX + curH, idx + 1) + 1;
	else
		return maxTree(curX, idx + 1);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t1, t2; cin >> t1 >> t2;
		vx.push_back(t1);
		vh.push_back(t2);
	}
	cout << maxTree(-1000000001, 0);
	return 0;
}
*/
//298_Div2_B.Covered Path
/*
int v1, v2, t, d;
int main()
{
	cin >> v1 >> v2;
	cin >> t >> d;
	int sum = v1;
	int cur = v1;
	for (int i = 0; i < t - 1; i++)
	{
		for (int j = d; j >= -d; j--)
		{
			if (cur + j - (t-2 - i) * d <= v2)
			{
				cur = cur + j;
				break;
			}
		}
		sum += cur;
	}
	cout << sum;
	return 0;
}
*/

//277.5_Div2_C.Given Length and Sum of Digits
/*
int main()
{
	int m, s; cin >> m >> s;
	int minv[100];
	int maxv[100];
	if (s == 0)
	{
		if (m == 1)
			cout << "0 0" << endl;
		else
			cout << "-1 -1" << endl;
		return 0;
	}
	int first = -1;
	for (int i = 1; i <= 9; i++)
	{
		if (i + (m - 1) * 9 >= s)
		{
			first = i;
			break;
		}
	}
	if (first == -1)
	{
		cout << "-1 -1"; return 0;
	}
	minv[0] = first; int curSum = first;
	for (int i = 1; i < m; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j + (m - i - 1) * 9 >= s-curSum)
			{
				curSum += j;
				minv[i] = j;
				break;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		cout << minv[i];
	}
	int second = -1;
	for (int i = 9; i >= 1; i--)
	{
		if (i <= s){
			second = i;
			break;
		}
	}
	maxv[0] = second; int curSum2 = second;
	for (int i = 1; i < m; i++)
	{
		for (int j = 9; j >= 0; j--)
		{
			if (j <= s - curSum2)
			{
				curSum2 += j;
				maxv[i] = j;
				break;
			}
		}
	}
	cout << " ";
	for (int i = 0; i < m; i++)
	{
		cout << maxv[i];
	}
	return 0;
}
*/

//272_Div2_B.Dreamoon and Wifi
/*
string s1; string s2;
int l; int a;
int countMethod(int idx,int sum)
{
	if (idx == l)
	{
		if (sum == a)
			return 1;
		else
			return 0;
	}
	if (s2[idx] == '+')
		return countMethod(idx + 1, sum + 1);
	else if (s2[idx] == '-')
		return countMethod(idx + 1, sum - 1);
	else
	{
		return countMethod(idx + 1, sum + 1) + countMethod(idx + 1, sum - 1);
	}
}
int main()
{
	cin >> s1 >> s2;
	l = s1.length();
	a = 0;
	for (int i = 0; i < l; i++)
	{
		if (s1[i] == '+')
			a++;
		else
			a--;
	}
	int ret = countMethod(0, 0);
	int m = 0;
	for (int i = 0; i < l; i++)
	{
		if (s2[i] == '?')
			m++;
	}
	double mm = pow(2.0, (double)m);
	printf("%.14f", (double)ret / mm);
	return 0;
}
*/
int n;
ll cache[1000][1000];
int l[1000];
int pack(int idx, int q)
{
	if (idx == n)
		return 0;
	ll& ret = cache[idx][q];
	if (ret != -1)
		return ret;
	ret = max(pack(idx + 1, q), pack(idx + 1, q + 1) + (q + 1) * l[idx]);
	return ret;
}
int main()
{
	cin >> n;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < n; i++)
	{
		cin >> l[i];
	}
	cout<<pack(0, 0);
	return 0;
}

• Subtask 1: 0 / 26
• Subtask 2: 0 / 44