제출 #734402

#제출 시각아이디문제언어결과실행 시간메모리
734402lovrotThe short shank; Redemption (BOI21_prison)C++17
0 / 100
86 ms133808 KiB
#include <cstdio> #include <algorithm> #include <cstring> #define X first #define Y second #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int LOG = 12; const int OFF = 1 << LOG; const int INF = 2e9; const int N = 4010; int n, d, t, C[OFF], E[OFF]; int T[2 * OFF], P[2 * OFF]; void add(int x, int val) { T[x] += val; P[x] += val; } void propagate(int x) { if(x >= OFF) return; add(2 * x, P[x]); add(2 * x + 1, P[x]); P[x] = 0; } void climb(int x, int val) { x += OFF; T[x] = val; x /= 2; for(x; x; x /= 2) T[x] = min(T[2 * x], T[2 * x + 1]); } int update(int l, int r, int val, int x = 1, int lo = 0, int hi = OFF) { if(r <= hi || lo <= l) return INF; if(l <= lo && hi <= r) { add(x, val); return T[x]; } propagate(x); int mi = (lo + hi) / 2; T[x] = min(update(l, r, val, 2 * x, lo, mi), update(l, r, val, mi, hi)); return T[x]; } int query(int val, int x = 1, int lo = 0, int hi = OFF) { if(lo + 1 == hi) return lo; if(T[x] > val) return -1; int mi = (lo + hi) / 2; if(T[2 * x + 1] <= val) return query(val, 2 * x + 1, mi, hi); return query(val, 2 * x, lo, mi); } int DP[OFF][OFF]; int dyn(int i, int w) { if(i >= n) return 0; if(DP[i][w] != -1) return 0; DP[i][w] = 0; for(int j = i; j < n; j++) DP[i][w] += E[j] >= i; if(w) { int cnt = 0; for(int j = i; j < n; j++) { cnt += E[j] >= i; DP[i][w] = min(DP[i][w], cnt + dyn(j + 1, w - 1)); } } return DP[i][w]; } int main() { for(int i = 0; i < 2 * OFF; i++) T[i] = INF; memset(DP, -1, sizeof(DP)); scanf("%d%d%d", &n, &d, &t); d = min(d, n); for(int i = 0; i < n; i++) { scanf("%d", C + i); climb(i, C[i]), update(0, i, 1); E[i] = query(t); //printf("// %d %d\n", i, E[i]); } printf("%d\n", dyn(0, d)); return 0; }

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

prison.cpp: In function 'void climb(int, int)':
prison.cpp:38:6: warning: statement has no effect [-Wunused-value]
   38 |  for(x; x; x /= 2)
      |      ^
prison.cpp: In function 'int main()':
prison.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d%d", &n, &d, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d", C + 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...