제출 #244864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244864		LittleFlowers__	Wiring (IOI17_wiring)	C++17	30 / 100	86 ms	8672 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);

long long min_total_length(vector<int> r, vector<int> b){
    int m=r.size(), n=b.size();

    if(m<=200 && n<=200){
        vector<vector<long long>> f(m+5,vector<long long>(n+5,1e15));
        f[0][0]=0;
        forinc(i,0,m) forinc(j,0,n){
            if(j) f[i+1][j]=min(f[i+1][j],f[i][j]+abs(r[i]-b[j-1]));
            if(i) f[i][j+1]=min(f[i][j+1],f[i][j]+abs(r[i-1]-b[j]));
            f[i+1][j+1]=min(f[i+1][j+1],f[i][j]+abs(r[i]-b[j]));
        }
        return f[m][n];
    }

    if(r[m-1]<b[0]){
        long long i=m-1, j=0, tot=0;
        while(i>=0 && j<n) tot+=abs(r[i--]-b[j++]);
        while(i>=0) tot+=abs(r[i--]-b[0]);
        while(j<n)  tot+=abs(r[m-1]-b[j++]);
        return tot;
    }

    vector<pair<long long,long long>> a;
    forv(i,r) a.pb({i,1});
    forv(i,b) a.pb({i,0});
    sort(all(a));

    int cr=0, cb=0, task3=1;
    forinc(i,1,m+n){
        (a[i-1].se ? cb++ : cr++);
        if(i>7) (a[i-8].se ? cb-- : cr--);
        if(i>=7) task3&=cb && cr;
    }

    vector<long long> s(m+n+1);
    forinc(i,1,m+n) s[i]=s[i-1]+a[i-1].fi;

    if(task3){
        int i=0, cnt=0, sz=0;
        vector<long long> f(100,1e15);
        f[0]=0;
        while(i<m+n){
            vector<long long> g(100,1e15);
            cnt++;
            int j=i;
            while(j<m+n && a[j].se==a[i].se) j++;

            g[j-i]=min(g[j-i],f[0]);
            forinc(t,0,sz){
                forinc(k,1,j-i){
                    if(!t && !i) continue;
                    g[j-i-k]=min(g[j-i-k],f[t]+(s[i+k]-s[i]) - (s[i]-s[i-t]) + a[i-(t<k)].fi*(t-k));
                }
            }
            swap(f,g);
            sz=j-i;
            i=j;
        }
        return f[0];
    }
    if(max(r[m-1],b[n-1])<=m+n){
        vector<int> seg;
        int i=0;
        while(i<m+n){
            int j=i;
            while(j<m+n && a[j].se==a[i].se) j++;
            seg.pb(j-i);
            i=j;
        }
        int bh=0,l=1,r;
        long long tot=0;
        forinc(i,0,seg.size()-1){
            r=l+seg[i]-1;
            tot+=s[l+bh-1]-s[l-1];
            int ql=l+bh;
            if(i+1<seg.size()){
                int f=seg[i]-bh, t=seg[i+1];
                bh=min(f,t);
                tot-=s[r]-s[r-bh];
            } else{
                bh=0;
            }
            int qr=r-bh;
            long long f1=i?a[l-2].fi:-1e15;
            long long f2=i+1<seg.size()?a[r].fi:1e15;
            forinc(j,ql,qr){
                tot+=min((long long)a[j-1].fi-f1,(long long)f2-a[j-1].fi);
            }
            l=r+1;
        }
        return tot;
    }
}

//#define unx

#ifdef unx
main(){
    #define task "TASK"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }

    vector<vector<int>> a;
    forinc(i,0,1){
        a.emplace_back();
        int n; cin>>n; a.back().resize(n);
        forv(j,a.back()) cin>>j;
    }
    cout<<min_total_length(a[0],a[1]);
}
#endif // unx

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i+1<seg.size()){
                ~~~^~~~~~~~~~~
wiring.cpp:103:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             long long f2=i+1<seg.size()?a[r].fi:1e15;
                          ~~~^~~~~~~~~~~
wiring.cpp:111:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45