Submission #505131

#	Time	Username	Problem	Language	Result	Execution time	Memory
505131		Jarif_Rahman	여별 열쇠 (JOI15_keys)	C++17	100 / 100	1 ms	484 KiB

keys

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+5;

int mn = inf;
int n, m, k;

vector<pair<int, int>> events;
vector<bool> bl;
vector<int> succ;
vector<pair<int, int>> pp;
vector<vector<int>> lines;

void dfs(int nd){
    if(bl[nd]) return;
    bl[nd] = 1;
    lines.back().pb(nd);
    if(succ[nd] != -1) dfs(succ[nd]);
}

int calc(int i){
    return events[i+1].f-events[i].f;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    k = n-k;

    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y; 
        events.pb({x, i+1});
        events.pb({y, -i-1});
    }

    sort(events.begin(), events.end());
    bl.resize(2*n, 0);
    vector<bool> have(2*n, 0);
    succ.resize(2*n, -1);
    pp.resize(n);
    for(int i = 0; i < 2*n; i++){
        if(events[i].sc > 0) pp[events[i].sc-1].f = i;
        else pp[-events[i].sc-1].sc = i-1;
    }
    for(int i = 0; i < n; i++){
        //cerr << pp[i].f << " " << pp[i].sc << "\n";
        if(pp[i].f != pp[i].sc) succ[pp[i].f] = pp[i].sc;
        have[pp[i].f] = 1;
        have[pp[i].sc] = 1;
    }

    for(int i = 0; i < 2*n; i++) if(have[i] && !bl[i]){
        lines.pb({});
        dfs(i);
    }

    vector<int> sth, br;
    for(int i = 0; i < lines.size(); i++){
        if(lines[i].size() == 1){
            sth.pb(lines[i][0]);
            br.pb(2);
            continue;
        }
        for(int j = 0; j < lines[i].size(); j++){
            sth.pb(lines[i][j]);
            br.pb(j == 0);
        }
    }

    //for(int x: sth) cerr << x << " "; cerr << "sth\n";
    //for(int x: br) cerr << x << " "; cerr << "br\n";

    int sz = sth.size();

    vector<vector<int>> dp(sz, vector<int>(k+1, inf));
    for(int i = 0; i < sz; i++) dp[i][0] = 0;

    for(int kk = 1; kk <= k; kk++){
        int mn = inf;
        if(kk == 1) mn = 0;
        for(int i = sz-1; i >= 0; i--){
            if(br[i] == 2){
                dp[i][kk] = calc(sth[i]) + mn;
                dp[i][kk] = min(dp[i][kk], inf);
                mn = min(mn, dp[i][kk-1]);
                continue;
            }
            if((kk == 1 && i == sz-1) || br[i+1] != 0) continue;
            if(i != sz-1 && br[i+1] == 0 && kk > 1){
                dp[i][kk] = calc(sth[i]) + dp[i+1][kk-1];
                dp[i][kk] = min(dp[i][kk], inf);
            }
            dp[i][kk] = min(dp[i][kk], calc(sth[i])+calc(sth[i+1])+mn);
            mn = min(mn, dp[i][kk-1]);
        }
    }

    int ans = inf;
    for(int i = 0; i < sz; i++) ans = min(ans, dp[i][k]);
    ans = m-ans;
    cout << ans << "\n";
}

Compilation message (stderr)

keys.cpp: In function 'int main()':
keys.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < lines.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
keys.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j = 0; j < lines[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~

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