Submission #949699

#	Time	Username	Problem	Language	Result	Execution time	Memory
949699		steveonalex	Discharging (NOI20_discharging)	C++14	47 / 100	82 ms	8284 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 > 100){
            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 > 100){
            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";
 
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:137:25: warning: variable 'check2' set but not used [-Wunused-but-set-variable]
  137 |     bool check1 = true, check2 = true;;
      |                         ^~~~~~

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