제출 #715317

#제출 시각아이디문제언어결과실행 시간메모리
715317stevancvThe short shank; Redemption (BOI21_prison)C++14
25 / 100
2056 ms24252 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 4000 + 2; const int inf = 1e9; int st[4 * N], lzy[4 * N]; void Propagate(int node, int l, int r) { if (lzy[node] == 0) return; if (l < r) { lzy[2 * node] += lzy[node]; lzy[2 * node + 1] += lzy[node]; } st[node] += lzy[node]; lzy[node] = 0; } void Add(int node, int l, int r, int ql, int qr, int x) { Propagate(node, l, r); if (r < ql || qr < l) return; if (ql <= l && r <= qr) { lzy[node] += x; Propagate(node, l, r); return; } int mid = l + r >> 1; Add(2 * node, l, mid, ql, qr, x); Add(2 * node + 1, mid + 1, r, ql, qr, x); st[node] = max(st[2 * node], st[2 * node + 1]); } int Get(int node, int l, int r, int ql, int qr) { Propagate(node, l, r); if (r < ql || qr < l) return 0; if (ql <= l && r <= qr) return st[node]; int mid = l + r >> 1; return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr)); } void Dodaj(int l, int r, int o) { Add(1, 0, N, l, r, o); } int cost[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, d, t; cin >> n >> d >> t; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; stack<int> s; vector<int> gr(n, inf); int ans = 0; for (int i = 0; i < n; i++) { if (a[i] > t) { while (!s.empty() && a[s.top()] - s.top() + i > t) s.pop(); if (!s.empty()) { gr[i] = s.top(); ans += 1; } } s.push(i); } for (int i = 0; i < n; i++) if (a[i] <= t) ans++; vector<array<int, 2>> svi; for (int i = 0; i < n; i++) { if (gr[i] != inf) svi.push_back({gr[i] + 1, i}); } if (d == 1) { vector<int> su(n); for (int i = 0; i < svi.size(); i++) { su[svi[i][0]] += 1; su[svi[i][1] + 1] -= 1; } int mx = 0; for (int i = 0; i < n; i++) { if (i > 0) su[i] += su[i - 1]; smax(mx, su[i]); } cout << ans - mx << en; return 0; } sort(svi.begin(), svi.end()); n = svi.size(); for (int i = 0; i < n; i++) { int y = 0; for (int j = i; j < n; j++) { Dodaj(svi[j][0], svi[j][1], 1); smax(y, svi[j][1]); cost[i][j] = Get(1, 0, N, svi[i][0], y); } for (int j = i; j < n; j++) Dodaj(svi[j][0], svi[j][1], -1); } vector<int> dp(n); while (d--) { vector<int> ndp(n); function<void(int, int, int, int)> Solve = [&] (int l, int r, int opl, int opr) { if (l > r) return; int best = 0; int mid = l + r >> 1; for (int j = opl; j <= min(opr, mid); j++) { int x = cost[j][mid]; if (j > 0) x += dp[j - 1]; if (x >= ndp[mid]) { ndp[mid] = x; best = j; } } Solve(l, mid - 1, opl, best); Solve(mid + 1, r, best, opr); }; Solve(0, n - 1, 0, n - 1); swap(dp, ndp); } cout << ans - dp.back() << en; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp: In function 'void Add(int, int, int, int, int, int)':
prison.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
prison.cpp: In function 'int Get(int, int, int, int, int)':
prison.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
prison.cpp: In function 'int main()':
prison.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < svi.size(); i++) {
      |                         ~~^~~~~~~~~~~~
prison.cpp: In lambda function:
prison.cpp:102:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int mid = l + r >> 1;
      |                       ~~^~~
#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...