oj.uz

Submission #852315

# Submission time Handle Problem Language Result Execution time Memory
852315 2023-09-21T15:06:29 Z iulia_morariu Growing Vegetables is Fun 4 (JOI21_ho_t1) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
    cin.tie(0);ios::sync_with_stdio(0);

    //1.
    int n = 0;

    //2.
    cin >> n;
    int v[n];

    //3.
    for(int i = 0; i < n; i++) cin >> v[i];
    int spd[n];
    int sps[n];

    spd[0] = v[0];
    sps[n - 1] = v[n - 1];

    for(int i = 1; i < n; i++){
        spd[i] = max(spd[i - 1] + 1, v[i]);
        sps[n - i - 1] = max(sps[n - i] + 1, v[n - i - 1]);
    }



    for(int i = 0; i < n; i++){
        spd[i] = spd[i] - v[i];
        sps[n - i - 1] = sps[n - i - 1] - v[n - i - 1];
    }

    //cout << "spd : ";
    //for(int i = 0; i < n; i++) cout << spd[i] << " ";
    //cout << endl;

    //cout << "sps : ";
    //for(int i = 0; i < n; i++) cout << sps[i] << " ";
    //cout << endl;

    int cd[n], cs[n];

    cd[0] = spd[0];
    cs[n - 1] = sps[n - 1];

    for(int i = 1; i < n; i++){
        cd[i] = cd[i - 1] + max(0ll, spd[i] - spd[i - 1]);
        cs[n - i - 1] = cs[n - i] + max(0ll, sps[n - i - 1] - sps[n - i]);
    }

    //cout << "cnterele dreapta : ";
    //for(int i = 0; i < n; i++) cout << cd[i] << " ";
    //cout << endl;

    //cout << "cnterele stanga : ";
    //for(int i = 0; i < n; i++) cout << cs[i] << " ";
    //cout << endl;

    int mini = INT_MAX;
    for(int i = 0; i < n; i++){
        //cout << "Presupunem ca facem varful la pozitia " << i << endl;
        int sum = 0;
        if(i > 0) sum += cd[i - 1];
        if(i + 1 < n) sum += cs[i + 1];

        int cf = v[i]; // nr care il punem pe poz i
        if(i > 0) cf = max(cf, v[i - 1] + spd[i - 1] + 1);
        if(i + 1 < n) cf = max(cf, v[i + 1] + sps[i + 1] + 1);

        //cout << "  -- > Punem pe pozitia " << i << "  " << cf << endl;
        //cout << "  -- > Normal avem " << sum << " op de facut" << endl;

        if(i > 0) sum += max(0ll, ( cf - v[i] ) - spd[i - 1] );
        if(i + 1 < n) sum += max(0ll, sps[i + 1] - (cf - v[i]) );
        if(i == 0 || i == n - 1) sum += cf - v[i];

        //cout << "  -- > Nr de op totale : " << sum << endl;

        mini = min(mini, sum);
    }

    cout  << mini << endl;

    return 0;
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -