290382026-06-03 20:38:39algoproDombokcpp17Hibás válasz 0/100771ms524288 KiB
// UUID: a597c49d-428e-4c60-b082-172c43f8f137
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    // dp[i][j][epult (0/1)] = első i domb közül j db-ra építek, ha az utolsóra nincs/van ház
	// dp[i][j][0] = min{dp[i-1][j][1], dp[i-2][j][1], ...} - ha nem lehet vmi, INF
    // dp[i][j][1] = dp[i-1][j-1]

    int n; cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>((n+1) / 2 + 1, vector<int>(2, 1e9)));
    dp[0][0][0] = dp[1][0][0] = dp[1][1][1] = 0;
    return 0;
    for (int i = 2; i <= n; i++) {
        dp[i][0][0] = 0;
        for (int j = 1; j <= (n+1) / 2; j++) {
            int both = max(0, a[i-1] - min(a[i-2], a[i]) + 1);
            // dp[i][j][0]
            dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1] + max(0, a[i] - a[i-1] + 1));
            // dp[i][j][1] - előtte nem áll ház, itt áll
            dp[i][j][1] = min(dp[i-2][j-1][0] + max(0, a[i-1] - a[i] + 1), dp[i-2][j-1][1] + both);
        }
    }

    for (int i = 1; i <= (n+1) / 2; i++) {
        cout << min(dp[n][i][0], dp[n][i][1]) << " ";
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
00/0
1Hibás válasz1ms316 KiB
2Hibás válasz1ms316 KiB
3Hibás válasz1ms316 KiB
10/7
4Hibás válasz1ms316 KiB
5Hibás válasz2ms536 KiB
6Hibás válasz1ms508 KiB
7Hibás válasz1ms500 KiB
8Kihagyva0s0 KiB
9Kihagyva0s0 KiB
10Kihagyva0s0 KiB
11Kihagyva0s0 KiB
12Kihagyva0s0 KiB
13Kihagyva0s0 KiB
20/15
14Hibás válasz1ms316 KiB
15Hibás válasz1ms316 KiB
16Hibás válasz1ms512 KiB
17Hibás válasz1ms500 KiB
18Kihagyva0s0 KiB
19Kihagyva0s0 KiB
20Kihagyva0s0 KiB
21Kihagyva0s0 KiB
22Kihagyva0s0 KiB
23Kihagyva0s0 KiB
24Kihagyva0s0 KiB
25Kihagyva0s0 KiB
26Kihagyva0s0 KiB
27Kihagyva0s0 KiB
28Kihagyva0s0 KiB
30/13
29Hibás válasz1ms316 KiB
30Hibás válasz1ms620 KiB
31Hibás válasz2ms564 KiB
32Hibás válasz1ms564 KiB
33Kihagyva0s0 KiB
34Kihagyva0s0 KiB
35Kihagyva0s0 KiB
36Kihagyva0s0 KiB
37Kihagyva0s0 KiB
38Kihagyva0s0 KiB
39Kihagyva0s0 KiB
40Kihagyva0s0 KiB
40/18
41Hibás válasz3ms572 KiB
42Hibás válasz3ms564 KiB
43Hibás válasz3ms564 KiB
44Hibás válasz3ms756 KiB
45Kihagyva0s0 KiB
46Kihagyva0s0 KiB
47Kihagyva0s0 KiB
48Kihagyva0s0 KiB
49Kihagyva0s0 KiB
50/22
50Hibás válasz2ms800 KiB
51Hibás válasz2ms564 KiB
52Hibás válasz13ms7084 KiB
53Hibás válasz14ms7220 KiB
54Kihagyva0s0 KiB
55Kihagyva0s0 KiB
56Kihagyva0s0 KiB
57Kihagyva0s0 KiB
58Kihagyva0s0 KiB
59Kihagyva0s0 KiB
60Kihagyva0s0 KiB
61Kihagyva0s0 KiB
62Kihagyva0s0 KiB
63Kihagyva0s0 KiB
60/25
64Hibás válasz50ms27864 KiB
65Hibás válasz54ms27956 KiB
66Futási hiba771ms524288 KiB
67Futási hiba764ms524288 KiB
68Kihagyva0s0 KiB
69Kihagyva0s0 KiB
70Kihagyva0s0 KiB
71Kihagyva0s0 KiB
72Kihagyva0s0 KiB
73Kihagyva0s0 KiB
74Kihagyva0s0 KiB
75Kihagyva0s0 KiB
76Kihagyva0s0 KiB