Submission #2123128


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i<r;i++)
#define dec(i, l, r) for (int i = l; i>=r;i--)
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define pb(c) push_back(c)
#define vii vector<pair<int,int>>
#define ii pair<int,int>
#define  mmax(a, b) (((a)<(b))?b:a)
#define min(a, b) ((a>b)?b:a)
#define mp(i, j) make_pair(i,j)
#define ull unsigned long long int
#define ll  long long int
#define pie 3.141592653589793238
#define inf ((ll)1e18)
#define eps 1e-14
#define mod ((int)1e9+7)
#define maxlg 18
#define maxn 200002
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)

typedef long long LL;

struct Edge {
    int from, to, cap, flow, index;
    Edge(int from, int to, int cap, int flow, int index) :
            from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel {
    int N;
    vector<vector<Edge> > G;
    vector<LL> excess;
    vector<int> dist, active, count;
    queue<int> Q;

    PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

    void AddEdge(int from, int to, int cap) {
        G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
        if (from == to) G[from].back().index++;
        G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
    }

    void Enqueue(int v) {
        if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); }
    }

    void Push(Edge &e) {
        int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
        if (dist[e.from] <= dist[e.to] || amt == 0) return;
        e.flow += amt;
        G[e.to][e.index].flow -= amt;
        excess[e.to] += amt;
        excess[e.from] -= amt;
        Enqueue(e.to);
    }

    void Gap(int k) {
        for (int v = 0; v < N; v++) {
            if (dist[v] < k) continue;
            count[dist[v]]--;
            dist[v] = max(dist[v], N+1);
            count[dist[v]]++;
            Enqueue(v);
        }
    }

    void Relabel(int v) {
        count[dist[v]]--;
        dist[v] = 2*N;
        for (int i = 0; i < G[v].size(); i++)
            if (G[v][i].cap - G[v][i].flow > 0)
                dist[v] = min(dist[v], dist[G[v][i].to] + 1);
        count[dist[v]]++;
        Enqueue(v);
    }

    void Discharge(int v) {
        for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
        if (excess[v] > 0) {
            if (count[dist[v]] == 1)
                Gap(dist[v]);
            else
                Relabel(v);
        }
    }

    LL GetMaxFlow(int s, int t) {
        count[0] = N-1;
        count[N] = 1;
        dist[s] = N;
        active[s] = active[t] = true;
        for (int i = 0; i < G[s].size(); i++) {
            excess[s] += G[s][i].cap;
            Push(G[s][i]);
        }

        while (!Q.empty()) {
            int v = Q.front();
            Q.pop();
            active[v] = false;
            Discharge(v);
        }

        LL totflow = 0;
        for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
        return totflow;
    }
};

int id=1;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
 #endif
    int n;
    cin>>n;
    ll sum=0;
    int arr[n];
    rep (i,0,n) {
        cin>>arr[i];
        if (arr[i]>0)
        sum+=arr[i];
    }

    PushRelabel mf(2+n);
    int sink = id+n;
    rep (i,0,n) {
        if (arr[i]<0)
        mf.AddEdge(0,i+1,-arr[i]);
        else
            mf.AddEdge(i+1,n+1,arr[i]);

    }

    rep (i,1,n+1) {
        int mul = 2*i;
        while (mul<=n) {
            mf.AddEdge(i,mul,(int)1e9);
            mul +=i;

        }
    }


    cout<<sum-mf.GetMaxFlow(0,n+1);
    return 0;
}






















Submission Info

Submission Time
Task E - MUL
User arasmus
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3862 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 49
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All example_0, example_1, example_2, example_3, kimeuti_0, kimeuti_1, kimeuti_10, kimeuti_11, kimeuti_12, kimeuti_13, kimeuti_14, kimeuti_15, kimeuti_16, kimeuti_17, kimeuti_18, kimeuti_19, kimeuti_2, kimeuti_3, kimeuti_4, kimeuti_5, kimeuti_6, kimeuti_7, kimeuti_8, kimeuti_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4
Case Name Status Exec Time Memory
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 AC 1 ms 256 KB
kimeuti_0 AC 1 ms 256 KB
kimeuti_1 AC 1 ms 256 KB
kimeuti_10 AC 1 ms 256 KB
kimeuti_11 AC 1 ms 256 KB
kimeuti_12 AC 1 ms 256 KB
kimeuti_13 AC 1 ms 256 KB
kimeuti_14 AC 1 ms 256 KB
kimeuti_15 AC 1 ms 256 KB
kimeuti_16 AC 1 ms 256 KB
kimeuti_17 AC 1 ms 256 KB
kimeuti_18 AC 1 ms 256 KB
kimeuti_19 AC 1 ms 256 KB
kimeuti_2 AC 1 ms 256 KB
kimeuti_3 AC 1 ms 256 KB
kimeuti_4 AC 1 ms 256 KB
kimeuti_5 AC 1 ms 256 KB
kimeuti_6 AC 1 ms 256 KB
kimeuti_7 AC 1 ms 256 KB
kimeuti_8 AC 1 ms 256 KB
kimeuti_9 AC 1 ms 256 KB
rand_0 AC 1 ms 256 KB
rand_1 AC 1 ms 256 KB
rand_10 AC 1 ms 256 KB
rand_11 AC 1 ms 256 KB
rand_12 AC 1 ms 256 KB
rand_13 AC 1 ms 256 KB
rand_14 AC 1 ms 256 KB
rand_15 AC 1 ms 256 KB
rand_16 AC 1 ms 256 KB
rand_17 AC 1 ms 256 KB
rand_18 AC 1 ms 256 KB
rand_19 AC 1 ms 256 KB
rand_2 AC 1 ms 256 KB
rand_3 AC 1 ms 256 KB
rand_4 AC 1 ms 256 KB
rand_5 AC 1 ms 256 KB
rand_6 AC 1 ms 256 KB
rand_7 AC 1 ms 256 KB
rand_8 AC 1 ms 256 KB
rand_9 AC 1 ms 256 KB
small_0 AC 1 ms 256 KB
small_1 AC 1 ms 256 KB
small_2 AC 1 ms 256 KB
small_3 AC 1 ms 256 KB
small_4 AC 1 ms 256 KB