fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int n, m;
  10.     cin >> n >> m;
  11.     vector<ll> a(n), b(n), c(m);
  12.     ll A = 0;
  13.     for(int i = 0; i < n; i++){
  14.         cin >> a[i];
  15.         A = max(A, a[i]);
  16.     }
  17.     for(int i = 0; i < n; i++){
  18.         cin >> b[i];
  19.     }
  20.     for(int j = 0; j < m; j++){
  21.         cin >> c[j];
  22.     }
  23.  
  24.     // 1) best[x] = min(a_i - b_i) over all i with a_i <= x
  25.     const ll INF = (ll)1e18;
  26.     vector<ll> best(A+1, INF);
  27.     for(int i = 0; i < n; i++){
  28.         ll delta = a[i] - b[i];
  29.         best[a[i]] = min(best[a[i]], delta);
  30.     }
  31.     // prefix-min so that best[x] = min over all a_i <= x
  32.     for(int x = 1; x <= A; x++){
  33.         best[x] = min(best[x], best[x-1]);
  34.     }
  35.  
  36.     // 2) ans[x] = max XP from exactly x ingots when x <= A
  37.     vector<ll> ans(A+1, 0);
  38.     for(int x = 1; x <= A; x++){
  39.         if(best[x] == INF){
  40.             // can't do even one forge+ melt cycle
  41.             ans[x] = 0;
  42.         } else {
  43.             // one cycle costs best[x] ingots and gives 2 XP
  44.             ans[x] = 2 + ans[x - best[x]];
  45.         }
  46.     }
  47.  
  48.     // 3) Process each metal pile c[j]
  49.     ll res = 0;
  50.     ll dA = best[A];  // the cheapest cycle cost at A
  51.     for(ll x : c){
  52.         if(x <= A){
  53.             res += ans[x];
  54.         } else {
  55.             // first do k cycles to bring x down to <= A
  56.             ll need = x - A;
  57.             ll k = (need + dA - 1) / dA;  // ceil(need / dA)
  58.             ll rem = x - k * dA;          // now rem <= A
  59.             res += 2*k + ans[rem];
  60.         }
  61.     }
  62.  
  63.     cout << res << "\n";
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
5 3
9 6 7 5 5
8 4 5 1 2
10 4 7
stdout
copy 
12
https://ideone.com/KupNp2
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!