# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

300168 | 2020-09-16T22:07:06 Z | model_code | Carnival Tickets (IOI20_tickets) | Java 11 | 991 ms | 121900 KB |

// yanhao-full class tickets { int c,k,s; int count_lower(int[] x, int target) { int low = -1; int high = x.length; while(high-low>1) { int mid = (low+high)/2; if(x[mid] < target) { low = mid; } else { high = mid; } } return high; } int count = 0; int get_median(int[][] arr) { int low = -1; int high = (int)2e9; int target = -1; int bigger = 0; int smaller = 0; while(high-low>1) { smaller = 0; bigger = 0; target = low + (high-low)/2; for(int i=0; i<arr.length; i++) { smaller += count_lower(arr[i], target); bigger += count_lower(arr[i], target+1); } if(smaller > c*k/2) { high = target; } else if(bigger < c*k/2) { low = target; } else { break; } } count = smaller; return target; } long find_maximum(int _k, int[][] d) { k = _k; c = d.length; s = d[0].length; int[][] sums = new int[c][k]; for(int i=0; i<c; i++) { for(int j=0; j<k; j++) { sums[i][j] = d[i][j] + d[i][s-k+j]; } } int median = get_median(sums); long ans = 0; int minus_day = 0; int plus_day = c*k-1; int[][] ret = new int[c][s]; for(int i=0; i<c; i++) { int j=0; for(;j<k && sums[i][j]<median; j++) { ret[i][j] = minus_day % k; minus_day++; ans -= d[i][j]; } for(;j<k && sums[i][j] == median && count < c*k/2; j++) { ret[i][j] = minus_day % k; minus_day++; count++; ans -= d[i][j]; } for(int l=j; l<s-k+j; l++) { ret[i][l] = -1; } for(j=s-k+j; j<s; j++) { ret[i][j] = plus_day % k; plus_day--; ans += d[i][j]; } } grader.allocate_tickets(ret); return ans; } }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 93 ms | 10096 KB | Output is correct |

2 | Correct | 83 ms | 10276 KB | Output is correct |

3 | Correct | 81 ms | 10148 KB | Output is correct |

4 | Correct | 85 ms | 9976 KB | Output is correct |

5 | Correct | 92 ms | 10348 KB | Output is correct |

6 | Correct | 102 ms | 10764 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 86 ms | 10088 KB | Output is correct |

2 | Correct | 85 ms | 10164 KB | Output is correct |

3 | Correct | 84 ms | 10020 KB | Output is correct |

4 | Correct | 129 ms | 11468 KB | Output is correct |

5 | Correct | 259 ms | 18644 KB | Output is correct |

6 | Correct | 889 ms | 111648 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 80 ms | 10260 KB | Output is correct |

2 | Correct | 92 ms | 10264 KB | Output is correct |

3 | Correct | 84 ms | 10304 KB | Output is correct |

4 | Correct | 133 ms | 11620 KB | Output is correct |

5 | Correct | 231 ms | 19944 KB | Output is correct |

6 | Correct | 868 ms | 112300 KB | Output is correct |

7 | Correct | 814 ms | 121348 KB | Output is correct |

8 | Correct | 132 ms | 12388 KB | Output is correct |

9 | Correct | 85 ms | 10260 KB | Output is correct |

10 | Correct | 85 ms | 10104 KB | Output is correct |

11 | Correct | 91 ms | 10164 KB | Output is correct |

12 | Correct | 193 ms | 15288 KB | Output is correct |

13 | Correct | 262 ms | 19896 KB | Output is correct |

14 | Correct | 269 ms | 20168 KB | Output is correct |

15 | Correct | 753 ms | 89332 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 82 ms | 10100 KB | Output is correct |

2 | Correct | 83 ms | 10236 KB | Output is correct |

3 | Correct | 81 ms | 10144 KB | Output is correct |

4 | Correct | 114 ms | 11820 KB | Output is correct |

