oj.uz

Submission #473185

# Submission time Handle Problem Language Result Execution time Memory
473185 2021-09-15T09:54:49 Z SaraMostafa San (COCI17_san) C++14
72 / 120
 2 ms 332 KB 
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define endl "\n"
#define Sara ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const long long mod=1e9+7;
const double PI=acos(-1);
// 1 2 3 --> 1,2,3 ...1,2..1,3..1..2,3..2..3..none (2 power number of elements)
//1 2 3 --> 2--> 1,2..1,3..2,3..(!n/(r!(n-r)!)) aka:ncr
// 1 2 3 -->2-->1,2..2,1..1,3..3,1..2,3..3,2..(n!/(n-r)!) aka:npr
//1 2 3--> 1..1,2..1,2,3..2..2,3..3  number of subarrays -->(n*(n+1))/2 "sum of numbers from 1 to n."
/*
ll power(ll x,ll y)
{
    if(y==0)
        return 1;
    else if(y==1)
        return x%mod;
    ll  r=power(x%mod,((y%mod)/2)%mod);
    if(y%2==0)
        return ((r%mod)*(r%mod));
    else
        return ((r%mod)*(r%mod)*(x%mod));
}

ll inverse(ll md,ll x)
{
    return power(x%mod,mod-2);
}

*/
ll n,k;
vector<pair<ll,ll>>v;
ll dp[50][50];
ll solve(int id,int prev,ll sum)
{
    if(id==n){
           return 0;
    }
    if(dp[id][prev]!=-1) return dp[id][prev];
    ll c1=0,c2=0;
    if(v[prev].first<=v[id].first){
        ll x=0;
          if(sum+v[id].second>=k) x=1;
        c1=solve(id+1,id,sum+v[id].second)+x;
    }
    c2=solve(id+1,prev,sum);
    return dp[id][prev]=c1+c2;
}
ll solve1(int id,int prev,ll sum)
{
    if(id==n){
            if(sum>=k)
        return 1;
       else return 0;
    }
    ll c1=0,c2=0;
    if(v[prev].first<=v[id].first){
        c1=solve1(id+1,id,sum+v[id].second);
    }
    c2=solve1(id+1,prev,sum);
    return c1+c2;
}
int main()
{
    //freopen("input.in","r",stdin);

    Sara
    cin>>n>>k;
    v.resize(n+1);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++) cin>>v[i].first>>v[i].second;
    v[n].first=0;v[n].second=0;
    if(n<=20)
   cout<<solve1(0,n,0);
   else{
    cout<<solve(0,n,0);
   }
    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -