oj.uz

Submission #447638

# Submission time Handle Problem Language Result Execution time Memory
447638 2021-07-27T07:42:48 Z Haruto810198 Cultivation (JOI17_cultivation) C++17
5 / 100
 2000 ms 464 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = 1e18;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 310;

int n;
int R, C;
pii pt[MAX];

int res;

int check(int dxl, int dxr){

    //cerr<<"check("<<dxl<<", "<<dxr<<") : "<<endl;

    multiset<int> st;
    vector<vi> ev;
    /// insert : time,  1, pos
    /// erase  : time, -1, pos

    vector<vi> seg; /// minL, minR, minSum, L, R

    FOR(i, 1, n, 1){
        ev.pb({pt[i].F - dxl, 1, pt[i].S});
        ev.pb({pt[i].F + dxr + 1, -1, pt[i].S});
    }

    sort(ev.begin(), ev.end());

    int pv_time = -LNF;
    int minL = LNF, minR = LNF, minSum = LNF;

    for(auto E : ev){

        int Time = E[0];
        int type = E[1];
        int pos = E[2];

        if(pv_time < Time){
            seg.pb({minL, minR, minSum, pv_time, Time - 1});
        }

        pv_time = Time;

        if(type == 1){
            st.insert(pos);
        }
        else{
            auto it = st.find(pos);
            st.erase(it);
        }

        if(st.empty()){
            minSum = LNF;
        }
        else{

            minSum = 0;
            for(auto it=st.begin(); it!=st.end(); it++){

                if(it == st.begin()){
                    minL = *it - 1;
                }

                if(next(it) == st.end()){
                    minR = C - *it;
                }
                else{
                    auto nit = next(it);
                    minSum = max(minSum, *nit - *it - 1);
                }

            }

        }

    }

    int retL = 0, retR = 0, retSum = 0;

    //cerr<<"seg : "<<endl;

    bool AC = 0;

    for(auto I : seg){

        if(I[3] > R or I[4] < 1){
            continue;
        }
        /*
        cerr<<"{";
        for(auto i : I){
            cerr<<i<<", ";
        }
        cerr<<"}"<<endl;
        */
        retL = max(retL, I[0]);
        retR = max(retR, I[1]);
        retSum = max(retSum, I[2]);

        if(I[4] >= R){
            AC = 1;
        }

    }

    retSum = max(retSum, retL + retR);

    if(AC == 0){
        retSum = LNF;
    }

    //cerr<<dxl + dxr + retSum<<endl;

    return dxl + dxr + retSum;

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>R>>C;
    cin>>n;
    FOR(i, 1, n, 1){
        cin>>pt[i].F>>pt[i].S;
    }

    res = LNF;

    FOR(dxl, 0, R, 1){
        FOR(dxr, 0, R, 1){
            res = min(res, check(dxl, dxr));
        }
    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 66 ms 336 KB Output is correct
19 Correct 34 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 96 ms 332 KB Output is correct
22 Correct 422 ms 336 KB Output is correct
23 Correct 52 ms 324 KB Output is correct
24 Correct 1081 ms 464 KB Output is correct
25 Correct 632 ms 348 KB Output is correct
26 Execution timed out 2079 ms 384 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 66 ms 336 KB Output is correct
19 Correct 34 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 96 ms 332 KB Output is correct
22 Correct 422 ms 336 KB Output is correct
23 Correct 52 ms 324 KB Output is correct
24 Correct 1081 ms 464 KB Output is correct
25 Correct 632 ms 348 KB Output is correct
26 Execution timed out 2079 ms 384 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 66 ms 336 KB Output is correct
19 Correct 34 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 96 ms 332 KB Output is correct
22 Correct 422 ms 336 KB Output is correct
23 Correct 52 ms 324 KB Output is correct
24 Correct 1081 ms 464 KB Output is correct
25 Correct 632 ms 348 KB Output is correct
26 Execution timed out 2079 ms 384 KB Time limit exceeded
27 Halted 0 ms 0 KB -