제출 #1336751

#제출 시각아이디문제언어결과실행 시간메모리
1336751WarinchaiCollecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
0 ms348 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int pos[205];
int t[205];
int dis[205][205];
int rr[205][205];
int ll[205][205];
int n,l;
int inf=1e18;

struct info{
    int c,cnt,id,ll,rr;
    info(int _c,int _cnt,int _id,int _ll,int _rr){
        c=_c,cnt=_cnt,id=_id,ll=_ll,rr=_rr;
    }
    friend bool operator<(info a,info b){
        if(a.c==b.c){
            if(a.cnt==b.cnt){
                if(a.ll==b.ll){
                    return a.rr>b.rr;
                }return a.ll<b.ll;
            }else return a.cnt>b.cnt;
        }else return a.c>b.c;
    }
};

int g(int a,int b){
    return min(abs(a-b),l-abs(a-b));
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>l;
    for(int i=1;i<=n;i++)cin>>pos[i];
    for(int i=1;i<=n;i++)cin>>t[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=inf;
    priority_queue<info,vector<info>>pq;
    for(int i=1;i<=n;i++){
        int ll=n+1,rr=0;
        int f=0;
        int x=pos[i]-l;
        if(x<0)x+=l,f=1;
        if(x<=t[i])pq.push(info(x,1,i,f?ll:min(ll,i),f?max(rr,i):rr));
        f=0,x=l-pos[i];
        if(x<0)x+=l,f=1;
        if(x<=t[i])pq.push(info(x,1,i,f?ll:min(ll,i),f?max(rr,i):rr));
    }
    int ans=0;
    while(!pq.empty()){
        auto temp=pq.top();
        pq.pop();
        int c=temp.c,cnt=temp.cnt,id=temp.id,ll=temp.ll,rr=temp.rr;
        if(dis[id][cnt]<=c)continue;
        //cerr<<id<<" "<<cnt<<" "<<c<<" "<<rr<<" "<<ll<<'\n';
        dis[id][cnt]=c;
        if(c<=inf)ans=max(ans,cnt);
        for(int i=rr+1;i<ll;i++){
            if(i==id)continue;
            int f=0;
            int x=pos[i]-pos[id];
            if(x<0)x+=l,f=1;
            if(x+c<=t[i])pq.push(info(x+c,cnt+1,i,f?ll:min(ll,i),f?max(rr,i):rr));
            f=0,x=pos[id]-pos[i];
            if(x<0)x+=l,f=1;
            if(x+c<=t[i])pq.push(info(x+c,cnt+1,i,f?ll:min(ll,i),f?max(rr,i):rr));
        }
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...