이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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, 1, 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;
}
}
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |