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

302196 | 2020-09-18T14:09:32 Z | kriii | Carnival Tickets (IOI20_tickets) | C++17 | 1220 ms | 62360 KB |

#include "tickets.h" #include <algorithm> #include <vector> using namespace std; long long find_maximum(int k, vector<vector<int> > x) { int n = x.size(); int m = x[0].size(); long long ans = 0; vector<pair<int, int> > sum; for (int i = 0; i < n; i++){ for (int j = 0; j < k; j++){ ans -= x[i][j]; sum.push_back({ x[i][j] + x[i][m - k + j], i }); } } sort(sum.rbegin(), sum.rend()); int neg[1500] = { 0, }, pos[1500] = { 0, }; int pop = n * k / 2; for (int i = 0; i < n; i++) neg[i] = k; for (int i = 0; i < pop; i++){ ans += sum[i].first; neg[sum[i].second]--; pos[sum[i].second]++; } vector<vector<int> > alloc(n, vector<int>(m, -1)); int negp[1500] = { 0, }, posp[1500] = { 0, }; for (int i = 0; i < n; i++) posp[i] = m - 1; for (int r = 0; r < k; r++){ vector<pair<int, int> > use; for (int i = 0; i < n; i++) use.push_back({ pos[i] - neg[i], i }); sort(use.begin(), use.end()); for (int i = 0; i < n / 2; i++){ int x = use[i].second; alloc[x][negp[x]++] = r; neg[x]--; } for (int i = n / 2; i < n; i++){ int x = use[i].second; alloc[x][posp[x]--] = r; pos[x]--; } } allocate_tickets(alloc); return ans; }

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

1 | Correct | 1 ms | 360 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 256 KB | Output is correct |

4 | Correct | 0 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 2 ms | 768 KB | Output is correct |

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

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 0 ms | 256 KB | Output is correct |

3 | Correct | 0 ms | 256 KB | Output is correct |

4 | Correct | 3 ms | 512 KB | Output is correct |

5 | Correct | 30 ms | 2424 KB | Output is correct |

6 | Correct | 752 ms | 51488 KB | Output is correct |

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

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 0 ms | 384 KB | Output is correct |

3 | Correct | 0 ms | 256 KB | Output is correct |

4 | Correct | 3 ms | 512 KB | Output is correct |

5 | Correct | 30 ms | 2480 KB | Output is correct |

6 | Correct | 736 ms | 53508 KB | Output is correct |

7 | Correct | 774 ms | 56432 KB | Output is correct |

8 | Correct | 4 ms | 676 KB | Output is correct |

9 | Correct | 0 ms | 288 KB | Output is correct |

10 | Correct | 1 ms | 384 KB | Output is correct |

11 | Correct | 0 ms | 256 KB | Output is correct |

12 | Correct | 8 ms | 904 KB | Output is correct |

13 | Correct | 25 ms | 2300 KB | Output is correct |

14 | Correct | 25 ms | 2300 KB | Output is correct |

15 | Correct | 782 ms | 58812 KB | Output is correct |

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

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 0 ms | 384 KB | Output is correct |

3 | Correct | 0 ms | 256 KB | Output is correct |

4 | Correct | 3 ms | 512 KB | Output is correct |

5 | Correct | 46 ms | 2808 KB | Output is correct |

6 | Correct | 7 ms | 768 KB | Output is correct |

7 | Correct | 9 ms | 1024 KB | Output is correct |

8 | Correct | 1121 ms | 62360 KB | Output is correct |

9 | Correct | 1118 ms | 58264 KB | Output is correct |

10 | Correct | 1089 ms | 58124 KB | Output is correct |

11 | Correct | 1171 ms | 62216 KB | Output is correct |

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

1 | Correct | 1 ms | 256 KB | Output is correct |

2 | Correct | 3 ms | 640 KB | Output is correct |

3 | Correct | 3 ms | 512 KB | Output is correct |

4 | Correct | 3 ms | 512 KB | Output is correct |

5 | Correct | 3 ms | 512 KB | Output is correct |

6 | Correct | 3 ms | 512 KB | Output is correct |

7 | Correct | 1 ms | 384 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 3 ms | 512 KB | Output is correct |

10 | Correct | 4 ms | 640 KB | Output is correct |

11 | Correct | 3 ms | 420 KB | Output is correct |

12 | Correct | 9 ms | 576 KB | Output is correct |

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

1 | Correct | 1 ms | 256 KB | Output is correct |

2 | Correct | 3 ms | 640 KB | Output is correct |

3 | Correct | 3 ms | 512 KB | Output is correct |

4 | Correct | 3 ms | 512 KB | Output is correct |

5 | Correct | 3 ms | 512 KB | Output is correct |

6 | Correct | 3 ms | 512 KB | Output is correct |

7 | Correct | 1 ms | 384 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 3 ms | 512 KB | Output is correct |

10 | Correct | 4 ms | 640 KB | Output is correct |

11 | Correct | 3 ms | 420 KB | Output is correct |

12 | Correct | 9 ms | 576 KB | Output is correct |

13 | Correct | 35 ms | 2364 KB | Output is correct |

14 | Correct | 32 ms | 2424 KB | Output is correct |

15 | Correct | 44 ms | 2676 KB | Output is correct |

