oj.uz

Submission #1038589

# Submission time Handle Problem Language Result Execution time Memory
1038589 2024-07-30T02:51:04 Z 12345678 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 5000 ms 16104 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5, c=1e6;

#define ll long long

ll m, z, p[nx], n[nx], dp[nx], l;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>m>>l;
    for (int i=m; i>=1; i--) cin>>n[i];
    cin>>z;
    for (int i=1; i<=m; i++) cin>>p[i];
    for (int i=0; i<nx; i++) dp[i]=-1;
    dp[c]=z;
    for (int i=1; i<=m; i++)
    {
        for (int t=0; t<n[i]; t++) 
        {
            for (int j=0; j<nx; j++) 
            {
                if (j+i<nx&&dp[j+i]!=-1) dp[j]=max(dp[j], dp[j+i]+1);
            }
        }
    }
    for (int i=1; i<=m; i++)
    {
        for (int t=0; t<p[i]; t++) 
        {
            for (int j=nx-1; j>=0; j--) 
            {
                if (j-i>=0&&dp[j-i]!=-1) dp[j]=max(dp[j], dp[j-i]+1);
            }
        }
    }
    if (l+c<0||l+c>nx||dp[l+c]<1) cout<<"impossible";
    else cout<<dp[l+c];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 14 ms 15960 KB Output is correct
4 Correct 83 ms 15964 KB Output is correct
5 Correct 3056 ms 16104 KB Output is correct
6 Correct 3374 ms 16100 KB Output is correct
7 Correct 1414 ms 16020 KB Output is correct
8 Correct 3442 ms 16100 KB Output is correct
9 Execution timed out 5037 ms 15960 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 14 ms 15960 KB Output is correct
4 Correct 83 ms 15964 KB Output is correct
5 Correct 3056 ms 16104 KB Output is correct
6 Correct 3374 ms 16100 KB Output is correct
7 Correct 1414 ms 16020 KB Output is correct
8 Correct 3442 ms 16100 KB Output is correct
9 Execution timed out 5037 ms 15960 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15964 KB Output is correct
2 Execution timed out 5078 ms 15960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15964 KB Output is correct
2 Execution timed out 5078 ms 15960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15964 KB Output is correct
2 Execution timed out 5078 ms 15960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 14 ms 15960 KB Output is correct
4 Correct 83 ms 15964 KB Output is correct
5 Correct 3056 ms 16104 KB Output is correct
6 Correct 3374 ms 16100 KB Output is correct
7 Correct 1414 ms 16020 KB Output is correct
8 Correct 3442 ms 16100 KB Output is correct
9 Execution timed out 5037 ms 15960 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15964 KB Output is correct
2 Execution timed out 5078 ms 15960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 14 ms 15960 KB Output is correct
4 Correct 83 ms 15964 KB Output is correct
5 Correct 3056 ms 16104 KB Output is correct
6 Correct 3374 ms 16100 KB Output is correct
7 Correct 1414 ms 16020 KB Output is correct
8 Correct 3442 ms 16100 KB Output is correct
9 Execution timed out 5037 ms 15960 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15964 KB Output is correct
2 Execution timed out 5078 ms 15960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 15 ms 15960 KB Output is correct
3 Correct 14 ms 15960 KB Output is correct
4 Correct 83 ms 15964 KB Output is correct
5 Correct 3056 ms 16104 KB Output is correct
6 Correct 3374 ms 16100 KB Output is correct
7 Correct 1414 ms 16020 KB Output is correct
8 Correct 3442 ms 16100 KB Output is correct
9 Execution timed out 5037 ms 15960 KB Time limit exceeded
10 Halted 0 ms 0 KB -