Submission #4669776

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;

const int N = 5228;
ll f[N][N];
int p[N];

const ll INF = (1ll << 60);

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif  
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    int n;
    ll a, b;
    cin >> n >> a >> b;

    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }

    p[n] = n;

    for (int i = 0; i <= n + 1; ++i) {
        fill(f[i], f[i] + n + 1, INF);
    }

    f[0][0] = 0;
   
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            ll cf = f[i][j];
            if (p[i] >= j) {
                f[i + 1][p[i]] = min(f[i + 1][p[i]], cf);
                f[i + 1][j] = min(f[i + 1][j], cf + a);
            } else {
                f[i + 1][j] = min(f[i + 1][j], cf + b);
            }
        }
    }

    cout << f[n + 1][n] << "\n";
}

Submission Info

Judge Result