제출 #783302

#제출 시각아이디문제언어결과실행 시간메모리
783302shezitt선물상자 (IOI15_boxes)C++17
20 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include <boxes.h> using namespace std; #define sz(x) (int) x.size() #define dbg(x) cout << #x << ": " << x << endl; using ll = long long; long long delivery(int N, int K, int L, int p[]){ sort(p, p+N); // SUBTASK 1 if(K == 1){ ll ans = 0; for(int i=0; i<N; ++i){ ans += min(p[i], L - p[i]) * 2; } return ans; } // SUBTASK 2 if(K == N){ ll ans = 2e9+5; // opcion 1 - desde izquierda voy y regreso hasta el final ans = p[N-1] * 2; // opcion 2 - desde derecha voy y regreso hasta el comienzo ans = min(ans, (L - p[0])*2ll); // opcion 3 - vuelta completa ans = min(ans, 1ll*L); // opcion 4 - voy por la izquierda hasta cierto punto, vuelvo y voy desde la derecha hasta donde me faltaba if(N > 1){ for(int i=0; i+1<N; ++i){ ll x = p[i]; ll y = p[i+1]; ans = min(ans, 2*x + 2*(L - y)); } } return ans; } // SUBTASK 3 if(N <= 20){ ll ans = 4e18; for(int mask=0; mask<(1<<N); ++mask){ // 0 -> from left // 1 -> from right ll res = 0; vector<int> left, right; for(int i=0; i<N; ++i){ if((1<<i) & mask){ right.push_back(p[i]); } else { left.push_back(p[i]); } } // left ll cur = K; ll prev = 0; for(int pos : left){ if(cur == 0){ // entonces recargo res += min(prev, L - prev); prev = 0; cur = K; } res += pos - prev; prev = pos; cur--; } res += min(prev, L - prev); // right cur = K; prev = L; for(int i=sz(right)-1; i>=0; --i){ int pos = right[i]; if(cur == 0){ // tengo que recargar res += min(prev, L - prev); prev = L; cur = K; } res += prev - pos; prev = pos; cur--; } res += min(prev, L - prev); ans = min(ans, res); } return ans; } return -1; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...