oj.uz

답안 #59167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59167 2018-07-20T21:56:14 Z TadijaSebez 전선 연결 (IOI17_wiring) C++11
100 / 100
 95 ms 102528 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
const int N=200050;
const ll inf=1e18;
pair<int,int> a[N];
ll dp[N],f[N];
int last[2],cnt[N];
ll max(ll a, ll b){ return a>b?a:b;}
ll min(ll a, ll b){ return a>b?b:a;}
ll min_total_length(vector<int> r, vector<int> b)
{
	int i,j,n;n=r.size()+b.size();
	for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
	for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
	sort(a+1,a+1+n);a[0].second=2;
	bool ok;ll sum=0;last[0]=last[1]=0;
	for(i=1;i<=n;i++)
	{
		dp[i]=inf;
		if(!last[a[i].second^1]){ last[a[i].second]=i;continue;}
		//printf("%i %i %i\n",i,last[0],last[1]);
		if(a[i].second!=a[i-1].second)
		{
			//printf("->%i<-\n",i);
			ll cost=0;
			dp[i]=dp[i-1]+a[i].first-a[i-1].first;
			for(j=i-1;j>last[a[i].second];j--)
			{
				cost+=a[i].first-a[j].first;
				f[j]=dp[j-1]+cost;
				if(dp[i]>=dp[j-1]+cost)
				{
					cnt[i]=i-j;
					dp[i]=dp[j-1]+cost;
				}
			}
			for(j=last[a[i].second]+2;j<i;j++) f[j]=min(f[j],f[j-1]);//,printf("%i %lld\n",j,f[j]);
			ok=1;sum=0;
		}
		else
		{
			sum+=a[i].first-a[last[a[i].second^1]+1].first;
			dp[i]=min(dp[i],dp[i-1]+a[i].first-a[last[a[i].second^1]].first);
			int sz=i-last[a[i].second^1];
			if(ok && a[last[a[i].second^1]-sz+1].second==(a[i].second^1))
			{
				dp[i]=min(dp[i],f[last[a[i].second^1]-sz+1]+sum);//dp[last[a[i].second^1]-sz-1]+a[i].first-a[last[a[i].second^1]-sz].first);
				//printf("%i %lld %lld\n",a[i].first,f[last[a[i].second^1]-sz+1],sum);
			}
			else ok=0;
			/*if(cnt[i-1]>=i-last[a[i].second^1])
			{
				cnt[i]=cnt[i-1];
				dp[i]=dp[i-1]+a[i].first-a[last[a[i].second^1]+1].first;
			}
			else
			{
				if(a[last[a[i].second^1]-cnt[i-1]].second==(a[i].second^1))
				{
					if(dp[last[a[i].second^1]-cnt[i-1]-1]+a[i].first-a[last[a[i].second^1]-cnt[i-1]].first<dp[i])
					{
						dp[i]=dp[last[a[i].second^1]-cnt[i-1]-1]+a[i].first-a[last[a[i].second^1]-cnt[i-1]].first;
						cnt[i]=cnt[i-1]+1;
					}
				}
				if(dp[i-1]+a[i].first-a[last[a[i].second^1]].first<dp[i])
				{
					dp[i]=dp[i-1]+a[i].first-a[last[a[i].second^1]].first;
					cnt[i]=cnt[i-1];
				}
			}*/
		}
		last[a[i].second]=i;
		//printf("%lld ",dp[i]);
	}
	return dp[n];
}
/*int main()
{
	int n,m,i,x;vector<int> r,b;
	scanf("%i %i",&n,&m);
	for(i=0;i<n;i++) scanf("%i",&x),r.pb(x);
	for(i=0;i<m;i++) scanf("%i",&x),b.pb(x);
	printf("%lld\n",min_total_length(r,b));
	return 0;
}*/

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++) a[i+1]=mp(r[i],0);
          ~^~~~~~~~~
wiring.cpp:19:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<b.size();i++) a[i+1+r.size()]=mp(b[i],1);
          ~^~~~~~~~~
