Submission #1232694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232694		walizamanee	카니발 티켓 (IOI20_tickets)	C++20	100 / 100	603 ms	109808 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
using namespace std;

struct getans{
	long long sum; // ekhane
	int row;
	int col;

	bool operator<( const getans& othe ) const {
		if( sum != othe.sum ) return sum < othe.sum;
		return col < othe.col;
	}
};

int pos[2501] , neg[2501] , taken[2501] , jog , biyog;

long long find_maximum(int k, vector<vector<int>> xx) { // ekhane


	long long uttor = 0; //ekhane
	int n = (int)xx.size();
	int m = (int)xx[0].size();
	vector<vector<long long>> x;
	vector<long long> lmao;
	for( int z = 0; z < n; z++ ) {
		lmao.clear();
		for( int y = 0; y < m; y++ ) {
			lmao.push_back((long long)xx[z][y]);
		}
		x.push_back(lmao);
	}
	vector<vector<int>> ans;
	ans.clear();
	vector<int> shuru(m , -1);
	vector<getans> storeans;
	storeans.clear();
	
	for( int z = 0; z < n; z++ ) {
		neg[z] = k;
		ans.push_back(shuru);
		for( int y = m - 1; y >= m - k; y-- ) {
			getans lol;
			lol.row = z;
			lol.col = y;
			lol.sum = x[z][y] + x[z][k - (m - y)];
			storeans.push_back(lol);
		}
	}
	
	sort(storeans.begin() , storeans.end() );
	for( int z = (int)storeans.size() - 1; z >= (int)storeans.size() - ((n * k) / 2); z-- ) {
		pos[storeans[z].row]++;
		neg[storeans[z].row]--;
	}
	for( int z = 0; z < n; z++ ) {
		cerr << pos[z] << " " << neg[z] << "\n";
	}
	for( int y = 0; y < k; y++ ) {
	   jog = n / 2;
		biyog = n / 2;
		for( int z = 0; z < n; z++ ) {
			taken[z] = 0;
		}
		for( int z = 0; z < n; z++ ) {
			if( pos[z] == 0 ) {
				taken[z] = 1;
				biyog--;
				neg[z]--;
				ans[z][neg[z]] = y;
				uttor -= x[z][neg[z]];

			}
			else if( neg[z] == 0 ) {
				taken[z] = 1;
				jog--;
				ans[z][m - pos[z]] = y;
				uttor += x[z][m - pos[z]];
				pos[z]--;
			}
		}
		for( int z = 0; z < n; z++ ) {
			if( taken[z] == 0 ) {
				if( jog > 0 ) {
					taken[z] = 1;
					jog--;
					ans[z][m - pos[z]] = y;
					uttor += x[z][m - pos[z]];
					pos[z]--;
				}
				else{
					taken[z] = 1;
					biyog--;
					neg[z]--;
					ans[z][neg[z]] = y;
					uttor -= x[z][neg[z]];
				}
			}
 		}
	}
	allocate_tickets(ans);
	return (long long)uttor;
}

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