Submission #601820

#TimeUsernameProblemLanguageResultExecution timeMemory
601820MazaalaiMeetings (IOI18_meetings)C++17
19 / 100
416 ms196316 KiB
#include "meetings.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() #define ALL(x) x.begin(), x.end() #define chmax(a, b) a=max(a,b) #define chmin(a, b) a=min(a,b) #define pb push_back #define ff first #define ss second using namespace std; using ll = long long; using VI = vector <int>; using PII = pair <int, int>; int n, m, q; const int N = 1e5+1; const int M = 3*N; const int N1 = 5001; ll dp[N1][N1]; int nums[N]; struct Node { int l, r, mx; bool full; } node[M]; Node merge(Node a, Node b) { Node res = { a.l + (a.full ? b.l : 0), (b.full ? a.r : 0) + b.r, max(a.mx, b.mx), a.full&&b.full }; res.mx = max({res.mx, res.l, res.r, a.r+b.l}); return res; } void build(int l, int r, int head) { if (l == r) { int x = (nums[l] == 1); node[head] = {x, x, x, (bool)x}; return; } int mid = (l+r)>>1; build(l, mid, head*2+1); build(mid+1, r, head*2+2); node[head] = merge(node[head*2+1], node[head*2+2]); } Node query(int l, int r, int L, int R, int head) { if (l > R || L > r) return {0, 0, 0, 1}; if (L <= l && r <= R) return node[head]; int mid = (l+r)>>1; return merge( query(l, mid, L, R, head*2+1), query(mid+1, r, L, R, head*2+2) ); } vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { n = sz(h); q = sz(L); // cout << n << ' ' << q << '\n'; vector<long long> ans(q, 1e18); if (n < N1) { for (int i = 0; i < n; i++) { for (int j = i, cur = 0; j < n; j++) { cur = max(cur, h[j]); dp[i][j] = cur; if (j > i) dp[i][j] += dp[i][j-1]; } for (int j = i, cur = 0; j >= 0; j--) { cur = max(cur, h[j]); dp[i][j] = cur; if (j < i) dp[i][j] += dp[i][j+1]; } } for (int i = 0; i < q; i++) { int l = L[i], r = R[i]; ll& res = ans[i]; for (int mid = l; mid <= r; mid++) { chmin(res, dp[mid][l]+dp[mid][r]-h[mid]); } } return ans; } else { for (int i = 0; i < n; i++) nums[i] = h[i]; build(0, n-1, 0); for (int i = 0; i < q; i++) { int cur = query(0, n-1, L[i], R[i], 0).mx; int len = R[i] - L[i] + 1; ans[i] = len * 2 - cur; } } }

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^
#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...