제출 #654516

#제출 시각아이디문제언어결과실행 시간메모리
654516cadmiumskyBoarding Passes (BOI22_passes)C++14
0 / 100
2065 ms3048 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using ll = long long; using namespace std; //#define int ll //#define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; ll dp[1 << 15]; int sum[1 << 15], sz[1 << 15]; signed main() { int n; string sp; vector<int> s; cin >> sp; n = sp.size(); dp[0] = 0; for(auto &x : sp) x -= 'A', s.emplace_back(1 << x); for(int i = 0; i < n; i++) sum[s[i]] += i, sz[s[i]]++; for(int i = 1; i < (1 << 15); i++) { vector<int> poz; vector<ll> alt[2]; for(int j = 0; j < n; j++) if(s[j] & i) poz.emplace_back(j); int total = 0, count = 0; alt[0].resize(poz.size()); alt[1].resize(poz.size()); for(int j = 0; j < 15; j++) if((1 << j) & i) total += sum[1 << j], count += sz[1 << j]; ll mn = n * (n - 1); for(int j = 0; j < 15; j++) { if(!((1 << j) & i)) continue; int remain = (i ^ (1 << j)); fill(all(alt[0]), 0); fill(all(alt[1]), 0); if(sz[1 << j] == 0) { mn = min(dp[remain], mn); continue; } ll last = 0, cnt = 0; ll delta = 0, sum = 0, altcnt = 0; for(int i = 0; i < poz.size(); i++) { if(s[poz[i]] & remain) sum += altcnt, delta++; else altcnt++; alt[0][i] = altcnt * delta - sum; } delta = 0, sum = 0; altcnt = 0; for(int i = poz.size() - 1; i >= 0; i--) { if(s[poz[i]] & remain) sum += altcnt, delta++; else altcnt++; alt[1][i] = delta * altcnt - sum; } for(int i = 0; i < poz.size(); i++) { if(!(remain & s[poz[i]])) { //cerr << mn << '/' << i << '\t' << dp[remain] << ' ' << alt[0][last] << ' ' << alt[1][last] << ' ' << poz[i] << ' ' << cnt << ' ' << sz[s[poz[i]]] - cnt << '\n'; mn = min(dp[remain] + (ll)(alt[0][last] + alt[1][i]) * 2 + (ll)cnt * (cnt - 1) / 2 + (ll)(sz[s[poz[i]]] - cnt) * ((sz[s[poz[i]]] - cnt) - 1) / 2, mn); cnt++; last = i; } } } dp[i] = mn; //cerr << dp[i] << '\n'; } ll u = dp[(1 << 15) - 1]; cout << u / 2; if(u % 2 == 1) cout << ".5"; cout << '\n'; } /** Când iar începe-a ninge Mă simt de-un dor cuprins. Mă văd, pe-un drum, departe, Mergând, încet, şi nins. Sub streşină, cerdacul Se-ntunecă mâhnit; Stă rezimată-o fată De stâlpu-nzăpezit. -- George Bacovia, Ninge */

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

passes.cpp: In function 'int main()':
passes.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for(int i = 0; i < poz.size(); i++) {
      |                      ~~^~~~~~~~~~~~
passes.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |       for(int i = 0; i < poz.size(); 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...