Submission #230533

#	Time	Username	Problem	Language	Result	Execution time	Memory
230533		VEGAnn	Sajam (COCI18_sajam)	C++14	0 / 90	11 ms	7680 KiB

sajam

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define pis pair<int,short>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 110;
const int PW = 20;
int f[2][N][N][N], n, k;
bool a[N][N];

void upd(int &x, int y){
    x = min(x, y);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    assert(n <= 100);

    if (n == 1){
        cout << "DA";
        return 0;
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            char c; cin >> c;

            if (c == 'x')
                a[i][j] = 1;
            else a[i][j] = 0;
        }
    }

    for (int tp = 0; tp < 2; tp++)
    for (int j = 0; j < n; j++)
        if (a[0][j] == tp){
            f[tp][0][j][0] = 0;
            f[tp][0][j][1] = 1;
        } else {
            f[tp][0][j][0] = 1;
            f[tp][0][j][1] = 0;
        }

    for (int i = 1; i < n; i++){
        for (int tp = 0; tp < 2; tp++)
        for (int j = 0; j < n; j++)
        for (int kl = 0; kl <= i; kl++)
            f[tp][i][j][kl] = oo;

        for (int ptp = 0; ptp < 2; ptp++)
        for (int j = 0; j < n; j++)
        for (int kl = 0; kl <= i; kl++){
            if (f[ptp][i - 1][j][kl] == oo) continue;

            for (int tp = 0; tp < 2; tp++){
                int nw = f[ptp][i - 1][j][kl];

                if (a[i][j] == tp){
                    upd(f[tp][i][j][kl], nw);
                    upd(f[tp][i][j][kl + 1], nw + 1);
                } else {
                    upd(f[tp][i][j][kl], nw + 1);
                    upd(f[tp][i][j][kl + 1], nw);
                }
            }
        }
    }

    for (int tp = 0; tp < 2; tp++){
        int res = 0;

        for (int j = 0; j < n; j++){
            int mn = oo;

            for (int kl = 0; kl <= n; kl++){
                if (f[tp][n - 1][j][kl] == oo) continue;

                mn = min(mn, min(kl, n - kl) + f[tp][n - 1][j][kl]);
            }

            if (mn == oo){
                res = oo;
                break;
            }
        }

        if (res <= k){
            cout << "DA";
            return 0;
        }
    }

    cout << "NE";

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15