제출 #1062772

#제출 시각아이디문제언어결과실행 시간메모리
1062772Malix전선 연결 (IOI17_wiring)C++14
13 / 100
35 ms2768 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> tii; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define MP make_pair #define LSOne(s) ((s)&(-s)) ll INF=1e18+10; int inf=1e9+10; ll M=1e9+7; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n=r.size(); int m=b.size(); if(r.back()<b[0]){ stack<int> ar,br; REP(i,0,n)ar.push(r[i]); REP(i,0,m)br.push(b[i]); ll ans=0; int x=r.back(),y=b[0]; while(!ar.empty()||!br.empty()){ int l=x,r=y; if(!ar.empty()){ l=ar.top(); ar.pop(); } if(!br.empty()){ r=br.top(); br.pop(); } ans+=(ll)r-l; } return ans; } priority_queue<pi> pq; REP(i,0,n)pq.push({r[i],0}); REP(i,0,m)pq.push({b[i],1}); ll k=1,t=pq.top().S;pq.pop(); vector<ll> arr; while(!pq.empty()){ int y=pq.top().S; pq.pop(); if(t==y)k++; else{ arr.PB(k); k=1; t=y; } } arr.PB(k); int s=arr.size();cerr<<s<<"\n"; vector<ll> brr(s,0); ll ans=0; REP(i,0,s-1){ if(arr[i]==0)continue; ll mn=min(arr[i],arr[i+1]); arr[i]-=mn;arr[i+1]-=mn; brr[i]=mn; ans+=mn*mn; } if(arr[0]!=0){ ll p=brr[0]+arr[0]; ans+=(p*(p+1))/2; ans-=(arr[0]*(arr[0]+1))/2; } REP(i,1,s){ if(arr[i]==0)continue; ll z=abs(brr[i]-brr[i-1]); if(z>=arr[i]){ ll q=min(brr[i],brr[i-1]); ll p=q+arr[i]; ans+=(p*(p+1))/2; ans-=(q*(q+1))/2; } else{ ll q=min(brr[i],brr[i-1]); ll p=q+z; ans+=(p*(p+1))/2; ans-=(q*(q+1))/2; arr[i]-=z; ll tmp=p+arr[i]/2; ll ta=(tmp*(tmp+1))/2-(p*(p+1))/2; ans+=ta*2; if(arr[i]%2==1){ ll tmp2=tmp+1; ans+=(tmp*(tmp+1))/2-(tmp2*(tmp2+1))/2; } } } return ans; }
#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...