제출 #393464

#제출 시각아이디문제언어결과실행 시간메모리
393464JimmyZJX전선 연결 (IOI17_wiring)C++14
20 / 100
28 ms3780 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> #include <numeric> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) LL dp[203][203]; int n, m; LL Task1DP(const Vi & r, const Vi & b) { LL sumR = 0, sumB = 0; forR(i, n) { sumR += abs(r[i] - b[0]); dp[i][0] = sumR; } forR(i, m) { sumB += abs(b[i] - r[0]); dp[0][i] = sumB; } for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) { LL planA = abs(r[i] - b[j]) + dp[i - 1][j - 1]; int minI = INT_MAX; forR(k, m) minI = min(minI, abs(r[i] - b[k])); LL planB = minI + dp[i - 1][j]; int minJ = INT_MAX; forR(k, n) minJ = min(minJ, abs(r[k] - b[j])); LL planC = minJ + dp[i][j - 1]; dp[i][j] = min({ planA, planB, planC }); } return dp[n - 1][m - 1]; } LL min_total_length(Vi r, Vi b) { n = r.size(), m = b.size(); if (n <= 200 && m <= 200) return Task1DP(r, b); int rMax = r.back(), bMin = b.front(); if (bMin > rMax) { // Task 2 LL ans = 0; for (int p : r) ans += rMax - p; for (int p : b) ans += p - bMin; ans += (LL)max(m, n) * (bMin - rMax); return ans; } } #ifdef TEST_LOCAL int main() { auto r = min_total_length(Vi{ 1, 2, 3, 7 }, Vi{ 0, 4, 5, 9, 10 }); return 0; } #endif

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

wiring.cpp: In function 'LL min_total_length(Vi, Vi)':
wiring.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^
#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...