Submission #130695

#	Time	Username	Problem	Language	Result	Execution time	Memory
130695		MohamedAhmed04	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	114 ms	8048 KiB

brunhilda

    #include <bits/stdc++.h>
    using namespace std ;
     
    const int MAX = 1e7 + 5 ;
    const int OO = 1e9 ;
     
    int dp[MAX] ;
     
    int main()
    {
        int n , q ;
        scanf("%d %d" , &n , &q) ;
        int arr[n] ;
        for(int i = 0 ; i < n ; ++i)
            scanf("%d" , &arr[i]) ;
        priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >pq ;
        multiset<int>s ;
        for(int i = 0 ; i < n ; ++i)
        {
            pq.push({arr[i] , arr[i]}) ;
            s.insert(0) ;
        }
        dp[0] = 0 ;
        const int cons = 1e7 ;
        for(int i = 1 ; i <= 20000 ; ++i)
        {
            while(pq.size() > 0)
            {
                pair<int , int>pp = pq.top() ;
                if(pp.first == i)
                {
                    pq.pop() ;
                    pq.push({pp.first + pp.second , pp.second}) ;
                    s.erase(s.find(pp.first - pp.second)) ;
                    s.insert(pp.first) ;
                }
                else
                    break ;
            }
            int x = *s.begin() ;
            if(x == i)
                dp[i] = OO ;
            else
                dp[i] = dp[x] + 1 ;
        }
        while(q--)
        {
            int x ;
            scanf("%d" , &x) ;
            if(dp[x] >= OO)
                cout<<"oo\n" ;
            else
                cout<<dp[x]<<"\n";
        }
        return 0 ;
    }

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:24:19: warning: unused variable 'cons' [-Wunused-variable]
         const int cons = 1e7 ;
                   ^~~~
brunhilda.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d" , &n , &q) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , &arr[i]) ;
             ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , &x) ;
             ~~~~~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60