Submission #1037785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037785		RiverFlow	Real Mountains (CCO23_day1problem2)	C++14	6 / 25	5025 ms	27028 KiB

Main

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)1e6 + 9;
const int mod = (int)1e6 + 3;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};


int n, dest[N], a[N], L[N], R[N];

long long dpL[N], dpR[N];

const long long INF = (long long)1e16;

namespace SUB1{
    vector<int> qr[107];

    void sol() {
        long long ans=0;
        FOR(i, 1, n) if (a[i]!=dest[i]){
            qr[a[i]].push_back(i);
        }
//        FOR(i, 1, n) cout << dest[i] << ' '; cout << nl;

        FOR(i, 1, 99) if (sz(qr[i])) {
            ans += 1LL * i * sz(qr[i]);
            auto g = qr[i];
            sort(all(g));
//            cout << i << ": ";
//            for(int j : g) cout << j << ' '; cout << nl;

            set<int> s;
            int lst=0;
            int idx=0;
            for(int i:g){
                while(lst+1<i){
                    ++lst;
                    s.insert(a[lst]);
                }
                L[idx++]=*s.upper_bound(a[i]);
            }
            s.clear();
            reverse(all(g));
            idx=sz(g)-1;
            lst=n+1;
            for(int i:g){
                while(lst-1>i){
                    --lst;
                    s.insert(a[lst]);
                }
                R[idx--]=*s.upper_bound(a[i]);
            }
            reverse(all(g));

            int m = sz(g);

            if (m == 1) {
                int p=g[0];
                ans+=L[0]+R[0];
                ++a[p];
                if (a[p]!=dest[p]){
                    qr[i+1].push_back(p);
                }
//                cout << "ans: " << ans << nl;

                continue;
            }

            long long h = i;
            dpL[0] = L[0] + (i + 1);
            for(int i = 1; i < m; ++i) {
                // tinh dpL[i]
                dpL[i] = dpL[i-1] + L[i] + (h + 1);
                for(int j = 0; j < i; ++j)
                    dpL[i] = min(dpL[i], (j>0?dpL[j-1]:0) + L[j]
                                  + (h+1) + (h * 2 + 2) * (i-j));
            }
//            if (h == 8) {
//                FOR(i, 0, m - 1) cerr << dpL[i] << ' '; cerr << nl;
//            }
            dpR[m - 1] = R[m - 1] + (i + 1);
            for(int i = m - 2; i >= 0; --i) {
                dpR[i] = dpR[i+1] + R[i] + (h + 1);
                for(int j = i + 1; j < m; ++j)
                    dpR[i] = min(dpR[i], (j<m-1?dpR[j+1]:0) + R[j]
                                    + (h+1) + (h * 2 + 2) * (j-i));
            }
            long long res=INF;
            FOR(i, 0, m - 1) {
                long long s = L[i] + R[i];
                // chi phi
                s += (i > 0 ? dpL[i-1] : 0);
                s += (i < m - 1 ? dpR[i + 1] : 0);
                res = min(res, s);
            }
            ans += res;
            for(int i : g) {
                ++a[i];
                if (a[i] != dest[i])
                    qr[h + 1].push_back(i);
            }
//                        cout << "ans: " << ans << nl;

        }
        cout << ans%mod;
    }
};

void main_code() {
    cin >> n;
    int mx = 0;
    int f=-1, l=-1;

    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] < mx) continue;
        if (a[i] > mx) {
            f=l=i; mx=a[i];
        } else {
            l=i;
        }
    }
    // (f..l) = mx
    // (1..f) tang dan
    // (f, n) giam dan
    for(int i = 1, mx = 0; i <= f; ++i) {
        mx=max(mx,a[i]);
        dest[i]=mx;
    }
    for(int i = n, mx = 0; i >= l; --i) {
        mx=max(mx,a[i]);
        dest[i]=mx;
    }
    FOR(i, f, l) dest[i] = mx;

    if (*max_element(a + 1, a + n + 1) <= 100) {
        return SUB1::sol(), void();
    }
}


/*     Let the river flows naturally     */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4