Submission #296206

#	Time	Username	Problem	Language	Result	Execution time	Memory
296206		BThero	Long Distance Coach (JOI17_coach)	C++17	16 / 100	4 ms	3456 KiB

coach

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)2e5 + 5;

struct Person {
  ll st, fee;
  
  Person() {
    st = fee = 0ll;
  }
} arr[MAXN];

ll S[MAXN];
ll X, W, T;
int n, m;

bool bit(int x, int p) {
  return x & (1 << p);
}

void getWater(ll L, ll R, ll st, ll &kl, ll &kr) {
  if (L > R || R < st) {
    kl = kr = -1;
    return;
  }

  // st + kT <= R
  // k <= (R - st) / T
  // st + kT >= L
  // k >= (L - st) / T
  
  kr = (R - st) / T;
  
  if (L < st) {
    kl = 0;
  }
  else {
    kl = (L - st + T - 1) / T;
  }
}

void solve() {
  scanf("%lld %d %d %lld %lld", &X, &n, &m, &W, &T);
  S[0] = -1;
  
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &S[i]);
  }
  
  S[++n] = X;
  
  for (int i = 0; i < m; ++i) {
    scanf("%lld %lld", &arr[i].st, &arr[i].fee);
  }
  
  sort(S, S + n + 1);
  n = unique(S, S + n + 1) - S;
  ll ans = (ll)1e18;
  
  for (int mask = 0; mask < (1 << m); ++mask) {
    ll cur_cost = 0;
    
    for (int i = 0; i < m; ++i) {
      if (!bit(mask, i)) {
        cur_cost += arr[i].fee;
      }
    }
    
    int on_trip = (1 << m) - 1;
    ll water = 0;
    
    for (int i = 0; i + 1 < n; ++i) {
      ll L = S[i] + 1, R = S[i + 1] - 1;
      ll lim = L - 1;
      
      { // for driver
        ll kl, kr;
        getWater(L, R, 0, kl, kr);
        
        if (kr != -1) {
          water += (kr - kl + 1);
          lim = max(lim, kr * T);
        }
      }
    
      for (int j = 0; j < m; ++j) {
        if (bit(mask, j)) {
          // mandatory persons
          ll kl, kr;
          getWater(L, R, arr[j].st, kl, kr);
          
          if (kr != -1 && kl <= kr) {
            lim = max(lim, arr[j].st + T * kr);
            water += (kr - kl + 1);
          }
        }
      }
      
      int new_on_trip = mask;
      
      for (int j = 0; j < m; ++j) {
        if (!bit(mask, j) && bit(on_trip, j)) {
          // have to throw away
          ll kl, kr, kl2, km;
          getWater(L, R, arr[j].st, kl, kr);
          getWater(L, lim, arr[j].st, kl2, km);
          
          if (kr == -1) {
            // does not drink
            new_on_trip += (1 << j);
            continue;
          }
          
          if (arr[j].st + T * kr > lim) {
            // will go away
            
            if (km != -1) {
              water += (km - kl2 + 1);
            }
          }
          else {
            water += (kr - kl + 1);
            new_on_trip += (1 << j);
          }
        }
      }
      
      on_trip = new_on_trip;
    }
    
    //printf("%d - %lld %lld\n", mask, water, water * W + cur_cost);
    ans = min(ans, water * W + cur_cost);
  }
  
  printf("%lld\n", ans);
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message (stderr)

coach.cpp: In function 'void solve()':
coach.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%lld %d %d %lld %lld", &X, &n, &m, &W, &T);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%lld", &S[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
coach.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%lld %lld", &arr[i].st, &arr[i].fee);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29