wiring.cpp:50:4: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(ok && a[last[a[i].second^1]-sz+1].second==(a[i].second^1))
    ^~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 4 ms 772 KB Output is correct
16 Correct 3 ms 776 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 780 KB Output is correct
2 Correct 2 ms 784 KB Output is correct
3 Correct 38 ms 6488 KB Output is correct
4 Correct 56 ms 7952 KB Output is correct
5 Correct 36 ms 8972 KB Output is correct
6 Correct 52 ms 12600 KB Output is correct
7 Correct 42 ms 14420 KB Output is correct
8 Correct 54 ms 16476 KB Output is correct
9 Correct 51 ms 18300 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18300 KB Output is correct
2 Correct 2 ms 18300 KB Output is correct
3 Correct 74 ms 21916 KB Output is correct
4 Correct 66 ms 23468 KB Output is correct
5 Correct 3 ms 23468 KB Output is correct
6 Correct 3 ms 23468 KB Output is correct
7 Correct 3 ms 23468 KB Output is correct
8 Correct 3 ms 23468 KB Output is correct
9 Correct 3 ms 23468 KB Output is correct
10 Correct 2 ms 23468 KB Output is correct
11 Correct 3 ms 23468 KB Output is correct
12 Correct 2 ms 23468 KB Output is correct
13 Correct 2 ms 23468 KB Output is correct
14 Correct 2 ms 23468 KB Output is correct
15 Correct 2 ms 23468 KB Output is correct
16 Correct 3 ms 23468 KB Output is correct
17 Correct 3 ms 23468 KB Output is correct
18 Correct 95 ms 25488 KB Output is correct
19 Correct 81 ms 27308 KB Output is correct
20 Correct 78 ms 29364 KB Output is correct
21 Correct 74 ms 31296 KB Output is correct
22 Correct 70 ms 33240 KB Output is correct
23 Correct 95 ms 35188 KB Output is correct
24 Correct 66 ms 36992 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 36992 KB Output is correct
2 Correct 84 ms 37648 KB Output is correct
3 Correct 80 ms 39548 KB Output is correct
4 Correct 61 ms 40824 KB Output is correct
5 Correct 62 ms 42184 KB Output is correct
6 Correct 2 ms 42184 KB Output is correct
7 Correct 2 ms 42184 KB Output is correct
8 Correct 3 ms 42184 KB Output is correct
9 Correct 2 ms 42184 KB Output is correct
10 Correct 2 ms 42184 KB Output is correct
11 Correct 2 ms 42184 KB Output is correct
12 Correct 2 ms 42184 KB Output is correct
13 Correct 2 ms 42184 KB Output is correct
14 Correct 2 ms 42184 KB Output is correct
15 Correct 2 ms 42184 KB Output is correct
16 Correct 2 ms 42184 KB Output is correct
17 Correct 3 ms 42184 KB Output is correct
18 Correct 57 ms 42628 KB Output is correct
19 Correct 65 ms 44660 KB Output is correct
20 Correct 56 ms 45644 KB Output is correct
21 Correct 63 ms 46536 KB Output is correct
22 Correct 63 ms 47540 KB Output is correct
23 Correct 59 ms 48816 KB Output is correct
24 Correct 47 ms 50124 KB Output is correct

