Submission #852315

#	Time	Username	Problem	Language	Result	Execution time	Memory
852315		iulia_morariu	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	0 ms	348 KiB

Main

#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
• Subtask 2: 0 / 60