9 контест Насте Косаревой

// 1
#include <iostream>
#include <vector>

using namespace std;

int height, width, a, b;
int cnt = 0;
int para_cnt = 0;
vector<vector<int>> graph;
vector<int> max_para;
vector<int> used;

void init(int n) {
    graph.resize(n);
    used.resize(n);
    max_para.resize(n, -1);
}

void input() {
    cin >> height >> width >> a >> b;

    init(height * width);
    vector<string> input_string(height);
    for (int i = 0; i < input_string.size(); i++) {
        cin >> input_string[i];
    }


    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (input_string[i][j] == '.')
                continue;
            cnt++;
            if ((i + j) % 2 == 1)
                continue;

            if (j && input_string[i][j - 1] == '*')
                graph[i * width + j].push_back(i * width + j - 1);

            if ((i < height - 1) && input_string[i + 1][j] == '*')
                graph[i * width + j].push_back((i + 1) * width + j);
            if (i && input_string[i - 1][j] == '*')
                graph[i * width + j].push_back((i - 1) * width + j);
            if ((j < width - 1) && input_string[i][j + 1] == '*')
                graph[i * width + j].push_back(i * width + j + 1);
        }
    }
}

int dfs(int vertex) {
    if (used[vertex])
        return 0;
    used[vertex] = 1;
    int to;
    for (int i = 0; i < graph[vertex].size(); i++) {
        to = graph[vertex][i];
        if (max_para[to] == -1 || dfs(max_para[to])) {
            max_para[to] = vertex;
            return 1;
        }
    }
    return 0;
}

void solve() {
    if (2 * b <= a) {
        cout << cnt * b;
        exit(0);
    }



    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if ((i + j) % 2 == 1)
                continue;
            used = vector<int>(height * width, false);
            dfs(i * width + j); // ищем парасочетание
        }
    }
    for (int i = 0; i < height * width; i++)
        if (max_para[i] != -1)
            para_cnt++;

}

void print() {
    cout << para_cnt * a + (cnt - 2 * para_cnt) * b;
}

int main() {
    input();
    solve();
    print();

    return 0;
}

// 2

#include <iostream>
#include <vector>

using namespace std;

int const DICE_SIDES = 6;

int height, width, a, b;
int n;
string name;
int cnt = 0;
int para_cnt = 0;
vector<vector<int>> graph;
vector<int> max_para;
vector<int> used;
vector<string> dices;


void init() {
    graph.resize(name.size());

    used.resize(n);
    max_para.resize(n, -1);
    dices.resize(n);
}

void input() {
    cin >> n >> name;

    init();

    if (name.size() > n){
        cout << "NO";
        exit(0);
    }

    for (int i = 0; i < dices.size(); i++)
        cin >> dices[i];
}

int dfs(int vertex) {
    if (used[vertex])
        return 0;
    used[vertex] = 1;
    int to;
    for (int i = 0; i < graph[vertex].size(); i++) {
        to = graph[vertex][i];
        if (max_para[to] == -1 || dfs(max_para[to])) {
            max_para[to] = vertex;
            return 1;
        }
    }
    return 0;
}

void solve() {
    for (int i = 0; i < name.size(); i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < DICE_SIDES; k++)
                if (name[i] == dices[j][k])
                    graph[j].push_back(i);

    for (int i = 0; i < n; i++){
        used = vector<int>(n, 0);
        dfs(i);
    }
    for (int i = 0; i < max_para.size(); i++){
        if (max_para[i] == -1)
            cnt++;
    }
}

void print() {
    if (cnt != 0) {
        cout << "NO";
    }
    else {
        cout << "YES" << endl;
        for (int i = 0; i < name.size(); i++){
            cout << max_para[i] + 1 << ' ';
        }
    }
}

int main() {
    input();
    solve();
    print();

    return 0;
}