QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181116 | #6695. Matching | iamshiqing | AC ✓ | 999ms | 9432kb | C++14 | 808b | 2023-09-16 15:52:19 | 2023-09-16 15:52:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e5 + 10;
const int P = 1e9 + 7;
int a[N];
map<int, int>mp;
void solve() {
int pos = 1;
priority_queue<int>ans[N];
mp.clear();
int n;
cin>>n;
for (int i = 1; i <= n; i++) cin>>a[i];
for (int i = 1; i <= n; i++) {
int tmp = i - a[i];
if (mp.find(tmp) != mp.end()) {
ans[mp[tmp]].push(a[i]);
} else {
mp[tmp] = pos++;
ans[mp[tmp]].push(a[i]);
}
}
int res = 0;
for (int i = 1; i < pos; i++) {
while(ans[i].size()>=2){
int tmp=ans[i].top();
ans[i].pop();
tmp+=ans[i].top();
ans[i].pop();
if(tmp>0) res+=tmp;
}
}
cout<<res<<endl;
}
signed main() {
int _ =1;
cin>>_;
while (_--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6716kb
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: 999ms
memory: 9432kb
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