제출 #523202

#제출 시각아이디문제언어결과실행 시간메모리
523202vonatlusPalembang Bridges (APIO15_bridge)C++17
22 / 100
192 ms3672 KiB
/// adil sultanov | vonat1us #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const ll INF = 1e15 + 1e2; void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int N = 1e5+10; void one(vector<int> all, vector<pii> v, ll ans) { int n = sz(v); sort(all(all)); //all.erase(unique(all(all)), all.end()); ll mn = (1ll<<50); int mid = all[sz(all)/2]; for (int i = max(0, mid-100); i <= min((int)1e9, 100+mid); ++i) { ll res = 0; for (auto [l, r] : v) { if (i < l) { res += (l-i)*2ll; } if (i > r) { res += (i-r)*2ll; } } mn = min(mn, res); } cout << ans + mn, exit(0); } void ma1n() { int k, n; cin >> k >> n; ll ans = 0; vector<pii> v; vector<int> all; for (int i = 0; i < n; ++i) { char c1, c2; int l, r; cin >> c1 >> l >> c2 >> r; if (l > r) swap(l, r); ans += r-l; if (c1 != c2) { ans++; v.pb({l, r}); all.pb(l); all.pb(r); } } if (all.empty()) { cout << ans, exit(0); } if (k == 1) one(all, v, ans); int x = all[sz(all)/3]; int y = all[sz(all)*2/3]; ll mIn = (1ll<<50); for (int i = max(0, x-500); i <= min((int)1e9, x+500); ++i) { for (int j = max(0, y-500); j <= min((int)1e9, y+500); ++j) { ll res = 0; for (auto [l, r] : v) { if (l <= i && i <= r) continue; if (l <= j && j <= r) continue; ll mn = INF; if (i < l) mn = min(mn, (l-i)*2ll); if (j < l) mn = min(mn, (l-j)*2ll); if (mn != INF) res += mn; mn = INF; if (i > r) mn = min(mn, (i-r)*2ll); if (j > r) mn = min(mn, (j-r)*2ll); if (mn != INF) res += mn; } mIn = min(mIn, res); } } cout << ans+mIn; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } return 0; }

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

bridge.cpp: In function 'void one(std::vector<int>, std::vector<std::pair<int, int> >, ll)':
bridge.cpp:33:9: warning: unused variable 'n' [-Wunused-variable]
   33 |     int n = sz(v);
      |         ^
#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...