結果

問題 No.2501 Maximum Inversion Number
ユーザー tnakao0123tnakao0123
提出日時 2024-06-20 15:26:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 1,390 bytes
コンパイル時間 597 ms
コンパイル使用メモリ 46,080 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-20 15:26:25
合計ジャッジ時間 3,508 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 48 ms
6,944 KB
testcase_02 AC 73 ms
6,940 KB
testcase_03 AC 56 ms
6,940 KB
testcase_04 AC 52 ms
6,944 KB
testcase_05 AC 51 ms
6,940 KB
testcase_06 AC 58 ms
6,940 KB
testcase_07 AC 51 ms
6,948 KB
testcase_08 AC 50 ms
6,944 KB
testcase_09 AC 32 ms
6,940 KB
testcase_10 AC 48 ms
6,944 KB
testcase_11 AC 49 ms
6,940 KB
testcase_12 AC 49 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 60 ms
6,944 KB
testcase_15 AC 47 ms
6,940 KB
testcase_16 AC 129 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2501.cc:  No.2501 Maximum Inversion Number - yukicoder
 */

#include<cstdio>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

using ll = long long;

/* global variables */

int ls[MAX_N], rs[MAX_N], cs0[MAX_N], cs1[MAX_N];

/* subroutines */

ll calc(int n, int k, int *cs = cs0) {
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    cs[i] = (k < ls[i]) ? ls[i] : (k > rs[i]) ? rs[i] : k;
    sum += cs[i];
  }
  return sum;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", ls + i);
    for (int i = 0; i < n; i++) scanf("%d", rs + i);

    ll lsum = 0, rsum = 0;
    for (int i = 0; i < n; i++) lsum += ls[i], rsum += rs[i];
    if (lsum > m || rsum < m) { puts("-1"); continue; }

    int k0 = 0, k1 = 1000000000 + 1;
    while (k0 + 1 < k1) {
      int k = (k0 + k1) / 2;
      if (calc(n, k) >= m) k1 = k;
      else k0 = k;
    }

    ll s0 = calc(n, k0, cs0);
    ll s1 = calc(n, k1, cs1);
    //printf(" %d,%lld %d,%lld\n", k0, s0, k1, s1);

    for (int i = 0; s1 > m && i < n; i++)
      if (cs0[i] < cs1[i]) cs1[i]--, s1--;

    ll sum = 0, f = 0;
    for (int i = n - 1; i >= 0; i--) {
      sum += f * cs1[i];
      f += cs1[i];
    }

    printf("%lld\n", sum);
  }
  
  return 0;
}
0