Submission #1215899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215899		duckindog	여별 열쇠 (JOI15_keys)	C++20	100 / 100	2 ms	1352 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 10,
            MAX = 1'000'000'000;

int n, m, k;
int s[N], t[N];

int type[N << 1], id[N << 1];
int nxt[N], deg[N];

int cost1[N], cost2[N];
int f[N][N][2];
int answer[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> s[i] >> t[i];

    vector<int> rrh(s + 1, s + n + 1);
    rrh.insert(rrh.end(), t + 1, t + n + 1);
    sort(rrh.begin(), rrh.end());
    rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());
    rrh.insert(rrh.begin(), 0);

    for (int i = 1; i <= n; ++i) { 
        s[i] = upper_bound(rrh.begin() + 1, rrh.end(), s[i]) - rrh.begin() - 1;
        t[i] = upper_bound(rrh.begin() + 1, rrh.end(), t[i]) - rrh.begin() - 1;
        
        type[s[i]] = 1;
        id[s[i]] = id[t[i]] = i;
    }

    for (int i = 2; i < (int)rrh.size(); ++i) { 
        int idI = id[i], idJ = id[i - 1];
        if (!type[i]) { 
            if (!type[i - 1] || idJ == idI) cost1[idI] += rrh[i] - rrh[i - 1];
            else {
                cost2[idI] += rrh[i] - rrh[i - 1];
                nxt[idJ] = idI;
                deg[idI] += 1;
            }
        } else { 
            if (type[i - 1]) cost1[idJ] += rrh[i] - rrh[i - 1];
        }
    }
    
    for (int i = 0; i <= n; ++i) { 
        for (int j = 0; j <= k; ++j) f[i][j][0] = f[i][j][1] = MAX;
    }
    fill(answer + 1, answer + n + 1, MAX);
    auto cal = [&](int x) { 
        f[x][0][0] = cost1[x];
        f[x][1][1] = 0;
        
        while (nxt[x]) { 
            int pre = x; x = nxt[x];
            for (int i = 0; i <= k; ++i) { 
                { // no key
                    auto& ret = f[x][i][0];
                    ret = min(ret, f[pre][i][0] + cost2[x] + cost1[x]);
                    ret = min(ret, f[pre][i][1] + cost2[x] + cost1[x]);
                }
                if (i) { // have key
                    auto& ret = f[x][i][1];
                    ret = min(ret, f[pre][i - 1][0] + cost2[x]);
                    ret = min(ret, f[pre][i - 1][1]);
                }
            }
        }
        
        for (int i = k; i >= 0; --i) { 
            int value = MAX;
            for (int j = i; j >= 0; --j) { 
                value = min(value, answer[i - j] + min(f[x][j][0], f[x][j][1]));
            }
            answer[i] = value;
        }
    };

    for (int i = 1; i <= n; ++i) { 
        if (!deg[i]) cal(i);
    }

    cout << m - *min_element(answer, answer + k + 1) << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90