Cod sursa(job #3231094)

Utilizator ClassicalClassical Classical Data 24 mai 2024 19:28:02
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;
const int N = 400000 + 7;
const ll INF = (ll) 1e18 + 7;
int n, m;
ll d, init[N], update[N], printing[N];

void print(vector<ll> v) {
  cout << " ---> ";
  for (auto &x : v) {
    cout << x << " ";
  }
  cout << "\n";
}

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

 /// freopen ("___input___.txt", "r", stdin);

  cin >> n >> m >> d;
  for (int i = 1; i <= n; i++) {
    cin >> init[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> update[i];
  }

  for (int iq = 1; iq <= m; iq++) {
    vector<ll> cords;

    for (int i = 1; i <= n; i++) {
      cords.push_back(init[i]);
    }
    for (int i = 1; i <= iq; i++) {
      cords.push_back(update[i]);
    }

    sort(cords.begin(), cords.end());

    ll sol = 0;

    for (int position = 0; position < (int) cords.size() - 1; position++) {
      ll dist = cords[position + 1] - cords[position];
      if (dist < d) {
        sol += (d - dist);
      }
    }

    printing[iq] = sol;
  }

  for (int i = 1; i <= m; i++) {
    cout << printing[i] / 2;
    if (printing[i] % 2) {
      cout << ".5";
    }
    cout << " ";
  }
  cout << "\n";
  return 0;
}