제출 #1369128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369128		pcheloveks	Teleporter 2 (JOI26_teleporter)	C++20	0 / 100	0 ms	344 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
 
#include <bits/stdc++.h>
 
#define endl '\n'
 
//#pragma GCC optimize("Ofast")
 
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
 
const ll INF = 2e18;
const ll DIM = 100007;
const ll DIMQ = 2007;
const ld PI = 3.1415926535;
const int mod = 998244353;

struct interval {
    ll l, r, c;
};

bool cmp(interval i1, interval i2) {
    if(i1.l != i2.l) return i1.l < i2.l;
    return i1.r < i2.r;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
#ifdef IloveCP
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif  

    int n, m, k;
    cin >> n >> m >> k;

    vector < interval > a(m + 1);
    for(int i = 1; i <= m; i++) {
        cin >> a[i].l >> a[i].r >> a[i].c;
    }

    if(k == 1) {
        vector < pii > R, L;
        for(int i = 1; i <= m; i++) {
            R.push_back({a[i].r, i});
            L.push_back({a[i].l, i});
        }

        sort(R.begin(), R.end());
        sort(L.begin(), L.end());

        vector < ll > res(m + 1, 0);
        int ptr = 0;
        ll sum = 0;
        for(int i = 0; i < m; i++) {
            while(ptr < m && R[ptr].first < R[i].first) {
                sum += a[R[ptr].second].c;
                ptr++;
            }
            res[R[i].second] += sum;
        }
        ptr = 0;
        sum = 0;
        for(int i = 1; i <= m; i++) sum += a[i].c;
        
        for(int i = 0; i < m; i++) {
            while(ptr < m && L[ptr].first < L[i].first) {
                sum -= a[L[ptr].second].c;
                ptr++;
            }
            res[L[i].second] += sum - a[L[i].second].c;
        }

        ll ans = INF;
        for(int i = 1; i <= m; i++) ans = min(ans, res[i]);
        cout << ans << endl;
    }
    else {

        sort(a.begin(), a.end(), cmp);

        vector < vector < ll > > dp(m + 2, vector < ll >(k + 1, INF));

        dp[0][0] = 0;
        for(int i = 0; i <= m; i++) {
            vector < pii > to;
            for(int j = 1; j <= m; j++) {
                if(a[j].l >= a[i].r) to.push_back({a[j].r, j});
            }

            sort(to.begin(), to.end());

            for(int x = 0; x <= k; x++) {
                if(dp[i][x] >= INF) continue;

                ll cost = 0;
                for(int j = 0; j < to.size(); j++) {
                    if(x != k) dp[to[j].second][x + 1] = min(dp[to[j].second][x + 1], dp[i][x] + cost);
                    cost += a[to[j].second].c;
                }
                dp[m + 1][x] = min(dp[m + 1][x], dp[i][x] + (ll)cost);
            }
        }

        ll res = INF;
        for(int i = 0; i <= k; i++) res = min(res, dp[m + 1][i]);

        cout << res << endl;
    }

    return 0;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 0 / 5
• 서브태스크 2: 0 / 3
• 서브태스크 3: 0 / 29
• 서브태스크 4: 0 / 23
• 서브태스크 5: 0 / 24
• 서브태스크 6: 0 / 16