QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712164 | #6695. Matching | wsyear# | AC ✓ | 52ms | 4796kb | C++20 | 1.3kb | 2024-11-05 14:45:31 | 2024-11-05 14:45:33 |
Judging History
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