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

300875 | 2020-09-17T14:43:04 Z | ainta | Carnival Tickets (IOI20_tickets) | C++17 | 1279 ms | 71972 KB |

#include "tickets.h" #include <vector> #include <algorithm> #define pii pair<int,int> using namespace std; int n, m, K, cc, L[1600], R[1600]; int PL[1600], PR[1600]; pii CL[1600]; vector<pii>V; long long find_maximum(int k, std::vector<std::vector<int>> x) { vector<vector<int>>res = x; n = x.size(); m = x[0].size(); K = k; int i, j; for(i=0;i<n;i++)for(j=0;j<m;j++)res[i][j]=-1; for(i=0;i<n;i++){ for(j=0;j<K;j++){ int b = x[i][j]; int e = x[i][m-K+j]; V.push_back({e+b,i}); } } sort(V.begin(),V.end()); for(i=0;i<n*K/2;i++){ L[V[i].second]++; } for(i=0;i<n;i++){ R[i]=K-L[i]; PL[i]=0,PR[i]=m-1; } long long ss=0; for(i=0;i<K;i++){ for(j=0;j<n;j++){ CL[j]={L[j],j}; } sort(CL,CL+n); for(j=0;j<n;j++){ int t = CL[j].second; if(j<n/2){ R[t]--; ss+=x[t][PR[t]]; res[t][PR[t]--] = i; } else{ L[t]--; ss-=x[t][PL[t]]; res[t][PL[t]++] = i; } } } allocate_tickets(res); return ss; }

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

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

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

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

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

6 | Correct | 831 ms | 51496 KB | Output is correct |

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

1 | Correct | 0 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 | 512 KB | Output is correct |

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

6 | Correct | 883 ms | 61232 KB | Output is correct |

7 | Correct | 763 ms | 64584 KB | Output is correct |

8 | Correct | 5 ms | 640 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 | 9 ms | 972 KB | Output is correct |

13 | Correct | 24 ms | 2540 KB | Output is correct |

14 | Correct | 23 ms | 2556 KB | Output is correct |

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

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

5 | Correct | 59 ms | 3180 KB | Output is correct |

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

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

8 | Correct | 1279 ms | 71964 KB | Output is correct |

9 | Correct | 1068 ms | 67096 KB | Output is correct |

10 | Correct | 1120 ms | 67108 KB | Output is correct |

11 | Correct | 1187 ms | 71972 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 | 5 ms | 512 KB | Output is correct |

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

4 | Correct | 4 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 | 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 | 45 ms | 2424 KB | Output is correct |

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

15 | Correct | 36 ms | 2800 KB | Output is correct |

16 | Correct | 43 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 | 36 ms | 2780 KB | Output is correct |

21 | Correct | 39 ms | 2828 KB | Output is correct |

22 | Correct | 37 ms | 3100 KB | Output is correct |

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

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

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

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

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

12 | Correct | 831 ms | 51496 KB | Output is correct |

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

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

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

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

17 | Correct | 27 ms | 2808 KB | Output is correct |

18 | Correct | 883 ms | 61232 KB | Output is correct |

19 | Correct | 763 ms | 64584 KB | Output is correct |

20 | Correct | 5 ms | 640 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 | 9 ms | 972 KB | Output is correct |

25 | Correct | 24 ms | 2540 KB | Output is correct |

26 | Correct | 23 ms | 2556 KB | Output is correct |

27 | Correct | 803 ms | 67672 KB | Output is correct |

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

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

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

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

32 | Correct | 59 ms | 3180 KB | Output is correct |

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

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

35 | Correct | 1279 ms | 71964 KB | Output is correct |

36 | Correct | 1068 ms | 67096 KB | Output is correct |

37 | Correct | 1120 ms | 67108 KB | Output is correct |

38 | Correct | 1187 ms | 71972 KB | Output is correct |

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

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

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

42 | Correct | 4 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 | 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 | 45 ms | 2424 KB | Output is correct |

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

53 | Correct | 36 ms | 2800 KB | Output is correct |

54 | Correct | 43 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 | 36 ms | 2780 KB | Output is correct |

59 | Correct | 39 ms | 2828 KB | Output is correct |

60 | Correct | 37 ms | 3100 KB | Output is correct |

61 | Correct | 43 ms | 3088 KB | Output is correct |

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

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

64 | Correct | 113 ms | 8172 KB | Output is correct |

65 | Correct | 426 ms | 27444 KB | Output is correct |

66 | Correct | 492 ms | 31916 KB | Output is correct |

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

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

69 | Correct | 888 ms | 51516 KB | Output is correct |

70 | Correct | 1059 ms | 61272 KB | Output is correct |

71 | Correct | 1148 ms | 71880 KB | Output is correct |

72 | Correct | 1026 ms | 68900 KB | Output is correct |

73 | Correct | 1145 ms | 68152 KB | Output is correct |

74 | Correct | 978 ms | 60260 KB | Output is correct |

75 | Correct | 984 ms | 59868 KB | Output is correct |