Submission #1336675

#TimeUsernameProblemLanguageResultExecution timeMemory
1336675alexddAmbulance (JOI25_ambulance)C++20
0 / 100
735 ms564 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];

bool solve(int lim1, int lim2)
{
    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=1;i<=n;i++)
    {
        assert(who[i].size() == 2);
        if(who[i][0] > who[i][1])
            swap(who[i][0], who[i][1]);
    }

    for(int c1=0;c1<=3;c1++)
    {
        int c2 = (c1+1)%4;
        vector<int> idk;
        for(int i=1;i<=n;i++)
            if(who[i] == vector<int>{c1,c2} || who[i] == vector<int>{c2,c1})
                idk.push_back(i);

        for(int sum=0;sum<=t;sum++)
            dp[c1][sum] = INF;
        dp[c1][0] = 0;
        int maxv = 0;
        for(int i:idk)
        {
            /*for(int sum=0;sum<=t;sum++)
            {
                newdp[c1][sum] = INF;
                if(sum - dist(i,c1) >= 0) newdp[c1][sum] = min(newdp[c1][sum], dp[c1][sum - dist(i,c1)]);
                newdp[c1][sum] = min(newdp[c1][sum], dp[c1][sum] + dist(i,c2));
            }
            for(int sum=0;sum<=t;sum++)
                dp[c1][sum] = newdp[c1][sum];*/
            maxv = min(t, maxv + dist(i,c1));
            for(int sum=maxv;sum>=0;sum--)
            {
                dp[c1][sum] = min(INF, dp[c1][sum] + dist(i,c2));
                if(sum >= dist(i,c1)) dp[c1][sum] = min(dp[c1][sum], dp[c1][sum - dist(i,c1)]);
            }
        }
        for(int sum=1;sum<=t;sum++)
            dp[c1][sum] = min(dp[c1][sum], dp[c1][sum-1]);
    }

    for(int p=0;p<=t;p++)
    {
        /*int ramase[4] = {t, t, t, t};
        ramase[0] -= p;
        ramase[1] -= dp[0][p];
        for(int c1=1;c1<=3;c1++)
        {
            if(ramase[c1] < 0)
                break;
            int c2 = (c1+1)%4;
            ramase[c2] -= dp[c1][ramase[c1]];
            ramase[c1] = 0;
        }
        if(min({ramase[0],ramase[1],ramase[2],ramase[3]}) >= 0)
            return 1;*/
        bool bun=1;
        int cur = p;
        for(int c1=0;c1<=3;c1++)
        {
            cur = t - dp[c1][cur];
            if(cur <= 0)
            {
                bun = 0;
                break;
            }
        }
        if(bun)
            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++)
    {
        for(int lim2=0;lim2<=n;lim2++)
        {
            if(solve(lim1,lim2))
            {
                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...