Submission #595356

#	Time	Username	Problem	Language	Result	Execution time	Memory
595356		Red_Inside	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3 ms	852 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int mni[maxn], mxi[maxn];
ll mx[maxn], mn[maxn];

long long find_maximum(int k, vector <vector <int> > a)
{
	vector <vector <int> > use;
	int n = a.size();
	int m = a[0].size();
	use = a;
	forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
	ll ret = 0;
	vector <int> vec;
	forn(0, i, n-1)
	{
		mni[i] = -1;
		mxi[i] = -1;
		forn(0, j, m-1)
		{
			if(mni[i] == -1 || a[i][mni[i]] > a[i][j]) mni[i] = j;
			if(mxi[i] == -1 || a[i][mxi[i]] < a[i][j]) mxi[i] = j;
		}
		vec.pb(a[i][mxi[i]]);
		vec.pb(a[i][mni[i]]);
		mx[i] = a[i][mxi[i]];
		mn[i] = a[i][mni[i]];
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	set <pii> Mn, Mx;
	ll smx = 0, smn = 0;
	forn(0, i, n-1) 
	{
		Mx.insert({mx[i], i});
		smx += mx[i];
	}
	vector <pii> used;
	for(auto i : vec)
	{
		while(Mx.size() && Mx.begin()->first < i)
		{
			Mn.insert({mn[Mx.begin()->s], Mx.begin()->s});
			smx -= mx[Mx.begin()->s];
			smn += mn[Mx.begin()->s];
			Mx.erase(Mx.begin());
		}
		vector <pii> temp;
		while(Mx.size() && Mx.begin()->f == i)
		{
			temp.pb(*Mx.begin());
			smx -= mx[Mx.begin()->s];
			Mx.erase(Mx.begin());
		}
		if(Mx.size() <= n / 2 && Mn.size() <= n / 2)
		{
			if(ret < i * ((int)Mn.size()) - smn + smx - i * ((int)Mx.size()))
			{
				ret = i * ((int)Mn.size()) - smn + smx - i * ((int)Mx.size());
				used.clear();
				for(auto j : Mx)
				{
					used.pb({j.s, mxi[j.s]});
				}
				for(auto j : Mn)
				{
					used.pb({j.s, mni[j.s]});
				}
				forn(0, j, temp.size())
				{
					if(j < (n + 1) / 2 - Mx.size())
					{
						used.pb({temp[j].s, mxi[temp[j].s]});
					}
					else
					{
						used.pb({temp[j].s, mni[temp[j].s]});
					}
				}
			}
		}
		for(auto j : temp) 
		{
			smx += mx[j.s];
			Mx.insert(j);
		}
	}
	for(auto i : used)
	{
		use[i.f][i.s] = 0;
	}
	allocate_tickets(use);
	return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:84:16: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |   if(Mx.size() <= n / 2 && Mn.size() <= n / 2)
      |      ~~~~~~~~~~^~~~~~~~
tickets.cpp:84:38: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |   if(Mx.size() <= n / 2 && Mn.size() <= n / 2)
      |                            ~~~~~~~~~~^~~~~~~~
tickets.cpp:12:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define forn(i, j, n) for(int j = i; j <= n; ++j)
......
   98 |     forn(0, j, temp.size())
      |             ~~~~~~~~~~~~~~              
tickets.cpp:98:5: note: in expansion of macro 'forn'
   98 |     forn(0, j, temp.size())
      |     ^~~~
tickets.cpp:100:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |      if(j < (n + 1) / 2 - Mx.size())
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 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