Submission #697486

#	Time	Username	Problem	Language	Result	Execution time	Memory
697486		hct_2so1	Discharging (NOI20_discharging)	C++14	36 / 100	1097 ms	8532 KiB

Discharging

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define all(v) (v).begin(), (v).end()
#define F first
#define S second
#define __builtin_popcount __builtin_popcountll
#define sz(v) ((int) (v).size())
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define pii(a, b) make_pair(a, b)

using namespace std;
typedef long long ll;

///

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 1e18 + 7;

const int N = 1e6 + 5;

int n, a[N], nxt[N];
ll dp[N];


void Input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    nxt[1] = 1;
    for (int i = 2; i <= n; i ++)
        if (a[nxt[i - 1]] < a[i]) nxt[i] = i;
        else nxt[i] = nxt[i - 1];
}

void solve()
{
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = 1LL * n * a[nxt[i]];
        for (int j = 1; j < i; j ++)
            dp[i] = min(dp[i], dp[j] + 1LL * (n - j) * a[nxt[i]]);
    }
    cout << dp[n];
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("DIAMOND.inp", "r", stdin);
//    freopen("DIAMOND.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test--)
    {
        Input();
        solve();
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 14 / 14
• Subtask 6: 0 / 28