oj.uz

Submission #971471

# Submission time Handle Problem Language Result Execution time Memory
971471 2024-04-28T15:18:11 Z CyberCow The short shank; Redemption (BOI21_prison) C++17
0 / 100
 2000 ms 524292 KB 
#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;
    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

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 10 ms 22108 KB Output is correct
3 Correct 17 ms 36952 KB Output is correct
4 Correct 47 ms 95348 KB Output is correct
5 Incorrect 81 ms 168532 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2935 ms 524292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 10 ms 22108 KB Output is correct
3 Correct 17 ms 36952 KB Output is correct
4 Correct 47 ms 95348 KB Output is correct
5 Incorrect 81 ms 168532 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 686 ms 381944 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 10 ms 22108 KB Output is correct
3 Correct 17 ms 36952 KB Output is correct
4 Correct 47 ms 95348 KB Output is correct
5 Incorrect 81 ms 168532 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 10 ms 22108 KB Output is correct
3 Correct 17 ms 36952 KB Output is correct
4 Correct 47 ms 95348 KB Output is correct
5 Incorrect 81 ms 168532 KB Output isn't correct
6 Halted 0 ms 0 KB -