Kapasitas Angkot
Hitung penumpang yang tertolak karena angkot penuh.
Angkot berkapasitas K orang menyusuri N halte. Di setiap halte, penumpang turun lebih dulu, lalu calon penumpang naik selama masih ada kursi. Calon penumpang yang tidak kebagian kursi tertolak.
Masukan
Baris pertama berisi K (1 sampai 100) dan N (1 sampai 1000). N baris berikutnya masing-masing berisi banyak penumpang turun dan banyak calon penumpang di halte itu. Penumpang yang turun tidak pernah lebih banyak dari isi angkot.
Keluaran
Dua baris: Penumpang tertolak: X dan Isi terbanyak: Y, dengan Y isi angkot terbanyak setelah meninggalkan sebuah halte.
Contoh masukan dan keluaran
Contoh 1
Masukan
12 4 0 8 2 7 5 3 10 9
Keluaran
Penumpang tertolak: 1 Isi terbanyak: 12
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Simpan isi angkot. Di setiap halte, kurangi dengan yang turun, lalu hitung kursi kosong.
Petunjuk 2
Yang naik adalah yang lebih kecil antara calon penumpang dan kursi kosong. Sisanya tertolak.