Submission #817763

#	Time	Username	Problem	Language	Result	Execution time	Memory
817763		tset	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	28 ms	13188 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int INF = 1e18+42;

 
signed main()
{
    int N;
    scanf("%lld", &N);
    vector<int > v(N+1);
    
    for(int i=1; i<=N; i++)
    {
        scanf("%lld", &v[i]);
    }
    vector<int > vMinLeft(N+2, 0);
    vector<int > vMinRight(N+2, 0);
    vector<int > addLeft(N+2, 0);
    vector<int > addRight(N+2, 0);
    vector<int > cumulLeft(N+2, 0);
    vector<int > cumulRight(N+2, 0);
    //vMinLeft[0] = 0;
    //vMinRight[N+1] = 0;
    for(int i=1; i<= N; i++)
        vMinLeft[i] = max(vMinLeft[i-1] + 1, v[i]);
    for(int i=N; i>=1; i--)
       vMinRight[i] = max(vMinRight[i+1] + 1, v[i]);

    for(int i=1; i<= N; i++)
        addLeft[i] = vMinLeft[i]- v[i];
    for(int i=N; i>=1; i--)
        addRight[i] = vMinRight[i]- v[i];

    for(int i =1; i<= N; i++)
    {
        cumulLeft[i] = cumulLeft[i-1];
        if(addLeft[i] > addLeft[i-1])
        {
            cumulLeft[i] += addLeft[i] - addLeft[i-1];
        }
    }
    for(int i=N; i>= 1; i--)
    {
        cumulRight[i] = cumulRight[i+1];
        if(addRight[i] > addRight[i+1])
        {
            cumulRight[i] += addRight[i] - addRight[i+1];
        }
    }
    int ans = min(cumulLeft[N], cumulRight[1]);
        


    for(int i=1; i<= N; i++)
    {
        ans = min(ans, max(cumulLeft[i], cumulRight[i]));
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60