В этой задаче отключены взломы. За круглым столом...

Question

В этой задаче отключены взломы.

За круглым столом сидят n
человек, пронумерованных 1,2,3,…,n
по часовой стрелке. Вы приготовили несколько подарков для раздачи среди них.

У каждого человека i
есть вес ai
и общее поле зрения d
. Поле зрения человека i
состоит из d
людей, сидящих по часовой стрелке, и d
людей, сидящих против часовой стрелки от него (всего 2d
человек, не считая самого человека i
).

Счастье, получаемое человеком i
, определяется следующими правилами:

Если человек i
получает подарок, и в его поле зрения находятся x
человек, не получивших подарок, он получает x⋅ai
счастья.
Если человек i
не получает подарок, и в его поле зрения находятся x
человек, получивших подарок, он теряет −x⋅ai
счастья.
Вы хотите максимизировать суммарное счастье всех n
человек. Найдите это максимальное значение.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤104
) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа n
и d
(3≤n≤2⋅105
, 1≤d<n2
).

Вторая строка содержит n
целых чисел a1,a2,…,an
(1≤ai≤108
), где ai
— вес i
-го человека.

Гарантируется, что сумма n
по всем наборам входных данных не превосходит 106
.

Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальное суммарное счастье.

Пример
Входные данныеСкопировать
5
3 1
1 2 3
5 1
1 4 5 2 6
6 2
1 1 4 5 1 4
10 2
230 24 3 42 432 234 934 2389 333 444
3 1
100000000 100000000 100000000
Выходные данныеСкопировать
3
15
26
8590
0
Примечание
В первом наборе входных данных за столом сидят 3 человека. Для каждого человека i
поле зрения равно d=1
, то есть включает 1 человека, сидящего по часовой стрелке, и 1 человека, сидящего против часовой стрелки. Если человек 2 получает подарок, он получает счастье от 2 соседей, не получивших его, что составляет 2⋅a2=2⋅2=4
. Однако человек 1 и человек 3 теряют счастье, так как не получили подарок, но имеют соседа, который его получил. После рассмотрения всех возможностей максимальное суммарное счастье равно 3.

Во втором наборе входных данных n=5,d=1
. Оптимальное решение — дать подарки людям 2, 3 и 5, что позволяет достичь максимального суммарного счастья равного 15.
реши на с++ без пояснений с норм маленькими иименами как в споррт прое в шаблоне
#include <bits/stdc++.h>
#define int long long

using namespace std;

using ll = long long;
using i128 = __int128_t;

const int N = 998244353;
const int L = 20;
const int C = 320;
const int B = 128;

void solve() {

}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
cin >> tests;
while (tests--) {
solve();
}
return 0;
}

Answer 1

cpp
#include <bits/stdc++.h>
#define int long long

using namespace std;

using ll = long long;
using i128 = __int128_t;

const int N = 998244353;
const int L = 20;
const int C = 320;
const int B = 128;

void out(i128 x) {
  if (x == 0) {
    cout << 0 << '\n';
    return;
  }
  string s;
  while (x) {
    s += char('0' + x % 10);
    x /= 10;
  }
  reverse(s.begin(), s.end());
  cout << s << '\n';
}

void solve() {
  int n, d;
  cin >> n >> d;

  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<int> b(3 * n);
  for (int i = 0; i < 3 * n; i++) b[i] = a[i % n];

  vector<int> pr(3 * n + 1, 0);
  for (int i = 0; i < 3 * n; i++) pr[i + 1] = pr[i] + b[i];

  i128 ans = 0;

  for (int i = 0; i < n; i++) {
    int p = i + n;
    int sm = pr[p] - pr[p - d] + pr[p + d + 1] - pr[p + 1];
    i128 cur = (i128)2 * d * a[i] - sm;
    if (cur > 0) ans += cur;
  }

  out(ans);
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  srand(time(0));
  int tests = 1;
  cin >> tests;
  while (tests--) {
    solve();
  }
  return 0;
}

В этой задаче отключены взломы. За круглым столом...

Frage

Gedanke

Antwort

Diesen Q&A teilen