Submission #870845

#TimeUsernameProblemLanguageResultExecution timeMemory
870845pccDischarging (NOI20_discharging)C++14
20 / 100
88 ms10068 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> vector<pll> v; vector<pll> st; int n; ll total = 0; ll sum = 0; inline bool check(pll a,pll b){ ll ta = a.fs*a.sc+b.sc*(a.fs+b.fs); ll tb = b.fs*(a.sc+b.sc); if(ta>=tb)return true; else return false; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i = 0;i<n;i++){ int k; cin>>k; if(v.empty()||v.back().fs < k)v.push_back({k,1}); else v.back().sc++; } for(auto &i:v){ while(!st.empty()&&check(st.back(),i)){ total -= sum*st.back().sc; sum -= st.back().fs; i.sc+=st.back().sc; st.pop_back(); } sum += i.fs; total += sum*i.sc; st.push_back(i); } cout<<total; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...