oj.uz

Submission #612361

# Submission time Handle Problem Language Result Execution time Memory
612361 2022-07-29T13:27:10 Z KrisjanisP Uplifting Excursion (BOI22_vault) C++14
5 / 100
 5000 ms 464124 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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=min(sum/i,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=min(sum/i,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);
        if(left_res==-1) continue;
        ll right_res = dp_right(1,y);
        if(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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 92 ms 15980 KB Output is correct
6 Correct 108 ms 26420 KB Output is correct
7 Correct 16 ms 6612 KB Output is correct
8 Correct 90 ms 17284 KB Output is correct
9 Correct 289 ms 29332 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 92 ms 15980 KB Output is correct
6 Correct 108 ms 26420 KB Output is correct
7 Correct 16 ms 6612 KB Output is correct
8 Correct 90 ms 17284 KB Output is correct
9 Correct 289 ms 29332 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 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 88 ms 15940 KB Output is correct
17 Correct 115 ms 26488 KB Output is correct
18 Correct 21 ms 6648 KB Output is correct
19 Correct 100 ms 17240 KB Output is correct
20 Correct 259 ms 29252 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 1064 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 3798 ms 382780 KB Output is correct
25 Correct 338 ms 28068 KB Output is correct
26 Execution timed out 5120 ms 464124 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 35 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 1 ms 340 KB Output is correct
2 Runtime error 35 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 1 ms 340 KB Output is correct
2 Runtime error 35 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 92 ms 15980 KB Output is correct
6 Correct 108 ms 26420 KB Output is correct
7 Correct 16 ms 6612 KB Output is correct
8 Correct 90 ms 17284 KB Output is correct
9 Correct 289 ms 29332 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 Runtime error 35 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 1 ms 340 KB Output is correct
2 Runtime error 35 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 92 ms 15980 KB Output is correct
6 Correct 108 ms 26420 KB Output is correct
7 Correct 16 ms 6612 KB Output is correct
8 Correct 90 ms 17284 KB Output is correct
9 Correct 289 ms 29332 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 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 88 ms 15940 KB Output is correct
17 Correct 115 ms 26488 KB Output is correct
18 Correct 21 ms 6648 KB Output is correct
19 Correct 100 ms 17240 KB Output is correct
20 Correct 259 ms 29252 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 1064 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 3798 ms 382780 KB Output is correct
25 Correct 338 ms 28068 KB Output is correct
26 Execution timed out 5120 ms 464124 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 35 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 92 ms 15980 KB Output is correct
6 Correct 108 ms 26420 KB Output is correct
7 Correct 16 ms 6612 KB Output is correct
8 Correct 90 ms 17284 KB Output is correct
9 Correct 289 ms 29332 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 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 88 ms 15940 KB Output is correct
17 Correct 115 ms 26488 KB Output is correct
18 Correct 21 ms 6648 KB Output is correct
19 Correct 100 ms 17240 KB Output is correct
20 Correct 259 ms 29252 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 1064 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 3798 ms 382780 KB Output is correct
25 Correct 338 ms 28068 KB Output is correct
26 Execution timed out 5120 ms 464124 KB Time limit exceeded
27 Halted 0 ms 0 KB -