DuongNhi99

YENOM

Mar 10th, 2022
674
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. long long T;
  6. vector <int> e;
  7.  
  8. int main()
  9. {
  10.    //freopen("YENOM.inp","r",stdin);
  11.    //freopen("YENOM.out","w",stdout);
  12.    //ios_base::sync_with_stdio(0);
  13.    //cin.tie(0); cout.tie(0);
  14.  
  15.    cin >> n >> T;
  16.    
  17.     while (n--){
  18.         int a; cin >> a;
  19.        e.push_back(a);
  20.     }
  21.    
  22.     n = e.back();
  23.     vector <long long> d(n, T+1);
  24.     vector <int> mark(n);
  25.    
  26.     d[0] = 0;
  27.     for (int i = 1; i < n; ++i)
  28.     {//Dijkstra
  29.        int x = -1;
  30.        for (int j = 0; j < n; ++j)
  31.             if (!mark[j])
  32.                 if (x == -1 || d[j] < d[x])
  33.                     x = j;
  34.        
  35.        if (d[x] > T) break;
  36.        
  37.         mark[x] = 1;
  38.        
  39.        for (int i : e) {
  40.             int y = (x + i) % n;
  41.            d[y] = min(d[y], d[x] + i);
  42.        }
  43.     }
  44.    
  45.     long long ans = 0;
  46.     for (int i = 0; i < n; ++i)
  47.         if (d[i] <= T)
  48.             ans += (T - d[i]) / n + 1;
  49.    
  50.     cout << ans;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment