Как побороть переполнение?

Question

[Homemade]

Решаю

эту

https://codeforces.com/problemset/problem/1471/A

задачу.
Мой

код

#include <bits/stdc++.h>

using namespace std;

long long div_up(int x, int y)
{
    return (x - 1) / y + 1;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        long long n,x;
        cin>>n>>x;
        vector<int> a(n);
        for(int i=0;i<n;i++)
            cin>>a[i];
        long long sum = 0;
        for(int i=0;i<n;i++)
            sum = sum + a[i];

        long long sum2 = 0;
        for(int i=0;i<n;i++)
            sum2 = sum2 + div_up(a[i],x);

        long long mn = div_up(sum,x),mx = sum2;

        cout<<mn<<" "<<mx<<endl;
    }
    return 0;
}

На большом числе выдало ошибку:

Ввод
1
100000 501901246
856802259 964126361 36942580 586287303 899177135 447296776 ...
Вывод
2 149973
Ответ
99678 149973
Протокол тестирования
wrong answer 1st numbers differ - expected: '99678', found: '2'

Думаю дело в переполнении переменной sum, но не знаю как быть.

Answer 1

[Rsa97]

Проанализировать, как меняется красота при операции сложения элементов и работать с остатками от деления.

Comments

[Homemade]

Благодарю

Answer 2

[Wataru]

В этой задаче все должно в long long помещаться. Никаких трюков не надо.

У вас ошибка вот тут:
long long div_up(int x, int y)

Типа параметров - int. Вы когда в эту функцию передаете long long сумму - происходит переполнение.

Просто измените типы на long long и должно пройти.

Comments

[Homemade]

Целую брат)