PID695 / 最优选法
题目描述

过几天就是小N的生日了,小A作为小N最好的朋友,想要送给他一些礼物,但是他不知道小N喜欢什么,所以小A给了小N一个长长的列表让小N自己挑礼物。列表上有N个物品。小N对每一个物品有一个喜爱值Ai。小N想从这些物品中选出一些物品使得喜爱值总和最大,但不能一个物品也不选。

现在小N想要知道最大的喜爱值总和是多少,有多少种选法符合。由于方法很多多,所以你只需要求出方案数mod 1000000000000000003的结果。

对于20%的数据:N<=20

对于40%的数据:N<=1000

对于100%的数据N<=1000000,|Ai|<=1000000

输入格式

第一行一个整数N。

第二行N个整数Ai,用空格分隔。

输出格式

输出一行两个整数,表示最大的喜爱值,以及方案数mod 1000000000000000003的结果。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论