Submission #1178667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178667		alexdd	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	143 ms	16168 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 4e9;
int n,m;
int s[100005],f[100005];
char dir[100005],sol[100005];
map<int,int> mp;

int dp[100005],prec[100005];
bool verif(int k)
{
    dp[0] = -1;
    int poz=0,pozk=0;
    for(int i=1;i<=n;i++)
    {
        int prima = -1, primak = -1;
        /*for(int j=m;j>=1;j--)
        {
            if(f[j] < s[i])
            {
                prima = f[j];
                break;
            }
        }
        for(int j=m;j>=1;j--)
        {
            if(f[j] < s[i] - k)
            {
                primak = f[j];
                break;
            }
        }*/
        while(poz+1<=m && f[poz+1] < s[i])
            poz++;
        while(pozk+1<=m && f[pozk+1] < s[i] - k)
            pozk++;
        if(poz!=0)
            prima = f[poz];
        else
            prima = -1;
        if(pozk != 0)
            primak = f[pozk];
        else
            primak = -1;

        dp[i] = -1;
        if(prima == -1)
        {
            dp[i] = s[i] + k;
            dir[i] = 'R';
            prec[i] = -1;
        }
        else
        {
            for(int j=i-1;j>max(0LL,i-2);j--)
            {
                if(dp[j] >= prima)
                {
                    dp[i] = s[i] + k;
                    prec[i] = j;
                    dir[i] = 'R';
                    break;
                }
            }
        }
        if(dp[i] == -1)
        {
            if(primak == -1)
            {
                dp[i] = s[i];
                prec[i] = -1;
                dir[i] = 'L';
            }
            if(dp[i-1] >= primak)
            {
                if(max(dp[i-1], s[i]) > dp[i])
                {
                    dp[i] = max(dp[i-1], s[i]);
                    prec[i] = i-1;
                    dir[i] = 'L';
                }
            }
            for(int j=i-2;j>=max(i-2,0LL);j--)
            {
                if(dp[j] >= primak)
                {
                    if(s[i-1] + k > dp[i])
                    {
                        dp[i] = s[i-1] + k;
                        prec[i] = j;
                        dir[i] = 'L';
                    }
                }
            }
        }
    }
    return (dp[n] >= f[m]);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        mp[s[i]]++;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>f[i];
        if(mp[f[i]])
        {
            i--;
            m--;
        }
    }
    if(!verif(INF))
    {
        cout<<-1;
        return 0;
    }
    int st=0,dr=INF,ans=INF;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(verif(mij))
        {
            ans = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }
    verif(ans);
    int cur = n;
    while(cur>0)
    {
        if(dir[cur] == 'R')
        {
            sol[cur] = 'R';
            for(int u=cur-1;u>prec[cur];u--)
                sol[u] = 'L';
        }
        else
        {
            sol[cur] = 'L';
            if(dp[cur] == s[cur-1] + ans)
            {
                sol[cur-1] = 'R';
                for(int u=cur-2;u>prec[cur];u--)
                    sol[u] = 'L';
            }
            else
            {
                for(int u=cur-1;u>prec[cur];u--)
                    sol[u] = 'L';
            }
        }
        cur = prec[cur];
    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}
/**

dp[i] = pozitia maxima cu care se pot extinde in dreapta primele i sprinklere daca toate florile <=i au fost acoperite


*/

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