Submission #168697

#	Time	Username	Problem	Language	Result	Execution time	Memory
168697		ho94949	Cultivation (JOI17_cultivation)	C++17	5 / 100	3 ms	1140 KiB

cultivation

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 303, INF = 0x3f3f3f3f;
int R, C, N, S[MAXN], E[MAXN];

int key[MAXN];
vector<int> val[MAXN];

int main()
{
    scanf("%d%d%d", &R, &C, &N);
    map<int, vector<int> > pts;
    for(int i=0; i<N; ++i)
    {
        scanf("%d%d", S+i, E+i);
        pts[E[i]].push_back(S[i]);
    }
    int K = 0;

    for(auto [a, b]: pts)
    {
        key[K] = a;
        val[K] = b;
        ++K;
    }

    auto ins = [](vector<int> &V, int x)
    {
        V.push_back(x);
        for(int i=(int)V.size()-1; i>0; --i)
        {
            if(V[i] < V[i-1]) swap(V[i], V[i-1]);
            else break;
        }
    };
    
    auto m2 = [](vector<tuple<int, int, int, int> > merged, vector<tuple<int, int, int, int> > abc)
    {
        //merge merged, abc
        vector<tuple<int, int, int, int> > newmerged;
        size_t tp1 = 0, tp2 = 0;

        while(tp1 != merged.size() || tp2 != abc.size())
        {
            int n1 = tp1==merged.size()?INF:get<0>(merged[tp1]);
            int n2 = tp2==abc.size()?INF:get<0>(abc[tp2]);
            if(n1 < n2)
            {
                auto [_n1, a1, b1, c1] = merged[tp1];
                auto [_n2, a2, b2, c2] = abc[tp2-1];
                newmerged.emplace_back(n1, max(a1, a2), max(b1, b2), max(c1, c2));
                ++tp1;
            }
            else if(n1 > n2)
            {
                auto [_n1, a1, b1, c1] = merged[tp1-1];
                auto [_n2, a2, b2, c2] = abc[tp2];
                newmerged.emplace_back(n2, max(a1, a2), max(b1, b2), max(c1, c2));
                ++tp2;
            }
            else
            {
                auto [_n1, a1, b1, c1] = merged[tp1];
                auto [_n2, a2, b2, c2] = abc[tp2];
                newmerged.emplace_back(n1, max(a1, a2), max(b1, b2), max(c1, c2));
                ++tp1; ++tp2;
            }
        }
        return newmerged;
    };

    long long rans = 2*INF;

    vector<tuple<int, int, int, int> > merged;
    merged.emplace_back(0, 0, 0, 0);
    for(int i=K-1; i>=0; --i)
    {
        vector<int> V;
        vector<tuple<int, int, int, int> > abc;
        for(int j=K-1; j>=0; --j)
        {
            for(auto x: val[j]) ins(V, x);
            int n = C-key[j] + key[i] - 1; //moved key[i]-1 west time
            int a = V[0]-1, b = R-V.back(), c = INF;
            for(int k=0; k<(int)V.size()-1; ++k)
                if(V[k] != V[k+1]) c = min(c, V[k+1]-V[k]-1);

            if(V[0] == V.back()) c = 0;

            c = max(a+b, c);
            
            if(abc.size() == 0 && n != 0)
                abc.emplace_back(0, INF, INF, INF);
            abc.emplace_back(n, a, b, c);
        }

        vector<tuple<int, int, int, int> > mm = m2(merged, abc);
        for(auto x: mm)
        {
            auto [a, b, c, d] = x;
            long long ans = 0LL + a + max(d, b+c);
            rans = min(ans, rans);
            //cout << a << " " << b << " " << c <<" " <<d <<endl;
        }

        if(i == 0) break;
        V.clear(); abc.clear();
        for(int j=i-1; j>=0; --j)
        {
            for(auto x: val[j]) ins(V, x);
            int n = key[i] - key[j] - 1;
            int a = V[0]-1, b = R-V.back(), c = a+b;
            for(int k=0; k<(int)V.size()-1; ++k)
                if(V[k] != V[k+1]) c = min(c, V[k+1]-V[k]-1);

            if(V[0] == V.back()) c = 0;
            c = max(a+b, c);

            if(abc.size() == 0 && n != 0)
                abc.emplace_back(0, INF, INF, INF);
            abc.emplace_back(n, a, b, c);
        }
        merged = m2(merged, abc);
    }
    printf("%lld\n", rans);
}

Compilation message (stderr)

cultivation.cpp: In lambda function:
cultivation.cpp:49:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1];
                                      ^
cultivation.cpp:50:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2-1];
                                      ^
cultivation.cpp:56:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1-1];
                                      ^
cultivation.cpp:57:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2];
                                      ^
cultivation.cpp:63:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1];
                                      ^
cultivation.cpp:64:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2];
                                      ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &R, &C, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", S+i, E+i);
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20