제출 #638688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638688		m15069	Balloons (CEOI11_bal)	C++17	20 / 100	532 ms	6776 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<int,long double>a, pair<int,long double>b)
  {
    return (a.first - b.first) * (a.first - b.first) / (4.0 * (a.second));
  }

void solve()
{

  int n; cin >> n; 
  stack<pair<int,long double>>st; 
  for(int i = 0 ; i < n; i++)
  {
    int 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: 0 / 10
• Subtask 3: 10 / 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