제출 #658046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658046		kusssso	Stove (JOI18_stove)	C++17	100 / 100	115 ms	82932 KiB

stove

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll inf = 1e18;

int n, k;
ll t[N];

namespace sub2 {
    ll dp[5005][5005];
    void solve() {
        for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = inf;
        dp[0][0] = 0;
        for (int z = 1; z <= k; z++) {
            ll min_dp = inf;
            for (int i = 1; i <= n; i++) {
                min_dp = min(min_dp, dp[i - 1][z - 1] - t[i]);
                dp[i][z] = min(dp[i][z], min_dp + t[i] + 1);
            }
        }
        cout << dp[n][k];
    }  
};

namespace full {
    void solve() {
        multiset<ll> s;
        for (int i = 2; i <= n; i++) {
            s.insert(t[i] - t[i - 1] - 1);
            if (s.size() > k - 1) {
                s.erase(s.begin());
            }
        }
        ll ans = t[n] - t[1] + 1;
        for (auto &x : s) {
            ans -= x;    
        }
        cout << ans;
    }  
};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> t[i];
    if (n <= 5000) sub2::solve();
    else full::solve();
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

stove.cpp: In function 'void full::solve()':
stove.cpp:31:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |             if (s.size() > k - 1) {
      |                 ~~~~~~~~~^~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50