oj.uz

Submission #612328

# Submission time Handle Problem Language Result Execution time Memory
612328 2022-07-29T13:06:55 Z KrisjanisP Uplifting Excursion (BOI22_vault) C++14
0 / 100
 5000 ms 304724 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll M = 100, A = 100;

ll m, l;
ll a[2*M+1];

bool dp_right_vis[M+1][M*M*A+1];
ll dp_right_res[M+1][M*M*A+1];

// i = [1;m]
ll dp_right(ll i, ll sum)
{
    if(sum<0) return -1;
    if(sum==0) return 0;
    if(i==m+1) return -1;
    if(dp_right_vis[i][sum])
        return dp_right_res[i][sum];
    ll res = -1;
    for(ll j=a[m+i];j>=0;j--)
    {
        ll r = dp_right(i+1,sum-i*j);
        if(r==-1) continue;
        return r+j;
        res = max(res,r+j);
    }
    dp_right_vis[i][sum] = 1;
    dp_right_res[i][sum] = res;
    return res;
}

bool dp_left_vis[M+1][M*M*A+1];
ll dp_left_res[M+1][M*M*A+1];

// i = [1;m]
ll dp_left(ll i, ll sum)
{
    if(sum<0) return -1;
    if(sum==0) return 0;
    if(i==m+1) return -1;
    if(dp_left_vis[i][sum])
        return dp_left_res[i][sum];
    ll res = -1;
    for(ll j=0;j<=a[m-i];j++)
    {
        ll r = dp_left(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
    }
    dp_left_vis[i][sum] = 1;
    dp_left_res[i][sum] = res;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin>>m>>l;
    for(ll i=0;i<2*m+1;i++)
        cin>>a[i];
    ll res = a[0];
    bool found = false;
    for(ll x=0;x<=M*M*A;x++)
    {
        ll y = l+x;
        if(y>M*M*A) continue;
        ll left_res = dp_left(1,x);
        ll right_res = dp_right(1,y);
        if(left_res==-1||right_res==-1) continue;
        found = true;
        res = max(res,left_res+right_res+a[m]);
    }
    if(found)
        cout<<res<<"\n";
    else
        cout<<"impossible\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 35476 KB Output is correct
2 Correct 88 ms 53072 KB Output is correct
3 Correct 40 ms 17944 KB Output is correct
4 Correct 399 ms 176368 KB Output is correct
5 Execution timed out 5053 ms 304724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 35476 KB Output is correct
2 Correct 88 ms 53072 KB Output is correct
3 Correct 40 ms 17944 KB Output is correct
4 Correct 399 ms 176368 KB Output is correct
5 Execution timed out 5053 ms 304724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 176364 KB Output is correct
2 Incorrect 2 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 366 ms 176364 KB Output is correct
2 Incorrect 2 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 366 ms 176364 KB Output is correct
2 Incorrect 2 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 76 ms 35476 KB Output is correct
2 Correct 88 ms 53072 KB Output is correct
3 Correct 40 ms 17944 KB Output is correct
4 Correct 399 ms 176368 KB Output is correct
5 Execution timed out 5053 ms 304724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 176364 KB Output is correct
2 Incorrect 2 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 76 ms 35476 KB Output is correct
2 Correct 88 ms 53072 KB Output is correct
3 Correct 40 ms 17944 KB Output is correct
4 Correct 399 ms 176368 KB Output is correct
5 Execution timed out 5053 ms 304724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 176364 KB Output is correct
2 Incorrect 2 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 76 ms 35476 KB Output is correct
2 Correct 88 ms 53072 KB Output is correct
3 Correct 40 ms 17944 KB Output is correct
4 Correct 399 ms 176368 KB Output is correct
5 Execution timed out 5053 ms 304724 KB Time limit exceeded
6 Halted 0 ms 0 KB -