Submission #1162670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162670		abysmal	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	75 / 100	1098 ms	56648 KiB

joi2019_ho_t3

#include <array>

template <typename T, int NDIMS> struct tensor_view {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    T* data;

    tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_, T* data_) : shape(shape_), strides(strides_), data(data_) {}

public:
    tensor_view() : shape{0}, strides{0}, data(nullptr) {}

protected:
    int flatten_index(std::array<int, NDIMS> idx) const {
        int res = 0;
        for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
        return res;
    }
    int flatten_index_checked(std::array<int, NDIMS> idx) const {
        int res = 0;
        for (int i = 0; i < NDIMS; i++) {
            assert(0 <= idx[i] && idx[i] < shape[i]);
            res += idx[i] * strides[i];
        }
        return res;
    }

public:
    T& operator[] (std::array<int, NDIMS> idx) const {
#ifdef _GLIBCXX_DEBUG
        return data[flatten_index_checked(idx)];
#else
        return data[flatten_index(idx)];
#endif
    }
    T& at(std::array<int, NDIMS> idx) const {
        return data[flatten_index_checked(idx)];
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) const {
        std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1, shape.end(), nshape.begin());
        std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1, strides.end(), nstrides.begin());
        T* ndata = data + (strides[0] * idx);
        return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) const {
        assert(0 <= idx && idx < shape[0]);
        return operator[](idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator * () const {
        return *data;
    }

    template <typename U, int D> friend struct tensor_view;
    template <typename U, int D> friend struct tensor;
};

template <typename T, int NDIMS> struct tensor {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    int len;
    T* data;

public:
    tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}

    explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
        shape = shape_;
        len = 1;
        for (int i = NDIMS-1; i >= 0; i--) {
            strides[i] = len;
            len *= shape[i];
        }
        data = new T[len];
        std::fill(data, data + len, t);
    }

    tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
        for (int i = 0; i < len; i++) {
            data[i] = o.data[i];
        }
    }

    tensor& operator=(tensor&& o) noexcept {
        using std::swap;
        swap(shape, o.shape);
        swap(strides, o.strides);
        swap(len, o.len);
        swap(data, o.data);
        return *this;
    }
    tensor(tensor&& o) : tensor() {
        *this = std::move(o);
    }
    tensor& operator=(const tensor& o) {
        return *this = tensor(o);
    }
    ~tensor() { delete[] data; }

    using view_t = tensor_view<T, NDIMS>;
    view_t view() {
        return tensor_view<T, NDIMS>(shape, strides, data);
    }
    operator view_t() {
        return view();
    }

    using const_view_t = tensor_view<const T, NDIMS>;
    const_view_t view() const {
        return tensor_view<const T, NDIMS>(shape, strides, data);
    }
    operator const_view_t() const {
        return view();
    }

    T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }
    T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
    const T& operator[] (std::array<int, NDIMS> idx) const { return view()[idx]; }
    const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) {
        return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
        return view().at(idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type operator[] (int idx) const {
        return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int idx) const {
        return view().at(idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator * () {
        return *view();
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), const T&>::type operator * () const {
        return *view();
    }
};

#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stdint.h>
#include<vector>

#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...)
#endif

using namespace std;

const int64_t INF = (int64_t) 1e18 + 777;
const int64_t mINF = (int64_t) 1e9 + 777;
const int64_t MOD = (int64_t) 1e9 + 7;

int getID(char c)
{
    if(c == 'R') return 0;
    if(c == 'G') return 1;
    if(c == 'Y') return 2;
    return -1;
}

struct Solution
{
	Solution() {}

	void solve()
	{
        int n;
        string s;
        cin >> n >> s;
        int k = 3;
        vector<vector<int> > colors(k);

        // ???
        for (int i = 0; i < k; i++) {
            colors.reserve(n);
        }

        vector<vector<int> > prefix(k, vector<int>(n + 1, 0));

        for(int i = 0; i < n; i++)
        {
            int x = getID(s[i]);
            colors[x].push_back(i);
            prefix[x][i + 1] = 1;
        }

        for(int i = 0; i < k; i++)
        {
            colors[i].push_back(n);
            // sort(colors[i].begin(), colors[i].end());

            for(int j = 1; j <= n; j++)
            {
                prefix[i][j] += prefix[i][j - 1];
            }
        }

        int r = colors[0].size();
        int g = colors[1].size();
        int y = colors[2].size();
        // vector<vector<vector<vector<vector<int> > > > > dp(2, vector<vector<vector<vector<int> > > >(k, vector<vector<vector<int> > >(r, vector<vector<int> >(g, vector<int>(y, mINF)))));
        tensor<int, 5> dp({2, k, r, g, y}, mINF);

        if(r > 1) dp[{0, 0, 1, 0, 0}] = colors[0][0];
        if(g > 1) dp[{0, 1, 0, 1, 0}] = colors[1][0];
        if(y > 1) dp[{0, 2, 0, 0, 1}] = colors[2][0];
        int t = 1;
        for(int i = 1; i < n; i++)
        {
            int p = t ^ 1;
            for(int last = 0; last < k; last++)
            {
                for(int cr = 0; cr < r; cr++)
                {
                    for(int cg = 0; cg < g; cg++)
                    {
                        for(int cy = 0; cy < y; cy++)
                        {
                            if(dp[{p, last, cr, cg, cy}] == mINF) continue;

                            // red
                            // A = last B = now C = other
                            if(last != 0 && cr != r - 1)
                            {
                                int a = last;
                                int b = 0;
                                int c = 0;

                                int cur_a = 0;
                                int cur_c = 0;
                                int cur_b = colors[b][cr];
                                if(a == 1)
                                {
                                    c = 2;
                                    cur_a = colors[a][cg];
                                    cur_c = colors[c][cy];
                                }
                                else
                                {
                                    c = 1;
                                    cur_a = colors[a][cy];
                                    cur_c = colors[c][cg];
                                }

                                int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                                int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                                cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);

                                int cost = cnt1 + cnt2;
                                dp[{t, b, cr + 1, cg, cy}] = min(dp[{t, b, cr + 1, cg, cy}], dp[{p, last, cr, cg, cy}] + cost); 
                            }

                            // green
                            if(last != 1 && cg != g - 1)
                            {
                                int a = last;
                                int b = 1;
                                int c = 0;

                                int cur_a = 0;
                                int cur_c = 0;
                                int cur_b = colors[b][cg];
                                if(a == 0)
                                {
                                    c = 2;
                                    cur_a = colors[a][cr];
                                    cur_c = colors[c][cy];
                                }
                                else
                                {
                                    c = 0;
                                    cur_a = colors[a][cy];
                                    cur_c = colors[c][cr];
                                }

                                int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                                int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                                cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);
                                int cost = cnt1 + cnt2;
                                dp[{t, b, cr, cg + 1, cy}] = min(dp[{t, b, cr, cg + 1, cy}], dp[{p, last, cr, cg, cy}] + cost); 
                            }

                            // yellow
                            if(last != 2 && cy != y - 1)
                            {
                                int a = last;
                                int b = 2;
                                int c = 0;

                                int cur_a = 0;
                                int cur_c = 0;
                                int cur_b = colors[b][cy];
                                if(a == 0)
                                {
                                    c = 1;
                                    cur_a = colors[a][cr];
                                    cur_c = colors[c][cg];
                                }
                                else
                                {
                                    c = 0;
                                    cur_a = colors[a][cg];
                                    cur_c = colors[c][cr];
                                }

                                int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                                int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                                cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);

                                int cost = cnt1 + cnt2;
                                dp[{t, b, cr, cg, cy + 1}] = min(dp[{t, b, cr, cg, cy + 1}], dp[{p, last, cr, cg, cy}] + cost); 
                            }
                        }
                    }
                }
            }

            t ^= 1;
            for(int last = 0; last < k; last++)
            {
                for(int cr = 0; cr < r; cr++)
                {
                    for(int cg = 0; cg < g; cg++)
                    {
                        for(int cy = 0; cy < y; cy++)
                        {
                            dp[{p, last, cr, cg, cy}] = mINF;
                        }
                    }
                }
            }
        }

        int ans = mINF;
        for(int last = 0; last < k; last++)
        {
            ans = min(ans, dp[{t ^ 1, last, r - 1, g - 1, y - 1}]);
        }
        if(ans == mINF) ans = -1;
        cout << ans << "\n";
	}

	int modadd(int a, int b)
	{
		int res = a + b;
		if(res >= MOD) res -= MOD;
		return res;
	}

	int modmul(int a, int b)
	{
		return (1LL * a * b) % MOD;
	}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	for(int i = 0; i < t; i++)
	{
		Solution().solve();
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25