Submission #1207736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207736		catsarecool5530	Balloons (CEOI11_bal)	C++20	20 / 100	93 ms	15020 KiB

bal

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n";
#define all(x) x.begin(), x.end()
#define int long long
int MOD = 1e9 + 7;
const ll INF = 1e18;


void solve() {
    int n; cin >> n;
    vector<array<int, 2>> balloons(n);
    for (int i = 0; i < n; i++) {
        cin >> balloons[i][0] >> balloons[i][1];
    }
    vector<array<long double, 2>> stack;
    // stack[i] = {x coord, height}
    vector<long double> ans(n);
    for (int i = 0; i < n; i++) {
        int x = balloons[i][0];
        long double curLowest = 1e18;
        for (int j = stack.size() - 1; j >= 0; j--) {
            if ((x-stack[j][0]) / 2 / sqrt(stack[j][1]) < curLowest) {
                curLowest = (x - stack[j][0]) / 2 / sqrt(stack[j][1]);
                if (j < stack.size() - 1) {
                    stack.pop_back();
                }
            } else {
                break;
            }
        }
        ans[i] = min((long double) balloons[i][1], curLowest * curLowest);
        stack.push_back({(long double) x, min((long double) balloons[i][1], curLowest * curLowest)});
    }
    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(3) << ans[i] << endl;
    }





}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    // freopen("walk.in", "r", stdin);
    // freopen("walk.out", "w", stdout);
    ll t = 1; //cin >> t;
    while (t--) {
        solve();
    }
}

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