oj.uz

답안 #919336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919336 2024-01-31T15:32:22 Z HuyQuang_re_Zero 전선 연결 (IOI17_wiring) C++14
7 / 100
 32 ms 8852 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "wiring.h"
II a[N];
ll f[N],n,i,j,k,Begin,sum[N],sub[N],l[N],r[N];
const ll oo=round(1e18);
ll min_total_length(vector <int> Red,vector <int> Blue)
{
    for(int k:Red) a[++n]={ k,0 };
    for(int k:Blue) a[++n]={ k,1 };
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)
    {
        if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
        if(i==n || a[i].snd!=a[i+1].snd)
        {
            sum[Begin]=a[Begin].fst; l[Begin]=1;
            for(j=Begin+1;j<=i;j++) sum[j]=sum[j-1]+a[j].fst,l[j]=j-Begin+1;
            sub[i]=-a[i].fst; r[i]=1;
            for(j=i-1;j>=Begin;j--) sub[j]=sub[j+1]-a[j].fst,r[j]=i-j+1;
        }
    }
    for(i=1;i<=n;i++) f[i]=oo;
    for(i=1;i<=n;i++)
    {
        if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
        if(Begin>1 && (i==n || a[i].snd!=a[i+1].snd))
        {
            ll mi=oo;
            for(j=Begin;j<=i;j++)
            {
                if(l[j]<=l[Begin-1])
                {
                    k=Begin-l[j];
                    mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin-1].fst*r[k]);
                }
                f[j]=min(f[j],mi+sum[j]-a[Begin-1].fst*l[j]);
            }
            mi=oo;
            for(k=Begin-l[Begin-1];k<Begin;k++)
            {
                mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin].fst*r[k]);
                if(r[k]<=r[Begin])
                {
                    j=Begin+r[k]-1;
                    f[j]=min(f[j],mi+sum[j]-a[Begin].fst*l[j]);
                }
            }
        }
    }
    return f[n];
}

/*
int main()
{
    freopen("wiring.inp","r",stdin);
    freopen("wiring.out","w",stdout);
    int n,m;
    cin>>n>>m;
    vector <int> r,b;
    for(int i=1;i<=n;i++) cin>>k,r.push_back(k);
    for(int i=1;i<=m;i++) cin>>k,b.push_back(k);
    cout<<min_total_length(r,b);
}
*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 2 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct
3 Runtime error 18 ms 7516 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Runtime error 32 ms 8852 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2476 KB Output is correct
2 Runtime error 20 ms 8128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 2 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2484 KB Output is correct
19 Runtime error 18 ms 7516 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -