結果

問題 No.706 多眼生物の調査
コンテスト
ユーザー squid
提出日時 2018-07-23 21:29:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,720 bytes
コンパイル時間 1,772 ms
コンパイル使用メモリ 165,764 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2024-12-30 15:29:03
合計ジャッジ時間 29,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 3
other TLE * 5
権限があれば一括ダウンロードができます

ソースコード

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