Submission #1095500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095500		0pt1mus23	Sirni (COCI17_sirni)	C++14	0 / 140	4180 ms	313776 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 1e7 +23 ,
            inf = INT_MAX ,
            L = 31 ;

void opt1z(){
    int n;
    cin>>n;
    int ans=0;

    vector<int> arr(n);
    set<int> lst;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        lst.ins(arr[i]);
    }
    int mx = (*lst.rbegin()) *2;

    map<int,int> var;
    map<int,int> var2;
    set<int> near;
    set<int> near2;
    for(auto v:lst){
        int c = v;
        near2.ins(v);
        var2[v]++;
        while(c<=mx){
            var[c]++;
            near.ins(c);
            c+=v;
        }
    }
    sort(all(arr));
    map<int,int> cevap;
    vector<int> yux;
    map<int,int> bagla;
    for(auto v:arr){
        if(cevap.find(v)!=cevap.end() || bagla.count(v)){
            continue;
        }
        if(var[v]==1){
            near.erase(v);
        }
        auto it = near.upper_bound(v);
        int x = inf;
        if(it!=near.begin()){
            --it;
            // cout<<v _ ": " _ *it<<endl;
            x=v - *it;
            // cevap[v]=v-*it;
        }

        if(var[v]==1){
            near.ins(v);
        }

        int c= v;
        yux.clear();
        while(c<=mx){
            yux.pb(c);
            c+=v;
        }
        if(var2[v]==1){
            near2.erase(v);
        }
        int c2=-1;
        for(auto c:yux){
            auto it2 = near2.lower_bound(c);
            if(it2!=near2.end()){
                // cout<<v _ "=> " _ c _ *it2 - c<<endl;
                int y =  *it2 - c;
                if(y <= x){
                    x = y;
                    c2 = *it2;
                }
            }
        }

        if(var2[v]==1){
            near2.ins(v);
        }
        // cout<<v _ ":=> " _ x<<endl;

        if(x!=inf){
            cevap[v]=x;
            if(c2!=-1){
                bagla[c2]=1;
            }
            ans+=x;
        }
    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14