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

303331 | 2020-09-20T08:09:50 Z | myungwoo | Carnival Tickets (IOI20_tickets) | C++17 | 1153 ms | 76488 KB |

#include <bits/stdc++.h> #include "tickets.h" using namespace std; #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #define mt make_tuple typedef pair<int, int> pii; typedef tuple<int, int, int> tiii; typedef long long lld; lld find_maximum(int K, vector<vector<int>> A) { int N = A.size(); int M = A[0].size(); lld ans = 0; vector<vector<int>> answer(N, vector<int>(M, -1)); vector <tiii> order; for (int i=0;i<N;i++){ for (int k=0;k<K;k++) ans -= A[i][k]; for (int k=1;k<=K;k++) order.push_back(mt(A[i][M-k]+A[i][K-k], i, M-k)); } sort(order.begin(), order.end()); vector <int> cnt(N, 0), lpt(N, 0); for (int i=1;i<=K*N/2;i++){ auto [v, p, q] = order[order.size()-i]; ans += v; cnt[p]++; } for (int k=0;k<K;k++){ vector <pii> arr; for (int i=0;i<N;i++) arr.push_back({-cnt[i], i}); sort(arr.begin(), arr.end()); for (int i=0;i<N/2;i++){ int t = arr[i].second; assert(cnt[t] > 0); answer[t][M-cnt[t]] = k; cnt[t]--; } for (int i=N/2;i<N;i++){ int t = arr[i].second; answer[t][lpt[t]++] = k; } } allocate_tickets(answer); return ans; }

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

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

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

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

4 | Correct | 1 ms | 256 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 | 1 ms | 256 KB | Output is correct |

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

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

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

5 | Correct | 32 ms | 2432 KB | Output is correct |

6 | Correct | 771 ms | 51448 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 | 28 ms | 2680 KB | Output is correct |

6 | Correct | 869 ms | 57904 KB | Output is correct |

7 | Correct | 772 ms | 62256 KB | Output is correct |

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

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

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

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

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

13 | Correct | 26 ms | 2424 KB | Output is correct |

14 | Correct | 26 ms | 2684 KB | Output is correct |

15 | Correct | 825 ms | 65840 KB | Output is correct |

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

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

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

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

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

5 | Correct | 43 ms | 3212 KB | Output is correct |

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

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

8 | Correct | 1108 ms | 76488 KB | Output is correct |

9 | Correct | 1084 ms | 74548 KB | Output is correct |

10 | Correct | 1081 ms | 74572 KB | Output is correct |

11 | Correct | 1153 ms | 76356 KB | Output is correct |

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

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

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

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

4 | Correct | 3 ms | 532 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 | 3 ms | 512 KB | Output is correct |

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

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

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

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

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

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

4 | Correct | 3 ms | 532 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 | 3 ms | 512 KB | Output is correct |

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

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

13 | Correct | 31 ms | 2356 KB | Output is correct |

14 | Correct | 33 ms | 2472 KB | Output is correct |

15 | Correct | 37 ms | 2680 KB | Output is correct |

16 | Correct | 42 ms | 3180 KB | Output is correct |

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

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

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

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

21 | Correct | 38 ms | 2804 KB | Output is correct |

22 | Correct | 39 ms | 3064 KB | Output is correct |

23 | Correct | 42 ms | 3060 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

11 | Correct | 32 ms | 2432 KB | Output is correct |

12 | Correct | 771 ms | 51448 KB | Output is correct |

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

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

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

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

17 | Correct | 28 ms | 2680 KB | Output is correct |

18 | Correct | 869 ms | 57904 KB | Output is correct |

19 | Correct | 772 ms | 62256 KB | Output is correct |

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

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

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

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

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

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

26 | Correct | 26 ms | 2684 KB | Output is correct |

27 | Correct | 825 ms | 65840 KB | Output is correct |

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

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

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

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

32 | Correct | 43 ms | 3212 KB | Output is correct |

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

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

35 | Correct | 1108 ms | 76488 KB | Output is correct |

36 | Correct | 1084 ms | 74548 KB | Output is correct |

37 | Correct | 1081 ms | 74572 KB | Output is correct |

38 | Correct | 1153 ms | 76356 KB | Output is correct |

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

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

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

42 | Correct | 3 ms | 532 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 | 3 ms | 512 KB | Output is correct |

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

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

51 | Correct | 31 ms | 2356 KB | Output is correct |

52 | Correct | 33 ms | 2472 KB | Output is correct |

53 | Correct | 37 ms | 2680 KB | Output is correct |

54 | Correct | 42 ms | 3180 KB | Output is correct |

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

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

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

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

59 | Correct | 38 ms | 2804 KB | Output is correct |

60 | Correct | 39 ms | 3064 KB | Output is correct |

61 | Correct | 42 ms | 3060 KB | Output is correct |

62 | Correct | 85 ms | 6008 KB | Output is correct |

63 | Correct | 87 ms | 6232 KB | Output is correct |

64 | Correct | 118 ms | 8168 KB | Output is correct |

65 | Correct | 411 ms | 25948 KB | Output is correct |

66 | Correct | 479 ms | 31820 KB | Output is correct |

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

68 | Correct | 7 ms | 840 KB | Output is correct |

69 | Correct | 761 ms | 51584 KB | Output is correct |

70 | Correct | 928 ms | 57904 KB | Output is correct |

71 | Correct | 1105 ms | 76336 KB | Output is correct |

72 | Correct | 996 ms | 75340 KB | Output is correct |

73 | Correct | 1087 ms | 66992 KB | Output is correct |

74 | Correct | 812 ms | 57272 KB | Output is correct |

75 | Correct | 940 ms | 56832 KB | Output is correct |