Как оптимизировать мое решение для dp программирования с алгоритмом c задача быстрее

Question

Теперь, когда у нас есть компьютер, нам нужно включить его в течение n дней. Каждый день магазин предлагает m батарей, которые будут работать только один день. Кроме того, когда вы покупаете k предметов в этот день, вам нужно заплатить налог, который составляет k ^ 2 Напечатайте минимальную стоимость работы вашего компьютера в течение n дней

For example for 
5 5
100 1 1 1 1 
100 2 2 2 2 
100 3 3 3 3 
100 4 4 4 4
100 5 5 5 5 
Output will be 18

10 1 
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
Output will be 10000000010

Я не могу решить эту задачу быстрее, чем проверка всех возможностей. Можете ли вы указать мне лучшее решение. Пределы 1 <= n * m <= 10 ^ 6 цена может быть от 1 до 10 ^ 9. </p>

Answer 1

Вы можете просто для каждого дня сортировать элементы (вам нужно сначала выбрать самую низкую цену для каждого дня) и добавить элемент в приоритетную очередь как значение + налог (когда налог рассчитывается как 2 * j -1 , где j - это j-тый предмет, купленный в тот день. Это работает, потому что k ^ 2 - (k + 1) ^ 2. И каждый день вы убираете первый элемент (лучшая батарея, которую вы можете купить в настоящее время).

#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>

using namespace std;

int n, m;
vector <long long> pom;
int x;
priority_queue<long long> q;

long long score;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> x;
            pom.push_back(x);
        }
        sort(pom.begin(), pom.end());

        for(int j = 0; j < pom.size(); j++){
            pom[j] += 1 + 2 * j;
            q.push(-pom[j]);
        }
        pom.clear();
        score += q.top();
        q.pop();
    }

    cout << -score;


}

Сложность для этого решения O (n * m logm)