제출 #817561

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

tickets

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (long long i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
typedef long long ll;
#include "tickets.h"

long long find_maximum(int32_t k, vector<vector<int32_t>> _arr) {
	int n = _arr.size();
	int m = _arr[0].size();
	vector<vector<ll>> arr(n,vector<ll>(m));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			arr[i][j]=_arr[i][j];
		}
	}
	int hed = k*((n+1)/2);
	vector<vector<ll>> dp(n,vector<ll>(hed+1,-1));
	vector<vector<ll>> pref = arr;
	vector<vector<ll>> suff = arr;
	for (int i = 0; i < n; i++){
		for (int j = 1; j < m; j++){
			pref[i][j]+=pref[i][j-1];
		}
		for (int j = m-2; j >= 0; j--){
			suff[i][j]+=suff[i][j+1];
		}
	}
	function<ll(int,int)> bastan = [&](int i, int j){
		if (j==0) return 0ll;
		return pref[i][j-1];
	};
	function<ll(int,int)> sondan = [&](int i, int j){
		if (j==0) return 0ll;
		return suff[i][m-j];
	};
	function<ll(int,int)> f;
	vector<vector<int>> way(n,vector<int>(hed+1,-1));
	f = [&](int node, int flag)->ll{
		if (node==n) {
			if (flag) return -23;
			return 0;
		}
		if (dp[node][flag]!=-1) return dp[node][flag];
		dp[node][flag]=-23;
		for (int i = 0; i <= min(k,flag); i++){
			if (f(node+1,flag-i)==-23) continue;
			ll crr = f(node+1,flag-i)+(sondan(node,k-i)-bastan(node,i));
			if (crr>dp[node][flag]){
				dp[node][flag]=crr;
				way[node][flag]=i;
			}
		}
		return dp[node][flag];
	};
	vector<vector<int>> rval(n,vector<int>(m,-1));
	ll ans = f(0,hed);
	vector<int> crr(n);
	for (int node = 0; node < n; node++){
		crr[node]=way[node][hed];
		hed-=way[node][hed];
	}
	vector<int> kucuk(k,n/2);
	vector<int> buyuk(k,n/2);
	set<int> avak;
	set<int> avab;
	for (int i = 0; i < k; ++i)
	{
		avak.insert(i);
		avab.insert(i);
	}
	for (int i = 0; i < n; i++){
		set<int> kul;
		for (int j = 0; j < crr[i]; j++){
			rval[i][j]=*avak.begin();
			kul.insert(rval[i][j]);
			avak.erase(avak.begin());
		}
		set<int> kul2;
		while (kul.size()){
			kul2.insert(*kul.begin());
			int node = *kul.begin();
			kul.erase(node);
			kucuk[node]--;
			if (kucuk[node]>0) avak.insert(node);
		}
		set<int> kul3;
		for (int j = m-1; j >= m-(k-crr[i]); j--){
			while (kul2.find(*avab.begin())!=kul2.end()){
				kul3.insert(*avab.begin());
				avab.erase(avab.begin());
			}
			rval[i][j]=*avab.begin();
			kul.insert(rval[i][j]);
			avab.erase(avab.begin());
		}
		while (kul.size()){
			int node = *kul.begin();
			kul.erase(node);
			buyuk[node]--;
			if (buyuk[node]>0) avab.insert(node);
		}
		while (kul3.size()){
			avab.insert(*kul3.begin());
			kul3.erase(kul3.begin());
		}
	}
	allocate_tickets(rval);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

• 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