Submission #1198344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198344		user736482	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	16 ms	3132 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,m,a;
vector<ll>v1,v2;
ll dp[100007][2];
ll pop[100007][2];
bool last;//1 to prawo

bool czy(ll x){
    ll ak=0;
    for(ll i=0;i<n;i++){
        vector<ll>v;
        for(;v2[ak]<v1[i];ak++){
            v.pb(v2[ak]);
        }
        v.pb(v1[i]);
        if(!i){
            dp[0][0]=0;
            if(v[0]+x<v1[i])dp[0][0]=-INFL;
            dp[0][1]=v1[i]-v[0]+1;
        }
        else{
            dp[i][0]=-INFL;
            dp[i][1]=INFL;
            pop[i][0]=1;
            pop[i][1]=0;
            if(dp[i-1][1]+v1[i]-v1[i-1]<=x || (dp[i-1][1]==0 && *lower_bound(v.begin(),v.end(),v1[i-1]+1)+x>=v1[i]))dp[i][0]=max(0LL,max(dp[i][0],x-v1[i]+v1[i-1]));
            if(v[0]+x>=v1[i]){dp[i][0]=max(0LL,max(dp[i][0],dp[i-1][0]-v1[i]+v1[i-1]));
                if(dp[i][0]==max(0LL,dp[i-1][0]-v1[i]+v1[i-1]))pop[i][0]=0;            
            }
            dp[i][1]=min(dp[i][1],max(dp[i-1][1]+v1[i]-v1[i-1],v1[i]-v[0]));
            if(dp[i][0]>=0)dp[i][1]=min(dp[i][1],v1[i]-*lower_bound(v.begin(),v.end(),v1[i-1]+1+dp[i-1][0]));
            if(dp[i][0]==max(dp[i-1][1]+v1[i]-v1[i-1],v1[i]-v[0]))pop[i][1]=1;
            
        }
    }
    if(v2.back()-v1.back()-dp[n-1][0]<=0){
        last=0;
        return 1;
    }
    if(v2.back()-v1.back()<=x && dp[n-1][1]==0){
        last=1;
        return 1;
    }
    return 0;
    
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>a;
        v1.pb(a);
    }
    for(ll i=0;i<m;i++){
        cin>>a;
        if(*lower_bound(v1.begin(),v1.end(),a)==a)continue;
        v2.pb(a);
    }
    ll pocz=0;
    ll kon=INFL/5;
    while(pocz!=kon){
        ll mid=(pocz+kon)/2;
        if(czy(mid))kon=mid;
        else pocz=mid+1;
    }
    if(kon==INFL/5){
        cout<<-1;return 0;
    }
    cout<<kon<<"\n";
    string s;
    for(ll i=0;i<n;i++){
        if(last)s.pb('R');
        else s.pb('L');
        last=pop[n-1-1][last];
    }
    reverse(s.begin(),s.end());cout<<s;
}

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