Submission #1290037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290037		loom	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	460 ms	9300 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

void solve(){
   int n, m;
   cin>>n>>m;

   int s[n+4];
   s[0] = s[1] = s[2] = -inf;
   for(int i = 3; i < n+3; i++) cin>>s[i];
   s[n+3] = inf;

   int f[m+1];
   f[0] = -inf;
   for(int i = 1; i <= m; i++) cin>>f[i];

   int dp[n+4][3];
   pair<int,int> rec[n+4][3];
   int k;

   for(int i : {0, 1, 2}){
      dp[i][0] = dp[i][1] = 0;
      dp[i][2] = 1;
   } 

   auto get = [&](int x){
      int i = lower_bound(f+1, f+m+1, x) - f - 1;
      return f[i];
   };

   auto set = [&](int i, int x, int fi, int fj){
      int p = get(x);
      auto &d = dp[fi][fj];
      auto &r = rec[fi][fj];

      if(dp[i][0] and p <= s[i] + k){ // R
         d = 1;
         r = {i, 0};
      }
      else if(dp[i][1] and p <= s[i-1] + k){ // RL
         d = 1;
         r = {i, 1};
      }
      else if(dp[i][2] and p <= s[i]){ // L
         d = 1;
         r = {i, 2};
      }
   };

   auto check = [&]{
      for(int i = 3; i <= n+3; i++){
         dp[i][0] = dp[i][1] = dp[i][2] = 0;

         // R
         set(i-1, s[i], i, 0);

         // RL
         if(get(s[i] - k) <= s[i-1] + k){
            set(i-2, min(s[i-1], s[i] - k), i, 1);
         }

         // L
         set(i-1, s[i] - k, i, 2);
      }

      return dp[n+3][0];
   };

   int lo = 0, hi = 1e9;
   while(lo < hi){
      k = (lo + hi)/2;

      if(check()) hi = k;
      else lo = k+1;
   }

   k = lo;
   if(!check()){
      cout<<-1<<nl;
      return;
   }

   string ans;
   int i = n+3, j = 0;

   while(i >= 3){
      auto [pi, pj] = rec[i][j];

      if(j == 0) ans += "R";
      if(j == 1) ans += "LR";
      if(j == 2) ans += "L";

      i = pi;
      j = pj;
   }

   reverse(ans.begin(), ans.end());
   ans.pop_back();
   cout<<lo<<nl<<ans;
}

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

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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