Main » 2013 October 11 » [NOIP2011模拟赛_No.12]偷菜
4:47 PM [NOIP2011模拟赛_No.12]偷菜 |
又偷懒了。。。用了STL中的std::lower_bound速度好慢。。。#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define N 3010 typedef long long LL; using namespace std; int n,m,T,k; LL f[N]; int Time[N]; struct node{int t;LL p2,p1;}; node s[N]; int find(int x) { int *p=lower_bound(Time+1,Time+1+k,x); return p-Time; } int main() { scanf("%d%d%d%d",&n,&m,&T,&k); int i,j; FOR(i,1,m) scanf("%d%d%d",&s[i].p1,&s[i].t,&s[i].p2); FOR(i,1,k) scanf("%d",&Time[i]); sort(Time+1,Time+1+k); memset(f,0,sizeof(f)); f[1]=0; FOR(i,1,k) { FOR(j,1,m) { int tt=s[j].t; int p=find(Time[i]+tt); f[p]=max(f[p],f[i]+s[j].p2-s[j].p1); } } LL ans=0; FOR(i,1,k) if (f[i]>ans) ans=f[i]; printf("%lld\n",ans*n); } |
|
|
| Total comments: 0 | |