Submission #463879

#	Time	Username	Problem	Language	Result	Execution time	Memory
463879		training4usaco	Balloons (CEOI11_bal)	C++11	100 / 100	239 ms	8524 KiB

bal

#include <iostream>
#include <vector>
using namespace std;
#define MAXN 200000

int x[MAXN + 1], r[MAXN + 1], sta[MAXN + 1], st;
double ans[MAXN + 1];
int n;

int eps(double x) {  
    return x < -1e-10 ? -1 : x > 1e-10;
}
double sqr(double x) {
    return x * x;
}
void downdate(double &a, double b){  
    return (void)((eps(a - b) > 0) ? (a = b) : 0);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> r[i];
    }
    ans[sta[st = 1] = 1] = r[1];
    for (int i = 2; i <= n; sta[++st] = i++) {
        for (ans[i] = r[i]; st && (downdate(ans[i], sqr(x[i] - x[sta[st]])/(4.0 * ans[sta[st]])), eps(ans[i] - ans[sta[st]]) >= 0); --st);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%.3f\n", ans[i]);
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10