Submission #16721075

Source Code Expand

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 2010;
long long mod = 1e9+7;
long long cache[N][N];
long long s;

long long dp(int ind, long long num)
{
    if(num > s || ind >=N)
        return 0;
    if(num == s)
        return 1;

    long long &ans = cache[ind][num];
    if(ans != -1)
        return ans;

    ans = 0;
    for(long long nnum = 3; nnum<=s; nnum++)
    {
        if(nnum + num <= s)
            ans =(ans + dp(ind+1, num + nnum))%mod;
        else
            break;
    }

    return ans%mod;
}

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

    cin>>s;
    memset(cache, -1, sizeof(cache));

    long long ans = dp(0, 0);
    cout<<ans;
    
    return 0;
}

Submission Info

Submission Time
Task D - Redistribution
User ateev_mishra7
Language C++ (GCC 9.2.1)
Score 0
Code Size 967 Byte
Status TLE
Exec Time 2207 ms
Memory 35132 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
TLE × 1
AC × 15
TLE × 5
Set Name Test Cases
Sample sample00, sample01, sample02
All case03, case04, case05, case06, case07, case08, case09, case10, case11, case12, case13, case14, case15, case16, case17, case18, case19, sample00, sample01, sample02
Case Name Status Exec Time Memory
case03 AC 37 ms 35016 KiB
case04 AC 34 ms 35020 KiB
case05 AC 34 ms 35004 KiB
case06 AC 27 ms 35108 KiB
case07 AC 27 ms 35012 KiB
case08 AC 32 ms 35072 KiB
case09 TLE 2207 ms 34848 KiB
case10 AC 141 ms 35084 KiB
case11 AC 179 ms 35132 KiB
case12 AC 96 ms 35072 KiB
case13 TLE 2207 ms 34840 KiB
case14 AC 384 ms 35024 KiB
case15 AC 35 ms 35072 KiB
case16 TLE 2207 ms 34920 KiB
case17 AC 220 ms 35036 KiB
case18 TLE 2207 ms 34824 KiB
case19 AC 1358 ms 35044 KiB
sample00 AC 34 ms 35044 KiB
sample01 AC 34 ms 35044 KiB
sample02 TLE 2207 ms 34764 KiB