제출 #1198552

#제출 시각아이디문제언어결과실행 시간메모리
1198552Born_To_LaughBalloons (CEOI11_bal)C++17
10 / 100
97 ms7492 KiB
// Born_To_Laugh - Hughie Do #include <bits/stdc++.h> #define alle(sth) sth.begin(), sth.end() using namespace std; typedef long long ll; typedef long double ld; [[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7; const int maxn = 2e5 + 10; int n; vector<int> x(maxn, 0), r(maxn, 0); vector<ld> val(maxn, 0.0); ld func(int i, int j){ ld num = (ld)(x[i] - x[j]) * (x[i] - x[j]); ld num1 = (ld)4 * val[j]; return num / num1; } void solve(){ cin >> n; for(int i=1; i<=n; ++i){ cin >> x[i] >> r[i]; } vector<int> st; for(int i=1; i<=n; ++i){ while(!st.empty() && func(i, st.back()) > val[st.back()]){ // cout << func(i, st.back()) << ' ' << val[st.back()]; st.pop_back(); } if(st.empty()) val[i] = (ld)r[i]; else { val[i] = func(i, st.back()); // cout << i << ' ' << st.back() << '\n'; } val[i] = min(val[i], (ld)r[i]); st.push_back(i); cout << val[i] << '\n'; } // cout << func(3, 1); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(7); solve(); } // Lotus
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...