Submission #69485861

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#define int long long
#define pii pair<int,int>
#define F first
#define S second

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 105, inf = 1e18;
int n, m, a[N], g[N], f[N];
pii sg[N];

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	n = read(), m = read();
	for(int i = 0; i < n; i++) a[i] = read();
	for(int i = 0; i < m; i++) sg[i].F = read(), sg[i].S = read();
	for(int i = 1; i <= m; i++) for(int j = 0; j < n; j++) g[i] += (a[j] >= i);
	sort(sg, sg + m, [&](pii a, pii b) { return a.F != b.F ? a.F > b.F : a.S > b.S; });
	for(int i = 1; i <= m; i++) f[i] = -inf;
	
	for(int i = 0; i < m; i++) 
		for(int j = m; j >= 1; j--)
			if(sg[i].F <= g[j])
				if(f[j - 1] != -inf) f[j] = max(f[j], f[j - 1] + sg[i].S);
	
	int ans = 0;
	for(int i = 0; i <= m; i++) ans = max(ans, f[i]);
	printf("%lld\n", ans);
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result