5 | Correct | 274 ms | 20384 KB | Output is correct |

6 | Correct | 129 ms | 11712 KB | Output is correct |

7 | Correct | 174 ms | 13448 KB | Output is correct |

8 | Correct | 933 ms | 121900 KB | Output is correct |

9 | Correct | 991 ms | 119368 KB | Output is correct |

10 | Correct | 872 ms | 120500 KB | Output is correct |

11 | Correct | 893 ms | 89812 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 79 ms | 10248 KB | Output is correct |

2 | Correct | 113 ms | 11124 KB | Output is correct |

3 | Correct | 120 ms | 11244 KB | Output is correct |

4 | Correct | 116 ms | 11128 KB | Output is correct |

5 | Correct | 109 ms | 11412 KB | Output is correct |

6 | Correct | 112 ms | 11492 KB | Output is correct |

7 | Correct | 97 ms | 10548 KB | Output is correct |

8 | Correct | 85 ms | 10420 KB | Output is correct |

9 | Correct | 118 ms | 11064 KB | Output is correct |

10 | Correct | 125 ms | 12536 KB | Output is correct |

11 | Correct | 118 ms | 11272 KB | Output is correct |

12 | Correct | 115 ms | 11344 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 79 ms | 10248 KB | Output is correct |

2 | Correct | 113 ms | 11124 KB | Output is correct |

3 | Correct | 120 ms | 11244 KB | Output is correct |

4 | Correct | 116 ms | 11128 KB | Output is correct |

5 | Correct | 109 ms | 11412 KB | Output is correct |

6 | Correct | 112 ms | 11492 KB | Output is correct |

7 | Correct | 97 ms | 10548 KB | Output is correct |

8 | Correct | 85 ms | 10420 KB | Output is correct |

9 | Correct | 118 ms | 11064 KB | Output is correct |

10 | Correct | 125 ms | 12536 KB | Output is correct |

11 | Correct | 118 ms | 11272 KB | Output is correct |

12 | Correct | 115 ms | 11344 KB | Output is correct |

13 | Correct | 222 ms | 18736 KB | Output is correct |

14 | Correct | 212 ms | 20092 KB | Output is correct |

15 | Correct | 210 ms | 20188 KB | Output is correct |

16 | Correct | 284 ms | 19508 KB | Output is correct |

17 | Correct | 108 ms | 11040 KB | Output is correct |

18 | Correct | 132 ms | 12288 KB | Output is correct |

19 | Correct | 115 ms | 11284 KB | Output is correct |

20 | Correct | 283 ms | 20736 KB | Output is correct |

21 | Correct | 263 ms | 19116 KB | Output is correct |

22 | Correct | 308 ms | 21348 KB | Output is correct |

23 | Correct | 318 ms | 21620 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 93 ms | 10096 KB | Output is correct |

2 | Correct | 83 ms | 10276 KB | Output is correct |

3 | Correct | 81 ms | 10148 KB | Output is correct |

4 | Correct | 85 ms | 9976 KB | Output is correct |

5 | Correct | 92 ms | 10348 KB | Output is correct |

6 | Correct | 102 ms | 10764 KB | Output is correct |

7 | Correct | 86 ms | 10088 KB | Output is correct |

8 | Correct | 85 ms | 10164 KB | Output is correct |

9 | Correct | 84 ms | 10020 KB | Output is correct |

10 | Correct | 129 ms | 11468 KB | Output is correct |

11 | Correct | 259 ms | 18644 KB | Output is correct |

12 | Correct | 889 ms | 111648 KB | Output is correct |

13 | Correct | 80 ms | 10260 KB | Output is correct |

14 | Correct | 92 ms | 10264 KB | Output is correct |

15 | Correct | 84 ms | 10304 KB | Output is correct |

16 | Correct | 133 ms | 11620 KB | Output is correct |

17 | Correct | 231 ms | 19944 KB | Output is correct |

