CMIX - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N spells. The i-th has volatility V_i and power A_i.
Combining two spells results in one whose strength equals the sum of the products of volatility and power of different spells.
Find the strongest spell that can be created.

EXPLANATION:

Since N \leq 100, a simple brute force solution will do.
Try each pair of spells i and j, compute the value (A_i\cdot V_j) + (A_j\cdot V_i), and take the maximum across all these.
Make sure not to consider i = j.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = []
    for i in range(n):
        x, y = map(int, input().split())
        a.append((x, y))
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ans = max(ans, a[i][0]*a[j][1] + a[i][1]*a[j][0])
    print(ans)