Submission #2923922


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int N;

vector<i64> a;

int main(){
  cin >> N;
  a.resize(N * 3);
  for(auto & x : a) cin >> x;
  vector<i64> A(N * 3 + 1,0);
  vector<i64> B(N * 3 + 1,0);

  {
    priority_queue<i64,vector<i64>,greater<i64>> que;
    i64 sum = 0;
    rep(i,0,3 * N - 1){
      que.push(a[i]);
      sum += a[i];
      if(i >= N){
        sum -= que.top();
        que.pop();
      }
      A[i] = sum;
    }
  }
  {
    priority_queue<i64> que;
    i64 sum = 0;
    for(int i = 3 * N - 1;i >= 0;i--)
    {
      que.push(a[i]);
      sum += a[i];
      if(i < 2 * N){
        sum -= que.top();
        que.pop();
      }
      B[i] = sum;
    }
  }

  i64 ans = A[N - 1] - B[N];
  for(int i = N - 1;i < N * 2;i++){
    ans = max(ans,A[i] - B[i + 1]);
  }

  cout << ans << endl;
}

Submission Info

Submission Time
Task D - 3N Numbers
User niuez
Language C++14 (GCC 5.4.1)
Score 500
Code Size 976 Byte
Status
Exec Time 163 ms
Memory 9068 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt
Subtask 300 / 300 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt
All 200 / 200 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 1 ms 256 KB
1_03.txt 1 ms 256 KB
1_04.txt 1 ms 256 KB
1_05.txt 1 ms 256 KB
1_06.txt 1 ms 256 KB
1_07.txt 1 ms 256 KB
1_08.txt 2 ms 384 KB
1_09.txt 3 ms 384 KB
1_10.txt 2 ms 384 KB
1_11.txt 2 ms 384 KB
1_12.txt 2 ms 384 KB
1_13.txt 2 ms 384 KB
1_14.txt 2 ms 384 KB
1_15.txt 2 ms 384 KB
1_16.txt 2 ms 384 KB
1_17.txt 2 ms 384 KB
1_18.txt 2 ms 384 KB
1_19.txt 2 ms 384 KB
1_20.txt 3 ms 384 KB
1_21.txt 3 ms 384 KB
1_22.txt 3 ms 384 KB
1_23.txt 3 ms 384 KB
2_00.txt 64 ms 9060 KB
2_01.txt 145 ms 9060 KB
2_02.txt 123 ms 9060 KB
2_03.txt 127 ms 9060 KB
2_04.txt 123 ms 9060 KB
2_05.txt 123 ms 9060 KB
2_06.txt 125 ms 9060 KB
2_07.txt 123 ms 9060 KB
2_08.txt 73 ms 8944 KB
2_09.txt 73 ms 8948 KB
2_10.txt 73 ms 9068 KB
2_11.txt 72 ms 8948 KB
2_12.txt 161 ms 8944 KB
2_13.txt 163 ms 9060 KB
2_14.txt 163 ms 9064 KB
2_15.txt 163 ms 9064 KB