Submission #1147661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147661		ray1457	Discharging (NOI20_discharging)	C++20	22 / 100	1096 ms	15944 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x,end()

#define int ll

void solve() {
	int n;
	cin >> n;
	// subtask 1
	if (n <= 3) {
		if (n == 1) {
			int a;
			cin >> a;
			cout << a << endl;
		}
		if (n == 2) {
			int a,b;
			cin >> a >> b;
			cout << min(
				2*a + b,
				max(a,b) * 2
				) << endl;
		}
		if (n == 3) {
			int a,b,c;
			cin >> a >> b >> c;
			cout << min(
				3*a + 2*b + c,
				min(
					max(a,b) *3 + c,
					min(
						3*a + max(b,c)*2,
						max(a,max(b,c)) * 3
						)
					)
				) << endl;
		}
		return;
	}
	vi a(n+1);
	for (int i = 1; i<=n; i++) cin >> a[i];
	const int INF = 1e18;
	vi dp(n + 1, INF);

	dp[0] = 0;
	for (int i = 1; i<=n; i++) {
		for (int j = 1; j<=i; j++) {
			dp[i] = min(dp[i], dp[j-1] + a[i] * (n - j + 1));
		}
	} 

	for(int i = 1; i <= n; i++){
        for(int j = i; j >= 1; --j){
            dp[i] = min(dp[i], dp[j - 1] + (n - j + 1) * a[i]);
        }
    } 



	cout << dp[n] << endl;
	
}


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

	solve();
}

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