oj.uz

답안 #814342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814342 2023-08-08T06:57:36 Z 이동현(#10122) Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 0 ms 212 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 L, n;
    cin >> L >> n;
    // L = n = 3000;
    vector<array<int, 4>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        --a[i][0], --a[i][1];

        // a[i][2] = 1;
        // a[i][0] = rand() % 3000;
        // a[i][1] = rand() % 3000;

        assert(a[i][2] == 1);

        if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
    }

    int ans = (int)1e9;
    auto sol = [&](){
        vector<int> pre(L);
        for(int i = 0; i < n; ++i){
            if(!a[i][3]){
                pre[a[i][0]] += 1;
                pre[a[i][1]] -= 1;
            }
            else{
                pre[a[i][1]] += 1;
                pre[0] += 1;
                pre[a[i][0]] -= 1;
            }
        }

        int nans = 0;
        for(int i = 0; i < L; ++i){
            if(i) pre[i] += pre[i - 1];

            nans = max(nans, pre[i]);
        }

        return nans;
    };

    // assert(n <= 300);

    auto doit = [&]{
        for(int i = 0; i < 1; ++i){
            for(int j = n - 1; j < n; ++j){
                for(int k = 0; k < n; ++k){
                    a[k][3] = (i <= k && k <= j);
                }
                
                int nans = sol();
                while(true){
                    int now = nans;

                    for(int i = 0; i < n; ++i){
                        a[i][3] ^= 1;

                        int prv = now;
                        now = min(now, sol());

                        if(now == prv) a[i][3] ^= 1;
                    }

                    if(now == nans) break;

                    nans = now;
                }

                ans = min(ans, nans);
            }
        }
    };
    
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0]) < make_pair(y[1], y[0]);});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0] + x[1]) < make_pair(y[1], y[0] + y[1]);});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[1], x[0] - x[1]) < make_pair(y[1], y[0] - y[1]);});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[1]) < make_pair(y[0], y[1]);});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[0] + x[1]) < make_pair(y[0], y[0] + y[1]);});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return make_pair(x[0], x[0] - x[1]) < make_pair(y[0], y[0] - y[1]);});
    // doit();
    sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] + x[1] < y[0] + y[1];});
    doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] < y[0];});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[0] - x[1] < y[0] - y[1];});
    // doit();
    // sort(a.begin(), a.end(), [&](array<int, 4>&x, array<int, 4>&y){return x[1] < y[1];});
    // doit();

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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