제출 #885990

#제출 시각아이디문제언어결과실행 시간메모리
885990waldi전선 연결 (IOI17_wiring)C++17
17 / 100
1088 ms9668 KiB
#include "wiring.h" #include <bits/stdc++.h> #define FOR(i,p,k) for(int i=(p);i<=(k);++i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) (int((x).size())) #define all(x) (x).begin(),(x).end() #define inf 1000000000000000000ll #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll, bool> plb; vector<ll> pom(vector<ll> popdp, vector<ll> poppoz, vector<ll> terpoz){ //~ printf("poppoz: "); //~ for(ll x : poppoz) printf("%lld ", x); //~ printf("\n"); //~ printf("popdp: "); //~ for(ll x : popdp) printf("%lld ", x); //~ printf("\n"); //~ printf("terpoz: "); //~ for(ll x : terpoz) printf("%lld ", x); //~ printf("\n"); int n = ssize(poppoz); int m = ssize(terpoz); ll dodaj = 0ll; for(int i = n-1; ~--i;){ dodaj += poppoz[n-1]-poppoz[i]; popdp[i] += dodaj; } ll delta = terpoz[0]-poppoz[n-1]; vector<ll> dp(m+1); dp[0] = popdp[n]; FOR(i, 1, m){ dp[i] = inf; REP(j, n) dp[i] = min(dp[i], popdp[j] + delta*max(i, n-j)); dp[i] = min(dp[i], popdp[n] + delta*i); } dodaj = 0ll; FOR(i, 2, m){ dodaj += terpoz[i-1]-terpoz[0]; dp[i] += dodaj; } //~ printf("dp: "); //~ for(ll x : dp) printf("%lld ", x); //~ printf("\n"); //~ printf("\n"); return dp; } ll min_total_length(vector<int> r, vector<int> b){ vector<plb> vec; for(int x : r) vec.emplace_back(x, 0); for(int x : b) vec.emplace_back(x, 1); sort(all(vec)); vector<ll> dp, poppoz, terpoz; REP(i, ssize(vec)){ terpoz.emplace_back(vec[i].fi); if(i+1 == ssize(vec) || vec[i+1].se != vec[i].se){ if(dp.empty()) dp.resize(ssize(terpoz)+1, inf), dp[0] = 0ll; else dp = pom(dp, poppoz, terpoz); poppoz = terpoz, terpoz.clear(); } } return dp.back(); }
#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...