RMQ的基础题目,简单题。
/* 4122 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxm = 1e5+;
const int maxn = ;
int T[maxn], N[maxn];
int cost[maxm], val[maxm];
int dp[maxm][];
int days[] = {
, , , , , ,
, , , , ,
};
int days_[] = {
, , , , , ,
, , , , ,
};
char month[][] = {
"Jan", "Feb", "Mar", "Apr",
"May", "Jun", "Jul", "Aug",
"Sep", "Oct", "Nov", "Dec"
};
char s[];
int yy, mm, dd, hh;
int n, m; int getMon(char *s) {
rep(i, , )
if (strcmp(month[i], s) == )
return i; return -;
} bool isLeapYear(int y) {
return y%== || (y%!= && y%==);
} int getTime() {
mm = getMon(s);
int ret = ; rep(i, , yy) {
if (isLeapYear(i))
ret += ;
else
ret += ;
}
if (isLeapYear(yy)) {
rep(i, , mm)
ret += days_[i];
} else {
rep(i, , mm)
ret += days[i];
}
ret += dd-;
ret *= ;
ret += hh + ; return ret;
} void init_RMQ() {
int i, j; for (i=; i<m; ++i)
dp[i][] = i; for (j=; (<<j)<=m; ++j) {
for (i=; i+(<<j)-<m; ++i) {
if (val[dp[i][j-]] < val[dp[i+(<<(j-))][j-]])
dp[i][j] = dp[i][j-];
else
dp[i][j] = dp[i+(<<(j-))][j-];
}
}
} int RMQ(int l, int r) {
if (l < )
l = ; int k = ; while (<<(k+) <= r-l+)
++k; if (val[dp[l][k]] < val[dp[r-(<<k)+][k]])
return dp[l][k];
else
return dp[r-(<<k)+][k];
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int st, cst;
int idx, tmp;
__int64 ans; while (scanf("%d%d", &n, &m)!=EOF && (n||m)) {
rep(i, , n) {
scanf("%s%d%d%d%d", s, &dd, &yy, &hh, &N[i]);
T[i] = getTime();
}
scanf("%d%d", &st, &cst);
rep(i, , m) {
scanf("%d", &cost[i]);
val[i] = cost[i] + cst * (m - i);
} ans = ;
init_RMQ();
rep(i, , n) {
idx = RMQ(T[i]-st, T[i]-);
tmp = cost[idx] + (T[i]--idx) * cst;
ans += 1LL * tmp * N[i];
} printf("%I64d\n", ans);
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}