SULIM - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef has N snacks. The i-th has tastiness A_i and B_i units of sugar.
Chef will choose some value L and only eat snacks whose sugar is \leq L.
Chef’s satisfaction is the total sum of tastiness of eaten snacks, minus the value L.

Find the maximum possible satisfaction.

EXPLANATION:

Suppose we fix the value of L.
Then, since the satisfaction equals the sum of tastiness of eaten snacks minus L, it’s now ideal to maximize the sum of tastiness.

This is simple to do: we only consider all snacks with B_i \le L, and among them, it’s ideal to eat those snacks with positive A_i.

So, for a fixed value of L, the satisfaction is easily computed in \mathcal{O}(N) time:

  • Start with S = 0
  • For each index i, if B_i \le L and A_i \gt 0, add A_i to S.
  • The final satisfaction is S - L.

To decide the optimal value of L: since B_i \leq 100, simply try all values of L from 0 to 100, since it’s useless to use any L beyond 100.
The answer is best among the values obtained for all L.

TIME COMPLEXITY:

\mathcal{O}(100\cdot N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    ans = 0
    for l in range(101):
        sm = 0
        for i in range(n):
            if b[i] <= l: sm += max(0, a[i])
        ans = max(ans, sm - l)
    print(ans)
2

hey there is no way to optimize L is this the only option to take a loop iterate till 100

3 
auto solve()
{
    int n;
    cin>>n;
    vi arr;
    vi sug;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    for (int i = 0; i < n; i++)
    {
        int x;  cin >> x;
        sug.push_back(x);
    }
    ll sum = 0;
    int maXX_L = 0;
    for(int i = 0; i < n; i++){
        if((arr[i] - sug[i]) >= 0){
            sum = sum + arr[i];
            maXX_L = max(maXX_L, sug[i]);
        }
    }
    if(sum == 0) return 0ll;
    return sum - maXX_L;
}

why is my code not working?
Don’t we need the lowest L that is present in B?