제출 #886260

#제출 시각아이디문제언어결과실행 시간메모리
886260tsumondaiPalembang Bridges (APIO15_bridge)C++14
22 / 100
41 ms5064 KiB
#include <bits/stdc++.h> using namespace std; #define Task "APIO15_bridge" #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int MAXN = 1e5 + 5; const int oo = 1e9, mod = 1e9 + 7; int K, N, M; int D[MAXN], E[MAXN]; struct Z { int a, b; } A[MAXN]; void proc(int V[]) { if (!N) return; int val = abs(A[1].a - A[1].b); priority_queue <int> p, q; int mid = A[1].a; if (A[1].b < mid) p.push(A[1].b); else q.push(-A[1].b); V[1] = val; for (int i = 2; i <= N; i++) { val += abs(mid - A[i].a) + abs(mid - A[i].b); if (A[i].a < mid) p.push(A[i].a); else q.push(-A[i].a); if (A[i].b < mid) p.push(A[i].b); else q.push(-A[i].b); while (p.size() < q.size()) { int nxt = -q.top(); q.pop(); p.push(mid); val += (int)(nxt - mid) * p.size() - (int)(nxt - mid) * (q.size() + 1); mid = nxt; } while (p.size() > q.size() + 1) { int nxt = p.top(); p.pop(); q.push(-mid); val += (int)(mid - nxt) * q.size() - (int)(mid - nxt) * (p.size() + 1); mid = nxt; } V[i] = val; } } int process() { cin >> K >> M; vector <int> arr; int def = 0; while (M--) { char p, q; int a, b; cin >> p >> a >> q >> b; if (p == q) { def += abs(a - b); continue; } A[++N] = {a, b}; } sort(A + 1, A + N + 1, [](const Z & a, const Z & b) { return a.a + a.b < b.a + b.b; }); proc(D); if (K == 1) { cout << D[N] + def + N; return 0; } reverse(A + 1, A + N + 1); proc(E); int ans = 1e9; for (int i = 0; i <= N; i++) ans = min(ans, def + D[i] + E[N - i] + N); cout << ans; } signed main() { cin.tie(0)->sync_with_stdio(false); if (fopen(Task".INP", "r")) { freopen(Task".INP", "r", stdin); freopen(Task".OUT", "w", stdout); } process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } // dont stop

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

bridge.cpp: In function 'long long int process()':
bridge.cpp:62:15: warning: control reaches end of non-void function [-Wreturn-type]
   62 |  vector <int> arr;
      |               ^~~
bridge.cpp: In function 'int main()':
bridge.cpp:85:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   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...