Submission #72554

#	Time	Username	Problem	Language	Result	Execution time	Memory
72554		호우주의보 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	0 / 100	4 ms	288 KiB

hill

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct A/// �Ѵ� 2�� ���صα�
{
    ll S,M;
    bool operator<(const A&Tt)const{return S*Tt.M<Tt.S*M;}
    bool operator==(const A&Tt)const{return S==Tt.S&&Tt.M==M;}
    A operator+(A&Tt)
    {
        return (A){S+Tt.S,M+Tt.M};
    }
    ll SPC()
    {
        return S/2*M;
    }
    ll CST(A&Tt)///Tt�� �Ʒ�����
    {
        return (*this+Tt).SPC()-(SPC()+Tt.SPC()+M*Tt.S);
    }
}EP;
struct AB
{
    A F;
    list<A>::iterator S;
    bool operator<(const AB&Tt)const{return F<Tt.F;}
};
int N,C;
list<A>L;
set<AB>S;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>C;
    int T;cin>>T;
    for(int i=1;i<N;i++)
    {
        int P;
        cin>>P;
        L.push_back({0,P-T});T=P;
    }
    cin>>T;
    for(auto&I:L)
    {
        int P;
        cin>>P;
        I.S=P-T;
        T=P;
    }
    EP=*L.begin();
    for(auto I=L.begin();I!=L.end();I++)S.insert({*I,I});
    while(S.empty()||(*(--S.end())).F==EP)
    {
        auto TT=(*(--S.end())).S,TP=TT;TP--;
        auto RMK=(*TP+*TT);
        if((C-=(*TT).CST(*TP))<0)break;
        S.erase({*TT,TT});
        S.erase({*TP,TP});
        L.insert(TT,RMK);
        L.erase(TT);
        L.erase(TP);
    }
    printf("%lld/%lld",(*(--S.end())).F.S,(*(--S.end())).F.M);
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 68