Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <fstream>
- using namespace std;
- ifstream fin("sabotage.in");
- FILE *fout = fopen("sabotage.out", "w");
- double L[100005], M[100005], R[100005];
- int N;
- bool ok(double k)
- {
- for(int i = 1; i <= N; i++)
- L[i] = L[i-1] + M[i] - k;
- double minRight = 999999;
- R[N] = M[N] - k;
- R[N-1] = R[N] + M[N-1] - k;
- for(int i = N-2; i >= 1; i--)
- {
- minRight = min(minRight, R[i+2]);
- if(minRight + L[i] <= 0)
- return true;
- R[i] = R[i+1] + M[i] - k;
- }
- return false;
- }
- int main()
- {
- fin >> N;
- for(int i = 1; i <= N; i++)
- fin >> M[i];
- double a = 1, b = 10005;
- double p = (a+b) / 2;
- for(int i = 1; i <= 100; i++)
- {
- if(ok(p))
- b = p;
- else
- a = p;
- p = (a+b) / 2;
- }
- fprintf(fout, "%.3f\n", p);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement