Участник:Kozlinskii/ADAMOLD

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAMOLD/ c++14(gcc 8.3)

#include <iostream>
using namespace std;
 
const int MAX_KN = 5000;
const int MAX_POWER = 30;
 
int n,k;
int64_t flower;
int64_t dnk[MAX_KN + MAX_POWER + 1][MAX_KN + MAX_POWER + 1];
int cum_furrow[MAX_KN + MAX_POWER + 1][MAX_POWER + 1];
int cut[MAX_KN + MAX_POWER + 1][MAX_KN + MAX_POWER + 1];
 
int64_t CalcMoldValue(int left, int right){
    int64_t sum = 0;
    for (int iter=0; iter < MAX_POWER; iter++){
        int64_t ones = cum_furrow[right][iter] - cum_furrow[left - 1][iter];
        int64_t zeros = (right - left + 1) - ones;
        sum += ones * zeros * (1 << iter);
    }
    return sum;
}
 
int main(){
    cin >> n >> k;
    if (k > n) {
        k = n;
    } else {
    	k += 1;
    }
 
    for (int iter=1; iter <= n; iter++){
        cin >> flower;
        for (int power=0; power < MAX_POWER; power++){
            cum_furrow[iter][power] = cum_furrow[iter - 1][power];
            if (flower & (1 << power))
                cum_furrow[iter][power]++;
        }
    }
 
    for (int iter=1; iter <= n; iter++){
        cut[iter][1] = 0;
        dnk[iter][1] = CalcMoldValue(1, iter);
    }
 
    for (int iter=2; iter <= n; iter++){
        for (int iter_k=min(k,iter); iter_k > 1; --iter_k){
            int left = cut[iter - 1][iter_k];
            int right = cut[iter][iter_k + 1];
            if (iter_k + 1 > min(k,iter))
                right = iter - 1;
            left = max(left,iter_k - 1);
            dnk[iter][iter_k] = INT64_MAX;
            for (int iter_n = left; iter_n <= right; iter_n++){
                int64_t alt_dnk = dnk[iter_n][iter_k - 1] + CalcMoldValue(iter_n + 1,iter);
                if (alt_dnk <= dnk[iter][iter_k])
                {
                    dnk[iter][iter_k] = alt_dnk;
                    cut[iter][iter_k] = iter_n;
                }
            }
        }
    }
 
    cout << dnk[n][k];
     return 0;
}