Submission #697478

#TimeUsernameProblemLanguageResultExecution timeMemory
697478steveonalexDischarging (NOI20_discharging)C++14
0 / 100
91 ms8148 KiB
#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 a[1]; } 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 (check2) cout << sub3() << "\n"; else if (n <= 10000) cout << sub5() << "\n"; else cout << subbo() << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...