제출 #689711

#제출 시각아이디문제언어결과실행 시간메모리
689711true22Discharging (NOI20_discharging)C++14
9 / 100
1086 ms23772 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; struct dt{ ll cost, li, wt; dt(){ cost = li = wt = inf; } void print(){ cout << cost << ' ' << li << ' ' << wt << nl; } }; ll n; vl t; /* Idea: - The state: - dp[i] = {cost, last index, waiting time}; Terms: - cost = best minimum ans till i - last index = the beginning of the segment - waiting time = waiting time of the person i Base cases: - dp[1] = {t[1], 1, t[1]}; Reccurence: dp[i].fr = min(dp[j].fr + cost(j + 1 to i), dp[i].fr) cost(j + 1 to i): (mx[j + 1, i] + dp[j].waiting) * (i - j) */ void solve(){ vector<pl> dp; dp.resize(n + 1, {inf, inf}); //dp[0] = {0, 0, 0}; dp[0] = {0, 0}; dp[1] = {t[1], t[1]}; fur(i, 2, n){ fur(j, 0, i - 1){ // i -> i - 1 ll mx = -1; fur(p, j + 1, i) mx = max(mx, t[p]); ll cost = (mx + dp[j].sc) * (i - j); if (dp[j].fr + cost < dp[i].fr){ dp[i].fr = dp[j].fr + cost; dp[i].sc = dp[j].sc + mx; } // if (dp[j].fr + cost == dp[i].fr){ // dp[i].sc = min(dp[i].sc, dp[j].sc + mx); // // if (dp[i].sc == dp[j].sc + mx) // } } } cout << dp[n].fr << 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]; 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...