Submission #1101700

#TimeUsernameProblemLanguageResultExecution timeMemory
1101700trieK blocks (IZhO14_blocks)C++17
0 / 100
1 ms2552 KiB
#include<bits/stdc++.h> #define mp make_pair #define fi first #define se second #define ii pair<int, int> #define iii pair<ii, int> #define ll long long #define pb push_back #define pli pair<ll, int> #define all(v) (v).begin(), (v).end() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define cntbit(mask) __builtin_popcount(mask) #define getbit(x, i) ((x >> i) & 1) #define MASK(i) (1 << i) #define pli pair<ll, int> using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;} const int N = 1e5 + 5; const int V = 105; const int MOD = 1e9 + 7; const int LOG = 19; int n, k, a[N], rmq[N][20]; ll dp[2][N]; int Cost(int i, int j) { int p = __lg(j - i + 1); return max(rmq[i][p], rmq[j - MASK(p) + 1][p]); } void calc(int u, int v, int l, int r, int cur) { if (l > r) return; int best = -1, m = (r + l) / 2; dp[cur][m] = 1e18; for(int i = u ; i <= min(m, v) ; i++) if (minimize(dp[cur][m], dp[1 - cur][i] + Cost(i + 1, m))) best = i; calc(u, best, l, m - 1, cur); calc(best, v, m + 1, r, cur); } void solve() { cin >> n >> k; for(int i = 1 ; i <= n ; i++) cin >> a[i]; for(int i = 1 ; i <= n ; i++) rmq[i][0] = a[i]; for(int j = 1 ; j <= LOG ; j++) for(int i = 1 ; i <= n - MASK(j) + 1 ; i++) rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]); for(int i = 1 ; i <= n ; i++) dp[1][i] = Cost(1, i); for(int i = 2 ; i <= k ; i++) calc(1, n, 1, n, i & 1); cout << dp[k & 1][n]; } int main(void) { //freopen("task.inp", "r", stdin); //freopen("task.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while(t--) solve(); return 0; }

Compilation message (stderr)

blocks.cpp: In function 'void solve()':
blocks.cpp:53:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |             rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
      |                                                         ~~^~~
blocks.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...