Submission #994033

#	Time	Username	Problem	Language	Result	Execution time	Memory
994033		vjudge1	Kas (COCI17_kas)	C++17	30 / 100	63 ms	77316 KiB

kas

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 1, N = 500 + 1, inf = 1e9;

int cnt[M],ans,pre[N][M*2],temp[M*2];

int main()
{
	int n,x;
	cin>>n;
	for (int i=0;i<n;i++)
		cin>>x,cnt[x]++;
	for (int i=1;i<M;i++)
		ans+=(cnt[i]/2)*i,cnt[i]%=2;
	int su=0;
	vector<int> a;
	for (int i=1;i<M;i++)
		if (cnt[i])
			su+=i,a.push_back(i);
	n=a.size();
	for (int i=0;i<M*2;i++)
		temp[i]=pre[0][i]=-inf;
	temp[M]=pre[0][M]=0;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<M*2;j++)
		{
			if (j+a[i]<M*2)
				temp[j+a[i]]=max(temp[j+a[i]],pre[i][j]+a[i]);
			if (j-a[i]>=0)
				temp[j-a[i]]=max(temp[j-a[i]],pre[i][j]+a[i]);
		}
		for (int j=0;j<M*2;j++)
			pre[i+1][j]=temp[j];
	}
	int div=pre[n][M];
	cout<<ans+div/2+su-div<<endl;
	
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10