oj.uz

Submission #971472

# Submission time Handle Problem Language Result Execution time Memory
971472 2024-04-28T15:24:58 Z CyberCow The short shank; Redemption (BOI21_prison) C++17
15 / 100
 2000 ms 524288 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;
    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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 10 ms 22144 KB Output is correct
3 Correct 18 ms 37000 KB Output is correct
4 Correct 47 ms 95420 KB Output is correct
5 Correct 88 ms 168620 KB Output is correct
6 Correct 7 ms 13660 KB Output is correct
7 Correct 37 ms 82896 KB Output is correct
8 Correct 13 ms 27484 KB Output is correct
9 Correct 22 ms 46684 KB Output is correct
10 Correct 48 ms 101716 KB Output is correct
11 Correct 85 ms 178004 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 10 ms 22144 KB Output is correct
3 Correct 18 ms 37000 KB Output is correct
4 Correct 47 ms 95420 KB Output is correct
5 Correct 88 ms 168620 KB Output is correct
6 Correct 7 ms 13660 KB Output is correct
7 Correct 37 ms 82896 KB Output is correct
8 Correct 13 ms 27484 KB Output is correct
9 Correct 22 ms 46684 KB Output is correct
10 Correct 48 ms 101716 KB Output is correct
11 Correct 85 ms 178004 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 13 ms 22104 KB Output is correct
14 Correct 18 ms 36956 KB Output is correct
15 Correct 46 ms 95472 KB Output is correct
16 Correct 80 ms 168788 KB Output is correct
17 Correct 7 ms 13656 KB Output is correct
18 Correct 38 ms 82728 KB Output is correct
19 Correct 13 ms 27484 KB Output is correct
20 Correct 23 ms 46880 KB Output is correct
21 Correct 53 ms 101980 KB Output is correct
22 Correct 81 ms 178004 KB Output is correct
23 Runtime error 293 ms 280028 KB Execution killed with signal 11
24 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 639 ms 382108 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 0 ms 348 KB Output is correct
2 Correct 10 ms 22144 KB Output is correct
3 Correct 18 ms 37000 KB Output is correct
4 Correct 47 ms 95420 KB Output is correct
5 Correct 88 ms 168620 KB Output is correct
6 Correct 7 ms 13660 KB Output is correct
7 Correct 37 ms 82896 KB Output is correct
8 Correct 13 ms 27484 KB Output is correct
9 Correct 22 ms 46684 KB Output is correct
10 Correct 48 ms 101716 KB Output is correct
11 Correct 85 ms 178004 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 13 ms 22104 KB Output is correct
14 Correct 18 ms 36956 KB Output is correct
15 Correct 46 ms 95472 KB Output is correct
16 Correct 80 ms 168788 KB Output is correct
17 Correct 7 ms 13656 KB Output is correct
18 Correct 38 ms 82728 KB Output is correct
19 Correct 13 ms 27484 KB Output is correct
20 Correct 23 ms 46880 KB Output is correct
21 Correct 53 ms 101980 KB Output is correct
22 Correct 81 ms 178004 KB Output is correct
23 Runtime error 293 ms 280028 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 10 ms 22144 KB Output is correct
3 Correct 18 ms 37000 KB Output is correct
4 Correct 47 ms 95420 KB Output is correct
5 Correct 88 ms 168620 KB Output is correct
6 Correct 7 ms 13660 KB Output is correct
7 Correct 37 ms 82896 KB Output is correct
8 Correct 13 ms 27484 KB Output is correct
9 Correct 22 ms 46684 KB Output is correct
10 Correct 48 ms 101716 KB Output is correct
11 Correct 85 ms 178004 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Execution timed out 2960 ms 524288 KB Time limit exceeded
14 Halted 0 ms 0 KB -