oj.uz

Submission #505131

# Submission time Handle Problem Language Result Execution time Memory
505131 2022-01-10T16:39:55 Z Jarif_Rahman JOI15_keys (JOI15_keys) C++17
100 / 100
 1 ms 484 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 484 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct