oj.uz

Submission #619722

# Submission time Handle Problem Language Result Execution time Memory
619722 2022-08-02T15:10:39 Z KLPP Carnival Tickets (IOI20_tickets) C++14
100 / 100
 1120 ms 767392 KB 
#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)

queue<lld> q[1000000];
priority_queue<pair<lld,int> >pq;
pair<int,int> tot[1000000];
int F[1000000];
int L[1000000];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer;
	
	lld ans=0;
	rep(i,0,n){
		F[i]=0;
		L[i]=m-1;
		tot[i]={0,i};
		rep(j,0,k){
			ans-=x[i][j];
		}
		for(int j=k-1;j>-1;j--){
			q[i].push(x[i][j+(m-k)]+x[i][j]);
		}
		q[i].push(-1);
	}
	rep(i,0,n){
		pq.push({q[i].front(),i});
	}
	rep(i,0,(n*k)/2){
		ans+=pq.top().first;
		int idx=pq.top().second;pq.pop();
		q[idx].pop();
		pq.push({q[idx].front(),idx});
		tot[idx].first++;
	}
	
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) {
			row[j]=-1;
		}
		answer.push_back(row);
	}
	rep(round,0,k){
		sort(tot,tot+n);
		rep(i,0,n){
			if(i<n/2){
				answer[tot[i].second][F[tot[i].second]]=round;
				F[tot[i].second]++;
			}else{
				answer[tot[i].second][L[tot[i].second]]=round;
				L[tot[i].second]--;
				tot[i].first--;
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 673384 KB Output is correct
2 Correct 423 ms 673396 KB Output is correct
3 Correct 435 ms 673496 KB Output is correct
4 Correct 397 ms 673428 KB Output is correct
5 Correct 455 ms 673520 KB Output is correct
6 Correct 398 ms 673964 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 673444 KB Output is correct
2 Correct 424 ms 673440 KB Output is correct
3 Correct 403 ms 673472 KB Output is correct
4 Correct 404 ms 673712 KB Output is correct
5 Correct 519 ms 676356 KB Output is correct
6 Correct 988 ms 746312 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 673472 KB Output is correct
2 Correct 389 ms 673496 KB Output is correct
3 Correct 403 ms 673420 KB Output is correct
4 Correct 401 ms 673580 KB Output is correct
5 Correct 477 ms 676000 KB Output is correct
6 Correct 885 ms 738344 KB Output is correct
7 Correct 905 ms 741596 KB Output is correct
8 Correct 443 ms 673876 KB Output is correct
9 Correct 385 ms 673424 KB Output is correct
10 Correct 405 ms 673492 KB Output is correct
11 Correct 376 ms 673404 KB Output is correct
12 Correct 437 ms 674132 KB Output is correct
13 Correct 459 ms 675564 KB Output is correct
14 Correct 450 ms 675680 KB Output is correct
15 Correct 921 ms 744524 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 673396 KB Output is correct
2 Correct 383 ms 673536 KB Output is correct
3 Correct 393 ms 673492 KB Output is correct
4 Correct 459 ms 673648 KB Output is correct
5 Correct 465 ms 677140 KB Output is correct
6 Correct 443 ms 674064 KB Output is correct
7 Correct 394 ms 674236 KB Output is correct
8 Correct 1078 ms 766672 KB Output is correct
9 Correct 1081 ms 753580 KB Output is correct
10 Correct 1080 ms 761008 KB Output is correct
11 Correct 1120 ms 767392 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 673492 KB Output is correct
2 Correct 390 ms 673656 KB Output is correct
3 Correct 387 ms 673660 KB Output is correct
4 Correct 389 ms 673712 KB Output is correct
5 Correct 401 ms 673588 KB Output is correct
6 Correct 379 ms 673612 KB Output is correct
7 Correct 390 ms 673520 KB Output is correct
8 Correct 381 ms 673620 KB Output is correct
9 Correct 405 ms 673628 KB Output is correct
10 Correct 423 ms 673664 KB Output is correct
11 Correct 452 ms 673680 KB Output is correct
12 Correct 460 ms 673636 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 673492 KB Output is correct
2 Correct 390 ms 673656 KB Output is correct
3 Correct 387 ms 673660 KB Output is correct
4 Correct 389 ms 673712 KB Output is correct
5 Correct 401 ms 673588 KB Output is correct
6 Correct 379 ms 673612 KB Output is correct
7 Correct 390 ms 673520 KB Output is correct
8 Correct 381 ms 673620 KB Output is correct
9 Correct 405 ms 673628 KB Output is correct
10 Correct 423 ms 673664 KB Output is correct
11 Correct 452 ms 673680 KB Output is correct
12 Correct 460 ms 673636 KB Output is correct
13 Correct 442 ms 676380 KB Output is correct
14 Correct 425 ms 676448 KB Output is correct
15 Correct 455 ms 676716 KB Output is correct
16 Correct 479 ms 677076 KB Output is correct
17 Correct 384 ms 673456 KB Output is correct
18 Correct 388 ms 673648 KB Output is correct
19 Correct 410 ms 673536 KB Output is correct
20 Correct 454 ms 676348 KB Output is correct
21 Correct 506 ms 676792 KB Output is correct
22 Correct 469 ms 676524 KB Output is correct
23 Correct 476 ms 677148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 673384 KB Output is correct
2 Correct 423 ms 673396 KB Output is correct
3 Correct 435 ms 673496 KB Output is correct
4 Correct 397 ms 673428 KB Output is correct
5 Correct 455 ms 673520 KB Output is correct
6 Correct 398 ms 673964 KB Output is correct
7 Correct 411 ms 673444 KB Output is correct
8 Correct 424 ms 673440 KB Output is correct
9 Correct 403 ms 673472 KB Output is correct
10 Correct 404 ms 673712 KB Output is correct
11 Correct 519 ms 676356 KB Output is correct
12 Correct 988 ms 746312 KB Output is correct
13 Correct 386 ms 673472 KB Output is correct
14 Correct 389 ms 673496 KB Output is correct
15 Correct 403 ms 673420 KB Output is correct
16 Correct 401 ms 673580 KB Output is correct
17 Correct 477 ms 676000 KB Output is correct
18 Correct 885 ms 738344 KB Output is correct
19 Correct 905 ms 741596 KB Output is correct
20 Correct 443 ms 673876 KB Output is correct
21 Correct 385 ms 673424 KB Output is correct
22 Correct 405 ms 673492 KB Output is correct
23 Correct 376 ms 673404 KB Output is correct
24 Correct 437 ms 674132 KB Output is correct
25 Correct 459 ms 675564 KB Output is correct
26 Correct 450 ms 675680 KB Output is correct
27 Correct 921 ms 744524 KB Output is correct
28 Correct 428 ms 673396 KB Output is correct
29 Correct 383 ms 673536 KB Output is correct
30 Correct 393 ms 673492 KB Output is correct
31 Correct 459 ms 673648 KB Output is correct
32 Correct 465 ms 677140 KB Output is correct
33 Correct 443 ms 674064 KB Output is correct
34 Correct 394 ms 674236 KB Output is correct
35 Correct 1078 ms 766672 KB Output is correct
36 Correct 1081 ms 753580 KB Output is correct
37 Correct 1080 ms 761008 KB Output is correct
38 Correct 1120 ms 767392 KB Output is correct
39 Correct 393 ms 673492 KB Output is correct
40 Correct 390 ms 673656 KB Output is correct
41 Correct 387 ms 673660 KB Output is correct
42 Correct 389 ms 673712 KB Output is correct
43 Correct 401 ms 673588 KB Output is correct
44 Correct 379 ms 673612 KB Output is correct
45 Correct 390 ms 673520 KB Output is correct
46 Correct 381 ms 673620 KB Output is correct
47 Correct 405 ms 673628 KB Output is correct
48 Correct 423 ms 673664 KB Output is correct
49 Correct 452 ms 673680 KB Output is correct
50 Correct 460 ms 673636 KB Output is correct
51 Correct 442 ms 676380 KB Output is correct
52 Correct 425 ms 676448 KB Output is correct
53 Correct 455 ms 676716 KB Output is correct
54 Correct 479 ms 677076 KB Output is correct
55 Correct 384 ms 673456 KB Output is correct
56 Correct 388 ms 673648 KB Output is correct
57 Correct 410 ms 673536 KB Output is correct
58 Correct 454 ms 676348 KB Output is correct
59 Correct 506 ms 676792 KB Output is correct
60 Correct 469 ms 676524 KB Output is correct
61 Correct 476 ms 677148 KB Output is correct
62 Correct 458 ms 681580 KB Output is correct
63 Correct 435 ms 681688 KB Output is correct
64 Correct 525 ms 683460 KB Output is correct
65 Correct 663 ms 709456 KB Output is correct
66 Correct 704 ms 714248 KB Output is correct
67 Correct 402 ms 674216 KB Output is correct
68 Correct 439 ms 674084 KB Output is correct
69 Correct 858 ms 746356 KB Output is correct
70 Correct 992 ms 755208 KB Output is correct
71 Correct 1072 ms 766744 KB Output is correct
72 Correct 1012 ms 743228 KB Output is correct
73 Correct 1105 ms 762576 KB Output is correct
74 Correct 890 ms 741768 KB Output is correct
75 Correct 966 ms 754244 KB Output is correct