#include <bits/stdc++.h>
#define INF 1000000005
using namespace std;
pair <int,int> din[2005][2005];
int n,mici,mari,v[2005],st,dr,mij,i,sol;
bool verif (int val)
{
int i,j,lung,dr;
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
din[i][j]={INF,INF};
}
}
for (lung=1;lung<=n;lung++)
{
for (i=1;i<=n-lung+1;i++)
{
dr=i+lung-1;
din[i][dr]={INF,INF};
if (v[dr]-v[i]+1<=val)
{
if (mici!=0)
{
din[i][dr]=min(din[i][dr],{0,1});
}
}
if (v[dr]-v[i]+1<=2*val)
{
if (mari!=0)
{
din[i][dr]=min(din[i][dr],{1,0});
}
}
for (j=i;j<=dr-1;j++)
{
if (din[i][j].first+din[j+1][dr].first<=mici&&din[i][j].second+din[j+1][dr].second<=mari)
{
din[i][dr]=min(din[i][dr],{din[i][j].second+din[j+1][dr].second,din[i][j].first+din[j+1][dr].first});
}
}
}
}
if (din[1][n].first!=INF&&din[1][n].second!=INF)
{
return 1;
}
return 0;
}
int main()
{
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n>>mici>>mari;
for (i=1;i<=n;i++)
{
cin>>v[i];
}
sort (v+1,v+n+1);
st=1;
dr=1000000000;
while (st<=dr)
{
mij=(st+dr)/2;
if (verif(mij)==1)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
cout<<sol;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Incorrect |
22 ms |
684 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1096 ms |
31672 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |