[BZOJ3375]geng4512膜你题1:隔膜

【问题描述】 steam夏季大促销来啦，azui大爷最近在steam上买了1mol的游戏。一天他突然发现了一个搬砖的游戏：有N种砖头，每种砖头有mi个，每一个的价值为di。每一个单位时间你必须搬一块砖，到无砖可搬为止。有一个得分系数F，初始时为1。搬一块砖的得分为当时的得分系数F*di。有T个时间分割点。每过一个时间分割点，F会自己加一。例如在时间pi的得分为i*di，而在时间pi+1的得分为(i+1)*di。 azui大爷觉得这个游戏too simple，不想去玩，于是让你去帮他上分，希望你能告诉他每局游戏的最大的分。你一定知道这么简单的题目怎么做，快帮帮azui大爷吧。   【输入格式】 第一行一个数N。 接下来的N行，每行两个数，表示mi和di。 之后的一行一个数T。 接下来的一行T个数，pi。 【样例输入1】 2 3 8 5 10 1 20 【样例输出1】 74 【样例输入2】 1 1 1000 1 1   【样例输出2】 1000   【数据范围】 对于30%的数据， 1<=N<=10 对于100%的数据， 1<=N<=100 1<=mi<=109 0<=di<=1000 1<=t<=100

1<=p2<p3<…<pt<=10^12

#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int N=110; LL n, T, F=1; struct node{ LL m, d; }Z[N]; LL p[N], sum, t; void Getin( LL &shu ) { char c; LL f=1; shu=0; for( c=getchar(); c<'0' || c>'9'; c=getchar() ) if( c=='-' ) f=-1; for( ; c>='0' && c<='9'; c=getchar() ) shu=shu*10+c-'0'; shu*=f; } bool cmp( node a, node b ) { return a.d<b.d; } int main() { Getin(n); for( LL i=1; i<=n; i++ ) Getin(Z[i].m), Getin(Z[i].d ); Getin(T); for( LL i=1; i<=T; i++ ) Getin(p[i] ); sort( Z+1, Z+n+1, cmp ); for( LL i=1; i<=n; i++ ) { while( p[F] && Z[i].m+t>p[F] ) { sum+=(p[F]-t)*Z[i].d*F; Z[i].m-=(p[F]-t); t=p[F++]; } sum+=Z[i].m*Z[i].d*F; t+=Z[i].m; } printf( "%lld\n", sum ); return 0; }