제출 #1239786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239786		Petrix	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	173 ms	2944 KiB

Main

#include <iostream>

using namespace std;

int s[100001];
int f[100001],n,m;
pair<int,int> dp[100001][2];

bool vf(int k){
    int p1=1,p2=1,p3=1,i;
    dp[0][0]=dp[0][1]={1,0};
    for(i=1;i<=n;i++){
        while(p1<=m && f[p1]<=s[i])
            p1++;
        while(p2<=m && f[p2]<=s[i-1]+k)
            p2++;
        while(p3<=m && f[p3]<=s[i]+k)
            p3++;
        dp[i][0]=dp[i][1]=max(make_pair(dp[i-1][0].first,0),
                              make_pair(dp[i-1][1].first,1));
        if(f[dp[i-1][0].first]>=s[i])
            dp[i][1]=max(dp[i][1],{p3,0});
        if(f[dp[i-1][1].first]>=s[i])
            dp[i][1]=max(dp[i][1],{p3,1});
        if(f[dp[i-1][0].first]>=s[i]-k)
            dp[i][0]=max(dp[i][0],{p1,0});
        if(f[dp[i-1][1].first]>=s[i]-k)
            dp[i][0]=max(dp[i][0],{max(p1,p2),1});

    }
    if(max(dp[n][0].first,dp[n][1].first)>m) return 1;
    return 0;
}
int main()
{
    int st=0,dr=1e9,rasp=-1,i,mij,aux;
    string rasp1;
    cin>>n>>m;rasp1.resize(n);
    for(i=1;i<=n;i++) cin>>s[i];
    for(i=1;i<=m;i++) cin>>f[i];
    s[0]=-1e9;f[m+1]=19;
    while(st<=dr){
        mij=(st+dr)/2;
        if(vf(mij)){
            rasp=mij;dr=mij-1;
        }else st=mij+1;
    }
    if(rasp!=-1){
        vf(rasp);
        if(dp[n][1]>dp[n][0]) aux=1;
        else aux=0;
        for(i=n;i>=1;i--){
            if(!aux) rasp1[i-1]='L';
            else rasp1[i-1]='R';
            aux=dp[i][aux].second;
        }
        cout<<rasp<<"\n"<<rasp1;
        return 0;
    }
    cout<<"-1";
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47