oj.uz

Submission #415003

# Submission time Handle Problem Language Result Execution time Memory
415003 2021-05-31T12:07:04 Z MKopchev Carnival Tickets (IOI20_tickets) C++14
100 / 100
 1035 ms 80872 KB 
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

//void allocate_tickets( std::vector<std::vector<int>> _d);

const int nmax=1500+42;

struct info
{
    int i,j;

    int diff;
};
vector<info> help;

bool cmp(info a,info b)
{
    return a.diff<b.diff;
}

int LHS[nmax];

std::vector<std::vector<int>> positions;

struct line
{
    int i,prefix,suffix;
};
vector<line> given;

bool cmp_2(line a,line b)
{
    return a.prefix<b.prefix;
}

int days;

int my_n,my_m;

void my_fill()
{
    sort(given.begin(),given.end(),cmp_2);

    for(int d=0;d<days;d++)
    {
        sort(given.begin(),given.end(),cmp_2);

        for(int j=my_n/2;j<my_n;j++)
        {
            given[j].prefix--;
            positions[given[j].i][given[j].prefix]=d;
        }

        for(int j=0;j<my_n/2;j++)
        {
            positions[given[j].i][my_m-given[j].suffix]=d;
            given[j].suffix--;
        }
    }
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
    days=k;
	int n = x.size();
	int m = x[0].size();

    my_n=n;
    my_m=m;


	long long outp=0;

	for (int i = 0; i < n; i++) {
		std::vector<int> row(m,-1);

		positions.push_back(row);

		for(int j=m-k;j<m;j++)
        {
            outp+=x[i][j];

            //cout<<i<<" "<<j<<" -> "<<x[i][j]<<" loss: "<<-x[i][j]-x[i][j-(m-k)]<<endl;

            info cur;
            cur.i=i;
            cur.j=j-(m-k);
            cur.diff=x[i][j]+x[i][j-(m-k)];

            help.push_back(cur);
        }
	}

	sort(help.begin(),help.end(),cmp);

	for(int i=0;i<n/2*k;i++)
	{
	    outp-=help[i].diff;

	    LHS[help[i].i]++;
	}

    for(int i=0;i<n;i++)
    {
        line me;

        me.i=i;

        me.prefix=LHS[i];
        me.suffix=days-LHS[i];

        given.push_back(me);
    }

    my_fill();

	allocate_tickets(positions);
	return outp;
}

/*
static int n;
static int m;
static int k;
static std::vector<std::vector<int>> d;
static std::vector<std::vector<int>> x;
static int called = 0;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        exit(0);
    }
}


void allocate_tickets( std::vector<std::vector<int>> _d) {
    check(!called, "allocate_tickets called more than once");
    d = _d;
    check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
    for (int i = 0; i < n; i++) {
        check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
    }
    called = 1;
}

int main() {
    assert(scanf("%d %d %d", &n, &m, &k) == 3);
    x.resize(n);
    for (int i = 0; i < n; i++) {
        x[i].resize(m);
        for (int j=0; j < m; j++) {
            assert(scanf("%d", &x[i][j]) == 1);
        }
    }
    fclose(stdin);

    long long answer = find_maximum(k, x);
    check(called, "failure to call allocate_tickets");
    printf("%lld\n", answer);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j) printf(" ");
            printf("%d", d[i][j]);
        }
        printf("\n");
    }
    fclose(stdout);
    return 0;
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 25 ms 2500 KB Output is correct
6 Correct 609 ms 51588 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 25 ms 3084 KB Output is correct
6 Correct 634 ms 65888 KB Output is correct
7 Correct 687 ms 70572 KB Output is correct
8 Correct 4 ms 688 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 960 KB Output is correct
13 Correct 22 ms 2560 KB Output is correct
14 Correct 22 ms 2672 KB Output is correct
15 Correct 688 ms 74572 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 38 ms 3488 KB Output is correct
6 Correct 7 ms 824 KB Output is correct
7 Correct 9 ms 1016 KB Output is correct
8 Correct 1035 ms 80680 KB Output is correct
9 Correct 977 ms 75328 KB Output is correct
10 Correct 945 ms 75384 KB Output is correct
11 Correct 1012 ms 80740 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 25 ms 2340 KB Output is correct
14 Correct 25 ms 2392 KB Output is correct
15 Correct 32 ms 2860 KB Output is correct
16 Correct 38 ms 3420 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 2 ms 448 KB Output is correct
20 Correct 28 ms 2924 KB Output is correct
21 Correct 35 ms 2916 KB Output is correct
22 Correct 31 ms 3292 KB Output is correct
23 Correct 36 ms 3272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 25 ms 2500 KB Output is correct
12 Correct 609 ms 51588 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 25 ms 3084 KB Output is correct
18 Correct 634 ms 65888 KB Output is correct
19 Correct 687 ms 70572 KB Output is correct
20 Correct 4 ms 688 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 7 ms 960 KB Output is correct
25 Correct 22 ms 2560 KB Output is correct
26 Correct 22 ms 2672 KB Output is correct
27 Correct 688 ms 74572 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 3 ms 460 KB Output is correct
32 Correct 38 ms 3488 KB Output is correct
33 Correct 7 ms 824 KB Output is correct
34 Correct 9 ms 1016 KB Output is correct
35 Correct 1035 ms 80680 KB Output is correct
36 Correct 977 ms 75328 KB Output is correct
37 Correct 945 ms 75384 KB Output is correct
38 Correct 1012 ms 80740 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 3 ms 332 KB Output is correct
41 Correct 3 ms 460 KB Output is correct
42 Correct 3 ms 460 KB Output is correct
43 Correct 3 ms 460 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Correct 1 ms 204 KB Output is correct
46 Correct 1 ms 332 KB Output is correct
47 Correct 3 ms 460 KB Output is correct
48 Correct 3 ms 460 KB Output is correct
49 Correct 3 ms 460 KB Output is correct
50 Correct 3 ms 460 KB Output is correct
51 Correct 25 ms 2340 KB Output is correct
52 Correct 25 ms 2392 KB Output is correct
53 Correct 32 ms 2860 KB Output is correct
54 Correct 38 ms 3420 KB Output is correct
55 Correct 1 ms 332 KB Output is correct
56 Correct 3 ms 460 KB Output is correct
57 Correct 2 ms 448 KB Output is correct
58 Correct 28 ms 2924 KB Output is correct
59 Correct 35 ms 2916 KB Output is correct
60 Correct 31 ms 3292 KB Output is correct
61 Correct 36 ms 3272 KB Output is correct
62 Correct 67 ms 6024 KB Output is correct
63 Correct 69 ms 6116 KB Output is correct
64 Correct 108 ms 9104 KB Output is correct
65 Correct 353 ms 29236 KB Output is correct
66 Correct 465 ms 35764 KB Output is correct
67 Correct 8 ms 972 KB Output is correct
68 Correct 7 ms 812 KB Output is correct
69 Correct 601 ms 51532 KB Output is correct
70 Correct 811 ms 65752 KB Output is correct
71 Correct 1012 ms 80872 KB Output is correct
72 Correct 784 ms 76896 KB Output is correct
73 Correct 942 ms 76124 KB Output is correct
74 Correct 660 ms 64728 KB Output is correct
75 Correct 809 ms 64456 KB Output is correct