Submission #1074921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074921		anton	Toy (CEOI24_toy)	C++17	0 / 100	0 ms	348 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

vector<int> flowers;
vector<int> sprinklers;


int last_under(vector<int>& v, int x){
    return (upper_bound(v.begin(), v.end(), x) - v.begin())-1;
}

int first_above(vector<int>& v, int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}


pii get_coverage(pii interval){
    return {first_above(flowers, interval.first), last_under(flowers, interval.second)};
}

bool is_in(pii inter, int pos){
    return (pos>=inter.first && pos<=inter.second);
}

int N, M;

struct DP{
    int val= 0;
    int anc =0;
    string p;
    DP(){};
    DP(int _val, int _anc, string s){
        p = s;
        val = _val;
        anc= _anc;
    }
};

void chmax(DP& a, DP b){
    if(b.val>a.val){
        a= b;
    }
}

vector<DP> solve(int k){
    vector<DP> dp(N+1);

    for(int cur_sprinkler = 0; cur_sprinkler<N; cur_sprinkler++){
        int uncovered_flower = dp[cur_sprinkler].val;
        pii before_inter = get_coverage({sprinklers[cur_sprinkler]-k, sprinklers[cur_sprinkler]});
        if(is_in(before_inter, uncovered_flower)){
            chmax(dp[cur_sprinkler+1], DP(before_inter.second+1, cur_sprinkler, string("L")));
        }
        before_inter = get_coverage({sprinklers[cur_sprinkler], sprinklers[cur_sprinkler]+k});
        if(is_in(before_inter, uncovered_flower)){
            chmax(dp[cur_sprinkler+1], DP(before_inter.second+1, cur_sprinkler, string("R")));
        }

        if(cur_sprinkler<N-1){
            if(sprinklers[cur_sprinkler+1]-sprinklers[cur_sprinkler]<k){
                pii interval = {sprinklers[cur_sprinkler+1]-k, sprinklers[cur_sprinkler]+k};
                if(is_in(get_coverage(interval), uncovered_flower)){
                    chmax(dp[cur_sprinkler+2], DP(before_inter.second+1, cur_sprinkler, string("LR")));

                }
            }
        }

        chmax(dp[cur_sprinkler+1], DP(uncovered_flower, cur_sprinkler, string("R")));

    }

    return dp;
}

string res;
void backtrack(vector<DP>& dp, int pos){
    bool ok = true;
    while(ok){
        res.append(dp[pos].p.begin(), dp[pos].p.end());
        pos= dp[pos].anc;
        ok = pos>0;
    }
}
signed main(){
    cin>>N>>M;
    sprinklers.resize(N);

    for(int i = 0; i<N; i++){
        cin>>sprinklers[i];
    }

    int k;
    flowers.push_back(sprinklers[0]);
    for(int i = 0; i<M; i++){
        cin>>k;
        flowers.push_back(k);
    }

    flowers.push_back(sprinklers.back());


    sort(flowers.begin(), flowers.end());
    int K=1e9;

    if(solve(K).back().val != M+2){
        cout<<-1<<endl;
        return 0;
    }

    for(int step = (1<<30); step>=1; step/=2){
        if(K-step>=0 && solve(K-step).back().val == M+2){
            K-=step;
        }
    }

    cout<<K<<endl;
    auto res_dp = solve(K);
    backtrack(res_dp, N);

    reverse(res.begin(), res.end());

    cout<<res<<endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27