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

300624 | 2020-09-17T10:36:25 Z | b00n0rp | Carnival Tickets (IOI20_tickets) | C++17 | 1136 ms | 101752 KB |

#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define REP(i,n) for(int i = 0; i < n; i ++) #define FOR(i,a,b) for(int i = a; i < b; i ++) #define vi vector<int> #define vvi vector<vi> #define pb push_back #define pii pair<int,int> #define F first #define S second #define all(v) v.begin(),v.end() const int MX = 1505; const ll INF = 1e16; int n,m,k; vvi a; int plow[MX],phigh[MX]; ll val[MX][MX]; ll pref[MX][MX]; ll find_maximum(int k, vvi x) { n = x.size(); m = x[0].size(); ::k = k; vvi ans(n,vi(m,-1)); a.resize(n); vector<pair<int,pii> > everything; ll res = 0; priority_queue<pair<ll,int> > pq; REP(i,n){ pref[i][0] = 0; REP(j,m){ a[i].pb(x[i][j]); pref[i][j+1] = a[i][j]+pref[i][j]; } REP(j,k+1){ val[i][j] = pref[i][m]-pref[i][m-(k-j)]-pref[i][j]; } plow[i] = -1; phigh[i] = m-1; res += val[i][0]; pq.push({val[i][1]-val[i][0],i}); } REP(i,(n*k)/2){ pair<ll,int> bruh = pq.top(); pq.pop(); res += bruh.F; plow[bruh.S]++; if(plow[bruh.S] != k-1){ pq.push({val[bruh.S][plow[bruh.S]+2]-val[bruh.S][plow[bruh.S]+1],bruh.S}); } } REP(turn,k){ vector<pii> v; REP(i,n){ if(plow[i] >= 0){ v.pb({-plow[i],i}); } else v.pb({1,i}); } sort(all(v)); REP(i,n/2){ int ind = v[i].S; ans[ind][plow[ind]] = turn; plow[ind]--; } FOR(i,n/2,n){ int ind = v[i].S; ans[ind][phigh[ind]] = turn; phigh[ind]--; } } allocate_tickets(ans); return res; }

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

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

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

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

4 | Correct | 2 ms | 1024 KB | Output is correct |

5 | Correct | 4 ms | 2816 KB | Output is correct |

6 | Correct | 8 ms | 12928 KB | Output is correct |

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

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

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

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

4 | Correct | 6 ms | 1152 KB | Output is correct |

5 | Correct | 52 ms | 6136 KB | Output is correct |

6 | Correct | 794 ms | 87288 KB | Output is correct |

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

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

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

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

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

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

6 | Correct | 798 ms | 97016 KB | Output is correct |

7 | Correct | 783 ms | 100212 KB | Output is correct |

8 | Correct | 6 ms | 1536 KB | Output is correct |

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

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

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

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

13 | Correct | 27 ms | 7672 KB | Output is correct |

14 | Correct | 27 ms | 4616 KB | Output is correct |

15 | Correct | 796 ms | 100808 KB | Output is correct |

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

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

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

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

4 | Correct | 5 ms | 1304 KB | Output is correct |

5 | Correct | 62 ms | 6904 KB | Output is correct |

6 | Correct | 8 ms | 1056 KB | Output is correct |

7 | Correct | 21 ms | 13312 KB | Output is correct |

8 | Correct | 1136 ms | 101728 KB | Output is correct |

9 | Correct | 1026 ms | 98100 KB | Output is correct |

10 | Correct | 1008 ms | 94968 KB | Output is correct |

11 | Correct | 1116 ms | 101752 KB | Output is correct |

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

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

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

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

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

5 | Correct | 4 ms | 1280 KB | Output is correct |

6 | Correct | 4 ms | 1280 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

5 | Correct | 4 ms | 1280 KB | Output is correct |

6 | Correct | 4 ms | 1280 KB | Output is correct |

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

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

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

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

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

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

13 | Correct | 34 ms | 6176 KB | Output is correct |

14 | Correct | 36 ms | 6212 KB | Output is correct |

15 | Correct | 38 ms | 6520 KB | Output is correct |

16 | Correct | 44 ms | 6880 KB | Output is correct |

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

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

19 | Correct | 4 ms | 2944 KB | Output is correct |

20 | Correct | 34 ms | 6596 KB | Output is correct |

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

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

23 | Correct | 43 ms | 6656 KB | Output is correct |

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

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

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

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

4 | Correct | 2 ms | 1024 KB | Output is correct |

5 | Correct | 4 ms | 2816 KB | Output is correct |

6 | Correct | 8 ms | 12928 KB | Output is correct |

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

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

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

10 | Correct | 6 ms | 1152 KB | Output is correct |

11 | Correct | 52 ms | 6136 KB | Output is correct |

12 | Correct | 794 ms | 87288 KB | Output is correct |

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

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

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

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

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

18 | Correct | 798 ms | 97016 KB | Output is correct |

19 | Correct | 783 ms | 100212 KB | Output is correct |

20 | Correct | 6 ms | 1536 KB | Output is correct |

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

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

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

24 | Correct | 9 ms | 2432 KB | Output is correct |

25 | Correct | 27 ms | 7672 KB | Output is correct |

26 | Correct | 27 ms | 4616 KB | Output is correct |

27 | Correct | 796 ms | 100808 KB | Output is correct |

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

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

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

31 | Correct | 5 ms | 1304 KB | Output is correct |

32 | Correct | 62 ms | 6904 KB | Output is correct |

33 | Correct | 8 ms | 1056 KB | Output is correct |

34 | Correct | 21 ms | 13312 KB | Output is correct |

35 | Correct | 1136 ms | 101728 KB | Output is correct |

36 | Correct | 1026 ms | 98100 KB | Output is correct |

37 | Correct | 1008 ms | 94968 KB | Output is correct |

38 | Correct | 1116 ms | 101752 KB | Output is correct |

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

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

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

42 | Correct | 4 ms | 1280 KB | Output is correct |

43 | Correct | 4 ms | 1280 KB | Output is correct |

44 | Correct | 4 ms | 1280 KB | Output is correct |

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

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

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

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

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

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

51 | Correct | 34 ms | 6176 KB | Output is correct |

52 | Correct | 36 ms | 6212 KB | Output is correct |

53 | Correct | 38 ms | 6520 KB | Output is correct |

54 | Correct | 44 ms | 6880 KB | Output is correct |

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

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

57 | Correct | 4 ms | 2944 KB | Output is correct |

58 | Correct | 34 ms | 6596 KB | Output is correct |

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

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

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

62 | Correct | 90 ms | 13148 KB | Output is correct |

63 | Correct | 92 ms | 13176 KB | Output is correct |

64 | Correct | 120 ms | 15224 KB | Output is correct |

65 | Correct | 403 ms | 47320 KB | Output is correct |

66 | Correct | 483 ms | 51704 KB | Output is correct |

67 | Correct | 16 ms | 13312 KB | Output is correct |

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

69 | Correct | 830 ms | 87324 KB | Output is correct |

70 | Correct | 955 ms | 97060 KB | Output is correct |

71 | Correct | 1088 ms | 101744 KB | Output is correct |

72 | Correct | 918 ms | 99720 KB | Output is correct |

73 | Correct | 1110 ms | 98028 KB | Output is correct |

74 | Correct | 819 ms | 95952 KB | Output is correct |

75 | Correct | 977 ms | 94396 KB | Output is correct |