Subtask #5
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 4 ms 772 KB Output is correct
16 Correct 3 ms 776 KB Output is correct
17 Correct 3 ms 780 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 38 ms 6488 KB Output is correct
20 Correct 56 ms 7952 KB Output is correct
21 Correct 36 ms 8972 KB Output is correct
22 Correct 52 ms 12600 KB Output is correct
23 Correct 42 ms 14420 KB Output is correct
24 Correct 54 ms 16476 KB Output is correct
25 Correct 51 ms 18300 KB Output is correct
26 Correct 3 ms 18300 KB Output is correct
27 Correct 2 ms 18300 KB Output is correct
28 Correct 74 ms 21916 KB Output is correct
29 Correct 66 ms 23468 KB Output is correct
30 Correct 3 ms 23468 KB Output is correct
31 Correct 3 ms 23468 KB Output is correct
32 Correct 3 ms 23468 KB Output is correct
33 Correct 3 ms 23468 KB Output is correct
34 Correct 3 ms 23468 KB Output is correct
35 Correct 2 ms 23468 KB Output is correct
36 Correct 3 ms 23468 KB Output is correct
37 Correct 2 ms 23468 KB Output is correct
38 Correct 2 ms 23468 KB Output is correct
39 Correct 2 ms 23468 KB Output is correct
40 Correct 2 ms 23468 KB Output is correct
41 Correct 3 ms 23468 KB Output is correct
42 Correct 3 ms 23468 KB Output is correct
43 Correct 95 ms 25488 KB Output is correct
44 Correct 81 ms 27308 KB Output is correct
45 Correct 78 ms 29364 KB Output is correct
46 Correct 74 ms 31296 KB Output is correct
47 Correct 70 ms 33240 KB Output is correct
48 Correct 95 ms 35188 KB Output is correct
49 Correct 66 ms 36992 KB Output is correct
50 Correct 3 ms 36992 KB Output is correct
51 Correct 84 ms 37648 KB Output is correct
52 Correct 80 ms 39548 KB Output is correct
53 Correct 61 ms 40824 KB Output is correct
54 Correct 62 ms 42184 KB Output is correct
55 Correct 2 ms 42184 KB Output is correct
56 Correct 2 ms 42184 KB Output is correct
57 Correct 3 ms 42184 KB Output is correct
58 Correct 2 ms 42184 KB Output is correct
59 Correct 2 ms 42184 KB Output is correct
60 Correct 2 ms 42184 KB Output is correct
61 Correct 2 ms 42184 KB Output is correct
62 Correct 2 ms 42184 KB Output is correct
63 Correct 2 ms 42184 KB Output is correct
64 Correct 2 ms 42184 KB Output is correct
65 Correct 2 ms 42184 KB Output is correct
66 Correct 3 ms 42184 KB Output is correct
67 Correct 57 ms 42628 KB Output is correct
68 Correct 65 ms 44660 KB Output is correct
69 Correct 56 ms 45644 KB Output is correct
70 Correct 63 ms 46536 KB Output is correct
71 Correct 63 ms 47540 KB Output is correct
72 Correct 59 ms 48816 KB Output is correct
73 Correct 47 ms 50124 KB Output is correct
74 Correct 58 ms 52268 KB Output is correct
75 Correct 78 ms 53828 KB Output is correct
76 Correct 67 ms 55776 KB Output is correct
77 Correct 63 ms 57196 KB Output is correct
78 Correct 57 ms 58492 KB Output is correct
79 Correct 56 ms 59844 KB Output is correct
80 Correct 45 ms 61188 KB Output is correct
81 Correct 46 ms 62664 KB Output is correct
82 Correct 41 ms 63948 KB Output is correct
83 Correct 42 ms 65092 KB Output is correct
84 Correct 49 ms 67080 KB Output is correct
85 Correct 59 ms 69532 KB Output is correct
86 Correct 51 ms 71292 KB Output is correct
87 Correct 52 ms 73028 KB Output is correct
88 Correct 55 ms 75360 KB Output is correct
89 Correct 51 ms 77232 KB Output is correct
90 Correct 56 ms 79112 KB Output is correct
91 Correct 50 ms 81164 KB Output is correct
92 Correct 49 ms 83120 KB Output is correct
93 Correct 49 ms 85052 KB Output is correct
94 Correct 66 ms 86940 KB Output is correct
95 Correct 84 ms 88876 KB Output is correct
96 Correct 74 ms 90592 KB Output is correct
97 Correct 65 ms 92656 KB Output is correct
98 Correct 59 ms 94600 KB Output is correct
99 Correct 62 ms 96484 KB Output is correct
100 Correct 74 ms 98640 KB Output is correct
101 Correct 63 ms 100576 KB Output is correct
102 Correct 76 ms 102528 KB Output is correct