QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419076#6695. MatchingXujjWA 35ms5216kbC++14869b2024-05-23 17:36:362024-05-23 17:36:36

Judging History

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

  • [2024-05-23 17:36:36]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:5216kb
  • [2024-05-23 17:36:36]
  • 提交

answer

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
struct node
{
	int num;
	int minu;
} N[100005];
bool cmp(node a, node b)
{
	return a.minu < b.minu;
}
void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> N[i].num;
		N[i].minu = N[i].num - i;
	}
	sort(N + 1, N + n, cmp);
	int l = 1, ans = 0;
	while (l <= n)
	{
		if (l == n)
			break;
		int tmp = l + 1, sum = N[l].num;
		while (N[l].minu == N[tmp].minu && tmp <= n)
		{
			sum += N[tmp].num;
			// cout << l << " " << tmp << endl;
			tmp++;
			ans = max(sum, ans);
		}
		// cout << ans << endl;
		l = tmp;
	}
	cout << ans << '\n';
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 35ms
memory: 5216kb

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
0
0
9
0
10
2
0
2
0
11
0
12
0
1999999989
11
1
11
9
1999999981
21
0
15
0
5
0
0
0
12
1
14
0
0
0
0
14
0
5
1999999997
0
0
3999999981
3
15
3999999963
1999999984
5
0
13
0
7
11
0
5
8
4999999975
4
0
9
0
0
3
2
0
1999999994
1999999990
0
0
12
0
0
0
9
2
0
7
0
1999999992
16
0
1
1999999995
25
0
37...

result:

wrong answer 5th numbers differ - expected: '1', found: '0'