Submission #1040488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040488		isaachew	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	409 ms	8724 KiB

Main

#include <bits/stdc++.h>
/*
 DP flowers
 
 
 */
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<int> sprinklers;
    std::vector<int> flowers;
    std::map<int,int> flowerinds;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        sprinklers.push_back(x);
    }
    for(int i=0;i<m;i++){
        int x;
        std::cin>>x;
        flowers.push_back(x);
        flowerinds[x]=i;
    }
    flowerinds[2000000000]=m;
    int lower=0,upper=1000000002;
    while(1){
        int kval=(lower+upper)/2-1;
        if(lower+1>=upper){
            if(lower==1000000001){
                std::cout<<"-1\n";
                return 0;
            }else{
                kval=lower;
            }
        }
        std::vector<std::pair<int,int>> dp(n+1);
        for(int i=0;i<n;i++){
            std::pair<int,int> curval=dp[i];
            dp[i+1]=std::max(dp[i+1],{curval.first,0});//do nothing
            if(curval.first<m){
                if(flowers[curval.first]>=sprinklers[i]-kval){
                    dp[i+1]=std::max(dp[i+1],{flowerinds.upper_bound(sprinklers[i])->second,-1});//left
                }
                if(flowers[curval.first]>=sprinklers[i]){
                    dp[i+1]=std::max(dp[i+1],{flowerinds.upper_bound(sprinklers[i]+kval)->second,1});//right
                }
                if(i+1<n&&sprinklers[i]<=sprinklers[i]+kval){//RL (no holes)
                    if(flowers[curval.first]>=sprinklers[i+1]-kval){
                        dp[i+2]=std::max(dp[i+2],{flowerinds.upper_bound(sprinklers[i]+kval)->second,2});
                    }
                }
            }
        }
        if(lower+1>=upper){
            std::cout<<lower<<'\n';
            std::string rec(n,' ');
            int ind=n;
            while(ind){
                if(dp[ind].second==-1){
                    rec[ind-1]='L';
                    ind--;
                }else if(dp[ind].second==1){
                    rec[ind-1]='R';
                    ind--;
                }else if(dp[ind].second==2){//RL
                    rec[ind-1]='L';
                    rec[ind-2]='R';
                    ind-=2;
                }else{//don't care ("do nothing")
                    rec[ind-1]='L';
                    ind--;
                }
            }
            std::cout<<rec<<'\n';
            return 0;
        }
        if(dp.back().first==m){
            upper=kval+1;
        }else{
            lower=kval+1;
        }
    }
    
}

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