oj.uz

답안 #801616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
801616 2023-08-02T06:55:54 Z 이동현(#10092) Cultivation (JOI17_cultivation) C++17
0 / 100
 7 ms 320 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int r, c, n;
    cin >> r >> c >> n;
    vector<array<int, 2>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1];
        --a[i][0];
        --a[i][1];
    }

    vector<int> dpu;
    sort(a.begin(), a.end());
    for(int i = 0; i < n; ++i){
        dpu.push_back(a[i][0] + 1);

        dpu.push_back(r - a[i][0]);
        for(int j = i + 1; j < n; ++j){
            dpu.push_back(a[j][0] - a[i][0] + 1);
        }
        for(int j = 0; j < n; ++j){
            dpu.push_back(a[j][0] + r - a[i][0]);
        }
    }

    sort(dpu.begin(), dpu.end());
    dpu.erase(unique(dpu.begin(), dpu.end()), dpu.end());

    auto sol = [&](int dulen)->int{
        int rv = (int)1e18;

        vector<array<int, 3>> que;
        
        for(int j = 0; j < n; ++j){
            que.push_back({a[j][0], -1, a[j][1]});
            que.push_back({a[j][0] + dulen, 1, a[j][1]});
        }

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

        auto insol = [&](int stpos){
            int lmx = 0, rmx = 0, lenmx = 0;
            
            multiset<int> st;

            for(int j = 0; j < (int)que.size(); ++j){
                auto i = que[j];
                if(i[1] == -1){
                    st.insert(i[2]);
                }
                else{
                    st.erase(st.find(i[2]));
                }

                if((j == (int)que.size() - 1 || que[j + 1][0] > i[0]) && i[0] >= stpos && i[0] < stpos + r){
                    // cout << dulen << ' ' << stpos << ' ' << i[0] << ' ' << (int)st.size() << endl;
                    if(!(int)st.size()){
                        lenmx = (int)1e9;
                    }
                    else{
                        lmx = max(lmx, *st.begin());
                        rmx = max(rmx, c - *(--st.end()) - 1);
                    }
                }
            }

            // cout << dulen << ' ' << stpos << ' ' << lenmx << ' ' << lmx << ' ' << rmx << endl;
            rv = min(rv, max(lenmx - 1, lmx + rmx));
        };
        // for(int i = 0; i < r; ++i){
        //     insol(i);
        // }

        for(int i = 0; i < n; ++i){
            insol(a[i][0]);
        }

        return rv;
    };

    int ans = (int)1e18;

    for(auto&dulen:dpu){
        ans = min(ans, dulen - 1 + sol(dulen));
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -