QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712164#6695. Matchingwsyear#AC ✓52ms4796kbC++201.3kb2024-11-05 14:45:312024-11-05 14:45:33

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 14:45:33]
  • 评测
  • 测评结果:AC
  • 用时:52ms
  • 内存:4796kb
  • [2024-11-05 14:45:31]
  • 提交

answer

// Author: Klay Thompson
// Problem: G. Matching
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 100010;

int n, a[maxn];
pii w[maxn];

void work() {
  cin >> n;
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) w[i] = pii(a[i] - i, a[i]);
  sort(w + 1, w + n + 1);
  ll ans = 0;
  for (int l = 1, r; l <= n; l = r + 1) {
    r = l;
    while (r < n && w[r + 1].fi == w[r].fi) r++;
    if ((r - l + 1) & 1) l++;
    reverse(w + l, w + r + 1);
    ll mx = 0, sum = 0;
    for (int i = l + 1; i <= r; i += 2) {
      sum += w[i - 1].se + w[i].se;
      chkmx(mx, sum);
    }
    ans += mx;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

output:

30
0
0

result:

ok 3 number(s): "30 0 0"

Test #2:

score: 0
Accepted
time: 52ms
memory: 4796kb

input:

5504
9
-1 -7 -6 -5 -4 -3 5 -1 0
5
999999995 999999993 999999995 999999995 999999995
5
3 -6 -5 -4 -2
4
-8 2 3 -5
4
-2 -1 0 1
9
-4 -9 3 -1 -1 -5 2 -3 -5
7
-1 -2 1 2 3 4 3
4
-2 5 2 -4
10
2 4 1 -3 -2 4 5 -3 0 -4
6
-1 0 1 2 4 -3
5
-4 -3 -2 -1 0
4
-1 0 1 2
8
1 0 -4 -1 0 -5 -3 -5
2
5 6
8
-4 -3 -2 -1 0 1 2 ...

output:

4
1999999988
0
5
1
1
11
0
9
3
0
3
0
11
6
9
0
1999999989
13
1
11
7
1999999981
40
0
11
0
6
0
0
7
9
1
15
4
3
0
7
23
0
5
1999999997
0
3
5999999976
3
16
5999999943
5999999933
5
0
11
0
10
12
0
6
8
3999999982
12
0
7
0
0
3
3
0
1999999994
3999999972
1
0
16
0
0
0
7
2
0
8
0
5999999964
16
0
1
1999999995
28
0
54...

result:

ok 5504 numbers