Submission #72775

#	Time	Username	Problem	Language	Result	Execution time	Memory
72775		leehosu01	Hill Reconstruction (FXCUP3_hill)	C++17	0 / 100	2 ms	248 KiB

hill

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct A/// 둘다 2를 곱해두기
{
    ll S,M,c;
    bool operator<(const A&Tt)const{return S*Tt.M==Tt.S*M?c<Tt.c: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,max(c,Tt.c)};
    }
    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;}
};
ll gcd(ll a, ll b)
{
    return b?gcd(b,a%b):a;
}
int N,C;
list<A>L;
set<AB>S;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>C;C<<=2;
    ll T;cin>>T;
    for(int i=1;i<N;i++)
    {
        ll P;
        cin>>P;
        L.push_back({0,P-T<<1,i});T=P;
    }
    cin>>T;
    for(auto&I:L)
    {
        ll P;
        cin>>P;
        I.S=P-T<<1;
        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});
        *TT=RMK;
        S.insert({*TT,TT});
        L.erase(TP);
    }
    ll TT=gcd((*(--S.end())).F.S,(*(--S.end())).F.M);
    printf("%lld/%lld",(*(--S.end())).F.S/TT,(*(--S.end())).F.M/TT);
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:45:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         L.push_back({0,P-T<<1,i});T=P;
                        ~^~
hill.cpp:52:14: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         I.S=P-T<<1;
             ~^~

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