# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966792 | 2024-04-20T11:18:40 Z | Amr | Wiring (IOI17_wiring) | C++17 | 1000 ms | 8928 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++) { allme+=v[j].F; ll allprev = 0; for(int k = start-1; k >= prevstart; k--) { allprev+=v[k].F; if(dp[k-1]==-1) continue; 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; dp[j] = max(dp[j],dp[k-1]+allme-allprev+mm); } } prevstart = start,start=i+1; } } // b r b rrrr //for(int i = 0; i <= n+m; i++) cout << dp[i] << " "; cout<< endl; return 1; return dp[n+m]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 344 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '34403' |
2 | Halted | 0 ms | 0 KB | - |
# | 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 | 1085 ms | 8928 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Incorrect | 1 ms | 348 KB | 3rd lines differ - on the 1st token, expected: '17703', found: '19052' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 344 KB | 3rd lines differ - on the 1st token, expected: '27', found: '42' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 344 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '34403' |
2 | Halted | 0 ms | 0 KB | - |