Submission #971472

#	Time	Username	Problem	Language	Result	Execution time	Memory
971472		CyberCow	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2960 ms	524288 KiB

prison

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using ull = unsigned long long;
using namespace std;
mt19937 rnd(348502);
ll mod1 = 998244353;
ll mod = 1e9 + 7;
const ll N = 510;

int a[N];
int dp[N][N][N];
int hm[N][N][N];

void solve()
{
    int n, d, k, t;
    cin >> n >> d >> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int oo = 2e9;
    hm[0][0][0] = 1;
    dp[0][0][0] = oo;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= d; j++)
        {
            for (int h = 0; h <= n; h++)
            {
                if (hm[i - 1][j][h] == 0)continue;
                if (a[i] > t)
                {
                    dp[i][j + 1][h] = oo;
                    hm[i][j + 1][h] = 1;
                }
                if (a[i] <= t || (dp[i - 1][j][h] + 1 <= t))
                {
                    dp[i][j][h + 1] = max(dp[i][j][h + 1], min(dp[i - 1][j][h] + 1, a[i]));
                    hm[i][j][h + 1] = 1;
                }
                else
                {
                    dp[i][j][h] = oo;
                    hm[i][j][h] = 1;
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i <= d; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (hm[n][i][j])
                ans = min(ans, j);
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void solve()':
prison.cpp:37:15: warning: unused variable 'k' [-Wunused-variable]
   37 |     int n, d, k, t;
      |               ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20