比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 观光公交 最终得分 100
用户昵称 Kulliu 运行时间 0.023 s
代码语言 C++ 内存使用 0.49 MiB
提交时间 2016-10-18 21:05:46
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. using namespace std;
  7. const int maxn = 1000+5;
  8. const int maxm = 10000+5;
  9. const int maxk = 1000000+5;
  10. int a[maxm],b[maxm],c[maxm],t[maxm];
  11. int r[maxn],get[maxn],off[maxn],in[maxn],leave[maxn],d[maxn],s[maxn];
  12. long long ans;
  13. int n,m,k;
  14. int main()
  15. {
  16. freopen("bus.in","r",stdin);
  17. freopen("bus.out","w",stdout);
  18. scanf("%d%d%d",&n,&m,&k);
  19. for (int i = 1; i < n; ++i) scanf("%d",&d[i]);
  20. for (int i = 0 ; i < m;++i)
  21. {
  22. scanf("%d%d%d", &t[i], &a[i], &b[i]);
  23. off[b[i]]++; in[a[i]]++;
  24. leave[a[i]] = max(leave[a[i]], t[i]);
  25. }
  26. for (int i = 2; i <= n;++i)
  27. {
  28. get[i] = max(get[i-1], leave[i-1])+d[i-1];
  29. }
  30. int p = 1;
  31. for (int i = 1; i <= n; ++i)
  32. {
  33. while (p < n && leave[p]<get[p] || p <= i) p++;
  34. r[i] = p;
  35. s[i] = s[i-1] + off[i];
  36. }
  37. while (k){
  38. int maxp = 0,station;
  39. for (int i = 1; i < n;++i)
  40. if (s[r[i]]-s[i]> maxp && d[i]>0) {
  41. maxp = s[r[i]] - s[i];
  42. station = i;
  43. }
  44. if (maxp == 0) break;
  45. int maxt = 0x7fffffff;
  46. for (int j = station + 1; j < n && leave[j] < get[j];++j)
  47. maxt = min(maxt, get[j]-leave[j]);
  48. int maxDecK = min(d[station], min(maxt, k));
  49. k -= maxDecK;
  50. d[station] -= maxDecK;
  51. for (int j = station+1; j <= r[station]; ++j)
  52. get[j] =max(get[j-1],leave[j-1])+d[j-1];
  53. for (int j = p = station ; j < r[station]; ++j)
  54. {
  55. while (p < n && leave[p]<get[p] || p <= j) p++;
  56. if (p>=r[j]) break;
  57. r[j] = p;
  58. }
  59. }
  60. int ans = 0;
  61. for (int i = 0; i < m ; ++i){
  62. ans +=(long long)(get[b[i]]-t[i]);
  63. }
  64. cout << ans << endl;
  65. return 0;
  66. }