제출 #500853

#제출 시각아이디문제언어결과실행 시간메모리
500853HalogenPalembang Bridges (APIO15_bridge)C++14
0 / 100
0 ms296 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> ii; main() { int K, N; scanf("%lld %lld", &K, &N); int ans = 0; vector<pair<int, int> > lst; for (int i = 0; i < N; i++) { char c1, c2; int i1, i2; scanf(" %c %lld %c %lld", &c1, &i1, &c2, &i2); if (c1 == c2) ans += abs(i2 - i1); else lst.emplace_back(i1, i2); } sort(lst.begin(), lst.end(), [](ii i, ii j) { return i.first + i.second < j.first + j.second; }); N = lst.size(); int pre[N + 5], suf[N + 5]; int left = 0, right = 0; priority_queue<int> l; priority_queue<int, vector<int>, greater<int> > r; for (int i = 0; i < N; i++) { r.push(lst[i].first); r.push(lst[i].second); right += lst[i].first + lst[i].second; while (l.size() < r.size() || r.top() < l.top()) { right -= r.top(); left += r.top(); l.push(r.top()); r.pop(); } while (l.size() > r.size()) { right += l.top(); left -= l.top(); r.push(l.top()); l.pop(); } pre[i] = right - r.size() * l.top() + l.top() * l.size() - left; } left = right = 0; while (!r.empty()) r.pop(); while (!l.empty()) l.pop(); for (int i = N - 1; i >= 0; --i) { r.push(lst[i].first); r.push(lst[i].second); right += lst[i].first + lst[i].second; while (l.size() < r.size() || r.top() < l.top()) { right -= r.top(); left += r.top(); l.push(r.top()); r.pop(); } while (l.size() > r.size()) { right += l.top(); left -= l.top(); r.push(l.top()); l.pop(); } suf[i] = right - r.size() * l.top() + l.top() * l.size() - left; } int mini = min(suf[0], pre[N - 1]); // for (int i = 0; i < N; i++) // printf("%lld %lld\n", pre[i], suf[i]); if (K == 1) { printf("%lld\n", mini + N + ans); return 0; } for (int i = 0; i < N - 1; i++) mini = min(mini, suf[i + 1] + pre[i]); printf("%lld\n", mini + N + ans); }

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

bridge.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main() {
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     int K, N; scanf("%lld %lld", &K, &N);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %c %lld %c %lld", &c1, &i1, &c2, &i2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...