oj.uz

Submission #851188

# Submission time Handle Problem Language Result Execution time Memory
851188 2023-09-18T19:52:45 Z abcvuitunggio Wiring (IOI17_wiring) C++17
7 / 100
 33 ms 12484 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15;
ll dp[200001],mn[200001],mn2[200001],val[200002],sum[200001];
pair <int, int> position[200001];
int id,cur[2],l,r,lo;
ll min_total_length(vector <int> a, vector <int> b){
    for (int i:a)
        position[++id]={i,0};
    for (int i:b)
        position[++id]={i,1};
    sort(position+1,position+id+1);
    for (int i=id;i;i--){
        val[i]=cur[position[i].second^1]-position[i].first;
        if (i<id&&position[i+1].second==position[i].second)
            val[i]+=val[i+1];
        if (position[i].second!=position[i-1].second)
            cur[position[i].second]=position[i].first;
    }
    for (int i=1;i<=id;i++)
        sum[i]=sum[i-1]+position[i].first;
    mn[0]=val[1];
    for (int i=1;i<=id;i++){
        dp[i]=INF;
        if (l){
            if (l==r)
                dp[i]=min(dp[r-1],dp[r])+sum[i]-sum[r]-position[r].first*(i-r);
            else{
                dp[i]=mn2[max(r*2-i,l-1)]+sum[i]-sum[r]-position[r].first*(i-r);
                if (i-r<r-l+1)
                    dp[i]=min(dp[i],mn[r*2-i]-val[r*2-i+1]+sum[i]-sum[r]*2+sum[r*2-i]);
            }
        }
        mn[i]=min(mn[i-1],dp[i]+val[i+1]);
        if (i==1||position[i-1].second!=position[i].second){
            lo=i;
            mn[i]=min(dp[i-1]+val[i],dp[i]+val[i+1]);
        }
        if (position[i].second!=position[i+1].second){
            l=lo;
            r=i;
            mn2[r]=INF;
            for (int i=r-1;i>=l-1;i--)
                mn2[i]=min(mn2[i+1],dp[i]+position[r].first*(r-i)-sum[r]+sum[i]);
        }
    }
	return dp[id];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 16 ms 10588 KB Output is correct
4 Correct 16 ms 10584 KB Output is correct
5 Incorrect 16 ms 10840 KB 3rd lines differ - on the 1st token, expected: '41752125325332', found: '58373648760852'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 33 ms 11156 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '5394062025'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 27 ms 11356 KB Output is correct
3 Correct 30 ms 11348 KB Output is correct
4 Correct 30 ms 11348 KB Output is correct
5 Correct 30 ms 11348 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6496 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Incorrect 28 ms 12484 KB 3rd lines differ - on the 1st token, expected: '2300170053', found: '2303908475'
19 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Correct 16 ms 10588 KB Output is correct
20 Correct 16 ms 10584 KB Output is correct
21 Incorrect 16 ms 10840 KB 3rd lines differ - on the 1st token, expected: '41752125325332', found: '58373648760852'
22 Halted 0 ms 0 KB -