제출 #1366717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366717		minhmc2019	Rabbit Carrot (LMIO19_triusis)	C++20	14 / 100	79 ms	196544 KiB

triusis

#include <bits/stdc++.h>
#define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
#define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
#define debug(x) cout << "[DEBUG]:  " << #x << " = " << x << endl;
#define int long long
using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e18;

int n, m, H[N];

namespace sub2 {
    int dp[5005][5005], suffix[5005];
    void solve() {
        int maxi = *max_element(H + 1, H + n + 1);
        memset(dp, 0x3f, sizeof(dp));
        memset(suffix, 0x3f, sizeof(suffix));

        dp[1][0] = 0;
        suffix[maxi] = dp[1][maxi];
        FOD(cur_h, maxi - 1, 0, 1) {
            suffix[cur_h] = min(suffix[cur_h + 1], dp[1][cur_h]);
        }

        FOR(i, 2, n, 1) {
            FOR(cur_h, 0, maxi, 1) {
                int changed = (cur_h != H[i]);
                dp[i][cur_h] = min(dp[i][cur_h], suffix[max(cur_h - m, 0LL)] + changed);
            }
            suffix[maxi] = dp[i][maxi];
            FOD(cur_h, maxi - 1, 0, 1) {
                suffix[cur_h] = min(suffix[cur_h + 1], dp[i][cur_h]);
            }
        }

        int res = INF;
        FOR(cur_h, 0, maxi, 1) {
            res = min(res, dp[n][cur_h]);
        }
        cout << res << '\n';
    }
}

void solve() {
    cin >> n >> m;
    ++n;
    FOR(i, 2, n, 1) cin >> H[i];
    if (n <= 5000 && *max_element(H + 1, H + n + 1) <= 5000) {
        sub2::solve();
    }
}

signed main() {
    #define name "task"
    if (ifstream(name".inp")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
}

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

triusis.cpp: In function 'int main()':
triusis.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 14 / 14
• 서브태스크 2: 0 / 21
• 서브태스크 3: 0 / 28
• 서브태스크 4: 0 / 37