Submission #111095

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
111095	2019-05-13 15:49:55	square1001	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	96 ms	6456 KiB

bridge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 62;
long long solve(int K, int N, vector<int> A, vector<int> B) {
  if(N == 0) return 0;
  vector<int> perm(N);
  for(int i = 0; i < N; ++i) perm[i] = i;
  sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] + B[i] < A[j] + B[j]; });
  vector<int> SA(N), SB(N);
  for(int i = 0; i < N; ++i) SA[i] = A[perm[i]], SB[i] = B[perm[i]];
  A = SA, B = SB;
  vector<long long> da(N + 1), db(N + 1);
  long long sum = 0, all = 0, last = -1;
  priority_queue<int> que;
  for(int i = 1; i <= N; ++i) {
    que.push(-A[i - 1]);
    que.push(-B[i - 1]);
    last = -que.top();
    que.pop();
    sum += last;
    all += A[i - 1] + B[i - 1];
    da[i] = (last * i - sum) + ((all - sum) - last * i);
  }
  sum = 0, all = 0, last = -1;
  que = priority_queue<int>();
  for(int i = 1; i <= N; ++i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37