CSES - Datatähti 2020 alku - Results
Submission details
Task:Mastot
Sender:caro
Submission time:2019-10-04 18:30:27
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#40.01 s1, 2, 3details
#50.01 s1, 2, 3details
#60.01 s1, 2, 3details
#70.01 s1, 2, 3details
#80.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#100.01 s1, 2, 3details
#110.01 s1, 2, 3details
#120.01 s1, 2, 3details
#130.01 s1, 2, 3details
#140.01 s1, 2, 3details
#150.01 s1, 2, 3details
#160.01 s1, 2, 3details
#170.01 s1, 2, 3details
#180.01 s1, 2, 3details
#190.01 s1, 2, 3details
#200.01 s1, 2, 3details
#210.01 s2, 3details
#22ACCEPTED0.01 s2, 3details
#230.01 s2, 3details
#240.01 s2, 3details
#250.01 s2, 3details
#260.01 s2, 3details
#270.01 s2, 3details
#280.01 s2, 3details
#290.01 s2, 3details
#300.01 s2, 3details
#310.01 s2, 3details
#32ACCEPTED0.01 s2, 3details
#330.01 s2, 3details
#340.05 s3details
#35ACCEPTED0.01 s3details
#360.05 s3details
#370.30 s3details
#380.28 s3details
#390.05 s3details
#400.05 s3details
#41--3details
#42--3details
#43--3details
#44--3details
#45--3details
#46--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &poles[i].cmpVal);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &poleCost);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef struct{
	ull cmpVal;
	ull minCost;
} pole_s;

ull d;
ull transmitter;
pole_s *poles;

