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

301835 | 2020-09-18T08:41:30 Z | majk | Carnival Tickets (IOI20_tickets) | C++17 | 973 ms | 62360 KB |

#include <vector> #include <algorithm> #include "tickets.h" using namespace std; #define x first #define y second typedef std::pair<int,int> pii; typedef long long ll; template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}}; ll find_maximum(int K, vector<vector<int>> A) { int N = A.size(), M = A[0].size(); ll tot = 0; vector<pii> S; for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { tot += A[i][j+M-K]; S.push_back({A[i][j] + A[i][j+M-K], i}); } } sort(S.begin(),S.end()); vector<int> CntLo(N, 0), CntHi(N); for (int i = 0; i < N*K/2; ++i) { tot -= S[i].x; CntLo[S[i].y]++; } for (int i = 0; i < N; ++i) CntHi[i] = K - CntLo[i]; vector2<int> T(N, M, -1); for (int i = 0; i < K; ++i) { int lo = N/2, hi = N/2; for (int j = 0; j < N; ++j) { if (CntLo[j] == 0) hi--; if (CntLo[j] == K-i) lo--; } for (int j = 0; j < N; ++j) { if (CntLo[j] == 0) { T[j][M-CntHi[j]] = i; --CntHi[j]; } else if (CntLo[j] == K-i) { --CntLo[j]; T[j][CntLo[j]] = i; } else if (lo > 0) { --CntLo[j]; --lo; T[j][CntLo[j]] = i; } else { T[j][M-CntHi[j]] = i; --CntHi[j]; --hi; } } } allocate_tickets(T); return tot; }

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

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

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

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

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

6 | Correct | 695 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 | 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 | 24 ms | 2460 KB | Output is correct |

6 | Correct | 616 ms | 53404 KB | Output is correct |

7 | Correct | 614 ms | 56508 KB | Output is correct |

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

9 | Correct | 1 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 | 6 ms | 896 KB | Output is correct |

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

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

15 | Correct | 630 ms | 58684 KB | Output is correct |

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

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

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

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

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

5 | Correct | 48 ms | 2800 KB | Output is correct |

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

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

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

9 | Correct | 884 ms | 58388 KB | Output is correct |

10 | Correct | 882 ms | 58264 KB | Output is correct |

11 | Correct | 939 ms | 62360 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 | 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 | 256 KB | Output is correct |

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

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

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

12 | Correct | 3 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 | 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 | 256 KB | Output is correct |

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

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

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

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

13 | Correct | 36 ms | 2432 KB | Output is correct |

14 | Correct | 29 ms | 2432 KB | Output is correct |

15 | Correct | 35 ms | 2452 KB | Output is correct |

16 | Correct | 52 ms | 2800 KB | Output is correct |

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

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

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

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

21 | Correct | 35 ms | 2564 KB | Output is correct |

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

23 | Correct | 38 ms | 2676 KB | Output is correct |

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

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

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

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

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

12 | Correct | 695 ms | 51448 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 | 24 ms | 2460 KB | Output is correct |

18 | Correct | 616 ms | 53404 KB | Output is correct |

19 | Correct | 614 ms | 56508 KB | Output is correct |

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

21 | Correct | 1 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 | 6 ms | 896 KB | Output is correct |

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

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

27 | Correct | 630 ms | 58684 KB | Output is correct |

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

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

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

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

32 | Correct | 48 ms | 2800 KB | Output is correct |

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

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

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

36 | Correct | 884 ms | 58388 KB | Output is correct |

37 | Correct | 882 ms | 58264 KB | Output is correct |

38 | Correct | 939 ms | 62360 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 | 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 | 256 KB | Output is correct |

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

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

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

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

51 | Correct | 36 ms | 2432 KB | Output is correct |

52 | Correct | 29 ms | 2432 KB | Output is correct |

53 | Correct | 35 ms | 2452 KB | Output is correct |

54 | Correct | 52 ms | 2800 KB | Output is correct |

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

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

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

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

59 | Correct | 35 ms | 2564 KB | Output is correct |

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

61 | Correct | 38 ms | 2676 KB | Output is correct |

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

63 | Correct | 88 ms | 6168 KB | Output is correct |

64 | Correct | 103 ms | 7272 KB | Output is correct |

65 | Correct | 377 ms | 24032 KB | Output is correct |

66 | Correct | 416 ms | 27860 KB | Output is correct |

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

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

69 | Correct | 701 ms | 51468 KB | Output is correct |

70 | Correct | 856 ms | 53436 KB | Output is correct |

71 | Correct | 946 ms | 62348 KB | Output is correct |

72 | Correct | 805 ms | 59544 KB | Output is correct |

73 | Correct | 889 ms | 59080 KB | Output is correct |

74 | Correct | 690 ms | 52668 KB | Output is correct |

75 | Correct | 806 ms | 52296 KB | Output is correct |