Submission #689682

#TimeUsernameProblemLanguageResultExecution timeMemory
689682zeroesandonesDischarging (NOI20_discharging)C++17
9 / 100
1087 ms23740 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector<ll> vi; typedef pair<ll, ll> pi; #define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i) #define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i) #define nl "\n" #define sp " " #define all(x) (x).begin(), (x).end() #define sc second #define fr first #define pb emplace_back // Binary Search, maybe void solve() { ll n; cin >> n; ll t[n + 1]; FOR(i, 1, n + 1) cin >> t[i]; pi dp[n + 1] = {}; // dp[i].fr = minimum time taken for the first i people // dp[i].sc = cumulative time taken per group for the first i people ll inf = 1e15; fill(dp, dp + n + 1, make_pair(inf, inf)); dp[1] = {t[1], t[1]}; dp[0] = {0, 0}; FOR(i, 2, n + 1) { ll mx = 0; FORD(j, i, 1) { // [j .. i] is one group mx = max(mx, t[j]); pi curr; ll len = i - j + 1; curr.sc = mx + dp[j - 1].sc; curr.fr = len * (curr.sc) + dp[j - 1].fr; dp[i] = min(dp[i], curr); } } cout << dp[n].fr << nl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; // cin >> t; while (t--) { solve(); } }
#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...