제출 #794577

#제출 시각아이디문제언어결과실행 시간메모리
794577firewater전선 연결 (IOI17_wiring)C++14
13 / 100
29 ms11604 KiB
#include "wiring.h" #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include <cassert> #define ll long long #define mp make_pair #define fs first #define sn second #define MX 202300 using namespace std; ll n,sum[MX],num[MX],f[MX]; pair<ll,ll>a[MX]; ll ask(ll l,ll r) { ll m1,m2,sum1,sum2; m1=num[r]-num[l-1]; m2=r-l+1-m1; if(a[l].sn==2)swap(m1,m2); sum1=sum[l+m1-1]-sum[l-1]; sum2=sum[r]-sum[r-m2]; return ((a[l+m1-1].fs*m1-sum1)+(sum2-a[r-m2+1].fs*m2)+(a[r-m2+1].fs-a[l+m1-1].fs)*max(m1,m2)); // m1=r.size(); // m2=b.size(); // ll sum1=0,sum2=0; // for(ll i=0;i<m1;++i) // sum1+=r[i]; // for(ll i=0;i<m2;++i) // sum2+=b[i]; // return ((sum2-b[0]*m2)+(r[m1-1]*m1-sum1)+(b[0]-r[m1-1])*max(m1,m2)); } long long min_total_length(std::vector<int> r, std::vector<int> b) { ll m1=r.size(),m2=b.size(); for(ll i=1;i<=m1;++i) a[i]=mp(r[i-1],1); for(ll i=1;i<=m2;++i) a[i+m1]=mp(b[i-1],2); n=m1+m2; sort(a+1,a+1+n); for(ll i=1;i<=n;++i){ if(a[i].sn==1)num[i]=1; num[i]+=num[i-1]; sum[i]=sum[i-1]+a[i].fs; } for(ll i=1;i<=n;++i) f[i]=100000000000000000ll; // printf("%lld\n",f[0]); f[0]=0; // for(ll i=n;i<=n;++i){ // ll j=i-1,now=1; // while(j>0){ // if(now==1&&a[j].sn==a[i].sn){ // j--; // continue; // } // now=2; // if(a[j].sn==a[i].sn)break; // f[i]=min(f[i],min(f[j-1],f[j])+ask(j,i)); // printf("%lld %lld %lld\n",j,i,f[i]); // j--; // } // } // return f[n]; return ask(1,n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...