제출 #992708

#제출 시각아이디문제언어결과실행 시간메모리
992708chanhchuong123Palembang Bridges (APIO15_bridge)C++14
78 / 100
165 ms13580 KiB
#include<bits/stdc++.h> using namespace std; const bool multiTest = false; #define task "" #define fi first #define se second #define MASK(i) (1LL << (i)) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define BIT(mask, i) ((mask) >> (i) & 1) template<typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) a = b; else return 0; return 1; } template<typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) a = b; else return 0; return 1; } const int MAX = 100010; int n, k; long long sumA; long long sumB; multiset<int> A; multiset<int> B; long long add = 0; vector<pair<int, int>> info; void ins(int value) { if (A.empty() || value <= (*A.rbegin())) A.insert(value), sumA += value; else B.insert(value), sumB += value; if (int(A.size()) - int(B.size()) > 1) { int temp = (*A.rbegin()); A.erase(A.find(temp)); B.insert(temp); sumA -= temp; sumB += temp; } if (int(B.size()) > int(A.size())) { int temp = (*B.begin()); B.erase(B.find(temp)); A.insert(temp); sumB -= temp; sumA += temp; } } void process(void) { cin >> k >> n; for (int i = 1; i <= n; ++i) { char P, Q; int S, T; cin >> P >> S >> Q >> T; if (P == Q) add += abs(S - T); else info.emplace_back(S, T); } if (info.empty()) { cout << add; return; } if (k == 1) { vector<int> value; for (pair<int, int> &p: info) { value.push_back(p.fi); value.push_back(p.se); } sort(all(value)); int median = value[value.size() / 2]; for (int &v: value) add += abs(median - v); cout << add; } else { sort(all(info), [](pair<int, int> &u, pair<int, int> &v) { return u.fi + u.se < v.fi + v.se; }); vector<long long> f(info.size()); for (int i = 0; i < info.size(); ++i) { ins(info[i].fi); ins(info[i].se); int median = (*A.rbegin()); f[i] = 1LL * (A.size()) * median - sumA + sumB - 1LL * (B.size()) * median; } long long res = add + f[info.size() - 1]; sumA = 0; sumB = 0; A.clear(); B.clear(); for (int i = info.size() - 1; i > 0; --i) { ins(info[i].fi); ins(info[i].se); int median = (*A.rbegin()); mini(res, f[i - 1] + 1LL * (A.size()) * median - sumA + sumB - 1LL * (B.size()) * median + add); } cout << res + (info.size()); } } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int nTest = 1; if (multiTest) cin >> nTest; while (nTest--) { process(); } return 0; }

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

bridge.cpp: In function 'void process()':
bridge.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < info.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
bridge.cpp: In instantiation of 'bool mini(T1&, T2) [with T1 = long long int; T2 = long long unsigned int]':
bridge.cpp:93:107:   required from here
bridge.cpp:14:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   14 |  if (a > b) a = b; else return 0; return 1;
      |      ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   freopen(task".inp", "r",  stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:104:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...