Submission #505071

#	Time	Username	Problem	Language	Result	Execution time	Memory
505071		Jarif_Rahman	여별 열쇠 (JOI15_keys)	C++17	100 / 100	4 ms	592 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<vector<vector<int>>> dp(lines.size());
    for(int i = 0; i < lines.size(); i++){
        dp[i] = vector<vector<int>>(lines[i].size(), vector<int>(k+1, inf));
    }
    vector<vector<int>> dpp(lines.size(), vector<int>(k+1, inf));
    for(int i = 0; i < lines.size(); i++) dpp[i][0] = 0;

    for(int i = 0; i < lines.size(); i++){
        int sz = lines[i].size();
        for(int j = 0; j < sz; j++) dp[i][j][0] = calc(lines[i][j]);
        for(int kk = 1; kk <= k; kk++){
            int mn = inf;
            for(int j = sz-2; j >= 0; j--){
                dp[i][j][kk] = calc(lines[i][j]) + dp[i][j+1][kk-1];
                dp[i][j][kk] = min(dp[i][j][kk], inf);
                dp[i][j][kk] = min(dp[i][j][kk], calc(lines[i][j])+calc(lines[i][j+1])+mn);
                mn = min(mn, dp[i][j][kk-1]);
            }
            if(sz == 1 && kk == 1){
                dp[i][0][kk] = calc(lines[i][0]);
            }
            dpp[i][kk] = inf;
            for(int j = 0; j < sz; j++) dpp[i][kk] = min(dpp[i][kk], dp[i][j][kk]);
        }
    }

    int sz = lines.size();
    for(int i = 0; i < sz; i++) dpp[i][0] = 0;

    for(int i = sz-2; i >= 0; i--){
        for(int j = k; j >= 0; j--){
            for(int kk = 0; kk <= j; kk++){
                dpp[i][j] = min(dpp[i][j],dpp[i][kk]+dpp[i+1][j-kk]);
            }
        }
    }

    cout << m-dpp[0][k] << "\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:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < lines.size(); i++) dpp[i][0] = 0;
      |                    ~~^~~~~~~~~~~~~~
keys.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < lines.size(); i++){
      |                    ~~^~~~~~~~~~~~~~

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