int main(){
	cin >> d;
	cin >> transmitter;

	if(d <= transmitter) {
		cout << 0 << '\n';
		return 0;
	}

	ull activeCount = 0;
	pole_s *activeConnectors = (pole_s*)malloc(sizeof(pole_s) * (d - 1));
	poles = (pole_s*) malloc(sizeof(pole_s) * (d - 1));
	for(ull i = 0; i < d - 1; i++) {
		scanf("%lld", &poles[i].cmpVal);
		poles[i].cmpVal += i + 1;
	}

	poles[0].minCost = 0;
	pole_s bestActive = poles[0];
	activeConnectors[activeCount++] = poles[0];

	for(ull i = 1; i < d - 1; i++) {
		ull poleCost;
		scanf("%lld", &poleCost);

		poles[i].minCost = 1e18;
		for(ull l = 0; l < activeCount; l++) {
			if((activeConnectors[l].cmpVal < i + 1) || 
					((bestActive.cmpVal > poles[i].cmpVal) && (bestActive.minCost < poles[i].minCost))) {
				activeConnectors[l] = activeConnectors[--activeCount];
				l--;
			}
			else {
				if(poles[i].minCost > activeConnectors[l].minCost) poles[i].minCost = activeConnectors[l].minCost;
			}
		}

		if(i + 1 <= transmitter) poles[i].minCost = 0;
		poles[i].minCost += poleCost;

		if((bestActive.cmpVal > poles[i].cmpVal) && (bestActive.minCost > poles[i].minCost)) {
			activeConnectors[activeCount++] = poles[i];
			bestActive = poles[i];
		}
		else if((bestActive.cmpVal < poles[i].cmpVal) || (bestActive.minCost > poles[i].minCost)) {
			activeConnectors[activeCount++] = poles[i];
		}
	}

	ull cost = 1e18;
	for(ull i = 0; i < activeCount; i++) {
		if(activeConnectors[i].cmpVal >= d) {
			if(cost > activeConnectors[i].minCost) cost = activeConnectors[i].minCost;
		}
	}

	cout << cost << '\n';

	return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
6
2 2 3 1 2 4
4 1 3 4 2

correct output
3

user output
4

Test 2

Group: 1, 2, 3

Verdict:

input
2
1 1
1

correct output
1

user output
0

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1
1

correct output
0

user output
0

Test 4

Group: 1, 2, 3

Verdict:

input
3
2 2 1
1 2

correct output
1

user output
0

Test 5

Group: 1, 2, 3

Verdict:

input
3
2 2 1
2 1

correct output
1

user output
0

Test 6

Group: 1, 2, 3

Verdict:

input
4
1 1 1 1
1000000000 1000000000 10000000...

correct output
3000000000

user output
2000000000

Test 7

Group: 1, 2, 3

Verdict:

input
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
19000000000

user output
18000000000

Test 8

Group: 1, 2, 3

Verdict:

input
20
1 1 2 1 1 1 2 1 1 2 1 1 1 2 1 ...

correct output
4609157377

user output
3002548579

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
20 20 20 20 20 20 20 20 20 20 ...

correct output
0

user output
0

Test 10

Group: 1, 2, 3

Verdict:

input
19
16 10 9 17 1 16 19 4 18 13 5 3...

correct output
8424700

user output
211350155

Test 11

Group: 1, 2, 3

Verdict:

input
20
2 4 3 4 4 4 4 1 1 3 4 2 1 3 3 ...

correct output
2817777553

user output
2812256131

Test 12

Group: 1, 2, 3

Verdict:

input
20
4 4 4 4 3 4 1 3 4 1 1 4 1 3 1 ...

correct output
3020673750

user output
3603493041

Test 13

Group: 1, 2, 3

Verdict:

input
20
5 1 3 4 2 4 2 2 5 1 3 3 2 4 1 ...

correct output
2064735712

user output
2606773005

Test 14

Group: 1, 2, 3

Verdict:

input
20
8 1 2 6 8 6 9 1 4 9 9 8 6 3 3 ...

correct output
378551508

user output
459527930

Test 15

Group: 1, 2, 3

Verdict:

input
20
5 2 8 9 4 10 1 8 9 9 8 1 7 8 9...

correct output
457149308

user output
308702398

Test 16

Group: 1, 2, 3

Verdict:

input
20
7 6 2 6 1 3 10 4 6 3 5 2 2 10 ...

correct output
471575451

user output
881579531

Test 17

Group: 1, 2, 3

Verdict:

input
20
6 2 2 3 8 7 2 10 8 9 6 3 10 5 ...

correct output
620685913

user output
671464736

Test 18

Group: 1, 2, 3

Verdict:

input
20
4 5 3 8 2 8 5 9 6 3 7 5 1 6 9 ...

correct output
1132427688

user output
1708792789

Test 19

Group: 1, 2, 3

Verdict:

input
20
15 9 7 18 3 20 19 20 17 16 16 ...

correct output
333300698

user output
342154223

Test 20

Group: 1, 2, 3

Verdict:

input
20
19 18 17 16 15 14 13 12 11 10 ...

correct output
660514815

user output
509111979

Test 21

Group: 2, 3

Verdict:

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4999000000000

user output
4998000000000

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 5000 5000 5000 5000 5000 ...

correct output
0

user output
0

Test 23

Group: 2, 3

Verdict:

input
5000
4999 4998 4997 4996 4995 4994 ...

correct output
576616581

user output
694559162

Test 24

Group: 2, 3

Verdict:

input
5000
3343 3711 2568 137 2621 3850 4...

correct output
671570

user output
1000000000000000000

Test 25

Group: 2, 3

Verdict:

input
5000
119 203 420 133 175 334 461 10...

correct output
85700253

user output
1000000000000000000

Test 26

Group: 2, 3

Verdict:

input
5000
8 6 2 1 4 5 7 3 4 2 1 10 3 6 6...

correct output
193210576015

user output
188429629302

Test 27

Group: 2, 3

Verdict:

input
5000
1 2 1 2 2 1 2 2 1 1 1 2 1 2 2 ...

correct output
1576581428593

user output
1563585670911

Test 28

Group: 2, 3

Verdict:

input
5000
300 1937 2136 770 429 2388 197...

correct output
3584707

user output
1000000000000000000

Test 29

Group: 2, 3

Verdict:

input
5000
949 46 29 2237 2413 36 42 1162...

correct output
3210354

user output
9589343

Test 30

Group: 2, 3

Verdict:

input
5000
1557 1727 1787 360 1698 2423 1...

correct output
3177107

user output
1000000000000000000

Test 31

Group: 2, 3

Verdict:

input
5000
484 1991 2309 1326 1901 2426 8...

correct output
4863018

user output
1000000000000000000

Test 32

Group: 2, 3

Verdict: ACCEPTED

input
5000
1833 459 1994 2050 272 31 708 ...

correct output
2876923

user output
2876923

Test 33

Group: 2, 3

Verdict:

input
4999
530 2248 1916 859 2394 1403 24...

correct output
5194452

user output
1000000000000000000

Test 34

Group: 3

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199999000000000

user output
199998000000000

Test 35

Group: 3

Verdict: ACCEPTED

input
200000
200000 200000 200000 200000 20...

correct output
0

user output
0

Test 36

Group: 3

Verdict:

input
200000
199999 199998 199997 199996 19...

correct output
819945000

user output
301534261

Test 37

Group: 3

Verdict:

input
200000
9036 179861 197509 187949 9444...

correct output
59563

user output
1000000000000000000

Test 38

Group: 3

Verdict:

input
200000
357 1516 141 399 860 1591 544 ...

correct output
247414000

user output
1000000000000000000

Test 39

Group: 3

Verdict:

input
200000
10 4 1 7 1 8 8 4 8 2 2 4 2 4 8...

correct output
7789595210075

user output
7798834965014

Test 40

Group: 3

Verdict:

input
200000
1 2 1 1 1 1 2 1 2 2 1 2 2 2 2 ...

correct output
62777824801872

user output
62684289181766

Test 41

Group: 3

Verdict:

input
200000
9473 42975 69773 60909 9354 20...

correct output
76814

user output
(empty)

Test 42

Group: 3

Verdict:

input
200000
31087 18493 14158 65333 95850 ...

correct output
180614

user output
(empty)

Test 43

Group: 3

Verdict:

input
200000
66563 17340 2293 5101 35636 96...

correct output
56642

user output
(empty)

Test 44

Group: 3

Verdict:

input
200000
4005 35201 22254 56956 49098 7...

correct output
287201

user output
(empty)

Test 45

Group: 3

Verdict:

input
200000
99266 91407 53419 70750 93505 ...

correct output
54045

user output
(empty)

Test 46

Group: 3

Verdict:

input
199999
23098 95019 27998 22880 40713 ...

correct output
184595

user output
(empty)