| 记录编号 |
422295 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
越低越买 |
最终得分 |
100 |
| 用户昵称 |
 rewine |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.026 s |
| 提交时间 |
2017-07-09 15:29:38 |
内存使用 |
8.56 MiB |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
void read(int &x) {
char c; bool flag = 0;
while((c=getchar())<'0'||c>'9') flag |= (c=='-');
x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
if(flag) x = -x;
}
#define ll "lld"
typedef long long LL;
const int BASE = 100000000,MAXLEN = 103; //高精度 压8位
char s[MAXLEN<<3];
struct BIGNUM {
int len; LL bt[MAXLEN];
void upzero(){while(!bt[len] && len!=1)--len;} //去前导0
void upbit() { //进位
LL x(0);
for (int i = 1; i <= len; i++) {
if(bt[i] < 0) {bt[i] += BASE; --bt[i+1];}
bt[i] += x; x = bt[i]/BASE; bt[i] %= BASE;
}
while(x) bt[++len] = x % BASE,x /= BASE;
}
LL to_long(){return len<3?bt[2]*BASE+bt[1]:-1;}
BIGNUM(LL num):len(1) {memset(bt,0,sizeof bt);bt[1]=num;upbit();} //构造函数
BIGNUM():len(1){memset(bt,0,sizeof bt);}
BIGNUM operator = (LL x) {len = 1;memset(bt,0,sizeof bt);bt[1]=x;upbit();}
//////////////////////////////////////////////////////////
void init() {
scanf("%s",s); len = 0;
char c[10];int tmp = strlen(s);
for (; tmp >= 8; tmp -= 8) {
strncpy(c,s+tmp-8,8);
sscanf(c,"%"ll,&bt[++len]);
}
if (tmp) {
memset(c,0,sizeof c);
strncpy(c,s,tmp);
sscanf(c,"%"ll,&bt[++len]);
}
upzero();
}
void out() {
printf("%"ll,bt[len]);
for (int i = len-1; i; i--)
printf("%08"ll,bt[i]);
printf("\n");
}
///////////////////////////////////////////////////// // 高精 ――低精
BIGNUM add(LL x) {bt[1] += x;upbit();return *this;} // this += x
BIGNUM div(LL x) { // this /= x
for (int i = len; i; i--) {
bt[i-1] += (bt[i]%x)*BASE;
bt[i] /= x;
}
upzero();return *this;
}
BIGNUM mul(LL x) {
for (int i = 1; i <= len; i++) bt[i] *= x;
upbit();
}
LL _mod(LL x) {
LL tmp = 0;
for (int i = len; i; i--) tmp = (tmp*BASE+bt[i])%x;
return tmp;
}
BIGNUM _mul(LL x) {BIGNUM ans(*this); return ans.mul(x);}
BIGNUM _add(LL x) {BIGNUM ans(*this); return ans.add(x);}
BIGNUM _div(LL x) {BIGNUM ans(*this); return ans.div(x);}
//////////////////////////////////////////////////// //各种cmp
bool operator < (const BIGNUM &lhs) const {
if (len != lhs.len) return len < lhs.len;
for (int i = len; i; i--)
if(bt[i] != lhs.bt[i]) return bt[i] < lhs.bt[i];
return false;
}
bool operator == (const BIGNUM &lhs) const {return (!(*this < lhs))&&(!(lhs < *this));}
bool operator > (const BIGNUM &lhs) const {return lhs < *this;}
bool operator >= (const BIGNUM &lhs) const {return !(*this < lhs);}
bool operator <= (const BIGNUM &lhs) const {return !(*this > lhs);}
//////////////////////////////////////////////////////////
BIGNUM operator * (const BIGNUM &b) const {
BIGNUM ans(0ll);
ans.len = len+b.len-1;
for (int i = 1; i <= len; i++)
for (int j = 1; j <= b.len; j++) {
ans.bt[i+j-1] += bt[i]*b.bt[j];
ans.bt[i+j] += ans.bt[i+j-1]/BASE;
ans.bt[i+j-1] %= BASE;
}
if(ans.bt[ans.len+1]) ++ans.len;
return ans;
}
BIGNUM operator - (const BIGNUM &b) const {
BIGNUM ans(*this); ans.len = len;
for (int i = 1; i <= b.len; i++)
ans.bt[i] = bt[i] - b.bt[i];
ans.upbit(); ans.upzero();
return ans;
}
BIGNUM operator + (const BIGNUM &b) const {
BIGNUM ans(0ll); ans.len = max(len,b.len);
for (int i = 1; i <= ans.len; i++)
ans.bt[i] = bt[i]+b.bt[i];
ans.upbit();
return ans;
}
BIGNUM operator / (const BIGNUM &b) const {
for (BIGNUM l(0ll),r = *this; ;) {
if(r <= l._add(1ll)) return r*b <= *this ? r : l;
BIGNUM mid = (l+r).div(2ll);
mid*b <= *this ? l=mid : r=mid;
}
}
BIGNUM operator % (const BIGNUM &b) const {return *this - (*this/b)*(b);}
////////////////////////////////////////////////////////
BIGNUM pow(LL b) {
BIGNUM ans(1);
for (BIGNUM p = *this; b; b >>= 1,p = p*p)
if (b&1) ans = ans*p;
return ans;
}
BIGNUM pow_mod(LL b,LL m) {
BIGNUM ans(1);
for (BIGNUM p = *this; b; b >>= 1,p = (p*p)._mod(m))
if (b&1) ans = (ans*p)._mod(m);
return ans;
}
BIGNUM sqrt () {
for (BIGNUM l(0ll),r = *this; ;) {
if(r <= l._add(1ll)) return r*r <= *this ? r : l;
BIGNUM mid((l+r).div(2ll));
mid*mid <= *this ? l=mid : r=mid;
}
}
BIGNUM nsqrt (int n) {
BIGNUM l(0ll),r(1ll);
while(r.pow(n) < *this) {
l = r;
r.mul(2);
}
for ( ; ;) {
if(r <= l._add(1ll)) return r.pow(n) <= *this ? r : l;
BIGNUM mid((l+r).div(2ll));
mid.pow(n) <= *this ? l=mid : r=mid;
}
}
};
typedef BIGNUM SL;
#define N 5100
int f[N],g[N],mx = 0,n,a[N],vv[N];
map<int,SL> ss[N]; map<int,bool> v;
SL b[N],sum[N],ans;
bool cmp(const int &x,const int &y) {
return b[x] < b[y];
}
int main() {
freopen("buylow.in","r",stdin);freopen("buylow.out","w",stdout);
read(n);
memset(g,127/3,sizeof g); g[0] = -1;
for (int i = 1; i <= n; i++) b[n-i+1].init();
for (int i = 1; i <= n; i++) vv[i] = i;
sort(vv+1,vv+n+1,cmp);
for (int i = 2; i <= n; i++)
if(b[vv[i]]==b[vv[i-1]]) a[vv[i]] = a[vv[i-1]];
else a[vv[i]] = i;
// for (int i = 1; i <= n; i++) cout << a[i] << " ";
for (int i = 1; i <= n; i++) {
f[i] = (lower_bound(g+0,g+i+1,a[i])-g);//-1+1
if(a[i] < g[f[i]]) g[f[i]] = a[i];
if(f[i] > mx) mx = f[i];
}
ss[0][-1] = 1;
for (int i = 1; i <= n; i++) {
for (map<int,SL>::iterator it = ss[f[i]-1].begin(); it != ss[f[i]-1].end(); it++)
if(it->first < a[i]) sum[i] = sum[i]+it->second;
ss[f[i]][a[i]] = sum[i];
}
for (int i = n; i; i--) if(!v[a[i]] && f[i]==mx) ans = ans + sum[i],v[a[i]] = 1;
printf("%d ",mx); ans.out();
return 0;
}