제출 #1336683

#제출 시각아이디문제언어결과실행 시간메모리
1336683alexddAmbulance (JOI25_ambulance)C++20
5 / 100
124 ms26240 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int L,n,t;
int x[165], y[165];
vector<int> cx, cy;
vector<int> ord1, ord2;
int f1(int a)
{
    return x[a] + y[a];
}
bool cmp1(int a, int b)
{
    if(f1(a) != f1(b))
        return f1(a) < f1(b);
    return x[a] < x[b];
}
int f2(int a)
{
    return x[a] + L - y[a];
}
bool cmp2(int a, int b)
{
    if(f2(a) != f2(b))
        return f2(a) < f2(b);
    return x[a] < x[b];
}
int dist(int i, int c)
{
    return abs(x[i] - cx[c]) + abs(y[i] - cy[c]);
}
vector<int> who[165];

int dp[4][10005][165];

bool solve(int lim1)
{
    for(int i=1;i<=n;i++)
        who[i].clear();
    for(int i=0;i<lim1;i++)
        who[ord1[i]].push_back(0);
    for(int i=lim1;i<ord1.size();i++)
        who[ord1[i]].push_back(2);

    /*
    for(int i=0;i<lim2;i++)
        who[ord2[i]].push_back(1);
    for(int i=lim2;i<ord2.size();i++)
        who[ord2[i]].push_back(3);
    */

    for(int i=0;i<ord2.size();i++)
        who[ord2[i]].push_back(3);

    for(int c1=0;c1<=1;c1++)
    {
        for(int sum=0;sum<=t;sum++)
            dp[c1][sum][0] = INF;
        dp[c1][0][0] = 0;
    }
    for(int lim2=1;lim2<=n;lim2++)
    {
        assert(lim2-1 >= 0);
        int i = ord2[lim2-1];
        assert(who[i][1] == 3);
        who[i][1] = 1;
        //add i to new zone

        int c1 = who[i][0], c2 = who[i][1];
        if(c2 != (c1+1)%4)
            swap(c1, c2);
        assert(c2 == (c1+1)%4);
        assert(c1 == 0 || c1 == 1);
        for(int sum=0;sum<=t;sum++)
        {
            dp[c1][sum][lim2] = INF;
            dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum][lim2 - 1] + dist(i,c2));
            if(sum - dist(i,c1) >= 0) dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum - dist(i,c1)][lim2 - 1]);
            if(sum >= 1) dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum - 1][lim2]);

            dp[1-c1][sum][lim2] = dp[1-c1][sum][lim2 - 1];
        }
    }

    for(int i=1;i<=n;i++)
        assert(who[i][1] == 1);
    for(int c1=2;c1<=3;c1++)
    {
        for(int sum=0;sum<=t;sum++)
            dp[c1][sum][n] = INF;
        dp[c1][0][n] = 0;
    }
    for(int lim2=n-1;lim2>=0;lim2--)
    {
        assert(lim2 < n);
        int i = ord2[lim2];
        assert(who[i][1] == 1);
        who[i][1] = 3;
        //add i to new zone

        int c1 = who[i][0], c2 = who[i][1];
        if(c2 != (c1+1)%4)
            swap(c1, c2);
        assert(c2 == (c1+1)%4);
        assert(c1 == 2 || c1 == 3);
        for(int sum=0;sum<=t;sum++)
        {
            dp[c1][sum][lim2] = INF;
            dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum][lim2 + 1] + dist(i,c2));
            if(sum - dist(i,c1) >= 0) dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum - dist(i,c1)][lim2 + 1]);
            if(sum >= 1) dp[c1][sum][lim2] = min(dp[c1][sum][lim2], dp[c1][sum - 1][lim2]);

            dp[5-c1][sum][lim2] = dp[5-c1][sum][lim2 + 1];
        }
    }

    for(int lim2=0;lim2<=n;lim2++)
    {
        for(int p=0;p<=t;p++)
        {
            int ramase[4] = {t, t, t, t};
            ramase[0] -= p;
            ramase[1] -= dp[0][p][lim2];
            for(int c1=1;c1<=3;c1++)
            {
                if(ramase[c1] < 0)
                    break;
                int c2 = (c1+1)%4;
                ramase[c2] -= dp[c1][ramase[c1]][lim2];
                ramase[c1] = 0;
            }
            if(min({ramase[0],ramase[1],ramase[2],ramase[3]}) >= 0)
                return 1;
        }
    }
    return 0;
}
signed main()
{
    cin>>L>>n>>t;
    L--;
    t /= 2;
    cx = {0, 0, L, L};
    cy = {0, L, L, 0};
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        x[i]--;
        y[i]--;
        ord1.push_back(i);
        ord2.push_back(i);
    }
    sort(ord1.begin(), ord1.end(), cmp1);
    sort(ord2.begin(), ord2.end(), cmp2);
    for(int lim1=0;lim1<=n;lim1++)
    {
        if(solve(lim1))
        {
            cout<<"Yes";
            exit(0);
        }
    }
    cout<<"No";
    return 0;
}
#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...