Submission #527880

---

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;}
/*}}}*/

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

static i64 DP[301][301];

static i64 solve() {
	int nk = K.size(), na = A.size();
	for(auto i = nk - 1; i >= 0; i--) {
		for(auto j = na - 1; j >= 0; j--) {
			DP[i][j] = max(max(DP[i + 1][j], DP[i][j + 1]), -K[i].first + (i64)A[j].first * min(K[i].second, A[j].second) + DP[i + 1][j + 1]);
		}
	}
	return DP[0][0];
}

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:53:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:57: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