Submission #1125383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125383		barkolorious	Balloons (CEOI11_bal)	C++20	10 / 100	363 ms	5388 KiB

bal

// barkolorious - 09 December 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

// #define USACO
#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define all(v) (v).begin(), (v).end()
#define int long long
#define pb  push_back
#define sz  size
#define fr  first
#define sc  second
#define __  << " " << 

const int MAXN = 2e5 + 5;
double x[MAXN], r[MAXN];

double calc (int i, int j) {
  return ((x[i] - x[j]) * (x[i] - x[j])) / (4.0 * r[i]);
}

void solve () {
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> x[i] >> r[i];
  stack<int> st;

  for (int i = 0; i < n; i++) {
    double y = r[i];
    while (!st.empty() && calc(st.top(), i) <= y) {
      y = min(y, calc(st.top(), i));
      st.pop();
    }
    r[i] = y;
    st.push(i); 
  }

  cout << fixed << setprecision(3);
  for (int i = 0; i < n; i++) cout << r[i] << endl;
}

/*
-- Sample 1 --
Input:
3
0 9
8 1
13 7
Output:
9.000
1.000
4.694
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\CEOI11\COI11_bal.cpp" -o _run
*/

int32_t main () {
  #if !defined(LOCAL)
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #if defined(LOCAL)
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #elif defined(USACO)
    FILE* __FILE_IN__ = FIN("usaco");
    FILE* __FILE_OUT__ = FOUT("usaco");
  #endif

  solve();

  #if defined(LOCAL)
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #elif defined(USACO)
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
  #endif

  return 0;
}

• Subtask 1: 0 / 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