oj.uz

Submission #1026638

# Submission time Handle Problem Language Result Execution time Memory
1026638 2024-07-18T08:55:21 Z gyg Uplifting Excursion (BOI22_vault) C++17
0 / 100
 100 ms 1036 KB 
#include <bits/stdc++.h>    
using namespace std;
#define int long long
const int OFFSET = 2e4, INF = 1e9;

int n, tar;
unordered_map<int, int> t;

array<int, 2 * OFFSET + 5> dp;
void comp() {
    fill(dp.begin(), dp.end(), -INF);
    dp[OFFSET] = 0;
    for (int x = -n; x <= n; x++) {
        for (int i = 1; i <= t[x]; i++) {
            array<int, 2 * OFFSET + 5> old_dp = dp;
            for (int y = OFFSET; y >= -OFFSET; y--)
                if (-OFFSET <= y - x && y - x <= OFFSET) dp[y + OFFSET] = max(old_dp[y + OFFSET], old_dp[y - x + OFFSET] + 1);
        }
    }
}

signed main() {
    // freopen("vault.in", "r", stdin);
    cin >> n >> tar;
    if (tar < -OFFSET || tar > OFFSET) { cout << "impossible" << '\n'; exit(0); }
    for (int i = -n; i <= n; i++) cin >> t[i];

    comp();

    cout << ((dp[tar + OFFSET] < 0) ? "impossible" : to_string(dp[tar + OFFSET])) << '\n';
    
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 100 ms 1036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 100 ms 1036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 100 ms 1036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 100 ms 1036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 100 ms 1036 KB Output isn't correct
7 Halted 0 ms 0 KB -