oj.uz

Submission #168693

# Submission time Handle Problem Language Result Execution time Memory
168693 2019-12-15T11:04:09 Z ho94949 Cultivation (JOI17_cultivation) C++17
5 / 100
 3 ms 1140 KB 
#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;
    };

    int 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;
            
            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;
            int ans = 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)
                c = min(c, V[k+1]-V[k]);
            
            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("%d\n", rans);
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Incorrect 3 ms 376 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Incorrect 3 ms 376 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Incorrect 3 ms 376 KB Output isn't correct
20 Halted 0 ms 0 KB -