Olimpiade Sains Provinsi (OSP) 2023 - Komputer, Nomor 20–22

Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.

Gambar di atas mengilustrasikan N = 5 situs artefak yang terletak di koordinat A = {3, 12, 15, 21, 40} dan artefak pada situs-situs tersebut mempunyai nilai B = {9, 1, 3, 8, 42}. Pak Dengklek berada di koordinat X = 9 dengan kapasitas bensin mobil K = 20 liter.

Seandainya mobil Pak Dengklek mengalami kerusakan sehingga mobil tersebut hanya dapat berjalan ke kanan (ke arah positif), berapakah jumlah terbesar yang mungkin dari nilai artefak-artefak yang didapat Pak Dengklek?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.

[Gambar: Garis bilangan horizontal dari 0 sampai 40+. Terdapat N = 5 situs arkeologi di koordinat A = {3, 12, 15, 21, 40} dengan nilai artefak B = {9, 1, 3, 8, 42}. Pak Dengklek berada di koordinat X = 9 dengan kapasitas bensin mobil K = 20 liter.]

Pak Dengklek sudah memperbaiki mobilnya. Dengan kondisi Pak Dengklek dapat mengubah arah sesuai keinginannya, berapakah jumlah terbesar yang mungkin dari nilai artefak-artefak yang didapat Pak Dengklek?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MENGUMPULKAN ARTEFAK

Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan jumlah terbesar yang mungkin dari nilai artefak-artefak yang didapat Pak Dengklek, dengan ketentuan sebagai berikut:

Format Masukan:
Baris pertama berisi tiga buah bilangan: N (banyaknya situs arkeologi), K (kapasitas bensin mobil Pak Dengklek), dan X (posisi Pak Dengklek dan mobilnya pada awalnya). Baris kedua berisi N buah bilangan bulat yang menyatakan nilai-nilai A₁, A₂, A₃, …, A_N yaitu posisi koordinat tiap situs arkeologi. Baris ketiga berisi N buah bilangan bulat yang menyatakan nilai-nilai B₁, B₂, B₃, …, B_N yaitu nilai dari artefak yang terletak di tiap situs arkeologi.

Format Keluaran:
Sebuah baris berisi sebuah bilangan bulat yang menyatakan maksimum jumlah nilai artefak yang dapat dikumpulkan.

Peringatan: Untuk dapat menjawab pertanyaan ini dengan benar, program Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!

Contoh Masukan dan Keluaran:

4 3 5
0 4 6 10
135 72 7 1273

79

1 1273 969345
969345
15073

15073

Penjelasan Contoh:
Pada contoh pertama, Pak Dengklek tidak bisa mencapai situs pertama, karena jarak dari posisi awal Pak Dengklek dengan situs pertama adalah X - A₁ = 5 dan mobil dengan kapasitas bensin 3 liter tidak bisa menempuh jarak lebih dari 3 satuan. Pak Dengklek juga tidak bisa mencapai situs keempat. Dengan bensin 3 liter, Pak Dengklek bisa mendapatkan artefak yang terletak di situs kedua dan situs ketiga dengan cara berikut:

• Pak Dengklek bergerak ke kiri sebanyak 1 satuan. Sekarang, Pak Dengklek berada di koordinat 4 dan mendapatkan artefak bernilai 72 dari situs kedua yang terletak di koordinat tersebut. Bensin mobil Pak Dengklek tersisa 2 liter.
• Pak Dengklek bergerak ke kanan sebanyak 1 satuan. Sekarang, Pak Dengklek berada di koordinat 5 dan tidak mendapatkan artefak. Bensin mobil Pak Dengklek tersisa 2 liter.
• Pak Dengklek bergerak ke kanan sebanyak 1 satuan. Sekarang, Pak Dengklek berada di koordinat 6 dan mendapatkan artefak bernilai 7 dari situs ketiga yang terletak di koordinat tersebut. Bensin mobil Pak Dengklek tersisa 0 liter.

Pada contoh kedua, Pak Dengklek mendapatkan artefak pada satu-satunya situs arkeologi tanpa menggunakan mobilnya. Perhatikan bahwa kita bisa menggunakan mobil tersebut untuk melewati situs arkeologi tersebut berulang kali, akan tetapi nilai artefak hanya akan terhitung sekali.

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ N ≤ 100 000
• 0 ≤ K, X, A_i ≤ 10⁹
• A₁ < A₂ < … < A_N
• 0 ≤ B_i ≤ 10⁹

Subtask 1 (20%)
Subtask ini hanya berisi satu kasus uji, yaitu sebagai berikut:

10 67 25
0 7 19 23 32 34 69 92 101 123
23 64 56 26 43 35 72 55 14 25

Subtask 2 (30%)
Pada subtask ini, dijamin bahwa:

• N ≤ 500
• K, X, A_i ≤ 5 000

Subtask 3 (50%)
Tidak ada batasan tambahan.