Аврора Интенсив день3

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include <cmath>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <cassert>
#include <functional>
//#include <intrin.h>
#include <stack>
#include <thread>
using namespace std;
//typedef long long ll;
#define ll long long
#define ld long double

const long long mod = 1000000007;

#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PI 3.14159265358979323846
#define ABS(a) ((a)<0?-(a):(a))
template <typename T> inline T gcd(T a, T b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}
long long fastpow(long long a, long long n)
{
    auto mult = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
            res *= mult;
        mult *= mult;
        n >>= 1;
    }
    return res;
}

void BackPackMatr()
{
    int N, W;
    cin >> N >> W;
    vector<int> weights(N);
    vector<vector<int>> backpack(N + 1);
    backpack[0].resize(W, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> weights[i];
        backpack[i + 1] = backpack[i];
        backpack[i + 1][weights[i] - 1] = 1;
        for (int j = weights[i] + 1; j <= W; j++)
        {
            backpack[i + 1][j - 1] = backpack[i][j - weights[i] - 1] || backpack[i][j - 1];
        }
    }
    int i = N;
    for (int j = W - 1; j >= 0; j--)
    {
        vector<int> ans;
        if (backpack[i][j])
        {
            cout << j + 1 << " ";
            while (j)
            {
                while (backpack[i][j])
                {
                    i--;
                }
                ans.push_back(weights[i]);
                j -= weights[i];
            }
            cout << ans.size() << endl;
            for (auto& w : ans)
                cout << w << " ";
        }
    }
}

void PricedBackpackMatr()
{
    int N, W;
    cin >> N >> W;
    vector<int> weights(N), costs(N);
    vector<vector<long long>> backpack(N + 1);
    backpack[0].resize(W + 1, -1);
    backpack[0][0] = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> weights[i] >> costs[i];
        backpack[i + 1] = backpack[i];
        for (int j = weights[i]; j <= W; j++)
        {
            if (backpack[i][j - weights[i]] >= 0)
                backpack[i + 1][j] = max(backpack[i][j], backpack[i][j - weights[i]] + costs[i]);
        }
    }
    int i = N;
    int max = 0, maxj = 1;
    for (int j = W; j >= 0; j--)
    {
        if (backpack[i][j] > max)
        {
            max = backpack[i][j];
            maxj = j;
        }
    }
    cout << maxj << " " << max;
    int j = maxj;
    vector<int> ans;
    while (j)
    {
        while (backpack[i - 1][j] == backpack[i][j])
        {
            i--;
        }
        ans.push_back(i + 1);
        j -= weights[i];
    }
    cout << ans.size() << endl;
    for (auto& w : ans)
        cout << w << " ";
}

void BackPackColumn()
{
    int N, W, w;
    cin >> N >> W;
    vector<int> backpack(W, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> w;
        backpack[w - 1] = 1;
        for (int j = W; j >= w + 1; j--)
        {
            backpack[j - 1] = backpack[j - w - 1] || backpack[j - 1];
        }
    }
    for (int j = W - 1; j >= 0; j--)
    {
        vector<int> ans;
        if (backpack[j])
        {
            cout << j + 1 << endl;
            return;
        }
    }
}

long long cost(int i, int j, int a, vector<long long>& w, vector<long long>& h)
{
    return h[i] * w[i + a] * w[j + 1];
}

void MinMatr()
{
    int n;
    cin >> n;
    vector<long long> w(n), h(n);
    vector<vector<long long>> matr_res(n + 1);
    for (int i = 0; i < n; i++)
    {
        cin >> h[i] >> w[i];
    }
    for (int i = 0; i < n + 1; i++)
        matr_res[i].resize(n + 1, 0);
    for (int ni = 0; ni < n - 1; ni++)
    {
        for (int nj = ni; nj < n - 1; nj++)
        {
            int i = nj - ni;
            int j = nj;
            long long min_res = INT64_MAX;
            for (int a = 0; a <= ni; a++)
            {
                min_res = min(min_res, matr_res[i + 1][i + a] + matr_res[i + a + 2][j + 1] + cost(i, j, a, w, h));
            }
            matr_res[i + 1][j + 1] = min_res;
        }
    }
    cout << matr_res[1][n - 1] << endl;
}

void LCS()
{
    string a, b;
    cin >> a >> b;
    vector<vector<int>> ans_matr(a.size() + 1);
    ans_matr[0].resize(b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++)
    {
        ans_matr[i + 1].resize(b.size() + 1, 0);
        for (int j = 0; j < b.size(); j++)
            if (a[i] == b[j])
                ans_matr[i + 1][j + 1] = ans_matr[i][j] + 1;
            else
                ans_matr[i + 1][j + 1] = max(ans_matr[i][j + 1], ans_matr[i + 1][j]);
    }
    cout << ans_matr[a.size()][b.size()] << endl;
    string ans = "";
    int i = a.size();
    int j = b.size();
    while (i && j)
    {
        while (i && ans_matr[i - 1][j] == ans_matr[i][j])
            i--;
        while (j && ans_matr[i][j - 1] == ans_matr[i][j])
            j--;
        if (i && j)
        {
            ans.push_back(a[i - 1]);
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}

void DFSMatr(vector<vector<bool>>& matr, vector<int>& passed, int i, int a)
{
    passed[i] = a;
    for (int j = 0; j < matr[i].size(); j++)
    {
        if (matr[i][j] && !passed[j])
        {
            DFSMatr(matr, passed, i, a);
        }
    }
}

void DFSList(vector<vector<int>>& matr, vector<int>& passed, int i, int a)
{
    passed[i] = a;
    for (int j : matr[i])
    {
        if (matr[i][j] && !passed[j])
        {
            DFSList(matr, passed, i, a);
        }
    }
}

void BFSMatr(vector<vector<bool>>& matr, vector<int>& passed, int i, int a)
{
    queue<int> que;
    que.push(i);
    passed[i] = a;
    while (que.size())
    {
        int ti = que.front();
        que.pop();
        for (int j = 0; j < matr[ti].size(); j++)
            if (matr[ti][j] && !passed[j])
            {
                passed[j] = a;
                que.push(j);
            }
    }
    vector<int> v;
    int p = 0;
    v.push_back(i);
    while (p < v.size())
    {
        int ti = v[p];
        p++;
        for (int j = 0; j < matr[ti].size(); j++)
            if (matr[ti][j] && !passed[j])
            {
                passed[j] = a;
                v.push_back(j);
            }
    }
}

void BFSList(vector<vector<int>>& matr, vector<int>& passed, int i, int a)
{
    queue<int> que;
    que.push(i);
    passed[i] = a;
    while (que.size())
    {
        int ti = que.front();
        que.pop();
        for (int j : matr[ti])
            if (matr[ti][j] && !passed[j])
            {
                passed[j] = a;
                que.push(j);
            }
    }
    vector<int> v;
    int p = 0;
    v.push_back(i);
    while (p < v.size())
    {
        int ti = v[p];
        p++;
        for (int j : matr[ti])
            if (matr[ti][j] && !passed[j])
            {
                passed[j] = a;
                v.push_back(j);
            }
    }
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    return 0;
}