Есеп D. Айбардың таңдауы

Айбардың ұзындықтары $n$ болатын $A$ және $B$ массивтары бар. Әр бір $i$ үшін, $(1 <= i <= n)$, Айбар не $A_i$, не $B_i$ таңдамақшы. Ол таңдалған $A_i$-лардың саммасы мен, барлық таңдалған $B_j$ үшін соммаларының көбейтіндісін ұлғайтпақшы. Айбарға ең үлкен мәнді табуға көмектесіңіз. Ең үлкен мән $10^9$ санынан аспайтынына кепілдік беріледі. Ең бірінші жолда $n$ $(2 <= n <= 1000)$ саны еңгізілген. Екінші жолда $n$ бүтін сан $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$ еңгізілген. Үшінші жолда $n$ бүтін сан $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$ еңгізілген. Есептің жауабын шығарыңыз. Есеп алты бөлімнен тұрады:

1. $2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 1$. $8$ ұпайға есептеледі.
2. $2 <=q n <=q 15, 1 <=q A_i, B_i <=q 10^9$. $9$ ұпайға есептеледі.
3. $2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . $10$ ұпайға есептеледі.
4. $2 <=q n <=q 1000$, $A_i=B_i$ барлық $i$ үшін, барлық $A_i$ соммасы $10^5$ аспайды. $18$ ұпайға есептеледі.
5. $2 <=q n <=q 100$, барлық $A_i$ соммасы 300 аспайды, барлық $B_i$ соммасы $300$ аспайды. $25$ ұпайға есептеледі.
6. $2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 10^9$. $30$ ұпайға есептеледі.

Вход

5
1 4 3 2 5
5 2 2 4 1

Ответ

108

Вход

2
5 7
3 5

Ответ

25

Вход

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Ответ

12

Бірінші мысалда Айбар $A$ массивынен $2, 3, 5$ орнынағы элементтерді алып, $B$ массивынан $1, 4$ орындарындағы элементтерді алса, жауап осындай болады: $(4 + 3 + 5) * (5 + 4)=108$.

Есеп E. НурлашКО

АланашКО мен НурлашКО графом ойнап жатыр, сол себепті сіздің көмегіңіз қажет. Ойын бағытталған, циклдік емес $G$ графынан басталады. Алғашында граф $n$ шыңнан тұрады және граф қабырғасыз болып келеді. Ойын барысында ойнаушылар $q$ операциялар орындайды. Операциялар түрлері осындай:

1. $u_i$ шыңынан $v_i$ шыңына бағытталған қабырға жасау.
2. 1-ші шыңнан $x_i$ шыңына дейін бағытталған қабырғалар арқылы жол табылса, $x_i$ шығарыңыз, табылмаса $0$ шығарыңыз.

Әр операциядан кейін граф циклсыз болатынына кеппілдік беріледі. Бірінші жолда үш бүтін сан $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — шыңдар саны, операциялар саны мен константалық сан енгізіледі. Келесі $q$ жол әр операцияның сипаттамасын береді.

1. Бірінші түрлі операция осылай сипатталады: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
2. Екінші түрлі операция осылай сипатталады: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.

Назар аударыңыз, бірінші операцияға арналған $u_i$, $v_i$ шыңдар номерлері мен екінші операцияға арналған $x_i$ шыңының номері кодталған болып келеді, және оларды алу үшін осындай тағы операциялар орындау қажет: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} $lastans$ — соңғы $2$ операциясынан шыққан жауап (алғашында $lastans$ $0$-тең). Мына жерде $\oplus$ аралас немесе операциясын білдіреді. Осы операция заманғы бағдарламалау тілдерінде ба, мысалға, C++ және Java — ^ арқылы белгіленген, Pascal — $xor$ арқылы. $a \mod b$ операциясы $a$-ның $b$-ға бөлгендегі қалдығын береді. Есепте кемінде бір екінші түрлі операция келетініне кепілдік беріледі. Аралас НЕМЕСЕ($xor$) операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $xor$ $Y$ = $68_{10}$ = $1000100_{2}$. Әр екінші түрлі операцияның жауабын бөлек жолға шығарыңыз. Есеп 5 бөлімнен тұрады:

1. Шарттағы мысалдар. $0$ ұпайға бағаланады.
2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. $11$ ұпайға бағаланады.
3. $n, q <= 10^3$. $18$ ұпайға бағаланады.
4. $t = 0$. $39$ ұпайға бағаланады.
5. Есептің толық шарттары. $32$ ұпайға бағаланады.

Вход

5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3

Ответ

1
0
2
0
4

Вход

5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3

Ответ

1
0
2
0
4

Есеп F. Оңдаңыз!

Барлық сандары теріс емес массивты, Тима жақсы деп есептейді. Тиманың ұзындығы $n$ болатын, бүтін сандардан тұратын $a$ массивы бар. Тима оны жақсы еткісі келеді, сол үшін ол осындай операция істей алады:

• $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ және $a_i \ge x$ орындалатын $i,j, x$ сандарын таңдап алып, $a_i$ санынан $x$ санын азайтып, ал $a_j$ санына $x$ қосу. Осы операцияның құны $|i - j| \cdot x$ теңге.

Қалайда аз теңге қолданып, Тиманың массивын жақсы етіңіз. Бірінші жолда екі бүтін сан $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$ енгізіледі. Екінші жолда $n$ бүтін сан $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$ енгізіледі. $a$ массивын жақсы ете алынуына кепілдік беріледі. Бірінші жолда массивты жақсы етуге құртылған тенге санын шығарыңыз. Егер $type = 1$ болса, екінші жолда бір бүтін сан $k (0 <= k <= 2 \cdot n)$ — операциялар санын шығарыңыз. Келесі $k$ жолда үш саннан $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — операциялар сипаттамасын шығарыңыз. Операциялар санын азайтудың қажеті жоқ, бастысы құртылған тенге санын азайтыңыз. Егер $type = 0$ болса, басқа ештеңе шығарудың керегі жоқ. Есеп сегіз бөлімнен тұрады:

1. Мысалдағы тесттер. 0 ұпайға бағаланады.
2. $n <= 10, type = 0, -1 <= a_i <= 1$. 8 ұпайға есептеледі.
3. $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. 16 ұпайға есептеледі.
4. $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. 12 ұпайға есептеледі.
5. $n <= 2000, type = 0, -1 <= a_i <= 1$. 15 ұпайға есептеледі.
6. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. 13 ұпайға есептеледі.
7. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. 15 ұпайға есептеледі.
8. $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. 21 ұпайға есептеледі.

Вход

7 0
1 1 -1 0 -1 1 1

Ответ

2

Вход

4 1
4 -2 -2 1

Ответ

5
3
1 2 2
1 3 1
4 3 1