제출 #1012768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012768		pawned	카니발 티켓 (IOI20_tickets)	C++17	0 / 100	0 ms	432 KiB

tickets

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "tickets.h"

ll find_maximum(int K, vector<vector<int>> a_given) {
	int N = a_given.size();
	int M = a_given[0].size();
	vector<vi> a(N, vi(M, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			a[i][j] = a_given[i][j];
		}
	}
	vi ans(N, -1);
	ll maximum = -1;
	for (int i = 0; i < N; i++) {
		// try with minimum
		vi ans1(N, -1);
		ans1[0] = 0;
		ll total1 = 0;
		for (int j = 1; j < N; j++) {
			if (abs(a[j][0] - a[i][0]) < abs(a[j][M - 1] - a[i][0])) {
				ans1[j] = M - 1;
				total1 += abs(a[j][M - 1] - a[i][0]);
			}
			else {
				ans1[j] = 0;
				total1 += abs(a[j][0] - a[i][0]);
			}
		}
		vi ans2(N, -1);
		ans2[0] = M - 1;
		ll total2 = 0;
		for (int j = 1; j < N; j++) {
			if (abs(a[j][0] - a[i][M - 1]) < abs(a[j][M - 1] - a[i][M - 1])) {
				ans2[j] = M - 1;
				total2 += abs(a[j][M - 1] - a[i][M - 1]);
			}
			else {
				ans2[j] = 0;
				total2 += abs(a[j][0] - a[i][M - 1]);
			}
		}
		if (total1 > maximum) {
			ans = ans1;
			maximum = total1;
		}
		if (total2 > maximum) {
			ans = ans2;
			maximum = total2;
		}
	}
	vector<vector<int>> answer(N, vector<int>(M, -1));
	for (int i = 0; i < N; i++) {
		answer[i][ans[i]] = 0;
	}
	allocate_tickets(answer);
	return maximum;
}

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