Submission #1181913

#TimeUsernameProblemLanguageResultExecution timeMemory
1181913mehmetkaganDischarging (NOI20_discharging)C++20
0 / 100
73 ms40184 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll const int INF = 1e18; // A large value to represent infinity struct Segment { int index; ll best_val; int chargingTime; }; int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<int> T(N); for (int i = 0; i < N; i++) { cin >> T[i]; } vector<ll> dp(N + 1, INF); dp[0] = 0; stack<Segment> st; for (int i = 1; i <= N; i++) { ll m = T[i - 1]; dp[i] = dp[i - 1] + T[i - 1]; while (!st.empty() && st.top().chargingTime <= T[i - 1]) { Segment seg = st.top(); st.pop(); m = T[i - 1]; dp[i] = min(dp[i], seg.best_val + i * m); } Segment newSeg = {i, dp[i] - i * T[i - 1], T[i - 1]}; st.push(newSeg); } cout << dp[N] << '\n'; 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...