Submission #142666

#	Time	Username	Problem	Language	Result	Execution time	Memory
142666		popovicirobert	Fence (CEOI08_fence)	C++14	100 / 100	5 ms	504 KiB

fence

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



/*const int MOD = 998244353;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

#define x first
#define y second

const int INF = 1e9;

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    vector < pair <int, int> > hole(n), tree(m);
    for(auto &it : hole) {
        cin >> it.x >> it.y;
    }
    for(auto &it : tree) {
        cin >> it.x >> it.y;
    }
    sort(hole.begin(), hole.end());
    sort(tree.begin(), tree.end());

    auto ccw = [&](pair <int, int> &a, pair <int, int> &b, pair <int, int> &c) {
        return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
    };

    vector < vector <int> > cnt(n, vector <int>(n));
    for(i = 0; i < n; i++) {
        for(auto &it : tree) {
            if(hole[i].x == it.x && it.y <= hole[i].y) {
                cnt[i][i]++;
            }
        }
        for(j = i + 1; j < n; j++) {
            for(auto &it : tree) {
                if(hole[i].x <= it.x && it.x <= hole[j].x && ccw(hole[i], it, hole[j]) > 0) {
                    cnt[i][j]++;
                }
            }
        }
    }

    vector < vector <int> > up(n, vector <int>(n, INF)), down(n, vector <int>(n, INF));
    for(int len = 1; len < n; len++) {
        for(i = 0; i + len < n; i++) {
            j = i + len;
            up[i][j] = 40 - cnt[i][j] * 111;
            down[i][j] = 40 + cnt[i][j] * 111;
            for(int k = i + 1; k < j; k++) {
                if(ccw(hole[i], hole[k], hole[j]) < 0) {
                    up[i][j] = min(up[i][j], up[i][k] + up[k][j] - 20 + 111 * cnt[k][k]);
                }
                else {
                    down[i][j] = min(down[i][j], down[i][k] + down[k][j] - 20 - 111 * cnt[k][k]);
                }
            }
        }
    }

    int ans = 111 * m;
    for(i = 0; i < n; i++) {
        for(j = i; j < n; j++) {
            ans = min(ans, up[i][j] + down[i][j] - 40 + 111 * m);
        }
    }
    cout << ans;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10