oj.uz

Submission #612354

# Submission time Handle Problem Language Result Execution time Memory
612354 2022-07-29T13:21:08 Z KrisjanisP Uplifting Excursion (BOI22_vault) C++14
5 / 100
 5000 ms 485852 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;
        res = max(res,r+j);
        break;
    }
    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=a[m-i];j>=0;j--)
    {
        ll r = dp_left(i+1,sum-i*j);
        if(r==-1) continue;
        res = max(res,r+j);
        break;
    }
    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;
    ll mn=0,mx=0;
    for(ll i=-m;i<0;i++)
        mn+=a[i+m]*i;
    for(ll i=1;i<=m;i++)
        mx+=a[i+m]*i;
    //cout<<mn<<" "<<mx<<"\n";
    for(ll x=0;x<=-mn;x++)
    {
        ll y = l+x;
        if(y>mx) break;
        ll left_res = dp_left(1,x);
        ll right_res = dp_right(1,y);
        if(left_res==-1||right_res==-1) continue;
        found = true;
        //cout<<"x y: "<<x<<" "<<y<<endl;
        //cout<<left_res<<" "<<right_res<<endl;
        res = max(res,left_res+right_res+a[m]);
    }
    if(found)
        cout<<res<<"\n";
    else
        cout<<"impossible\n";
}

Subtask #1
5.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 340 KB Output is correct
5 Correct 87 ms 15908 KB Output is correct
6 Correct 102 ms 26500 KB Output is correct
7 Correct 15 ms 6612 KB Output is correct
8 Correct 81 ms 17276 KB Output is correct
9 Correct 227 ms 29288 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct

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 340 KB Output is correct
5 Correct 87 ms 15908 KB Output is correct
6 Correct 102 ms 26500 KB Output is correct
7 Correct 15 ms 6612 KB Output is correct
8 Correct 81 ms 17276 KB Output is correct
9 Correct 227 ms 29288 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 86 ms 15948 KB Output is correct
17 Correct 100 ms 26464 KB Output is correct
18 Correct 15 ms 6740 KB Output is correct
19 Correct 85 ms 17260 KB Output is correct
20 Correct 227 ms 29284 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2492 ms 382780 KB Output is correct
25 Correct 277 ms 28080 KB Output is correct
26 Execution timed out 5099 ms 485852 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 31 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 31 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 31 ms 340 KB Execution killed with signal 11
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 340 KB Output is correct
5 Correct 87 ms 15908 KB Output is correct
6 Correct 102 ms 26500 KB Output is correct
7 Correct 15 ms 6612 KB Output is correct
8 Correct 81 ms 17276 KB Output is correct
9 Correct 227 ms 29288 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Runtime error 31 ms 340 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 31 ms 340 KB Execution killed with signal 11
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 340 KB Output is correct
5 Correct 87 ms 15908 KB Output is correct
6 Correct 102 ms 26500 KB Output is correct
7 Correct 15 ms 6612 KB Output is correct
8 Correct 81 ms 17276 KB Output is correct
9 Correct 227 ms 29288 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 86 ms 15948 KB Output is correct
17 Correct 100 ms 26464 KB Output is correct
18 Correct 15 ms 6740 KB Output is correct
19 Correct 85 ms 17260 KB Output is correct
20 Correct 227 ms 29284 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2492 ms 382780 KB Output is correct
25 Correct 277 ms 28080 KB Output is correct
26 Execution timed out 5099 ms 485852 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 31 ms 340 KB Execution killed with signal 11
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 340 KB Output is correct
5 Correct 87 ms 15908 KB Output is correct
6 Correct 102 ms 26500 KB Output is correct
7 Correct 15 ms 6612 KB Output is correct
8 Correct 81 ms 17276 KB Output is correct
9 Correct 227 ms 29288 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 86 ms 15948 KB Output is correct
17 Correct 100 ms 26464 KB Output is correct
18 Correct 15 ms 6740 KB Output is correct
19 Correct 85 ms 17260 KB Output is correct
20 Correct 227 ms 29284 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2492 ms 382780 KB Output is correct
25 Correct 277 ms 28080 KB Output is correct
26 Execution timed out 5099 ms 485852 KB Time limit exceeded
27 Halted 0 ms 0 KB -