Submission #1193516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193516		Unforgettablepl	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	419 ms	3640 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<int> S(N+1);
    vector<int> F(M+1);
    for(int i=1;i<=N;i++)cin>>S[i];
    for(int i=1;i<=M;i++)cin>>F[i];
    vector<int> turn(N+1); // 1 is right, 2 is twisty
    auto getNext = [&](int x){
        auto iter = upper_bound(F.begin()+1,F.end(),x);
        if(iter==F.end())return -1ll;
        return *iter;
    };
    auto solve = [&](int K){
        vector<int> DP(N+1,-1);
        for(int i=1;i<=N;i++){
            {
                if(getNext(DP[i-1])==-1){
                    DP[i]=DP[i-1];
                    turn[i]=1;
                    continue;
                } else if(getNext(DP[i-1])>=S[i]-K){
                    DP[i]=S[i];
                    turn[i]=0;
                }
                if(getNext(DP[i-1])>=S[i]){
                    DP[i]=S[i]+K;
                    turn[i]=1;
                }
            }
            {
                if(i!=1 and getNext(DP[i-2])>=S[i]-K){
                    if(S[i-1]+K>DP[i]){
                        DP[i]=S[i-1]+K;
                        turn[i]=2;
                    }
                }
            }
        }
        return getNext(DP[N])==-1;
    };
    int ans = -1;
    for(int jump=(1ll<<31);jump;jump/=2){
        if(!solve(ans+jump))ans+=jump;
    }
    ans++;
    if(ans>1e9)cout<<"-1\n";
    else {
        solve(ans);
        cout << ans << '\n';
        for(int i=N;i;i--)if(turn[i]==2){
            turn[i]=0;
            turn[i-1]=1;
            i--;
        }
        for(int i=1;i<=N;i++)if(turn[i])cout<<'R';
            else cout << 'L';
        cout << '\n';
    }
}

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