# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
4675561 |
Practice:
Kyuubi |
351A
- 34
|
GNU C++
|
Accepted
|
92 ms
|
31380 KB
|
2013-10-05 01:30:29 |
2013-10-05 01:30:31 |
|
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
inline float minOf(float x, float y){return (x<y?x:y);}
inline float maxOf(float x, float y){return (x>y?x:y);}
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin >> n;
int a[4005];
string s;
int pos;
for(int i =1;i<=2*n;i++){
cin >> s;
pos = 0;
while(s[pos]!= '.')
pos++;
pos++;
a[i] = 0;
for(int j = 0;j<3;j++)
a[i] = a[i]*10 + s[pos++]-'0';
}
int dp[4005][2005];
int x,y;
for(int i = 0;i<=2*n;i++){
for(int j = 0; j<=(i<=n?i:n);j++){
if(i == 0){
dp[i][j] = 0;
continue;
}
if(j == 0){
dp[i][j] = dp[i-1][j] - a[i];
continue;
}
x = dp[i-1][j-1] + (((1-a[i])==1)?0:(1000-a[i]));
y = dp[i-1][j]- a[i];
x = x<0.0?-x:x;
y = y<0.0?-y:y;
if(x<y || i == j)
dp[i][j] = dp[i-1][j-1] + (((1-a[i])==1)?0:(1000-a[i]));
else
dp[i][j] = dp[i-1][j]- a[i];
}
}
if(dp[2*n][n] <0)
dp[2*n][n] = -dp[2*n][n];
float ans = dp[2*n][n];
ans /= 1000.00;
cout << fixed;
cout << setprecision(3) << ans << endl;
return 0;
}
Click to see test details