結果

問題 No.3345 Reducible Sequence
コンテスト
ユーザー GOTKAKO
提出日時 2025-11-13 23:08:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 3,720 bytes
コンパイル時間 2,323 ms
コンパイル使用メモリ 213,692 KB
実行使用メモリ 22,432 KB
最終ジャッジ日時 2025-11-13 23:08:39
合計ジャッジ時間 4,707 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct edge{ int to; long long cap; int rev;};
class Dinic{
    public:
    int n;
    vector<pair<int,int>> Es; //i番目の辺がどこにあるか.
    vector<vector<edge>> Graph;
 
    Dinic():n(0){}
    Dinic(int N):n(N),Graph(N){}
 
    int addedge(int u, int v, long long c){ //u->vに容量c.
        int m = Es.size();
        Es.push_back({u,Graph.at(u).size()});
        int gv = Graph.at(v).size(), gu = Graph.at(u).size();
        Graph.at(u).push_back(edge{v,c,gv});
        Graph.at(v).push_back(edge{u,0,gu});
        return m;
    }
 
    long long maxflow(int s, int t,long long limit = numeric_limits<long long>::max()){ //s->tにいくつ流せるか.
        long long ret = 0;
        vector<int> dist(n),search(n);
        auto bfs = [&]() -> void {
            queue<int> Q;
            fill(dist.begin(),dist.end(),-1);
            dist.at(s) = 0,Q.push(s);
            while(Q.size()){
                int pos = Q.front(); Q.pop();
                for(auto e : Graph.at(pos)){
                    if(e.cap == 0 || dist.at(e.to) != -1) continue;
                    dist.at(e.to) = dist.at(pos)+1;
                    if(e.to == t) return;
                    Q.push(e.to);
                }
            }
        };
        auto dfs = [&](auto dfs,int pos,long long f){
            if(pos == s) return f;
            long long flow = 0;
            int nowd = dist.at(pos);
            for(int &i=search.at(pos); i<Graph.at(pos).size(); i++){
                edge &e = Graph.at(pos).at(i);
                if(nowd <= dist.at(e.to) || Graph.at(e.to).at(e.rev).cap == 0) continue;
                long long now = dfs(dfs,e.to,min(f-flow,Graph.at(e.to).at(e.rev).cap));
                if(now <= 0) continue;
                Graph.at(pos).at(i).cap += now;
                Graph.at(e.to).at(e.rev).cap -= now;
                flow += now;
                if(flow == f) break;
            }
            return flow;
        };
 
        while(ret < limit){
            bfs();
            if(dist.at(t) == -1) break;
            fill(search.begin(),search.end(),0);
            while(ret < limit){
                long long f = dfs(dfs,t,limit-ret);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
 
    vector<pair<int,int>> mincost(int s){ //maxflowの後の復元
        vector<bool> already(n);
        queue<int> Q;
        Q.push(s),already.at(s) = true;
        while(Q.size()){
            int pos = Q.front(); Q.pop();
            for(auto e : Graph.at(pos)) if(e.cap && !already.at(e.to)) already.at(e.to) = true,Q.push(e.to);
        }
 
        vector<pair<int,int>> ret;
        for(auto [pos,i] : Es) if(already.at(pos)){
            edge &e = Graph.at(pos).at(i);
            if(!already.at(e.to)) ret.push_back({pos,e.to});
        }
        return ret; //[from,to]は辺の追加順になっている.
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> A(N);
    for(auto &a : A) cin >> a;

    vector<vector<int>> D(5001);
    for(int i=1; i<=5000; i++) for(int k=i; k<=5000; k+=i) D.at(k).push_back(i);

    int low = 0,high = N+1;
    while(high-low > 1){
        int mid = (low+high)/2;
        Dinic Z(N+mid+2);
        int s = N+mid,t = s+1;
        for(int i=0; i<N; i++){
            Z.addedge(s,i,1);
            for(auto d : D.at(A.at(i))){
                if(d > mid) break;
                Z.addedge(i,N+d-1,1);
            }
        }
        for(int i=0; i<mid; i++) Z.addedge(N+i,t,1);
        if(Z.maxflow(s,t) == mid) low = mid;
        else high = mid;
    }
    cout << low << endl;
}
0