Submission #690680

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
690680	2023-01-30T10:54:39 Z	true22	Discharging (NOI20_discharging)	C++14	13 / 100	1000 ms	41920 KB

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, sz;
vl t, st;

ll maxr(ll l, ll r, ll k, ll kl, ll kr){
    if (kl > r || kr < l)
        return 0;
    if (kl >= l && kr <= r)
        return st[k];
    ll m = (kl + kr)/2;
    return max(maxr(l, r, 2 * k, kl, m), maxr(l, r, 2 *k + 1, m + 1, kr));
}


void solve(){
    //cout << "n = " << n << nl;
    ll dp[n + 1];
    dp[0] = 0;
    //dp[1] = t[1];

    fur(x, 1, n){

        dp[x] = inf;
        ruf(i, x, 1)
            dp[x] = min(dp[x], dp[i - 1] + (t[x] * (n - i + 1)));

    }
    cout << dp[n] << nl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // #ifndef ONLINE_JUDGE
    //     freopen("/home/compslab9/Desktop/Abhineet/cpp/input.txt", "r", stdin);
    //     freopen("/home/compslab9/Desktop/Abhineet/cpp/output.txt", "w", stdout);
    // #endif

    cin >> n;
    t.resize(n + 1);
    t[0] =  0;
    fur(i, 1, n)
        cin >> t[i];

    sz = n;
    while(__builtin_popcountll(sz) != 1)
        sz++;
    st.resize(2*sz, 0);
    fur(i, 0, n - 1)
        st[i + sz] = t[i + 1];
    ruf(i, sz - 1, 1)
        st[i] = max(st[2 * i], st[2*i + 1]);
    
    

    solve();

    return 0;
}

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Incorrect	1 ms	328 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	328 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	2 ms	328 KB	Output is correct
6	Correct	2 ms	324 KB	Output is correct
7	Correct	2 ms	324 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	2 ms	328 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	328 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	2 ms	328 KB	Output is correct
6	Correct	2 ms	324 KB	Output is correct
7	Correct	2 ms	324 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	2 ms	328 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Execution timed out	1072 ms	37312 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-