the problem is ↵
http://codeforces.com/contest/513/problem/C↵
↵
the solution is ↵
http://codeforces.com/contest/513/submission/9761274↵
↵
code ↵
↵
int n,l[6],r[6];↵
double dp[6][10009][6][6];↵
double bt(int i,int maxi,int eq,int gr)↵
{↵
if(i==n)↵
{↵
if(eq+gr>1&&gr<=1)↵
return maxi;↵
else↵
return 0;↵
}↵
if(dp[i][maxi][eq][gr]!=-1)↵
return dp[i][maxi][eq][gr];↵
double ret;↵
if(maxi>=l[i]&&maxi<=r[i])↵
{↵
if(gr)↵
ret=((maxi-l[i])*bt(i+1,maxi,eq,gr)+bt(i+1,maxi,eq+1,gr))/(r[i]-l[i]+1);↵
else↵
ret=((maxi-l[i])*bt(i+1,maxi,eq,0)+bt(i+1,maxi,eq+1,0)+(r[i]-maxi)*bt(i+1,maxi,eq,1))/(r[i]-l[i]+1);↵
}↵
else if(maxi>r[i])↵
return bt(i+1,maxi,eq,gr);↵
else if(maxi<l[i])↵
return bt(i+1,maxi,eq,gr+1);↵
return dp[i][maxi][eq][gr]=ret;↵
}↵
↵
int main()↵
{↵
cin>>n;↵
for(int f=0;f<n;f++)↵
{↵
cin>>l[f]>>r[f];↵
}↵
for(int f1=0;f1<6;f1++)↵
for(int f2=0;f2<10009;f2++)↵
for(int f3=0;f3<6;f3++)↵
for(int f4=0;f4<6;f4++)↵
dp[f1][f2][f3][f4]=-1;↵
↵
double ans=0;↵
for(int f=0;f<10009;f++)↵
{↵
ans+=bt(0,f,0,0);↵
}↵
cout<<setprecision(9)<<fixed<<ans<<endl;↵
}i wonder how this solution not TLE it is 1009*1009*6*6*6 which is TLE
http://codeforces.com/contest/513/problem/C↵
↵
the solution is ↵
http://codeforces.com/contest/513/submission/9761274↵
↵
↵
int n,l[6],r[6];↵
double dp[6][10009][6][6];↵
double bt(int i,int maxi,int eq,int gr)↵
{↵
if(i==n)↵
{↵
if(eq+gr>1&&gr<=1)↵
return maxi;↵
else↵
return 0;↵
}↵
if(dp[i][maxi][eq][gr]!=-1)↵
return dp[i][maxi][eq][gr];↵
double ret;↵
if(maxi>=l[i]&&maxi<=r[i])↵
{↵
if(gr)↵
ret=((maxi-l[i])*bt(i+1,maxi,eq,gr)+bt(i+1,maxi,eq+1,gr))/(r[i]-l[i]+1);↵
else↵
ret=((maxi-l[i])*bt(i+1,maxi,eq,0)+bt(i+1,maxi,eq+1,0)+(r[i]-maxi)*bt(i+1,maxi,eq,1))/(r[i]-l[i]+1);↵
}↵
else if(maxi>r[i])↵
return bt(i+1,maxi,eq,gr);↵
else if(maxi<l[i])↵
return bt(i+1,maxi,eq,gr+1);↵
return dp[i][maxi][eq][gr]=ret;↵
}↵
↵
int main()↵
{↵
cin>>n;↵
for(int f=0;f<n;f++)↵
{↵
cin>>l[f]>>r[f];↵
}↵
for(int f1=0;f1<6;f1++)↵
for(int f2=0;f2<10009;f2++)↵
for(int f3=0;f3<6;f3++)↵
for(int f4=0;f4<6;f4++)↵
dp[f1][f2][f3][f4]=-1;↵
↵
double ans=0;↵
for(int f=0;f<10009;f++)↵
{↵
ans+=bt(0,f,0,0);↵
}↵
cout<<setprecision(9)<<fixed<<ans<<endl;↵
}