Submission #697481

#	Time	Username	Problem	Language	Result	Execution time	Memory
697481		steveonalex	Discharging (NOI20_discharging)	C++14	47 / 100	428 ms	20428 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MOD 1000000007
#define INF 1000000000000000000

#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask) {return (mask) & (-mask);}
ll pop_cnt(ll mask) {return __builtin_popcountll(mask);}
ll ctz(ll mask) {return __builtin_ctzll(mask);}
ll clz(ll mask) {return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }

template <class T>
    void printArr(vector<T> &a, char separator = ' ', char finish = '\n'){
        for(long i = 0; i<a.size(); ++i) cout << a[i] << separator;
        cout << finish;
    }

long n;
vector<long> a(n+1);

ll sub4(){
    return 1LL * a[1] * n;
}

ll sub5(){
    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    for(long i = 1; i<=n; ++i){
        ll ma = 0;
        for(long j = i; j>=1; --j){
            maximize(ma, a[j]);
            minimize(dp[i], dp[j-1] + ma * (n - j + 1));
        }
    }

    return dp[n];
}

ll sub3(){
    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    for(long i = 1; i<=n; ++i){
        dp[i] = min(dp[0] + 1LL * n * a[i], dp[i-1] + 1LL * (n - i + 1) * a[i]);

        long l = 1, r = i;
        while(r - l > 300){
            long m1 = l + (r - l) / 3;
            long m2 = r - (r - l) / 3;
            ll val1 = dp[m1 - 1] + 1LL * (n - m1 + 1) * a[i];
            ll val2 = dp[m2 - 1] + 1LL * (n - m2 + 1) * a[i];

            if (val1 > val2) l = m1;
            else r = m2;
        }

        for(long j = l; j<=r; ++j)
            minimize(dp[i], dp[j-1] + 1LL * (n - j + 1) * a[i]);
    }

    return dp[n];
}


#define MAX 1000001
#define LOGMAX 20
long rmq[MAX][LOGMAX];

long getMax(long l, long r){
    long len = r - l + 1;
    long j = logOf(len);
    return max(rmq[l][j], rmq[r - MASK(j) + 1][j]);
}

ll subbo(){
    for(long i = 1; i<=n; ++i) rmq[i][0] = a[i];
    for(long j = 1; MASK(j) <= n; ++j)
        for(long i = 1; i + MASK(j) - 1 <= n; ++i)
            rmq[i][j] = max(rmq[i][j-1], rmq[i + MASK(j-1)][j-1]);

    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    for(long i = 1; i<=n; ++i){
        dp[i] = min(dp[0] + 1LL * n * getMax(1, i), dp[i-1] + 1LL * (n - i + 1) * a[i]);

        long l = 1, r = i;
        while(r - l > 300){
            long m1 = l + (r - l) / 3;
            long m2 = r - (r - l) / 3;
            ll val1 = dp[m1 - 1] + 1LL * (n - m1 + 1) * getMax(m1, i);
            ll val2 = dp[m2 - 1] + 1LL * (n - m2 + 1) * getMax(m2, i);

            if (val1 > val2) l = m1;
            else r = m2;
        }

        for(long j = l; j<=r; ++j)
            minimize(dp[i], dp[j-1] + 1LL * (n - j + 1) * getMax(j, i));
    }

    return dp[n];
}

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

    //freopen("discharg.inp", "r", stdin);

    cin >> n;

    a.resize(n+1);
    for(long i = 1; i<=n; ++i)
        cin >> a[i];

    bool check1 = true, check2 = true;;
    for(long i = 1; i<n; ++i){
        if (a[i] < a[i+1]) check1 = false;
        if (a[i] > a[i+1]) check2 = false;
    }

    if (check1) cout << sub4() << "\n";
    else if (n <= 10000) cout << sub5() << "\n";
    else if (check2) cout << sub3() << "\n";
    else cout << subbo() << "\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