oj.uz

Submission #994031

# Submission time Handle Problem Language Result Execution time Memory
994031 2024-06-07T04:24:15 Z vjudge1 Kas (COCI17_kas) C++17
0 / 100
 4 ms 860 KB 
#include <bits/stdc++.h>

using namespace std;

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

int x,n,cnt[M]={},ans,pre[N][M*2],suf[N][M*2],temp[M*2];
vector<int> a;

bool pos(int x)
{
	bool isp[x+1]={};
	isp[0]=true;
	for (int i=0;i<n;i++)
		for (int j=a[i];j<=x;j++)
			isp[j]|=isp[j-a[i]];
	return isp[x];
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -