This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int n,k;
int towers[100],gold[100];
int dp[50][1000000];
int solve(int idx,int sum)
{
//cout<<idx<<" "<<sum<<endl;
if(idx==n)return 0;
if(sum<1000000)if(dp[idx][sum]!=-1)return dp[idx][sum];
sum+=gold[idx];
int ret = 0;
if(sum>=k)ret = 1;
for(int i=idx+1;i<n;i++)
{
if(towers[i]>=towers[idx])ret+=solve(i,sum);
}
if(sum<1000000)dp[idx][sum] = ret;
return ret;
}
main()
{
memset(dp,-1,sizeof dp);
cin>>n>>k;
for(int i=0;i<n;i++)cin>>towers[i]>>gold[i];
int ans = 0;
for(int i=0;i<n;i++)ans+=solve(i,0);
cout<<ans<<endl;
}
Compilation message (stderr)
san.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
26 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |