Submission #408683

#	Time	Username	Problem	Language	Result	Execution time	Memory
408683		mat_v	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	673 ms	99548 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pii pair<int,int>
#define xx first
#define yy second
#define pb push_back


using namespace std;
typedef long long ll;

pii mat[1505][1505];
int ans[1505][1505];
int kol[1505];
int ima[1505];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ff(i,0,n - 1){
        ff(j,0,m - 1){
            mat[i + 1][j + 1] = {x[i][j], j+1};
        }
	}
	ff(i,1,n)sort(mat[i] + 1, mat[i] + m + 1);
//	ff(i,1,n){
//        ff(j,1,m){
//            cout << mat[i][j].xx << mat[i][j].yy << " ";
//        }
//        cout << "\n";
//	}
//	cout << "\n";
    ff(i,1,n)ff(j,1,m)ans[i][j] = -1;

    ll suma = 0;
    ff(i,1,n){
        ff(j,1,k)suma -= mat[i][j].xx;
    }

    priority_queue<pii> pq;
    ff(i,1,n){
        pq.push({mat[i][m].xx + mat[i][k].xx, i});
    }
    ff(i,1,(n*k)/2){
        pii sta = pq.top();
        pq.pop();
        kol[sta.yy]++;
        suma += sta.xx;
        if(kol[sta.yy] < k){
            pq.push({mat[sta.yy][k-kol[sta.yy]].xx + mat[sta.yy][m-kol[sta.yy]].xx, sta.yy});
        }
    }
    ff(i,1,n){
        //cout << kol[i] << "\n";
        int dole = k - kol[i];
        ff(j,1,k){
            if(ima[j] < n/2){
                if(kol[i] > 0){
                    ans[i][mat[i][m-kol[i]+1].yy] = j-1;
                    kol[i]--;
                    ima[j]++;
                }
                else{
                    ans[i][mat[i][dole].yy] = j-1;
                    dole--;
                }
            }
            else{
                ans[i][mat[i][dole].yy] = j-1;
                dole--;
            }
        }
    }
    vector<vector<int>>answer;
    ff(i,1,n){
        vector<int> row;
        ff(j,1,m)row.pb(ans[i][j]);
        answer.pb(row);
    }

	allocate_tickets(answer);
	return suma;
}
/*
2 3 2
0 2 5
1 1 3
*/

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:23:2: note: in expansion of macro 'ff'
   23 |  ff(i,0,n - 1){
      |  ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:24:9: note: in expansion of macro 'ff'
   24 |         ff(j,0,m - 1){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:28:2: note: in expansion of macro 'ff'
   28 |  ff(i,1,n)sort(mat[i] + 1, mat[i] + m + 1);
      |  ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:36:5: note: in expansion of macro 'ff'
   36 |     ff(i,1,n)ff(j,1,m)ans[i][j] = -1;
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:36:14: note: in expansion of macro 'ff'
   36 |     ff(i,1,n)ff(j,1,m)ans[i][j] = -1;
      |              ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:39:5: note: in expansion of macro 'ff'
   39 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:40:9: note: in expansion of macro 'ff'
   40 |         ff(j,1,k)suma -= mat[i][j].xx;
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:44:5: note: in expansion of macro 'ff'
   44 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:47:5: note: in expansion of macro 'ff'
   47 |     ff(i,1,(n*k)/2){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:56:5: note: in expansion of macro 'ff'
   56 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:59:9: note: in expansion of macro 'ff'
   59 |         ff(j,1,k){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:78:5: note: in expansion of macro 'ff'
   78 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:80:9: note: in expansion of macro 'ff'
   80 |         ff(j,1,m)row.pb(ans[i][j]);
      |         ^~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10