제출 #942948

#제출 시각아이디문제언어결과실행 시간메모리
942948oblantisPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms456 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; typedef long long ll; typedef pair<int, int> pii; const ll inf = 1e16; const int mod = 1e9+7; const int maxn = 1e6 + 1; void solve() { int k, n, sz = 0; cin >> k >> n; ll ans = 0, s = inf, sum = 0, c1 = 0, c2 = 0; vt<pair<ll, bool>> v; for(int i = 0; i < n; i++){ char a, b; int x, y; cin >> a >> x >> b >> y; if(x > y)swap(x, y); ans += y - x; if(a != b){ v.pb({x, 0}); v.pb({y, 1}); sum += x; ans++; c1++; sz += 2; } } sort(all(v)); for(int j = 0; j < sz; j++){ if(v[j].ss == 0)sum -= v[j].ff, c1--; else sum -= v[j].ff, c2++; s = min(s, sum + (c2 - c1) * v[j].ff); } cout << ans + s * 2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#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...