oj.uz

Submission #230533

# Submission time Handle Problem Language Result Execution time Memory
230533 2020-05-10T10:25:26 Z VEGAnn Sajam (COCI18_sajam) C++14
0 / 90
 11 ms 7680 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2048 KB Output is correct
2 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 8 ms 4736 KB Output is correct
3 Correct 11 ms 7680 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 8 ms 4224 KB Output is correct
6 Incorrect 9 ms 4096 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -