SubsetofFive

NC206673. SubsetofFive

描述

"Today is another day! I'm five." With the fail of unit tests, XiaoYang tiredly lies on the sofa. As we all know, XiaoYang is not good at implementing algorithms. The unit test is for a subset searching algorithm. Here is the task.

You are given a set A with n **distinct** integers $a_1, a_2, \cdots, a_n$ . You should find a "five" subset S, so that the sum of numbers in S is maximized and the sum is divisible by 5. A set $B = \lbrace b_1, b_2, \cdots, b_m \rbrace$ of size m is called the subset of set $A = \lbrace a_1, a_2, \cdots, a_n \rbrace$ when $b_i \in A$ holds for $i = 1, 2, \cdots, m$ and all integers in B are distinct.

输入描述

The first line contains integer $n ~ (n \leq 10^6)$ , the size of set A.

The second line contains n integers $a_1, a_2, a_3, \cdots, a_n ~ (0 \leq a_i \leq 10^9)$ .

输出描述

Output the maximal sum of S.

示例1

输入:

5
2 10 6 3 1

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 414ms, 内存消耗: 620K, 提交时间: 2020-06-16 17:29:38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e6;
ll a[5];
ll b[5];
ll n;
int main() {
	cin>>n;
	while(n--) {
		ll x;
		cin>>x;
		for(int i=0;i<5;i++) {
			b[i] = a[i]+x;
		}
		for(int i=0;i<5;i++) {
			a[b[i]%5] = max(a[b[i]%5],b[i]);
		}

	}
	cout<<a[0]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 190ms, 内存消耗: 504K, 提交时间: 2020-06-13 15:08:47

#include <iostream>
#define int long long
int a[10],b[10],n;
signed main()
{
	scanf("%lld",&n);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%lld",&x);
		for(int j=0;j<5;j++)
		 b[j]=a[j]+x;
		for(int j=0;j<5;j++)
		 a[b[j]%5]=std::max(a[b[j]%5],b[j]);
	}
	printf("%lld\n",a[0]);
	return 0;
}