Submission #1233665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233665		sophiaeternalia	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2096 ms	5020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int int64_t

int n, m;
vector<int> s, f;
string st;

int so(){
    /*if (st!="LLR"){
        return 1e18;
    }*/
    vector<pair<int, int>> je(m, {-1e18, 1e18});
    int a=-1e18, in=0;
    for (int i=0; i<m; i++){
        while (in!=n and s[in]<=f[i]){
            if (st[in]=='R'){
                a=s[in];
            }
            in++;
        }
        je[i].first=a;
        //cout<<a<<" "<<in<<"\n";
    }
    a=1e18;
    in=n-1;
    for (int i=m-1; i>=0; i--){
        while (in!=-1 and s[in]>=f[i]){
            if (st[in]=='L'){
                a=s[in];
            }
            in--;
        }
        je[i].second=a;
    }
    int ma=-1e18;
    for (int i=0; i<m; i++){
        int mi=1e18;
        if (je[i].first!=-1e18){
            mi=min(mi, f[i]-je[i].first);
        }
        if (je[i].second!=1e18){
            mi=min(mi, je[i].second-f[i]);
        }
        ma=max(ma, mi);
    }
    /*for (auto u: je){
        cout<<"--------------->   "<<u.first<<" "<<u.second<<"\n";
    }
    cout<<st<<" "<<ma<<"\n";*/
    return ma;
}

pair<int, string> e(int i){
    if (i==n){
        return {so(), st};
    }
    pair<int, string> a={1e18, ""};
    st.push_back('L');
    a=min(a, e(i+1));
    st[st.size()-1]='R';
    a=min(a, e(i+1));
    st.pop_back();
    return a;
}

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(NULL);

    cin>>n>>m;
    s.resize(n);
    f.resize(m);
    for (int i=0; i<n; i++){
        cin>>s[i];
    }
    for (int i=0; i<m; i++){
        cin>>f[i];
    }
    pair<int, string> a=e(0);
    if (a.first==1e18){
        cout<<-1<<"\n";
        return 0;
    }
    cout<<a.first<<"\n"<<a.second<<"\n";
}

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