제출 #428227

#제출 시각아이디문제언어결과실행 시간메모리
428227patrikpavic2The short shank; Redemption (BOI21_prison)C++17
0 / 100
21 ms5724 KiB
#include <cstdio> #include <cstring> #include <stack> #include <vector> #define X first #define Y second #define PB push_back using namespace std; const int N = 1e5 + 500; const int OFF = (1 << 17); typedef long long ll; typedef pair < int, int > pii; ll LO, HI = (ll)1e9, COST; inline ll get_cost(pii &tmp){ return 1000LL * tmp.X + COST * tmp.Y; } inline pii bolji(pii A, pii B){ if(get_cost(A) < get_cost(B)) return A; return B; } pii T[2 * OFF]; int prop[2 * OFF]; int n, d, tme[N], L; vector < int > q[N]; void refresh(int x){ if(!prop[x]) return; T[x].X += prop[x]; if(x < OFF){ prop[2 * x] += prop[x]; prop[2 * x + 1] += prop[x]; } prop[x] = 0; } void update(int i, int a, int b, int lo, int hi){ refresh(i); if(lo <= a && b <= hi) { prop[i]++; refresh(i); return; } if(a > hi || b < lo) { return; } update(2 * i, a, (a + b) / 2, lo, hi); update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi); T[i] = bolji(T[2 * i], T[2 * i + 1]); } void postavi(int i, int a, int b, int gdje, pii kog){ refresh(i); refresh(i ^ 1); if(a == b){ T[i] = kog; return; } if(gdje <= (a + b) / 2) postavi(2 * i, a, (a + b) / 2, gdje, kog); else postavi(2 * i + 1, (a + b) / 2 + 1, b, gdje, kog); T[i] = bolji(T[2 * i], T[2 * i + 1]); } pii dp[N]; pii probaj(){ for(int i = 0;i < 2 * OFF;i++) T[i] = {N, N}, prop[i] = 0; postavi(1, 0, OFF - 1, 0, {0, 0}); for(int i = 1;i <= n;i++){ for(int j : q[i]){ //printf("%d %d += 1\n", 0, j - 1); update(1, 0, OFF - 1, 0, j - 1); } dp[i] = T[1]; dp[i].Y++; postavi(1, 0, OFF - 1, i, dp[i]); // printf("dp[ %d ] = %d %d\n", i, dp[i].X, dp[i].Y); } return T[1]; } int main(){ scanf("%d%d%d", &n, &d, &L); stack < int > Q; for(int i = 1;i <= n;i++){ scanf("%d", tme + i); Q.push(i); while(!Q.empty() && tme[Q.top()] + i - Q.top() > L) Q.pop(); if(!Q.empty()){ // printf("%d %d\n", Q.top(), i); q[i].PB(Q.top()); } } for(int i = 0;i < 29;i++){ COST = (LO + HI) / 2; int odg = probaj().Y; if(odg == d) break; if(odg < d) HI = COST; else LO = COST + 1; } pii fin = probaj(); printf("%lld\n", (get_cost(fin) - COST * d) / 1000LL); return 0; }

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

prison.cpp: In function 'int main()':
prison.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d%d%d", &n, &d, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d", tme + 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...