QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#809421	#3157. IOI Manju	rlc202204	100 ✓	7ms	3940kb	C++17	813b	2024-12-11 14:58:13	2024-12-11 14:58:28

Judging History

你现在查看的是最新测评结果

[2024-12-11 14:58:28]
评测

测评结果：100
用时：7ms
内存：3940kb

查看

[2024-12-11 14:58:13]
提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505;
const int M = 1e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m;
int p[M] = {0};
int c[N] = {0}, e[N] = {0};
int f[M * 2] = {0};

int main() {
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= m; i++)
		scanf("%d", &p[i]);
	sort(p + 1, p + m + 1, [](int x, int y){return x > y;});
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &c[i], &e[i]);
		for (int j = 20000; j >= c[i]; j--)
			f[j] = min(f[j], f[j - c[i]] + e[i]);
	}
	for (int j = 20000; j >= 0; j--)
		f[j] = min(f[j], f[j + 1]);
	int ans = 0, sum = 0;
	for (int j = 1; j <= m; j++) {
		sum += p[j];
		ans = max(ans, sum - f[j]);
	}
	cout << ans << endl;
	return 0;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 25

Accepted

Test #1:

score: 25

Accepted

time: 1ms

memory: 3904kb

input:

1 1
9120
6124 9262

output:

result:

ok single line: '0'

Test #2:

score: 25

Accepted

time: 0ms

memory: 3880kb

input:

1 1
7581
9723 5615

output:

result:

ok single line: '1966'

Test #3:

score: 25

Accepted

time: 2ms

memory: 3708kb

input:

output:

50209793

result:

ok single line: '50209793'

Test #4:

score: 25

Accepted

time: 1ms

memory: 3916kb

input:

output:

99999999

result:

ok single line: '99999999'

Test #5:

score: 25

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok single line: '0'

Test #6:

score: 25

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok single line: '25547'

Test #7:

score: 25

Accepted

time: 1ms

memory: 3824kb

input:

output:

result:

ok single line: '495399'

Test #8:

score: 25

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok single line: '262705'

Test #9:

score: 25

Accepted

time: 1ms

memory: 3732kb

input:

output:

49785599

result:

ok single line: '49785599'

Test #10:

score: 25

Accepted

time: 1ms

memory: 3872kb

input:

output:

49879260

result:

ok single line: '49879260'

Subtask #2:

score: 35

Accepted

Test #11:

score: 35

Accepted

time: 7ms

memory: 3780kb

input:

output:

21300729

result:

ok single line: '21300729'

Test #12:

score: 35

Accepted

time: 7ms

memory: 3928kb

input:

output:

49999500

result:

ok single line: '49999500'

Test #13:

score: 35

Accepted

time: 7ms

memory: 3924kb

input:

output:

result:

ok single line: '0'

Test #14:

score: 35

Accepted

time: 3ms

memory: 3872kb

input:

output:

16537203

result:

ok single line: '16537203'

Test #15:

score: 35

Accepted

time: 7ms

memory: 3816kb

input:

output:

16149287

result:

ok single line: '16149287'

Test #16:

score: 35

Accepted

time: 3ms

memory: 3768kb

input:

output:

result:

ok single line: '103089'

Test #17:

score: 35

Accepted

time: 6ms

memory: 3796kb

input:

output:

12014025

result:

ok single line: '12014025'

Test #18:

score: 35

Accepted

time: 7ms

memory: 3860kb

input:

output:

result:

ok single line: '9973685'

Test #19:

score: 35

Accepted

time: 6ms

memory: 3748kb

input:

output:

result:

ok single line: '3110339'

Test #20:

score: 35

Accepted

time: 7ms

memory: 3816kb

input:

output:

15598072

result:

ok single line: '15598072'

Subtask #3:

score: 40

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #21:

score: 40

Accepted

time: 4ms

memory: 3860kb

input:

output:

99999999

result:

ok single line: '99999999'

Test #22:

score: 40

Accepted

time: 5ms

memory: 3932kb

input:

output:

result:

ok single line: '0'

Test #23:

score: 40

Accepted

time: 5ms

memory: 3864kb

input:

output:

99963537

result:

ok single line: '99963537'

Test #24:

score: 40

Accepted

time: 5ms

memory: 3816kb

input:

output:

81597258

result:

ok single line: '81597258'

Test #25:

score: 40

Accepted

time: 2ms

memory: 3924kb

input:

output:

99986898

result:

ok single line: '99986898'

Test #26:

score: 40

Accepted

time: 5ms

memory: 3872kb

input:

output:

14259382

result:

ok single line: '14259382'

Test #27:

score: 40

Accepted

time: 6ms

memory: 3708kb

input:

output:

result:

ok single line: '8220599'

Test #28:

score: 40

Accepted

time: 3ms

memory: 3860kb

input:

output:

37475438

result:

ok single line: '37475438'

Test #29:

score: 40

Accepted

time: 7ms

memory: 3924kb

input:

output:

46830648

result:

ok single line: '46830648'

Test #30:

score: 40

Accepted

time: 7ms

memory: 3940kb

input:

output:

16630076

result:

ok single line: '16630076'

Extra Test:

score: 0

Extra Test Passed