제출 #154333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154333		brcode	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	21.43 / 100	405 ms	37528 KiB

brunhilda

#include <iostream>

using namespace std;
const int MAXN = 2e5+5;
const int MAXN2 = 1e7+5;
int arr[MAXN];
int dp[MAXN2];
int dp2[MAXN2];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<arr[n];i++){
        dp[i] = 1;
    }
    for(int i=arr[n];i<MAXN;i++){
        dp[i] = 1e9;
    }
    for(int i=1;i<=n;i++){
        for(int j=arr[i]-1;j<MAXN;j+=arr[i]){

            dp2[j] = max(dp2[j],arr[i]-1);
            //cout<<j<<" "<<dp2[j]<<endl;
        }
    }
    for(int i=MAXN-1;i>=0;i--){
        dp2[i] = max(dp2[i],dp2[i+1]-1);
    }
    for(int i=arr[n];i<MAXN;i++){
        dp[i] = min(dp[i],dp[i-dp2[i]]+1);
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        if(dp[x]==1e9){
            cout<<"oo"<<endl;
        }else{
            cout<<dp[x]<<endl;
        }

    }

}

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