結果

問題 No.706 多眼生物の調査
ユーザー squidsquid
提出日時 2018-07-23 21:29:11
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,720 bytes
コンパイル時間 1,588 ms
コンパイル使用メモリ 165,728 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-06-09 18:21:55
合計ジャッジ時間 8,244 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

//constant
const long long int inf = 1<<30;
const int N = 1e5+1;
const int M = 1e5+1;

//variable
vector<int> prime;
vector<int> A[N];

//function

bool isPrime(int x){
    if(x<=1){
        return false;
    }
    for(int i=2; i<x-1; i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}

void createPrime(){

    for(int i=2; i<(int)(sqrt(1e5))+1; i++){
        if(isPrime(i)){
            prime.push_back(i);
        }
    }
}

void factVar(int in, int i){
    for(int j=0; j<prime.size(); j++){
        if(in%prime[j]==0){
            while(in%prime[j]==0){
                in/=prime[j];
            }
            A[i].push_back(prime[j]);
        }
    }
    if(in > (int)(sqrt(1e5))+1){
        A[i].push_back(in);
    }
}


int main()
{
    int n,k;

    createPrime();

    cin>>n>>k;
    for(int i=0; i<n; i++){
        int in;
        cin>>in;
        factVar(in,i);
    }

    /*for(int i=0; i<A[0].size(); i++){
        cout<<A[0][i]<<endl;
    }*/

    set<int> dupList;
    int maxDist=0, rest=0;

    for(int left=0; left<n; left++){
        for(int right=left+1; right<n+1;){
            for(int i=left; i<right; i++){
                for(int j=0; j<A[i].size(); j++){
                    dupList.insert(A[i][j]);
                    //cout<<left<<' '<<right<<' '<<dupList.size()<<endl;
                }
            }
            if(dupList.size()<=k){
                maxDist=max(maxDist, right-left);
                right++;
            }
            else{
                dupList.clear();
                break;
            }
        }
    }

    maxDist=max(maxDist, rest);
    cout<<maxDist<<endl;


    return 0;
}
0