المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۵:سوال ۷

Padeshah

جشنواره‌ی فیلم فجر در حال برگزاری است و محمد به عنوان داور آن انتخاب شده است. او تصمیم گرفته است تا به ترتیب فیلم‌های $a_0, a_1, \ldots, a_{n - 1}$ را ببیند. توجه کنید که ممکن است محمد یک فیلم را بیش از یک‌بار ببیند.

در این جشنواره، $m$ سینما در جشنواره‌ی فیلم فجر در حال اکران فیلم هستند. هر سینِما مجموعه‌ $v_i$ از فیلم‌ها را نشان می‌دهد. محمد می‌تواند با پرداخت هزینه $p_i$ به سینما‌ی شماره $i$ رفته و تمامی فیلم‌های آن سینما را به هر تعداد و به هر ترتیب که بخواهد، ببیند. اما او حتما باید هر فیلم اکران شده در این سینما را، در همان روز، حداقل یک بار ببیند. محمد در هر روز تنها می‌تواند به یک سینما برود.

محمد می‌خواهد با کم‌ترین هزینه تمامی فیلم‌های دنباله‌ی $a$ را به همان ترتیب ببیند. برای او کم‌ترین هزینه را بیابید.

توجه کنید که جشنواره‌ی فیلم فجر تا مدت‌ها برقرار است. همچنین محمد می‌تواند به تعداد دلخواه در هر روز فیلم ببیند و از لحاظ زمانی محدودیتی ندارد.

پیاده‌سازی

در این سوال شما باید تابع زیر را پیاده‌سازی کنید:

  • long long getMinimumCost(int n, int m, int *a, int *p, int* size, int **v)

این تابع دقیقاً یک‌بار فراخوانی می‌شود. آن را طوری پیاده‌سازی کنید تا کم‌ترین هزینه‌ای را که محمد با آن به هدفش می‌رسد، برگرداند . اگر محمد نمی‌توانست به هدفش برسد، تابع باید عدد $-1$ را برگرداند.

  • $n$: طول دنباله‌ی $a$}
  • $m$: تعداد سینماهای جشنواره فیلم فجر
  • $p$: یک آرایه به طول $m$، $p_i$ $(0 \leq i \leq m - 1)$ هزینه‌ی استفاده از سینمای $i$ ام به مدت یک روز است.
  • $size$: یک آرایه به طول $m$، $size_i$ $(0 \leq i \leq m - 1)$ بیانگر تعداد فیلم‌هایی است که سینمای $i$ اکران می‌کند.
  • $v$: یک آرایه‌ی دو بعدی با $m$ سطر. سطر $i$ $(0 \leq i \leq m - 1)$ ام آرایه‌ای به طول $size_i$ است و شامل مجموعه‌ی فیلم‌های اکران شده در این سینما است. دقت کنید در سطر مربوط به یک سینما فیلم تکراری وجود ندارد.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند:

  1. در خط اول دو عدد $n$ و $m$ آمده است.
  2. سپس در خط دوم $n$ عدد $a_0, a_1, \ldots, a_{n - 1}$ آمده است.
  3. در هر یک از $m$ خط بعدی، اطلاعات هر سینما آمده است.
  4. در خط $i$ ام، به ترتیب $p_i$، $size_i$ و سپس $size_i$ عدد متفاوت $v_{i,j}$ $(0 \leq j < size_i)$ آمده است.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۳۰ نمره): $0 \le a_i, v_{i, j} < 20$.
  • زیرمسئله‌ی دوم (۷۰ نمره): بدون محدودیت اضافی.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n, m \le 10^5$
  • $0 \le \sum_{i=0}^{m - 1}{size_i} < 10^5$
  • $0 \le a_i, v_{i, j} \le 10^5$

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
8 4
1 4 3 1 2 4 3 3
10 2 1 2
10 3 1 4 3
20 2 4 3
1 5 1 2 3 4 5
40

ابزار صفحه