제출 #636339

#제출 시각아이디문제언어결과실행 시간메모리
636339SirCovidThe19th휴가 (IOI14_holiday)C++17
0 / 100
5060 ms6552 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mx = 1e5 + 5; int n, d, st, pos[mx], A[mx]; pair<int, int> S[mx]; ll ans, F[2][2][mx], bit[mx][2]; void upd(int i, int type){ int val = S[i].first; for (; i < mx; i += i & (-i)) bit[i][0] += type * val, bit[i][1] += type; } ll qry(int k){ ll ret = 0; for (int pw = (1 << 17), pos = 0; pw; pw /= 2) if (pos + pw < mx and bit[pos + pw][1] <= k){ pos += pw; ret += bit[pos][0]; k -= bit[pos][1]; } return ret; } void dnq(int l, int r, int distL, int distR, bool dir, bool rep){ if (l > r) return; for (int i = distL; i <= distR; i++) upd(pos[i], -1); int midD = (l + r) / 2, stopMid; for (int stop = distL; stop <= distR; stop++){ int visit = midD - (stop - st) * (rep ? 2 : 1); upd(pos[stop], 1); if (visit < 0) continue; ll val = qry(visit); if (val >= F[dir][rep][midD]){ F[dir][rep][midD] = val; stopMid = stop; } } for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], -1); dnq(l, midD - 1, distL, stopMid, dir, rep); for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], 1); dnq(midD + 1, r, stopMid, distR, dir, rep); } void work(int start, int tmpA[], bool dir, bool rep){ for (int i = 0; i < n; i++){ A[i + 1] = tmpA[i]; S[i + 1] = {tmpA[i], i + 1}; } sort(S + 1, S + n + 1, greater<pair<int, int>>()); for (int i = 1; i <= n; i++) pos[S[i].second] = i; memset(bit, 0, sizeof(bit)); for (int i = start; i <= n; i++) upd(pos[i], 1); st = start; dnq(0, d, start, n, dir, rep); } ll findMaxAttraction(int tmpN, int start, int tmpD, int tmpA[]){ n = tmpN; d = tmpD; start++; work(start, tmpA, 0, 0); work(start + 1, tmpA, 0, 1); reverse(tmpA, tmpA + n); work(n - start + 1, tmpA, 1, 0); work(n - start + 2, tmpA, 1, 1); for (int i = 0; i <= d - 2; i++) ans = max({ans, F[0][1][i] + F[1][0][d - i - 2], F[1][1][i], F[0][0][d - i - 2]}); return max({ans, F[0][0][d], F[1][0][d]}); }

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

holiday.cpp: In function 'void dnq(int, int, int, int, bool, bool)':
holiday.cpp:41:14: warning: 'stopMid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], -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...