Решение задачи Книжные полки с Codeforces

Без пояснения   Просмотров: 308


Мистер Кекс — типичный офисный работник в Байтландии.

У него в офисе стоит одна большая книжная полка, на каждой книге на ней написана стоимость — целое положительное число.

Он оценивает стоимость полки как сумму стоимостей книг на ней.

Код

#!/usr/bin/python3.7

import sys


n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

cur = 0

def is_submask(n, mask):
    return (n & mask) == mask

def f(mask):
    s = [[False for j in range(n)] for i in range(n)]
    for l in range(n):
        cur = 0
        for r in range(l, n):
            cur += a[r]
            s[l][r] = is_submask(cur, mask)
    dp = [[False for j in range(n)] for i in range(k)]
    dp[0] = s[0][:]
    for k1 in range(1, k):
        for r in range(n):
            for l in range(1, r + 1):
                    dp[k1][r] |= dp[k1 - 1][l - 1] & s[l][r]
    return dp[k - 1][n - 1]

cur = 0
for i in range(56, -1, -1):
    if f(cur + 2 ** i):
        cur += 2 ** i
print(cur)

         

Администратор Photo Автор: Администратор


Код

#include <bits/stdc++.h>

using namespace std;
using ll = long long ;
bool dp[55][55];
ll pre[55];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> pre[i], pre[i]+=pre[i-1];
    ll res = 0;
    for(int i = 59; ~i; -- i) {
        res |= 1LL << i;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int d = 1;d <= m;d ++) {
            for(int r = d;r <= n;r ++) {
                for(int l = d-1;l < r;l ++) {
                    dp[d][r] |= dp[d-1][l] && ((pre[r]-pre[l])&res) == res;
                }
            }
        }
        if(!dp[m][n]) res ^= 1LL << i;
    }
    cout << res << '\n';
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться