oj.uz

Submission #229750

# Submission time Handle Problem Language Result Execution time Memory
229750 2020-05-06T09:25:22 Z Coder T-Covering (eJOI19_covering) C++14
0 / 100
 5 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define PR(x) cerr << #x << "=" << (x) << endl;
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
const int N = 1000001;
int i, j, k, m, n;
int a[N];

int b[N], d[N], c[N];
vector<pii> v;
int clbest, clsum;
ll ans;
const int DX[]={-1,0,1,0,0};
const int DY[]={0,1,0,-1,0};

void nosol() {
    cout << "No" << endl;
    exit(0);
}

bool Empty(int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n) return 0;
    return !c[x*n + y];
}

int GetA(int x, int y) {
    return a[x*n + y];
}

void Set(int x, int y, int val) {
    c[x*n + y] = val;
}

void Fill(int x, int y) {
    Set(x, y, 1);
    ans += GetA(x, y);
}

void DFS(int x, int y) {
    F0(k, 4) {
        int x2 = x + 2 * DX[k], y2 = y + 2 * DY[k];
        if (Empty(x2, y2) && b[x2*n + y2]) {
            Fill(x2, y2);
            v.push_back(pii(x2, y2));
            DFS(x2, y2);
        }
    }
}

int its;
void go(int at) {
    if (its++ > 1000000) return;
    if (at == SZ(v)) {
        if (clsum > clbest) clbest = clsum;
        return;
    }

    F0(k, 4) {
        int sum = 0;
        F0(dir, 4) if (dir != k) {
            if (!Empty(v[at].first + DX[dir], v[at].second + DY[dir])) {
                sum = -1; break;
            } else sum += GetA(v[at].first + DX[dir], v[at].second + DY[dir]);
        }
        if (sum != -1) {
            clsum += sum;
            F0(dir, 4) if (dir != k) {
                Set(v[at].first + DX[dir], v[at].second + DY[dir], 1);
            }
            go(at + 1);
            F0(dir, 4) if (dir != k) {
                Set(v[at].first + DX[dir], v[at].second + DY[dir], 0);
            }
            clsum -= sum;
        }
    }
}

int main() {
    freopen("x.in", "r", stdin);
    cin >> m >> n;
    F0(i, m * n) scanf("%d", &a[i]);
    cin >> k;
    while (k--) {
        scanf("%d%d", &i, &j);
        b[i*n+j] = 1;
    }
    // find pairs
    F0(i, m) F0(j, n) if (b[i*n + j]) {
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) if (dx || dy) {
                int i2 = i + dx, j2 = j + dy;
                if (i2 < 0 || i2 >= m || j2 < 0 || j2 >= n || !b[i2*n + j2]) continue;
                if (d[i*n + j] && d[i2*n + j2]) continue;
                if (d[i*n + j] || d[i2*n + j2]) nosol();
                d[i*n + j] = 1;
                d[i2*n + j2] = 1;
                F0(k, 5) if (!Empty(i + DX[k], j + DY[k])) nosol();
                F0(k, 5) if (!Empty(i2 + DX[k], j2 + DY[k])) nosol();
                F0(k, 5) if (Empty(i + DX[k], j + DY[k])) Fill(i + DX[k], j + DY[k]);
                F0(k, 5) if (Empty(i2 + DX[k], j2 + DY[k])) Fill(i2 + DX[k], j2 + DY[k]);
            }
        }
    }

    F0(i, m) F0(j, n) if (b[i*n + j] && !d[i*n + j]) {
        if (!Empty(i, j)) nosol();
        int found = 0;
        F0(k, 4) {
            int good = 1;
            F0(dir, 4) if (dir != k) {
                if (!Empty(i + DX[dir], j + DY[dir])) {
                    good = 0;
                    break;
                }
            }
            found = 1;
            break;
        }
        if (!found) nosol();
    }

    F0(i, m) F0(j, n) if (b[i*n + j] && Empty(i, j)) {
        v.clear();
        v.push_back(pii(i, j));
        Fill(i, j);
        DFS(i, j);

        clbest = -1;
        its = 0;
        go(0);

        if (clbest == -1) nosol();
        ans += clbest;
    }

    cout << ans << endl;

    return 0;
}

Compilation message

covering.cpp: In function 'int main()':
covering.cpp:118:17: warning: variable 'good' set but not used [-Wunused-but-set-variable]
             int good = 1;
                 ^~~~
covering.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("x.in", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
covering.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     F0(i, m * n) scanf("%d", &a[i]);
                  ~~~~~^~~~~~~~~~~~~
covering.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &i, &j);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -