Submission #45301693

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
namespace r = ranges;
#define BE(x) x.begin(), x.end()
using ll = long long;
template<class T> using vec = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);



    chrono::system_clock::time_point time_a, time_b, time_c;
    time_a = chrono::system_clock::now();



    int t, h, w, i0;
    cin >> t >> h >> w >> i0;
    vec<string> hs(h-1), vs(h);
    for (auto &e : hs) cin >> e;
    for (auto &e : vs) cin >> e;

    const int n = h*w;
    vec<vec<int>> g(n);

    const int di[] = {-1, 1, 0, 0};
    const int dj[] = {0, 0, -1, 1};
    for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j) {
        const int v = i*w+j;
        for (int d = 0; d < 4; ++d) {
            int ni = i+di[d];
            int nj = j+dj[d];
            if (ni < 0 || h <= ni) continue;
            if (nj < 0 || w <= nj) continue;
            if (d==0 && hs[i-1][j]=='1') continue;
            if (d==1 && hs[i][j]  =='1') continue;
            if (d==2 && vs[i][j-1]=='1') continue;
            if (d==3 && vs[i][j]  =='1') continue;
            g[v].push_back(ni*w+nj);
        }
    }

    const int door = i0*w;

    vec<int> level(n,-1);
    int yet = r::count(level,-1);
    while (yet) {
        static int lev = 0;
        for (int i = 0; i < n; ++i) {
            if (level[i] != -1) continue;
            bitset<400> bs;
            auto dfs = [&](auto &f, int v) -> void {
                bs[v] = true;
                for (auto &e : g[v]) {
                    if (level[e] == lev) {
                        bs[e] = true;
                        continue;
                    }
                    if (level[e] != -1) continue;
                    if (bs[e]) continue;
                    if (e == i) continue;
                    f(f, e);
                }
            };
            if (i != door) dfs(dfs, door);
            if (r::count(level,-1)+r::count(level,lev) == (ll)(bs.count()+1)) level[i] = lev;
        }
        int nyet = r::count(level,-1);
        if (yet == nyet) break;
        yet = nyet;
        ++lev;
    }
    vec<pair<int,int>> lev_v(n);
    for (int i = 0; i < n; ++i) {
        lev_v[i] = {level[i],i};
    }
    r::sort(lev_v);



    int k;
    cin >> k;
    vec<int> s(k), d(k);
    for (int i = 0; i < k; ++i) {
        cin >> s[i] >> d[i];
    }
    vec<int> score(k);
    for (int i = 0; i < k; ++i) {
        score[i] = d[i]-s[i]+1;
    }

    vector crops(101, vector(101, vec<tuple<float,float,int>>())); // [m][d] {-(s-m),d-m,i}
    for (int m = 1; m <= t; ++m) {
        for (int i = 0; i < k; ++i) {
            if (s[i] < m) continue;
            tuple<float,float,int> tt = {-(s[i]-m), d[i]-m, i};
            for (int j = d[i]; j <= 100; ++j) {
                crops[m][j].push_back(tt);
            }
        }
    }

    using Plan = vec<tuple<int,int,int,int>>; // k, i, j, s
    Plan ans;
    int score_max = 0;

    const float exp_init = 1;
    const float exp_step = 0.8;
    const float exp_lim  = 16;
    const float powbase = 1.125;

    chrono::milliseconds last_lap(0);
    for (float exp = exp_init; exp <= exp_lim; exp += exp_step) {
        time_c = std::chrono::system_clock::now();
        last_lap = chrono::duration_cast<chrono::milliseconds>(time_c - time_b);
        chrono::milliseconds elapsed = chrono::duration_cast<chrono::milliseconds>(time_c - time_a);
        time_b = time_c;
        if (exp != exp_init && elapsed+last_lap > (chrono::milliseconds)1950) break;

        for (auto &cm : crops)
        for (auto &e : cm) {
            const float spow = pow(powbase,exp);
            const float dpow = pow(powbase,-exp);
            r::sort(e,  [&exp, &spow, &dpow](auto a, auto b) {
                auto f = [&exp, &spow, &dpow](tuple<float,float,int> &x) {
                    auto& [xs, xd, _] = x;
                    return xs*spow + xd*dpow;
                };
                return f(a) < f(b);
            });
        }

        Plan plan;
        int score_sum = 0;
        bitset<40000> done;
        vec<int> harvest(n,-1);
        for (int month = 1; month <= t; ++month) {
            auto cm = crops[month];

            for (auto &[lev,v] : lev_v) {
                if (harvest[v] != -1) continue;

                // check limit
                bitset<400> bs;
                auto dfs = [&](auto &f, int u) -> void {
                    bs[u] = true;
                    for (auto &e : g[u]) {
                        if (e == v) continue;
                        if (bs[e]) continue;
                        if (harvest[e] != -1) {
                            bs[e] = true;
                            continue;
                        }
                        f(f, e);
                    }
                };
                if (harvest[door] == -1 && v != door)
                    dfs(dfs, door);
                int md = 100;
                for (int i = 0; i < n; ++i) {
                    if (bs[i]) continue;
                    if (i == v) continue;
                    md = min(md, harvest[i]);
                }

                // plant
                for (int i = md; i >= 0; --i) {
                    bool flg = false;
                    while (!cm[i].empty()) {
                        auto [_,__,cr] = cm[i].back();
                        cm[i].pop_back();
                        if (done[cr]) continue;
                        flg = true;
                        plan.emplace_back(cr+1, v/w, v%w, month);
                        score_sum += score[cr];
                        done[cr] = true;
                        harvest[v] = d[cr];
                        break;
                    }
                    if (flg) break;
                }
            }
            for (int v = 0; v < n; ++v) {
                if (harvest[v] == month) harvest[v] = -1;
            }
        }
        if (score_sum > score_max) ans = plan;
        // cout << "score:" << score_sum << ", window:" << exp << ", time:" << last_lap << "\n";
    }



    cout << ans.size() << '\n';
    for (auto &[k,i,j,s] : ans) {
        cout << k << ' ' << i << ' ' << j << ' ' << s << '\n';
    }
}

Submission Info

Judge Result