oj.uz

Submission #505071

# Submission time Handle Problem Language Result Execution time Memory
505071 2022-01-10T12:58:56 Z Jarif_Rahman JOI15_keys (JOI15_keys) C++17
100 / 100
 4 ms 592 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<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

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

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

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 2 ms 568 KB Output is correct
17 Correct 3 ms 592 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 4 ms 572 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct