Submission #1147754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147754		imarn	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	111 ms	3300 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=1e5+5;
int f[mxn],s[mxn],n,m;
pii dp[2][mxn];
int solve(int k){
    dp[0][0]={1,-1};
    dp[1][0]={1,-1};
    int c1=1,c2=1,c3=1;
    for(int i=1;i<=n;i++){
        while(c1<=m&&f[c1]<=s[i])c1++;
        while(c2<=m&&f[c2]-k<=s[i])c2++;
        while(i>1&&c3<=m&&f[c3]-k<=s[i-1])c3++;
        dp[0][i]=max(make_pair(dp[0][i-1].f,0),make_pair(dp[1][i-1].f,1));
        dp[1][i]=max(make_pair(dp[0][i-1].f,0),make_pair(dp[1][i-1].f,1));
        if(s[i]-f[dp[0][i-1].f]<=k)dp[0][i]=max(dp[0][i],{c1,0});
        if(s[i]-f[dp[1][i-1].f]<=k)dp[0][i]=max(dp[0][i],{max(c1,dp[1][i-1].f),1});
        if(f[dp[1][i-1].f]>=s[i])dp[1][i]=max(dp[1][i],{c2,1});
        if(f[dp[0][i-1].f]>=s[i])dp[1][i]=max(dp[1][i],{c2,0});
        if(i>1&&s[i]-f[dp[0][i-2].f]<=k)dp[0][i]=max(dp[0][i],{c3,4});
        if(i>1&&s[i]-f[dp[1][i-2].f]<=k)dp[0][i]=max(dp[0][i],{c3,5});
    }
    return max(dp[0][n],dp[1][n]).f;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=m;i++)cin>>f[i];
    ll l=0,r=2e9;
    while(l<r){
        ll md=(l+r)>>1;
        if(solve(md)>=m+1)r=md;
        else l=md+1;
    }if(l==2e9){cout<<-1;return 0;}
    cout<<l<<'\n';
    solve(l);int cur=0;
    if(dp[1][n].f==m+1)cur=1;
    stack<int>st;
    for(int i=n;i>=1;i--){
        st.push(cur);
        int x=dp[cur][i].s;
        if(x==0||x==1)cur=x;
        if(x==4||x==5)st.push(1),cur=x-4,i--;
    }
    while(!st.empty()){
        cout<<(st.top()==1?'R':'L');st.pop();
    }
}

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