# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
994032 |
2024-06-07T04:26:59 Z |
vjudge1 |
Kas (COCI17_kas) |
C++17 |
|
3 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)*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--)
{
for (int j=0;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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |