𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

def solve(priceList):
    floors = len(priceList)
    frequencies = len(priceList[0])
    dp = [[0] * frequencies for _ in range(floors)]
    for j in range(frequencies):
        dp[0][j] = priceList[0][j]
    for i in range(1, floors):
        for j in range(frequencies):
            min_cost = float('inf')
            for k in range(frequencies):
                if k != j: 
                    min_cost = min(min_cost, dp[i-1][k])
            dp[i][j] = priceList[i][j] + min_cost
    return min(dp[-1])

758 views05:36

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> tree;
vector<int> values;
long long total = 0;

void dfs(int node, int parent, vector<int>& path) {
    path.push_back(values[node]);

    if (path.size() % 2 == 1) {

        vector<int> sorted_path = path;
        sort(sorted_path.begin(), sorted_path.end());
        int median = sorted_path[sorted_path.size() / 2];
        total += median;
    }

    for (int neighbor : tree[node]) {
        if (neighbor != parent) {
            dfs(neighbor, node, path);
        }
    }

    path.pop_back();
}

int main() {
    int n;
    cin >> n;

    values.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }

    tree.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    vector<int> path;
    dfs(0, -1, path);

    cout << total<< endl;

    return 0;
}

//median path ✅

715 views07:01

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

635 views07:02

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define MOD 1000000007
#define MOD2 998244353
#define vll vector<ll>

struct SegmentTree {
    ll N;
    vll tree;
    ll neutral = 0;

    ll combine(ll a, ll b) {
        return a + b;
    }

    void build(ll u, ll L, ll R, vll &v) {
        if(L == R) {
            tree[u] = v[L];
        } else {
            ll M = (L + R) / 2;
            build(u * 2, L, M, v);
            build(u * 2 + 1, M + 1, R, v);
            tree[u] = combine(tree[u * 2], tree[u * 2 + 1]);
        }
    }

    SegmentTree(vll v) {
        N = v.size() - 1;
        tree.assign(4 * N + 1, 0);
        build(1, 1, N, v);
    }

    ll query(ll lq, ll rq, ll u, ll L, ll R) {
        if(L > rq || R < lq) {
            return neutral;
        } else if(L >= lq && R <= rq) {
            return tree[u];
        } else {
            ll M = (L + R) / 2;
            return combine(query(lq, rq, u * 2, L, M), query(lq, rq, u * 2 + 1, M + 1, R));
        }
    }

    void update(ll idx, ll val, ll u, ll L, ll R) {
        if(L > idx || R < idx) {
            return;
        } else if(L == R) {
            tree[u] = val;
            return;
        } else {
            ll M = (L + R) / 2;
            update(idx, val, u * 2, L, M);
            update(idx, val, u * 2 + 1, M + 1, R);
            tree[u] = combine(tree[u * 2], tree[u * 2 + 1]);
        }
    }
};

const int MAXN = 1e6 + 1;
vector<int> spf(MAXN);

void sieve() {
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)
        spf[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        spf[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sieve();
    int n, q; cin >> n >> q;
    vll arr(n + 1);
    for(int i = 1; i <= n; i++) cin >> arr[i];
    SegmentTree sgt(arr);
    set<int> s;
    for(int i = 1; i <= n; i++)
        s.insert(i);

    while(q--) {
        int type; cin >> type;
        int a, b; cin >> a >> b;
        if(type == 3) {
            sgt.update(a, b, 1, 1, n);
            int temp = a;
            auto it = s.lower_bound(temp);
            if(it != s.end() and s.size() != 0 and *it == a) {
                s.erase(temp);
                s.insert(a);
            } else {
                s.insert(a);
            }
            arr[a] = b;
        } else if (type == 2) {
            cout << sgt.query(a, b, 1, 1, n) << endl;
        } else {
            while(a <= b) {
                int temp = a;
                auto it = s.lower_bound(temp);
                if(it == s.end()) break;
                if(*it > b) break;
                int c = *it + 1;
                sgt.update(a, arr[a] / spf[arr[a]], 1, 1, n);
                if(spf[a] == 1) {
                    s.erase(temp);
                }
                arr[a] = spf[a];
                a = c;
            }
        }
    }
    return 0;
}

Divisor queries ✅

652 viewsedited 07:03

About

Blog

Apps

Platform