# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
940911 | 2024-03-08T02:05:26 Z | beaboss | 전선 연결 (IOI17_wiring) | C++14 | 32 ms | 11836 KB |
// Source: https://oj.uz/problem/view/IOI17_wiring // #include "wiring.h" #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<ll, ll> pii; typedef vector<pii> vpii; typedef vector<ll> vi; #define FOR(i, a, b) for (ll i = (a); i<b; i++) bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; } bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; } const ll INF = 1e9; ll min_total_length(vector<int> r, vector<int> b) { vector<vi> dp; vector<vi> pref; ll n = r.size(), m = b.size(); ll i, j; i = j = 0; r.pb(INF); b.pb(INF); while (i != n || j != m) { ll sz = 0; ll here=pref.size(); pref.pb({0}); if (r[i] < b[j]) { while (i != n && r[i] < b[j]) { pref[here].pb(r[i]); sz++;i++; } } else { while (j != m && b[j] < r[i]) { pref[here].pb(b[j]); sz++;j++; } } dp.pb(vi(sz+1, INF)); assert(pref[here].size() == sz+1); FOR(i, 1, sz+1) pref[here][i] += pref[here][i-1]; } dp[0][0] = 0; FOR(i, 1, dp.size()) { ll best = INF; FOR(j, 0, dp[i].size()) { if ((ll) dp[i-1].size() - j - 1 >= 0) { // cout << 'd' << endl; // cout << best << endl; best = min(best, dp[i-1][dp[i-1].size() - j-1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j-1])); // cout << best << endl; // cout << dp[i-1].size() - j-1 << endl; } // cout << i << j << ' ' << best << pref[i][j] << endl; ckmin(dp[i][j], best + pref[i][j]); best -= pref[i-1][pref[i-1].size() - 1] - pref[i-1][pref[i-1].size() - 2]; // get the last element from before // cout << ' ' << dp[i][j] << endl; } best = INF; for (ll j = dp[i].size() - 1; j >= 0; j--) { if (dp[i-1].size() - j - 1 >= 0) { best = min(best, dp[i-1][dp[i-1].size() - j - 1] - (pref[i-1][dp[i-1].size()-1] - pref[i-1][dp[i-1].size() - j - 1])); } ckmin(dp[i][j], best + pref[i][j]); best += pref[i][1]; // cout << i << j << ' ' << dp[i][j] << endl; } } return dp[dp.size()-1][dp[dp.size()-1].size()-1]; } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // ll res = min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}); // cout << res << endl; // }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 440 KB | 3rd lines differ - on the 1st token, expected: '14340', found: '3917' |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 344 KB | 3rd lines differ - on the 1st token, expected: '904', found: '1000000000' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 436 KB | Output is correct |
3 | Incorrect | 32 ms | 11836 KB | 3rd lines differ - on the 1st token, expected: '1068938599', found: '999650046' |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 18 ms | 6568 KB | 3rd lines differ - on the 1st token, expected: '373710605', found: '116069314' |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 440 KB | 3rd lines differ - on the 1st token, expected: '14340', found: '3917' |
3 | Halted | 0 ms | 0 KB | - |