QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#678595 | #6695. Matching | Master640# | AC ✓ | 44ms | 7792kb | C++17 | 1.3kb | 2024-10-26 15:28:20 | 2024-10-26 15:28:21 |
Judging History
answer
//
// Created by 35263 on 2024/10/25.
//
//二分图每次两个顶点的集合都可以被划分成不相同的u,v
//u,v的顶点相同,该图为平衡二分图
//连接u,v中的一对点,使得匹配数正好是增加的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 200005;
ll n,k,a[maxn],b[maxn];
map<ll,vector<ll> >mp;
void update(){
mp.clear();
}
void init(){
cin>>n;
for(ll i=1;i<=n;i++){
cin>>a[i];
mp[a[i]-i].push_back(a[i]);
}
for(auto &v:mp){
vector<ll>*tmp=&v.second;
sort(tmp->begin(),tmp->end(),[&](ll x,ll y){
return x>y;
});
}
/* for(auto v:mp){
cout<<v.first<<"\n";
for(auto u:v.second){
cout<<u<<" ";
}
cout<<"\n";
}*/
ll ans=0;
for(auto v:mp){
vector<ll>tmp=v.second;
ll N=tmp.size();
for(ll i=0;i+1<N;i+=2){
if(tmp[i]+tmp[i+1]>0){
ans+=tmp[i]+tmp[i+1];
}
else{
break;
}
}
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll t=1;//可以保留t=1;
cin>>t;
while(t--){
update();
init();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5652kb
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: 44ms
memory: 7792kb
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