Блог пользователя vibster

Автор vibster, история, 6 лет назад, По-английски

Hey!

I've been stuck at this problem for the past 2 days. I came at a DP recurrence DP(i) = 1+DP(i+1)+DP(nextPossibleInterval(i)), where DP(i) represents all possible subsets of classes b/w ith and nth interval(sorted by endTime).

IMO & from what I've been able to see from solutions of other people(inTheProcessOfDebuggingMine) this logic is correct. For some reason I'm getting WA in some testCases that I'm testing myself & while submitting. I've not been able to debug my code and for that any insight into what might be going wrong is highly appreciated. Thanks!

ACCEPTED CODE, WA Code

Problem

Sample test case:

8 4 9 1 15 2 18 4 5 7 19 14 25 19 20 3 26 -1 Expected Output: 00000017; Actual Output: 00000026

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Just think this releation:

ll rec(ll l,vl& dp,vl& aa,vl& bb,ll& n){
  if(l==n)return 0;
  if(dp[l]!=-1)return dp[l];
  auto it=lower_bound(aa.begin()+l+1,aa.end(),bb[l]);
  ll ans=rec(l+1,dp,aa,bb,n)%mm;
  ans= ((ans%mm)+1+ (rec(it-aa.begin(),dp,aa,bb,n)%mm))%mm;
  return dp[l]=ans;


}