#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[1001][1001];
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];
}
for (int i = n; i >= 0; i--)
{
for (int j = n ; j >= 0; j--)
{
if (i == n) cache[i][j] = 0;
else
{
cache[i][j] = max(cache[i + 1][j], cache[i + 1][j + 1] + (j + 1)*l[i]);
}
}
}
cout<<cache[0][0]<<endl;
return 0;
}
/*
int arrayN[65600];
int arrayK[65600];
int visited[65600];
int count1(int n)
{
if (n == 0)
return 0;
return count1(n / 2) + n % 2;
}
void f
int main()
{
memset(visited, -1, sizeof(visited));
int n, k; cin >> n >> k;
int size = (int)pow(2.0, (double)n);
int sum = 0;
for (int i = 0; i < size; i++)
{
arrayN[i] = count1(i);
sum += arrayN[i];
}
int size2 = (int)pow(2.0, (double)k);
int gaesu = size / size2;
int each = sum / size2;
for (int i = 0; i < size; i++)
{
if (visited[i] == -1)
find1(i);
}
return 0;
}
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
9552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
