oj.uz

Submission #849976

# Submission time Handle Problem Language Result Execution time Memory
849976 2023-09-15T15:14:40 Z Ahmed57 Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 16496 KB 
#include <bits/stdc++.h>
using namespace std;
long long dp[2][505000*2+1],arr[301],br = 505000,n,m;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>m>>n;
    for(int i = 0;i<2*m+1;i++){
        cin>>arr[i];
    }
    for(int i = 2*m+1;i>=0;i--){
        for(int j = 0;j<=505000*2;j++){
            if(i==2*m+1){
                if(j==n+br){
                    dp[i&1][j] = 0;
                }else{
                    dp[i&1][j] = -1e18;
                }
                continue;
            }
            long long ans = -1e18;
            for(int e = 0;e<=arr[i];e++){
                if(j+e*(i-m)<0||j+e*(i-m)>505000*2)continue;
                ans = max(ans,dp[!(i&1)][j+e*(i-m)]+e);
            }
            dp[i&1][j] = ans;
        }
    }
    long long vl = dp[0][505000];
    if(vl<0)cout<<"impossible\n";
    else cout<<vl<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16220 KB Output is correct
2 Correct 20 ms 16268 KB Output is correct
3 Correct 12 ms 16220 KB Output is correct
4 Correct 79 ms 16220 KB Output is correct
5 Correct 2185 ms 16260 KB Output is correct
6 Correct 2315 ms 16240 KB Output is correct
7 Correct 1010 ms 16244 KB Output is correct
8 Correct 2222 ms 16464 KB Output is correct
9 Correct 4162 ms 16244 KB Output is correct
10 Correct 262 ms 16240 KB Output is correct
11 Correct 227 ms 16216 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16220 KB Output is correct
2 Correct 20 ms 16268 KB Output is correct
3 Correct 12 ms 16220 KB Output is correct
4 Correct 79 ms 16220 KB Output is correct
5 Correct 2185 ms 16260 KB Output is correct
6 Correct 2315 ms 16240 KB Output is correct
7 Correct 1010 ms 16244 KB Output is correct
8 Correct 2222 ms 16464 KB Output is correct
9 Correct 4162 ms 16244 KB Output is correct
10 Correct 262 ms 16240 KB Output is correct
11 Correct 227 ms 16216 KB Output is correct
12 Correct 20 ms 16220 KB Output is correct
13 Correct 20 ms 16272 KB Output is correct
14 Correct 16 ms 16272 KB Output is correct
15 Correct 82 ms 16496 KB Output is correct
16 Correct 2178 ms 16244 KB Output is correct
17 Correct 2368 ms 16472 KB Output is correct
18 Correct 999 ms 16260 KB Output is correct
19 Correct 2187 ms 16468 KB Output is correct
20 Correct 4160 ms 16248 KB Output is correct
21 Correct 254 ms 16240 KB Output is correct
22 Correct 218 ms 16220 KB Output is correct
23 Execution timed out 5054 ms 16220 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16220 KB Output is correct
2 Execution timed out 5042 ms 16216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16220 KB Output is correct
2 Execution timed out 5042 ms 16216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16220 KB Output is correct
2 Execution timed out 5042 ms 16216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16220 KB Output is correct
2 Correct 20 ms 16268 KB Output is correct
3 Correct 12 ms 16220 KB Output is correct
4 Correct 79 ms 16220 KB Output is correct
5 Correct 2185 ms 16260 KB Output is correct
6 Correct 2315 ms 16240 KB Output is correct
7 Correct 1010 ms 16244 KB Output is correct
8 Correct 2222 ms 16464 KB Output is correct
9 Correct 4162 ms 16244 KB Output is correct
10 Correct 262 ms 16240 KB Output is correct
11 Correct 227 ms 16216 KB Output is correct
12 Correct 84 ms 16220 KB Output is correct
13 Execution timed out 5042 ms 16216 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16220 KB Output is correct
2 Execution timed out 5042 ms 16216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16220 KB Output is correct
2 Correct 20 ms 16268 KB Output is correct
3 Correct 12 ms 16220 KB Output is correct
4 Correct 79 ms 16220 KB Output is correct
5 Correct 2185 ms 16260 KB Output is correct
6 Correct 2315 ms 16240 KB Output is correct
7 Correct 1010 ms 16244 KB Output is correct
8 Correct 2222 ms 16464 KB Output is correct
9 Correct 4162 ms 16244 KB Output is correct
10 Correct 262 ms 16240 KB Output is correct
11 Correct 227 ms 16216 KB Output is correct
12 Correct 20 ms 16220 KB Output is correct
13 Correct 20 ms 16272 KB Output is correct
14 Correct 16 ms 16272 KB Output is correct
15 Correct 82 ms 16496 KB Output is correct
16 Correct 2178 ms 16244 KB Output is correct
17 Correct 2368 ms 16472 KB Output is correct
18 Correct 999 ms 16260 KB Output is correct
19 Correct 2187 ms 16468 KB Output is correct
20 Correct 4160 ms 16248 KB Output is correct
21 Correct 254 ms 16240 KB Output is correct
22 Correct 218 ms 16220 KB Output is correct
23 Execution timed out 5054 ms 16220 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16220 KB Output is correct
2 Execution timed out 5042 ms 16216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16220 KB Output is correct
2 Correct 20 ms 16268 KB Output is correct
3 Correct 12 ms 16220 KB Output is correct
4 Correct 79 ms 16220 KB Output is correct
5 Correct 2185 ms 16260 KB Output is correct
6 Correct 2315 ms 16240 KB Output is correct
7 Correct 1010 ms 16244 KB Output is correct
8 Correct 2222 ms 16464 KB Output is correct
9 Correct 4162 ms 16244 KB Output is correct
10 Correct 262 ms 16240 KB Output is correct
11 Correct 227 ms 16216 KB Output is correct
12 Correct 20 ms 16220 KB Output is correct
13 Correct 20 ms 16272 KB Output is correct
14 Correct 16 ms 16272 KB Output is correct
15 Correct 82 ms 16496 KB Output is correct
16 Correct 2178 ms 16244 KB Output is correct
17 Correct 2368 ms 16472 KB Output is correct
18 Correct 999 ms 16260 KB Output is correct
19 Correct 2187 ms 16468 KB Output is correct
20 Correct 4160 ms 16248 KB Output is correct
21 Correct 254 ms 16240 KB Output is correct
22 Correct 218 ms 16220 KB Output is correct
23 Execution timed out 5054 ms 16220 KB Time limit exceeded
24 Halted 0 ms 0 KB -