Submission #689707

#	Time	Username	Problem	Language	Result	Execution time	Memory
689707		true22	Discharging (NOI20_discharging)	C++14	9 / 100	1093 ms	23768 KiB

Discharging

#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);
     //       cout << "cost = " << cost << nl;
            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);
            }
        }
    }
    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;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28