Submission #1142494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142494		Mighilon	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	43 ms	1092 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> s(n),f(m);
    for(int i=0;i<n;++i)
        cin>>s[i];
    for(int i=0;i<m;++i)
        cin>>f[i];
    vector<string> dir(n+1);
    auto fun=[&](int k)->bool{
        vector<int> dp(n+1);
        auto update=[&](int i,int j,string x){
            if(dp[i]<=j){
                dp[i]=j;
                dir[i]=x;
            }
        };
        for(int i=0;i<n;++i){
            update(i+1,i,"L");
            if(dp[i]>=m)continue;
            int x=f[dp[i]];
            if(s[i]-k<=x&&x<=s[i]){
                int id=upper_bound(all(f),s[i])-f.begin();
                update(i+1,id,"L");
            }
            if(s[i]<=x&&x<=s[i]+k){
                int id=upper_bound(all(f),s[i]+k)-f.begin();
                update(i+1,id,"R");
            }
            if(i<n-1){
                if(s[i+1]-k<=x&&x<=s[i]+k){
                    int id=upper_bound(all(f),s[i]+k)-f.begin();
                    update(i+2,id,"RL");
                }
            }
        }
        return dp[n]>=m;
    };
    int ans=-1;
    int l=0,r=1e9;
    while(l<=r){
        int m=l+(r-l)/2;
        //cout<<m<<" "<<fun(m)<<endl;
        if(fun(m)){
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    if(!~ans){
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
    string x;
    for(int i=n-1;i>=0;--i){
        if(dir[i+1].size()==1){
            x.push_back(dir[i+1][0]);
        }
        else{
            x.push_back(dir[i+1][1]);
            x.push_back(dir[i+1][0]);
            i--;
        }
    }
    reverse(all(x));
    cout<<x<<endl;
    return 0;
}

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