結果

問題 No.3051 Make All Divisible
ユーザー Andrew8128
提出日時 2025-03-07 22:57:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,590 bytes
コンパイル時間 935 ms
コンパイル使用メモリ 99,304 KB
実行使用メモリ 11,044 KB
最終ジャッジ日時 2025-06-20 02:25:42
合計ジャッジ時間 5,293 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <array>
using namespace std;
typedef long long ll;
int main()
{
  int T;
  cin >> T;
  while (T--)
  {
    ll n, k;
    cin >> n >> k;
    vector<ll> A(n);
    for (size_t i = 0; i < n; i++)
    {
      cin >> A[i];
    }
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    ll sum = 0, ma = 0, cnt = 0;
    for (size_t i = 0; i < n; i++)
    {
      if (A[i] % k == 0 && A[i] != 0)
      {
        pq.push({k, A[i]});
      }
      if (A[i] % k != 0)
      {
        if (A[i] % k < A[i])
        {
          pq.push({A[i] % k + k, A[i]});
        }
        cnt++;
        sum += A[i] % k;
        ma = max(ma, A[i] % k);
      }
    }
    if (sum == 0)
    {
      cout << 0 << '\n';
      continue;
    }
    if (sum % k != 0)
    {
      cout << -1 << '\n';
      continue;
    }
    while ((cnt < k) || (sum / k < ma))
    {
      if (pq.empty())
      {
        break;
      }
      auto a = pq.top();
      pq.pop();
      if (a[0] == k)
      {
        cnt++;
        ma = max(ma, a[0]);
        sum += k;
        if (a[0] + k <= a[1])
        {
          pq.push({a[0] + k, a[1]});
        }
      }
      else
      {
        ma = max(ma, a[0]);
        sum += k;
        if (a[0] + k <= a[1])
        {
          pq.push({a[0] + k, a[1]});
        }
      }
    }
    if ((cnt < k) || (sum / k < ma))
    {
      cout << -1 << '\n';
    }
    else
    {
      cout << sum / k << '\n';
    }
  }
  return 0;
}
/*
  File : ~/yukicoder/526/D.cpp
  Date : 2025/03/07
  Time : 22:15:56
*/
0