Submission #1329770

#TimeUsernameProblemLanguageResultExecution timeMemory
1329770Zbyszek99Ambulance (JOI25_ambulance)C++20
100 / 100
1534 ms51032 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<pii> amb;
int L,n,T;
int costs[163][4];
pii points[163];
pii points2[163];
int dp[4][163][20001];
int cur_dp[2][20001];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> L >> n >> T;
    amb = {{1,1},{L,1},{L,L},{1,L}};
    vector<pair<pii,int>> vs1,vs2;
    rep(i,n)
    {
        cin >> points[i].ff >> points[i].ss;
        rep(d,4) costs[i][d] = (abs(points[i].ff-amb[d].ff)+abs(points[i].ss-amb[d].ss))*2;
        vs1.pb({{points[i].ss-points[i].ff,points[i].ff+points[i].ss},i});
        vs2.pb({{points[i].ff+points[i].ss,points[i].ss-points[i].ff},i});
    }
    sort(all(vs1));
    sort(all(vs2));
    int p1 = 1;
    int p2 = 1;
    forall(it,vs1) points2[it.ss].ff = p1++;
    forall(it,vs2) points2[it.ss].ss = p2++;
    vi vert = {-1};
    forall(it,vs2) vert.pb(it.ss);
    p2--;
    rep2(b1,0,p1)
    {
        rep(d,2) rep2(i,0,T) cur_dp[d][i] = T+1;
        rep(d,2) cur_dp[d][0] = 0;
        rep2(i,0,p2)
        {
            if(i != 0)
            {
                if(points2[vert[i]].ff < b1)
                {
                    for(int j = T; j >= costs[vert[i]][0]; j--) cur_dp[0][j] = min(cur_dp[0][j]+costs[vert[i]][1],cur_dp[0][j-costs[vert[i]][0]]);
                    for(int j = min(T,costs[vert[i]][0]-1); j >= 0; j--) cur_dp[0][j] += costs[vert[i]][1];
                }
                else
                {
                    for(int j = T; j >= costs[vert[i]][3]; j--) cur_dp[1][j] = min(cur_dp[1][j]+costs[vert[i]][0],cur_dp[1][j-costs[vert[i]][3]]);
                    for(int j = min(T,costs[vert[i]][3]-1); j >= 0; j--) cur_dp[1][j] += costs[vert[i]][0];
                }
            }
            rep(d,2) rep2(j,0,T) dp[d][i][j] = cur_dp[d][j];
            rep(d,2) rep2(j,1,T) dp[d][i][j] = min(dp[d][i][j],dp[d][i][j-1]);
        }
        rep(d,2) rep2(i,0,T) cur_dp[d][i] = T+1;
        rep(d,2) cur_dp[d][0] = 0;
        for(int i = p2; i >= 0; i--)
        {
            rep(d,2) rep2(j,0,T) dp[d+2][i][j] = cur_dp[d][j];
            rep(d,2) rep2(j,1,T) dp[d+2][i][j] = min(dp[d+2][i][j],dp[d+2][i][j-1]);
            if(i != 0)
            {
                if(points2[vert[i]].ff < b1)
                {
                    for(int j = T; j >= costs[vert[i]][1]; j--) cur_dp[0][j] = min(cur_dp[0][j]+costs[vert[i]][2],cur_dp[0][j-costs[vert[i]][1]]);
                    for(int j = min(T,costs[vert[i]][1]-1); j >= 0; j--) cur_dp[0][j] += costs[vert[i]][2];
                }
                else
                {
                    for(int j = T; j >= costs[vert[i]][2]; j--) cur_dp[1][j] = min(cur_dp[1][j]+costs[vert[i]][3],cur_dp[1][j-costs[vert[i]][2]]);
                    for(int j = min(T,costs[vert[i]][2]-1); j >= 0; j--) cur_dp[1][j] += costs[vert[i]][3];
                }
            }
        }
        //check
        rep2(i,0,p2)
        {
            rep2(j,0,T)
            {
                int p1 = j;
                int p2 = dp[0][i][p1];
                if(p2 > T) continue;
                int p3 = dp[2][i][T-p2];
                if(p3 > T) continue;
                int p4 = dp[3][i][T-p3];
                if(p4 > T) continue;
                if(dp[1][i][T-p4] > T-p1) continue;
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
}
#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...