小码农

趣味编程-面向每个人的创意编程

机会成本

avatar 2022-09-28 19:28 339次浏览 0 条评论 C++

题目描述

每个人的一生只能做好一件事。

给定一个整数 n,表示人生中遇到的 n 件事。若认真对待某件事,可以获得的分数分别为 a1,a2,…,an,若不认真对待这些事,则获得的分数分别为 b1,b2,…,bn

请选择应该认真对待哪一件事,才能让分数的总和达到最大。

输入格式

第一行:单个整数表示 n
第二行到第 n+1 行:每行两个整数表示 aibi

输出格式

单个整数:表示最大的分数之和

数据范围

  • 对于 30% 的数据,1≤n≤5,000
  • 对于 60% 的数据,1≤n≤20,000
  • 对于 100% 的数据,1≤n≤500,000
  • 0≤bi≤ai≤4000

样例数

输入:
3
1 1
2 0
3 2
输出:
5
说明:

选择做好第二件事

发表评论