1086 - Submit

Enunt

Vasilică se antrenează pe un site de probleme cu evaluare online. Când el trimite pe site soluţia la o problemă, aceasta este evaluată pe un anumit număr de teste. Punctajul obţinut la problema respectivă va fi egal cu suma punctajelor obţinute la fiecare test. Punctajele asociate testelor pot fi diferite. În plus, dacă problema a fost complet rezolvată (a obţinut punctaj maxim la toate testele), Vasilică primeşte şi un bonus.

Vasilică poate trimite soluţia la o problemă de mai multe ori. Când trimite soluţia prima dată, punctajul se calculează în modul prezentat anterior. Când trimite soluţia a doua oară, Vasilică va fi penalizat cu două puncte (adică din punctajul total obţinut la problemă se scad două puncte). Când trimite soluţia a treia oară penalizarea este de 4 puncte, a patra oară de 6 puncte ş.a.m.d. Observaţi că la fiecare nouă încercare penalizarea creşte cu două puncte.

Cerinţa

Date fiind rezultatele obţinute pe teste de Vasilică la fiecare soluţie trimisă, să se determine punctajul maxim pe care el l-a obţinut la problema respectivă.

Date de intrare

Fișierul de intrare submit.in conține pe prima linie numărul natural N reprezentând numărul de teste pe care este evaluată soluţia. Pe cea de a doua linie se află N numere naturale separate prin spaţii P1 P2 … PN, reprezentând în ordine punctajul acordat pentru fiecare dintre cele N teste. Pe cea de a treia linie se află numărul natural B reprezentând bonusul (numărul de puncte acordate în cazul în care pentru toate testele soluţia obţine punctaj pe toate testele). Pe a patra linie este scris un număr natural M reprezentând numărul de soluţii trimise de Vasilică la problemă. Urmează M linii, fiecare linie conţinând rezultatele obţinute pe teste la cele M soluţii trimise de Vasilică, în ordinea trimiterii lor. Pe cea de a i-a linie (1≤i≤M) dintre cele M sunt scrise N valori din mulţimea {0, 1}, separate prin spaţii; a j-a valoare (1≤j≤N) este 0 dacă testul j nu a fost rezolvat corect, respectiv 1 dacă testul j a fost corect rezolvat (obţinând punctajul maxim alocat pe test).

Date de ieșire

Fișierul de ieșire submit.out va conţine o singură linie pe care va fi scris punctajul maxim obţinut de Vasilică la problema respectivă.

Restricţii şi precizări

• 1 ≤ N, M ≤ 100
• 0 ≤ Pi ≤ 100, pentru orice 1 ≤ i ≤ N
• 0 ≤ B ≤ 100

Exemplul 1

submit.in

 4
 10 5 5 20
 13
 3
 0 0 0 0
 1 1 1 1
 0 1 0 1

submit.out

 51

Explicație

Problema este evaluată pe 4 teste. Punctajele acordate pe teste sunt 10, 5, 5 şi respectiv 20. În cazul în care toate testele sunt rezolvate corect, se acordă 13 puncte bonus.

La această problemă Vasilică trimite 3 surse.

Prima sursă trimisă nu rezolvă corect niciun test, deci obţine 0 puncte.

A doua sursă trimisă rezolvă corect toate testele, primind 10+5+5+20=40 puncte pe teste, la care se adaugă 13 puncte bonus; dar fiind a doua soluţie trimisă se aplică o penalizare de două puncte. În total 40+13-2=51 puncte.

A treia sursă trimisă rezolvă numai teste 2 şi 4 deci obţine 5+20=25 puncte şi este penalizată cu 4 puncte, deci punctajul total este 21.

Punctajul maxim obţinut de Vasilică este prin urmare 51.

Rezolvare

def max_score(N, points, bonus, M, solutions):
    max_score = 0
    penalty = 0

    for i in range(M):
        correct_tests = sum(solutions[i])
        score = sum(points[j] for j in range(N) if solutions[i][j] == 1)
        score += bonus if correct_tests == N else 0
        score -= penalty
        max_score = max(max_score, score)
        penalty += 2

    return max_score

def main():
    with open("submit.in", "r") as fin:
        N = int(fin.readline().strip())
        points = list(map(int, fin.readline().split()))
        bonus = int(fin.readline().strip())
        M = int(fin.readline().strip())
        solutions = [list(map(int, fin.readline().split())) for _ in range(M)]

    max_score_value = max_score(N, points, bonus, M, solutions)

    with open("submit.out", "w") as fout:
        fout.write(str(max_score_value))

if __name__ == "__main__":
    main()