Submission #320482

#	Time	Username	Problem	Language	Result	Execution time	Memory
320482		egas	Discharging (NOI20_discharging)	C++14	47 / 100	234 ms	150496 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

template < typename T >

class SegmentTree {

private:

    T *Stree;

    T *Snum;

    long long n;

    T NullValue = 0;

    T combine(T a, T b) {

        return max(a,b);

    }

    void build(long long idx, long long s, long long e) {

        if (s > e)

            return;

        if (s == e) {

            Stree[idx] = Snum[s];

            return ;

        }

        long long m = ( s + e ) / 2;

        build( 2 * idx, s, m);

        build( 2 * idx + 1, m + 1, e);

        Stree[idx] = combine(Stree[2 * idx], Stree[2 * idx + 1] );

        return;

    }

    T queryUtil(long long idx, long long s, long long e, long long l, long long r) {

        if (l > e || r < s)

            return NullValue;

        if (s >= l && e <= r) {

            return Stree[idx];

        }

        long long m = ( s + e ) / 2;

        T left = queryUtil(2 * idx, s, m, l, r);

        T right = queryUtil(2 * idx + 1, m + 1, e, l, r);

        return combine(left, right );

    }

public:

    SegmentTree(vector<T> a) {

        this->n = a.size();

        Stree = new T[4 * n + 5];

        Snum = new T[n];

        for (long long i = 0; i < n; i++) {

            Snum[i] = a[i];

        }

        build(1, 0, n - 1);

    }

    T query(long long l, long long r) {

        return queryUtil(1, 0, n - 1, l - 1, r - 1);

    }

};

long long dp[2000][2000];

long long solve(long long idx,long long last,long long n,SegmentTree<long long> &ST) {

    if(idx>=n)return 0;

    if(dp[idx][last]!=-1) {

        return dp[idx][last];

    }

    if(last>=n) {

        dp[idx][last]=ST.query(idx+1,last+1)*(n-idx);

        return ST.query(idx+1,last+1)*(n-idx);

    }

    long long pos1 = ST.query(idx+1,last+1)*(n-idx) + solve(last+1,last+1,n,ST);

    long long pos2 = solve(idx,last+1,n,ST);

    dp[idx][last]=min(pos1,pos2);

    return min(pos1,pos2);

}

bool is_this_subtask4(vector<long long> a) {

    reverse(a.begin(),a.end());

    return is_sorted(a.begin(),a.end());

}

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    long long n;

    cin >> n;

    vector<long long> a(n);

    for(long long i = 0 ; i < n ; i++) {

        cin >> a[i];

    }

    if(is_this_subtask4(a)) {

        cout << a[0]*n << '\n';

        return 0;

    }

    SegmentTree<long long> ST(a);

    memset(dp,-1,sizeof dp);

    long long res = solve(0,0,n,ST);

    cout << res << '\n';

    return 0;

}

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