18 | Correct | 868 ms | 112300 KB | Output is correct |

19 | Correct | 814 ms | 121348 KB | Output is correct |

20 | Correct | 132 ms | 12388 KB | Output is correct |

21 | Correct | 85 ms | 10260 KB | Output is correct |

22 | Correct | 85 ms | 10104 KB | Output is correct |

23 | Correct | 91 ms | 10164 KB | Output is correct |

24 | Correct | 193 ms | 15288 KB | Output is correct |

25 | Correct | 262 ms | 19896 KB | Output is correct |

26 | Correct | 269 ms | 20168 KB | Output is correct |

27 | Correct | 753 ms | 89332 KB | Output is correct |

28 | Correct | 82 ms | 10100 KB | Output is correct |

29 | Correct | 83 ms | 10236 KB | Output is correct |

30 | Correct | 81 ms | 10144 KB | Output is correct |

31 | Correct | 114 ms | 11820 KB | Output is correct |

32 | Correct | 274 ms | 20384 KB | Output is correct |

33 | Correct | 129 ms | 11712 KB | Output is correct |

34 | Correct | 174 ms | 13448 KB | Output is correct |

35 | Correct | 933 ms | 121900 KB | Output is correct |

36 | Correct | 991 ms | 119368 KB | Output is correct |

37 | Correct | 872 ms | 120500 KB | Output is correct |

38 | Correct | 893 ms | 89812 KB | Output is correct |

39 | Correct | 79 ms | 10248 KB | Output is correct |

40 | Correct | 113 ms | 11124 KB | Output is correct |

41 | Correct | 120 ms | 11244 KB | Output is correct |

42 | Correct | 116 ms | 11128 KB | Output is correct |

43 | Correct | 109 ms | 11412 KB | Output is correct |

44 | Correct | 112 ms | 11492 KB | Output is correct |

45 | Correct | 97 ms | 10548 KB | Output is correct |

46 | Correct | 85 ms | 10420 KB | Output is correct |

47 | Correct | 118 ms | 11064 KB | Output is correct |

48 | Correct | 125 ms | 12536 KB | Output is correct |

49 | Correct | 118 ms | 11272 KB | Output is correct |

50 | Correct | 115 ms | 11344 KB | Output is correct |

51 | Correct | 222 ms | 18736 KB | Output is correct |

52 | Correct | 212 ms | 20092 KB | Output is correct |

53 | Correct | 210 ms | 20188 KB | Output is correct |

54 | Correct | 284 ms | 19508 KB | Output is correct |

55 | Correct | 108 ms | 11040 KB | Output is correct |

56 | Correct | 132 ms | 12288 KB | Output is correct |

57 | Correct | 115 ms | 11284 KB | Output is correct |

58 | Correct | 283 ms | 20736 KB | Output is correct |

59 | Correct | 263 ms | 19116 KB | Output is correct |

60 | Correct | 308 ms | 21348 KB | Output is correct |

61 | Correct | 318 ms | 21620 KB | Output is correct |

62 | Correct | 369 ms | 30440 KB | Output is correct |

63 | Correct | 336 ms | 26328 KB | Output is correct |

64 | Correct | 428 ms | 32800 KB | Output is correct |

65 | Correct | 660 ms | 60196 KB | Output is correct |

66 | Correct | 638 ms | 60896 KB | Output is correct |

67 | Correct | 135 ms | 11916 KB | Output is correct |

68 | Correct | 123 ms | 11692 KB | Output is correct |

69 | Correct | 884 ms | 110508 KB | Output is correct |

70 | Correct | 865 ms | 111912 KB | Output is correct |

71 | Correct | 989 ms | 90560 KB | Output is correct |

72 | Correct | 844 ms | 121636 KB | Output is correct |

73 | Correct | 926 ms | 121612 KB | Output is correct |

74 | Correct | 773 ms | 111336 KB | Output is correct |

75 | Correct | 920 ms | 112876 KB | Output is correct |