제출 #636083

#제출 시각아이디문제언어결과실행 시간메모리
636083null_aweBoarding Passes (BOI22_passes)C++14
컴파일 에러
0 ms0 KiB
#include <iostream> #include <vector> using namespace std; #define ll long long int n, g; vector<vector<int>> p, pos; vector<vector<ll>> l, r; ll calc(int b, int s, int i) { ll ans = l[pos[b][i]][b] + r[pos[b][i + 1]][b]; for (int bef = 0; bef < g; ++bef) if (s & (1 << bef)) ans += 2 * (l[pos[b][i]][bef] + r[pos[b][i + 1]][bef]); return ans; } int main() { string str; cin >> str; n = str.size(), g = 0; for (int i = 0; i < n; ++i) g = max(g, str[i] - 'A' + 1); p = vector<vector<int>>(n + 1, vector<int>(g)); for (int i = 0; i < n; ++i) p[i + 1] = p[i], ++p[i + 1][str[i] - 'A']; l = vector<vector<ll>>(n, vector<ll>(g)), r = vector<vector<ll>>(n, vector<ll>(g)); vector<vector<ll>> last(g, vector<ll>(g)); for (int i = 0; i < n; ++i) { int val = str[i] - 'A'; l[i] = last[val]; for (int j = 0; j < g; ++j) l[i][j] += p[i][j]; last[val] = l[i]; } last = vector<vector<ll>>(g, vector<ll>(g)); for (int i = n - 1; i >= 0; --i) { int val = str[i] - 'A'; r[i] = last[val]; for (int j = 0; j < g; ++j) r[i][j] += p[n][j] - p[i + 1][j]; last[val] = r[i]; } pos.resize(g); for (int i = 0; i < g; ++i) pos[i].push_back(0); for (int i = 0; i < n; ++i) pos[str[i] - 'A'].push_back(i); for (int i = 0; i < g; ++i) pos[i].push_back(n - 1); vector<ll> dp(1 << g, LLONG_MAX); dp[0] = 0; for (int mask = 1; mask < (1 << g); ++mask) { for (int b = 0; b < g; ++b) { if (!(mask & (1 << b))) continue; int bef = mask ^ (1 << b), lo = 0, hi = pos[b].size() - 1; while (lo < hi - 1) { int mid = (lo + hi) / 2; if (calc(b, bef, mid - 1) >= calc(b, bef, mid)) lo = mid; else hi = mid; } dp[mask] = min(dp[mask], dp[bef] + calc(b, bef, lo)); } } ll ans = dp[(1 << g) - 1]; cout << ans / 2; if (ans & 1) cout << ".5"; cout << '\n'; return 0; }

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

passes.cpp: In function 'int main()':
passes.cpp:43:25: error: 'LLONG_MAX' was not declared in this scope
   43 |   vector<ll> dp(1 << g, LLONG_MAX); dp[0] = 0;
      |                         ^~~~~~~~~
passes.cpp:3:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    2 | #include <vector>
  +++ |+#include <climits>
    3 | using namespace std;