Submission #527901

---

Source Code Expand

/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/

typedef i64 ll;
static const int AMAX = 300;
static const int BMAX = 300;
class Hun {
	private:
		int A,B,M; i64 cost[AMAX][BMAX];
		int fa[AMAX],fb[BMAX];
		i64 ca[AMAX],cb[BMAX];
		bool d[AMAX], e[BMAX];
		bool dfs(int a) {
			d[a]=1;
			for(int b=0;b<B;b++) {
				if(ca[a]+cb[b]!=cost[a][b])continue;
				if(fb[b]>=0&&(d[fb[b]]||!dfs(fb[b])))continue;
				fa[a]=b;fb[b]=a;return 1;
			}
			return 0;
		}
	public:
		inline i64 *operator[](int a) {return cost[a];}
		inline void init(int a,int b) {assert(0<=a&&a<=b);A=a;B=b;}
		// Hopcroft-Karp algorithm, O(m*sqrt(n))
		int BM() {
			int a; bool flag;
			do {
				flag=false;memset(d,0x00,A);
				for(a=0;a<A;a++)if(fa[a]<0&&!d[a]&&dfs(a)){M++;flag=true;}
			} while(flag);
			return M;
		}
		// Hungarian algorithm, O(a^2*b)
		ll solve() {
			int i,j; i64 k; ll ret=0;
			memset(fa,0xFF,A*sizeof(int));memset(ca,0x00,A*sizeof(i64));
			memset(fb,0xFF,B*sizeof(int));memset(cb,0x00,B*sizeof(i64));
			for(i=0;i<A;i++)for(j=0;j<B;j++)ca[i]=max(ca[i],cost[i][j]);
			for(M=0;BM()!=A;) {
				for(j=0;j<B;j++)e[j]=(fb[j]>=0&&d[fb[j]]);
				for(i=0;i<A;i++)d[i]=!d[i];
				k=LLONG_MAX;
				for(i=0;i<A;i++)if(!d[i])
					for(j=0;j<B;j++)if(!e[j])
						k=min(k,ca[i]+cb[j]-cost[i][j]);
				for(i=0;i<A;i++)if(!d[i])ca[i]-=k;
				for(j=0;j<B;j++)if( e[j])cb[j]+=k;
			}
			for(i=0;i<A;i++)ret+=ca[i];
			for(j=0;j<B;j++)ret+=cb[j];
			return ret;
		}
};

static vector<pair<int, int>> K, A;

static i64 solve() {
	static Hun hun;
	int nk = K.size(), na = A.size();
	if(nk == 0 || na == 0) return 0;
	int AS, BS;
	if(nk <= na) {
		AS = nk;
		BS = na;
		for(int i = 0; i < nk; i++)
			for(int j = 0; j < na; j++)
				hun[i][j] = max((i64)0, -K[i].first + (i64)A[j].first * min(K[i].second, A[j].second));
	} else {
		AS = na;
		BS = nk;
		for(int j = 0; j < na; j++)
			for(int i = 0; i < nk; i++)
				hun[j][i] = max((i64)0, -K[i].first + (i64)A[j].first * min(K[i].second, A[j].second));
	}
	hun.init(AS, BS);
	//for(int i = 0; i < AS; i++) {
	//	for(int j = 0; j < BS; j++) printf("%5lld ", hun[i][j]);
	//	puts("$");
	//}
	auto s = hun.solve();
	//printf("s = %lld\n", s);
	return s;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<pair<int, int>> r(n);
	auto h = 0LL; auto m = 0;
	for(auto i = 0; i < n; i++) {
		scanf("%d%d", &r[i].first, &r[i].second);
		if(r[i].first == 2) {
			h += r[i].second;
			m++;
		}
	}
	for(auto i = 0; i < n; ) {
		if(r[i].first == 2) {
			m--;
			i++;
			continue;
		}
		vector<int> ks, as;
		do {
			if(r[i].first == 0) {
				ks.push_back(r[i].second);
			} else {
				as.push_back(r[i].second);
			}
		} while(++i < n && r[i].first != 2);
		sort(begin(ks), end(ks));
		sort(begin(as), end(as), greater<int>());
		for(auto k : ks) K.emplace_back(k, m);
		for(auto a : as) A.emplace_back(a, m);
	}
	printf("%lld\n", h - solve());
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:121:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:125:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r[i].first, &r[i].second);
                                           ^

Judge Result