16 | Correct | 43 ms | 2808 KB | Output is correct |

17 | Correct | 1 ms | 384 KB | Output is correct |

18 | Correct | 4 ms | 512 KB | Output is correct |

19 | Correct | 1 ms | 384 KB | Output is correct |

20 | Correct | 35 ms | 2552 KB | Output is correct |

21 | Correct | 40 ms | 2544 KB | Output is correct |

22 | Correct | 42 ms | 2676 KB | Output is correct |

23 | Correct | 51 ms | 2668 KB | Output is correct |

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

1 | Correct | 1 ms | 360 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 256 KB | Output is correct |

4 | Correct | 0 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 2 ms | 768 KB | Output is correct |

7 | Correct | 0 ms | 256 KB | Output is correct |

8 | Correct | 0 ms | 256 KB | Output is correct |

9 | Correct | 0 ms | 256 KB | Output is correct |

10 | Correct | 3 ms | 512 KB | Output is correct |

11 | Correct | 30 ms | 2424 KB | Output is correct |

12 | Correct | 752 ms | 51488 KB | Output is correct |

13 | Correct | 0 ms | 256 KB | Output is correct |

14 | Correct | 0 ms | 384 KB | Output is correct |

15 | Correct | 0 ms | 256 KB | Output is correct |

16 | Correct | 3 ms | 512 KB | Output is correct |

17 | Correct | 30 ms | 2480 KB | Output is correct |

18 | Correct | 736 ms | 53508 KB | Output is correct |

19 | Correct | 774 ms | 56432 KB | Output is correct |

20 | Correct | 4 ms | 676 KB | Output is correct |

21 | Correct | 0 ms | 288 KB | Output is correct |

22 | Correct | 1 ms | 384 KB | Output is correct |

23 | Correct | 0 ms | 256 KB | Output is correct |

24 | Correct | 8 ms | 904 KB | Output is correct |

25 | Correct | 25 ms | 2300 KB | Output is correct |

26 | Correct | 25 ms | 2300 KB | Output is correct |

27 | Correct | 782 ms | 58812 KB | Output is correct |

28 | Correct | 0 ms | 256 KB | Output is correct |

29 | Correct | 0 ms | 384 KB | Output is correct |

30 | Correct | 0 ms | 256 KB | Output is correct |

31 | Correct | 3 ms | 512 KB | Output is correct |

32 | Correct | 46 ms | 2808 KB | Output is correct |

33 | Correct | 7 ms | 768 KB | Output is correct |

34 | Correct | 9 ms | 1024 KB | Output is correct |

35 | Correct | 1121 ms | 62360 KB | Output is correct |

36 | Correct | 1118 ms | 58264 KB | Output is correct |

37 | Correct | 1089 ms | 58124 KB | Output is correct |

38 | Correct | 1171 ms | 62216 KB | Output is correct |

39 | Correct | 1 ms | 256 KB | Output is correct |

40 | Correct | 3 ms | 640 KB | Output is correct |

41 | Correct | 3 ms | 512 KB | Output is correct |

42 | Correct | 3 ms | 512 KB | Output is correct |

43 | Correct | 3 ms | 512 KB | Output is correct |

44 | Correct | 3 ms | 512 KB | Output is correct |

45 | Correct | 1 ms | 384 KB | Output is correct |

46 | Correct | 1 ms | 384 KB | Output is correct |

47 | Correct | 3 ms | 512 KB | Output is correct |

48 | Correct | 4 ms | 640 KB | Output is correct |

49 | Correct | 3 ms | 420 KB | Output is correct |

50 | Correct | 9 ms | 576 KB | Output is correct |

51 | Correct | 35 ms | 2364 KB | Output is correct |

52 | Correct | 32 ms | 2424 KB | Output is correct |

53 | Correct | 44 ms | 2676 KB | Output is correct |

54 | Correct | 43 ms | 2808 KB | Output is correct |

55 | Correct | 1 ms | 384 KB | Output is correct |

56 | Correct | 4 ms | 512 KB | Output is correct |

57 | Correct | 1 ms | 384 KB | Output is correct |

58 | Correct | 35 ms | 2552 KB | Output is correct |

59 | Correct | 40 ms | 2544 KB | Output is correct |

60 | Correct | 42 ms | 2676 KB | Output is correct |

61 | Correct | 51 ms | 2668 KB | Output is correct |

62 | Correct | 83 ms | 6116 KB | Output is correct |

63 | Correct | 85 ms | 6136 KB | Output is correct |

64 | Correct | 121 ms | 7268 KB | Output is correct |

65 | Correct | 407 ms | 24052 KB | Output is correct |

66 | Correct | 495 ms | 27868 KB | Output is correct |

67 | Correct | 9 ms | 1024 KB | Output is correct |

68 | Correct | 9 ms | 768 KB | Output is correct |

69 | Correct | 771 ms | 51368 KB | Output is correct |

70 | Correct | 975 ms | 53468 KB | Output is correct |

71 | Correct | 1220 ms | 62320 KB | Output is correct |

72 | Correct | 1016 ms | 59636 KB | Output is correct |

73 | Correct | 1113 ms | 59048 KB | Output is correct |

74 | Correct | 841 ms | 52568 KB | Output is correct |

75 | Correct | 1033 ms | 52208 KB | Output is correct |