oj.uz

Submission #1037785

# Submission time Handle Problem Language Result Execution time Memory
1037785 2024-07-29T08:18:23 Z RiverFlow Real Mountains (CCO23_day1problem2) C++14
6 / 25
 5000 ms 27028 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct
35 Incorrect 1 ms 4444 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct
35 Incorrect 1 ms 4444 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct
35 Execution timed out 5025 ms 27028 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct
35 Incorrect 1 ms 4444 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 751 ms 12384 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 7 ms 10788 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2129 ms 12920 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 701 ms 12516 KB Output is correct
12 Correct 697 ms 12372 KB Output is correct
13 Correct 727 ms 12116 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 784 ms 12136 KB Output is correct
17 Correct 806 ms 12372 KB Output is correct
18 Correct 702 ms 12180 KB Output is correct
19 Correct 797 ms 12372 KB Output is correct
20 Correct 1981 ms 12884 KB Output is correct
21 Correct 2000 ms 13036 KB Output is correct
22 Correct 1933 ms 12956 KB Output is correct
23 Correct 738 ms 12372 KB Output is correct
24 Correct 737 ms 12372 KB Output is correct
25 Correct 729 ms 12372 KB Output is correct
26 Correct 645 ms 12112 KB Output is correct
27 Correct 727 ms 12116 KB Output is correct
28 Correct 684 ms 12376 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 10588 KB Output is correct
34 Correct 1 ms 8544 KB Output is correct
35 Incorrect 1 ms 4444 KB Output isn't correct
36 Halted 0 ms 0 KB -