제출 #690853

#제출 시각아이디문제언어결과실행 시간메모리
690853true22Discharging (NOI20_discharging)C++14
36 / 100
1025 ms35392 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<ll, ll> pl; typedef vector<ll> vl; typedef vector<pl> vp; #define nl "\n" #define fr first #define sc second #define pb push_back #define all(x) x.begin(), x.end() #define fur(i, a, b) for(ll i = a; i <= b; ++i) #define ruf(i, a, b) for(ll i = a; i >= b; --i) #define pv(x) for(auto k : x){cout << k << " ";} cout << nl const ll inf = 1e17; ll n, sz; vl t, st; ll maxr(ll l, ll r, ll k, ll kl, ll kr){ if (kl > r || kr < l) return 0; if (kl >= l && kr <= r) return st[k]; ll m = (kl + kr)/2; return max(maxr(l, r, 2*k, kl, m), maxr(l, r, 2*k + 1, m + 1, kr)); } void printst(){ ll idx = 1; ll t = log2(2*sz); fur(i, 0, t){ fur(j, 1, 1<<i) cout << st[idx++] << ' '; cout << nl; } } void solve(){ //cout << "n = " << n << nl; ll dp[n + 1]; dp[0] = 0; //dp[1] = t[1]; fur(x, 1, n){ dp[x] = inf; ruf(i, x, 1){ ll mx = maxr(i, x, 1, 1, sz); //cout << "max in " << i << ' ' << x << " is :" << mx << nl; dp[x] = min(dp[x], dp[i - 1] + (mx * (n - i + 1))); } } cout << dp[n] << nl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; t.resize(n + 1); t[0] = 0; fur(i, 1, n) cin >> t[i]; sz = n; while(__builtin_popcountll(sz) != 1) sz++; st.resize(2*sz, 0); fur(i, 0, n - 1) st[i + sz] = t[i + 1]; ruf(i, sz - 1, 1) st[i] = max(st[2 * i], st[2*i + 1]); //printst(); //cout << maxr(1, 3, 1, 1, sz) << nl; solve(); return 0; }
#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...