Submission #1041150

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1041150	2024-08-01 16:07:30	Lucpp	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	494 ms	8580 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)
constexpr ll inf = 1e9 + 10;
int main(){
  cin.tie(0)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<ll> s(n), f(m);
  for(ll& e : s) cin >> e;
  for(ll& e : f) cin >> e;
  auto check = [&](ll len) -> string {
    vector<int> dp(n+1, -1);
    dp[0] = 0;
    vector<pair<int, string>> prv(n+1);
    for(int i = 0; i < n; i++){
      ll nxtf = dp[i] < m ? f[dp[i]] : inf;
      if(nxtf + len < s[i]) continue;
      vector<tuple<int, int, string>> opts;
      opts.emplace_back(i+1, upper_bound(all(f), s[i]) - f.begin(), "L");
      if(nxtf >= s[i]) opts.emplace_back(i+1, upper_bound(all(f), s[i]+len) - f.begin(), "R");
      if(i < n-1 && s[i+1]-len <= nxtf) opts.emplace_back(i+2, upper_bound(all(f), s[i]+len) - f.begin(), "RL");
      for(auto [i2, x, str] : opts){
        if(dp[i2] < x){
          dp[i2] = x;
          prv[i2] = {i, str};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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