oj.uz

Submission #994037

# Submission time Handle Problem Language Result Execution time Memory
994037 2024-06-07T04:43:03 Z vjudge1 Kas (COCI17_kas) C++17
100 / 100
 277 ms 393280 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
	int n;
	cin>>n;
	int su=0,a[n];
	for (int i=0;i<n;i++)
		cin>>a[i],su+=a[i];
	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<<div/2+su-div<<endl;
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9816 KB Output is correct
2 Correct 7 ms 9816 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9820 KB Output is correct
2 Correct 9 ms 10588 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11352 KB Output is correct
2 Correct 8 ms 12124 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12124 KB Output is correct
2 Correct 8 ms 11984 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29268 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37200 KB Output is correct
2 Correct 34 ms 41092 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 158544 KB Output is correct
2 Correct 171 ms 197744 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 236628 KB Output is correct
2 Correct 218 ms 314948 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 354132 KB Output is correct
2 Correct 277 ms 393280 KB Output is correct