Submission #1236015

#TimeUsernameProblemLanguageResultExecution timeMemory
1236015hamanp87Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
0 ms328 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int inf=1e9,mod=1e9+7,neginf=-1e9; const double PI=acos(-1); void solve() { int n; cin>>n; vecl a(n+2); for(int i=1;i<=n;i++) cin>>a[i]; vecl b(n+2),d(n+2),rs1(n+2); b[0]=d[0]=rs1[0]=0; for(int i=1;i<=n;i++) { b[i]=max(b[i-1]+1,a[i]); d[i]=b[i]-a[i]; ll dif=d[i]-d[i-1]; rs1[i]=rs1[i-1]+max(dif,0LL); } vecl c(n+2),e(n+2),rs2(n+2); c[n+1]=e[n+1]=rs2[n+1]=0; for(int i=n;i>=1;i--) { c[i]=max(c[i+1]+1,a[i]); e[i]=c[i]-a[i]; ll dif=e[i]-e[i+1]; rs2[i]=rs2[i+1]+max(dif,0LL); } ll ans=min(rs2[1],rs1[n]); for(int i=1;i<n;i++) if(b[i]>c[i+1]) ans=min(ans,max(rs1[i],rs2[i+1])); cout<<ans<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...