fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define nl '\n'
  6. #define fromst(i, start, j) for (int i = start; i <= j; i++)
  7. #define from(i, j) for (int i = 0; i < j; i++)
  8.  
  9. const int maxn = 1e4 + 1;
  10.  
  11. int n, m;
  12. vector<int> a(1e4);
  13.  
  14. struct light {
  15.     int p, r;
  16. };
  17.  
  18. vector<light> b(11);
  19.  
  20. void solve() {
  21.     vector<int> dp(1000001, 1e17), idx(1000001);
  22.     set<int> pos;
  23.     dp[1] = dp[0] = 0;
  24.  
  25.     fromst(i, 1, n) {
  26.         if (dp[i - 1] == 1e17) continue;
  27.  
  28.         from(j, m) {
  29.             auto nd = upper_bound(a.begin() + i, a.begin() + n + 1, a[i] + b[j].r) - a.begin() - 1;
  30.             if (nd < i) continue;
  31.  
  32.             auto st = upper_bound(a.begin() + nd, a.begin() + n + 1, a[nd] + b[j].r) - a.begin() - 1;
  33.  
  34.             if (dp[st] > dp[i - 1] + b[j].p) {
  35.                 dp[st] = dp[i - 1] + b[j].p;
  36.                 pos.insert(st);
  37.                 idx[st] = j + 1;
  38.             }
  39.         }
  40.     }
  41.  
  42.     cout << dp[n] << ' ' << pos.size() << nl;
  43. }
  44.  
  45. signed main() {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.     cout.tie(NULL);
  49.  
  50.     cin >> n >> m;
  51.     from(i, m) cin >> b[i].p >> b[i].r;
  52.     fromst(i, 1, n) cin >> a[i];
  53.  
  54.     sort(a.begin(), a.begin() + n + 1);
  55.     solve();
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 18852KB
comments (?)
stdin 
Standard input is empty
stdout 
0 0
https://ideone.com/KdR5m3
language:
C++ (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!