제출 #1331061

#제출 시각아이디문제언어결과실행 시간메모리
1331061user736482Ambulance (JOI25_ambulance)C++20
100 / 100
1217 ms50904 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll ple[4][167][10007];
void solve(){
    ll l,n,t,a,b;
    cin>>l>>n>>t;
    t/=2;
    vii pts;
    vii v1;
    for(ll i=0;i<n;i++){
        cin>>a>>b;pts.pb({a,b});
        v1.pb({a+b,i});
    }
    sort(al(v1));
    for(ll k=0;k<=n;k++){
        vii v2,v4;
        for(ll i=0;i<k;i++)v2.pb(pts[v1[i].ss]);
        for(ll i=k;i<n;i++)v2.pb(pts[v1[i].ss]);
        
        for(ll i=0;i<k;i++)v4.pb({v2[i].ff-v2[i].ss,i});
        for(ll i=k;i<n;i++)v4.pb({v2[i].ff-v2[i].ss,-i-1});

        sort(al(v4));
        //cout<<v2<<"\n"<<v4<<"\n";
        for(ll i=0;i<4;i++)for(ll m=0;m<=t;m++)ple[i][0][m]=ple[i][n][m]=0;
        ll sm[4];
        sm[0]=sm[1]=sm[2]=sm[3]=0;
        ll sm2[4][167];
        for(ll i=0;i<=n;i++)sm2[0][i]=sm2[1][i]=sm2[2][i]=sm2[3][i]=0;
        for(ll i=1;i<=n;i++){
            for(ll j=0;j<=t;j++){
                ple[0][i][j]=ple[0][i-1][j];
                ple[3][i][j]=ple[3][i-1][j];
            }
            if(v4[i-1].ss<0){
                ll id=-v4[i-1].ss-1;
                ll ksz=v2[id].ff-1+l-v2[id].ss;
                ll zs=l-v2[id].ff+l-v2[id].ss;
                sm[1]+=zs;
                for(ll j=ksz;j<=t;j++){
                    ple[0][i][j]=max(ple[0][i][j],ple[0][i-1][j-ksz]+zs);
                }
            }
            else{
                ll id=v4[i-1].ss;
                ll ksz=v2[id].ff-1+v2[id].ss-1;
                ll zs=v2[id].ff-1+l-v2[id].ss;
                sm[0]+=zs;
                for(ll j=ksz;j<=t;j++){
                    ple[3][i][j]=max(ple[3][i][j],ple[3][i-1][j-ksz]+zs);
                }
            }
            for(ll j=0;j<4;j++)sm2[j][i]+=sm[j];
        }
        sm[0]=sm[1]=sm[2]=sm[3]=0;
        for(ll i=n-1;i+1;i--){
            for(ll j=0;j<=t;j++){
                ple[1][i][j]=ple[1][i+1][j];
                ple[2][i][j]=ple[2][i+1][j];
            }
            if(v4[i].ss<0){
                ll id=-v4[i].ss-1;
                ll ksz=l-v2[id].ff+l-v2[id].ss;
                ll zs=l-v2[id].ff+v2[id].ss-1;
                sm[2]+=zs;
                for(ll j=ksz;j<=t;j++){
                    ple[1][i][j]=max(ple[1][i][j],ple[1][i+1][j-ksz]+zs);
                }
            }
            else{
                ll id=v4[i].ss;
                ll ksz=l-v2[id].ff+v2[id].ss-1;
                ll zs=v2[id].ff-1+v2[id].ss-1;
                sm[3]+=zs;
                for(ll j=ksz;j<=t;j++){
                    ple[2][i][j]=max(ple[2][i][j],ple[2][i+1][j-ksz]+zs);
                }
            }
            for(ll j=0;j<4;j++)sm2[j][i]+=sm[j];
        }
        // for(ll i=0;i<4;i++){
        //     for(ll j=0;j<=n;j++){
        //         for(ll m=0;m<=t;m++){
        //             cout<<ple[i][j][m]<<" ";
        //         }
        //         cout<<"\n";
        //     }
        //     cout<<"\n";
        // }
        for(ll i=0;i<=n;i++){
            for(ll j=0;j<=t;j++){
                ll ak=j;
                for(ll m=0;m<4;m++){
                    //cout<<ak<<" "<<sm2[(m+1)%4][i]<<"  ";
                    if(ak<0)continue;
                    ak=t+ple[m][i][ak]-sm2[(m+1)%4][i];
                }
                //cout<<ak<<"\n";
                if(ak>=j){
                    cout<<"Yes";return;
                }
            }
            //cout<<"\n";
        }
    }
    cout<<"No";
}
int main(){
    fct[0]=1;
    for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}
#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...