oj.uz

Submission #612275

# Submission time Handle Problem Language Result Execution time Memory
612275 2022-07-29T12:31:17 Z KrisjanisP Uplifting Excursion (BOI22_vault) C++14
0 / 100
 472 ms 26604 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll M = 300;
ll a[2*M+1];

ll m, l;

bool dp_vis[M*2+1][2*100*M+1];
ll dp_res[M*2+1][2*100*M+1];

// returns max items that can be picked
ll dp(ll v, ll sum)
{
    if(sum<0) return -1;
    if(v==m+1&&sum==0) return 0;
    if(v==m+1) return -1;
    if(dp_vis[v+m][sum])
        return dp_res[v+m][sum];
    dp_vis[v+m][sum] = 1;

    //cout<<v<<" "<<sum<<"\n";
    ll res = -1;
    for(ll i=0;i<=a[v+m];i++)
    {
        ll r = dp(v+1,sum-(v*i));
        if(r==-1) continue;
        res = max(res, r+i);
    }
    dp_res[v+m][sum] = res;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin>>m>>l;
    for(ll i=-m;i<=m;i++)
        cin>>a[i+m];
    ll r = -1;
    if(l<=M*100)
        r = dp(-m,l);
    if(r==-1) cout<<"impossible\n";
    else cout<<r<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 472 ms 26604 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 472 ms 26604 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 0 ms 212 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 1 ms 468 KB Output is correct
2 Incorrect 0 ms 212 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 1 ms 468 KB Output is correct
2 Incorrect 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 472 ms 26604 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 472 ms 26604 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 472 ms 26604 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -