제출 #1369126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369126		pcheloveks	Teleporter 2 (JOI26_teleporter)	C++20	32 / 100	3599 ms	125816 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;
    }

    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: 3 / 3
• 서브태스크 3: 29 / 29
• 서브태스크 4: 0 / 23
• 서브태스크 5: 0 / 24
• 서브태스크 6: 0 / 16