علف هرز


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ابواسحاق پس از ترمیم رشتهٔ افکار خود، آغاز به کشت خیار کرد! امّا در این بین، علف‌های هرز مانع کسب و کار او شدند. برای همین، شروع به حذف کردن علف‌های هرز کرد.

مزرعهٔ او به شکل جدولی n×mn\times m است که دارای nn سطر با شماره‌های 00 تا n1n - 1 از بالا به پایین و mm ستون با شماره‌های 00 تا m1m - 1 از چپ به راست می‌باشد. در ابتدا kk علف هرز در مزرعه وجود دارد. او در هر مرحله می‌تواند یکی از عملیات‌های زیر را انجام دهد:

  • یک علف‌ هرز از خانهٔ (i,j)(i, j) را با دست بکَنَد. در این صورت wi,jw_{i, j} انرژی مصرف می‌کند. (برای خم شدن و کندن علف هرز)

  • پا روی خانهٔ (i,j)(i, j) بگذارد، در این صورت یکی از علف‌های هرز موجود در آن خانه از بین رفته و یک علف هرز به خانه‌ی ((i+1)modn,j)((i + 1)\mod n, j) و علف هرزی دیگر به خانه‌ی (i,(j+1)modm)(i, (j + 1)\mod m) اضافه می‌شود. توجه کنید که در این عملیات هیچ انرژی‌ای از او کم نمی‌شود (amodba\mod b برابر با باقی مانده تقسیم aa بر bb است).

حال او وضعیت اولیهٔ مزرعه و علف‌های هرز را به شما می‌دهد و از شما می‌خواهد که کمترین انرژی لازم برای از بین بردن تمامی علف‌های هرز مزرعه را محاسبه کنید.

ورودی🔗

در خط اول دو عدد nn و mm و kk داده می‌شود.

در هر یک از nn سطر بعدی mm عدد آمده است که عدد jj ام در سطر ii ام مقدار wi,jw_{i, j} را مشخص می‌کند.

در خط ii ام از kk خط بعدی دو عدد xix_i و yiy_i آمده که نشان می‌دهد علف هرز ii ام در خانه (xi,yi)(x_i, y_i) است. 1n,m1 000 1 \le n, m \le 1\ 000 1k1 0001 \le k \le 1\ 000 0xi<n 0 \le x_i < n 0yj<m 0 \le y_j < m 1wi,j1 000 1 \le w_{i, j} \le 1\ 000 دقت کنید ممکن است در ابتدا در یک خانه بیش از یک علف هرز وجود داشته باشد.

خروجی🔗

در یک خط عدد خواسته شده را چاپ کنید.

ورودی نمونه ۱🔗

2 2 1
3 1
1 1
0 0
Plain text

خروجی نمونه ۱🔗

2
Plain text

در ابتدا یک علف هرز در خانهٔ (0,0)(0 ,0) وجود دارد. ابواسحاق روز آن پا گذاشته و در نتیجه در هر یک از خانه‌های (1,0)(1 ,0) و (0,1)(0 ,1) یک علف هرز بوجود می‌آید. سپس هر کدام از علف‌های هرز جدید را با دست می‌کند و در مجموع ۲ واحد انرژی از دست می‌دهد.

ورودی نمونه ۲🔗

3 3 2
7 5 1
4 3 1
1 2 1
0 1
1 0
Plain text

خروجی نمونه ۲🔗

8
Plain text

در ابتدا دو علف هرز یکی در خانه (0,1)(0,1) و دیگری در خانه (1,0)(1,0) موجود است، ابواسحاق با پا گذاشتن روی این دو علف آنها را به صورت (0,2)(0,2)، (1,1)(1,1)، (1,1)(1,1) و (2,0)(2,0) درمی‌آورد (توجه کنید دو علف هرز در خانه (1,1)(1,1) موجود است) سپس تمامی آنها را با دست می‌کند که در مجموع از او ۸ واحد انرژی می‌گیرد همچنین می‌توان ثابت کرد این مقدار کمینه انرژی لازم است.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.