Submission #1337731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337731		JungPS	Mobile (BOI12_mobile)	C++20	0 / 100	162 ms	57580 KiB

mobile

#include<bits/stdc++.h>
using namespace std;

int x[1000007],y[1000007];
vector<pair<int,pair<long double,long double>>> vec;

long double dist(long double a,long double b,long double c,long double d){
    return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,l; cin >> n >> l;
    for(int i=1;i<=n;++i){
        cin >> x[i] >> y[i];
    }
    stack<pair<int,pair<long double,long double>>> st;
    long double cx=0;
    for(int r=1;r<=n;++r){
        if(st.empty()) st.push({r,{x[r],y[r]}});
        else{
            pair<int,int> prev=st.top().second;
            pair<int,int> cur={x[r],y[r]};
            int previd=st.top().first;
            int curid=r;
            long double a=prev.first;
            long double b=prev.second;
            long double c=cur.first;
            long double d=cur.second;
            long double tx=(c*c+d*d-a*a-b*b)/(2*(c-a));
            if(tx<cx || tx>c) continue;
            if(previd==1){
                vec.push_back({st.top().first,{0,tx}});
            }
            else{
                vec.push_back({st.top().first,{vec[vec.size()-1].second.second,tx}});
            }
            //cout << "LESS THAT" << tx << ":" << st.top().first << endl;
            //cout << "AFTER THAT" << tx << ":" << r << endl;
            cx=tx;
            st.pop();
            st.push({r,cur});
        }
    }
    vec.push_back({st.top().first,{vec[vec.size()-1].second.second,l}});
    long double mx=0;
    for(auto i:vec){
        mx=max(dist(x[i.first],y[i.first],i.second.first,0),mx);
        mx=max(dist(x[i.first],y[i.first],i.second.second,0),mx);
        //cout << "from " << i.second.first << " to " << i.second.second << " use " << i.first << endl;
    }
    cout << mx;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5