# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966804 | 2024-04-20T11:49:39 Z | Amr | Wiring (IOI17_wiring) | C++17 | 1000 ms | 9648 KB |
#include "wiring.h" #include<bits/stdc++.h> using namespace std; #define sz size() typedef long long ll; #define all(x) (x).begin(),(x).end() #define F first #define S second const int N = 2e5+2; ll a[N]; ll dp[N]; long long min_total_length(std::vector<int> r, std::vector<int> b) { ll n = r.sz, m = b.sz; vector<pair<ll,ll> > v; v.push_back({-1,-1}); for(int i = 0; i < r.sz; i++) v.push_back({r[i],0}); for(int i = 0; i < b.sz; i++) v.push_back({b[i],1}); sort(all(v)); ll start = 1,prevstart=1; for(int i = 1; i <= n+m; i++) { if(i==n+m||(v[i].S!=v[i+1].S)) { ll en = i; if(start==1) { for(int j = 1; j <= en; j++) dp[j] = -1; prevstart = start; start = i+1; continue; } ll allme = 0; for(int j = start; j <= en; j++) { dp[j] = 1e18; allme+=v[j].F; ll allprev = 0; for(ll k = start-1; k >= prevstart; k--) { allprev+=v[k].F; ll kk = k-1; ll mm = 0; if(j-start+1>start-k) mm = -((j-start+1)-(start-k))*v[start-1].F; else mm = (start-k-(j-start+1))*v[start].F; if(dp[kk]!=-1){ dp[j] = min(dp[j],dp[kk]+allme-allprev+mm); //if(j==6&&k==3) cout << allme << " " << allprev << " " << dp[kk] << endl; } if(k==prevstart) { if(dp[k]!=-1) dp[j]=min(dp[j],dp[k]+allme-allprev+mm); } } } prevstart = start,start=i+1; } } // b r b rrrr return dp[n+m]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 444 KB | Output is correct |
12 | Correct | 1 ms | 444 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 344 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Execution timed out | 1050 ms | 9412 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 44 ms | 9648 KB | Output is correct |
4 | Correct | 44 ms | 9160 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 448 KB | Output is correct |
18 | Correct | 42 ms | 9388 KB | Output is correct |
19 | Correct | 36 ms | 9376 KB | Output is correct |
20 | Correct | 40 ms | 9404 KB | Output is correct |
21 | Correct | 36 ms | 9256 KB | Output is correct |
22 | Correct | 38 ms | 9404 KB | Output is correct |
23 | Correct | 37 ms | 9268 KB | Output is correct |
24 | Correct | 45 ms | 9628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Execution timed out | 1090 ms | 8688 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 444 KB | Output is correct |
12 | Correct | 1 ms | 444 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 344 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Execution timed out | 1050 ms | 9412 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |