Submission #140626

#	Time	Username	Problem	Language	Result	Execution time	Memory
140626		CaroLinda	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	80.32 / 100	439 ms	79352 KiB

brunhilda

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define ll long long

const int MAXN = 1e5+10;
const int MAX = 1e7+5 ;

using namespace std;

int n , q ;
int prime[MAXN] , myMod[MAX] , dp[MAX] ;

int main()
{
    scanf("%d %d", &n , &q ) ;
    lp(i,0,n) scanf("%d" , &prime[i] ) ;


    sort(prime, prime+n) ;

    lp(i,0,n)
        for(int j = prime[i] ; j < MAX ; j += prime[i] )
           myMod[j-1] = max( myMod[j-1] , prime[i] - 1 ) ;

    for(int i = MAX ; i > 0 ; i-- )
        myMod[i] = max( myMod[i] , myMod[i+1] - 1 ) ;

    for(int i = 1 ; i <= MAX ; i++ )
    {
        dp[i] = MAX ;

        dp[i] = min( dp[i-myMod[i]] + 1 , dp[i] ) ;

    }

    lp(i,0,q)
    {
        int a ;
        scanf("%d", &a ) ;
        if(dp[a] >= MAX) printf("oo\n") ;
        else printf("%d\n" , dp[a]) ;
    }


}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n , &q ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:22:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     lp(i,0,n) scanf("%d" , &prime[i] ) ;
               ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a ) ;
         ~~~~~^~~~~~~~~~~
brunhilda.cpp:38:15: warning: iteration 10000004 invokes undefined behavior [-Waggressive-loop-optimizations]
         dp[i] = min( dp[i-myMod[i]] + 1 , dp[i] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:34:23: note: within this loop
     for(int i = 1 ; i <= MAX ; i++ )
                     ~~^~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 18.88888888888889 / 20
• Subtask 3: 41.42857142857143 / 60