Submission #65461474

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
const int N=2e3+7;
const int mod=1e9+7;
const double eps=1e-9;
const double pi=    3.14159265358979323846;
using namespace std;  
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    op_set;

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

    int n;
    cin >> n;

    vector<int> jmps(n);
    for(int i=1;i<n;i++)
        cin >> jmps[i];

    vector<int> beans(n);
    for(int i=1;i<n;i++)
        cin >> beans[i];

    int totalBeans=std::accumulate(beans.begin(),beans.end(),0);
    vector<vector<int>> dp(n+1,vector<int>(n+1));

    multiset<int> vals[n+1];
    vector<int> removals[n+1];
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<=n;j++)
        {
            if(!vals[j].empty())
                dp[i][j]=*vals[j].begin()+(j!=0);
        }
        
        if(beans[i])
        {
            for(int j=n;j>=1;j--)
            {
                vals[j].clear();
                dp[i][j]=dp[i][j-1];
            }
            dp[i][0]=1e9;
        }

        for(auto rem : removals[i])
        {
            for(int j=0;j<=n;j++)
            {
                if(vals[j].find( dp[rem][j] )!=vals[j].end())
                    vals[j].erase( vals[j].find( dp[rem][j]) );
            }
        }

        int end=std::max(0,i-jmps[i]);
        removals[end].pb(i);
        for(int j=0;j<=n;j++)
            vals[j].insert(dp[i][j]);
    }

    cout << dp[0][totalBeans] << "\n";
}

/*
Mar Gaye Ehsaas Meray, 
Chubay Wo Ilfaaz Teray, 
Tumne Dekha Tak Na Jaty Way, 
*/

Submission Info

Submission Time
Task E - Bowls and Beans
User 18o3
Language C++ 20 (gcc 12.2)
Score 0
Code Size 1855 Byte
Status WA
Exec Time 1669 ms
Memory 206932 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 475
Status
AC × 3
AC × 55
WA × 25
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt, test_71.txt, test_72.txt, test_73.txt, test_74.txt, test_75.txt, test_76.txt, test_77.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 3420 KiB
sample_02.txt AC 1 ms 3484 KiB
sample_03.txt AC 1 ms 3440 KiB
test_01.txt AC 1 ms 3348 KiB
test_02.txt AC 1 ms 3416 KiB
test_03.txt AC 1 ms 3432 KiB
test_04.txt AC 1 ms 3492 KiB
test_05.txt AC 1 ms 3476 KiB
test_06.txt AC 1 ms 3432 KiB
test_07.txt AC 1 ms 3472 KiB
test_08.txt AC 485 ms 206932 KiB
test_09.txt AC 102 ms 19552 KiB
test_10.txt AC 109 ms 19956 KiB
test_11.txt AC 112 ms 19456 KiB
test_12.txt AC 95 ms 19576 KiB
test_13.txt AC 103 ms 19508 KiB
test_14.txt AC 100 ms 19464 KiB
test_15.txt AC 440 ms 86056 KiB
test_16.txt WA 1008 ms 89936 KiB
test_17.txt WA 1020 ms 40216 KiB
test_18.txt WA 1669 ms 70696 KiB
test_19.txt WA 259 ms 22980 KiB
test_20.txt WA 151 ms 20804 KiB
test_21.txt AC 108 ms 19840 KiB
test_22.txt AC 100 ms 19512 KiB
test_23.txt AC 444 ms 91156 KiB
test_24.txt WA 1220 ms 79544 KiB
test_25.txt WA 1203 ms 52264 KiB
test_26.txt WA 491 ms 27288 KiB
test_27.txt WA 457 ms 27024 KiB
test_28.txt WA 268 ms 22832 KiB
test_29.txt WA 194 ms 23084 KiB
test_30.txt AC 96 ms 19472 KiB
test_31.txt WA 193 ms 21924 KiB
test_32.txt WA 323 ms 22100 KiB
test_33.txt AC 382 ms 21924 KiB
test_34.txt AC 373 ms 21788 KiB
test_35.txt WA 367 ms 22060 KiB
test_36.txt WA 123 ms 20404 KiB
test_37.txt WA 126 ms 20216 KiB
test_38.txt AC 95 ms 19432 KiB
test_39.txt AC 137 ms 20356 KiB
test_40.txt AC 167 ms 20332 KiB
test_41.txt AC 177 ms 20420 KiB
test_42.txt AC 169 ms 20332 KiB
test_43.txt WA 156 ms 20336 KiB
test_44.txt WA 129 ms 20144 KiB
test_45.txt WA 117 ms 19896 KiB
test_46.txt AC 96 ms 19500 KiB
test_47.txt AC 116 ms 19700 KiB
test_48.txt AC 117 ms 19776 KiB
test_49.txt AC 119 ms 19756 KiB
test_50.txt AC 123 ms 19708 KiB
test_51.txt AC 122 ms 19640 KiB
test_52.txt WA 123 ms 19772 KiB
test_53.txt WA 109 ms 19620 KiB
test_54.txt AC 97 ms 19368 KiB
test_55.txt AC 114 ms 19824 KiB
test_56.txt AC 116 ms 19716 KiB
test_57.txt AC 112 ms 19548 KiB
test_58.txt AC 112 ms 19604 KiB
test_59.txt AC 111 ms 19552 KiB
test_60.txt AC 108 ms 19668 KiB
test_61.txt AC 107 ms 19740 KiB
test_62.txt AC 97 ms 19452 KiB
test_63.txt AC 146 ms 20832 KiB
test_64.txt AC 133 ms 20304 KiB
test_65.txt AC 118 ms 19808 KiB
test_66.txt AC 121 ms 19788 KiB
test_67.txt AC 118 ms 19884 KiB
test_68.txt AC 115 ms 19692 KiB
test_69.txt AC 107 ms 19528 KiB
test_70.txt AC 100 ms 19460 KiB
test_71.txt WA 424 ms 82132 KiB
test_72.txt AC 118 ms 19880 KiB
test_73.txt AC 245 ms 25232 KiB
test_74.txt WA 344 ms 24392 KiB
test_75.txt WA 372 ms 25036 KiB
test_76.txt AC 115 ms 19728 KiB
test_77.txt WA 676 ms 35912 KiB