Submission #638725

#	Time	Username	Problem	Language	Result	Execution time	Memory
638725		m15069	Balloons (CEOI11_bal)	C++17	100 / 100	494 ms	5624 KiB

bal

#include<bits/stdc++.h>
using namespace std; 
using ll = long long; 
#define IO ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
const int N = 5e7 + 10;
int tc; 

long double r2(pair<ll,long double>a, pair<ll,long double>b)
  {
    return (a.first - b.first) * (a.first - b.first) / (4.0 * (a.second));
  }

void solve()
{

  long long n; cin >> n; 
  stack<pair<ll,long double>>st; 
  for(int i = 0 ; i < n; i++)
  {
    long long x,r; cin >> x >> r; 
    long double best_ans = r; 
    while(!st.empty())
    {
        long double temp = r2(st.top(), {x,best_ans});
        best_ans = min(temp,best_ans);
        // when to pop? 
        if(best_ans >= st.top().second)st.pop(); 
        else break;
        // cout << i << " " <<  best_ans << '\n';
    }
    st.push({x,best_ans}); // best redius 
    cout << fixed << setprecision(4)<< best_ans << '\n';
  }

}


int main()
{
    // freopen("path.in", "r", stdin);
    // IO
    int t = 1; 
    // get prime numbers using sieve 
    // cin >> t; 
    while(t--)
        {tc++;
          solve(); 
        }
}

• 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