Salvens

A

Aug 7th, 2023
527
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7.  
  8. const long long INF = 1e9 + 7;
  9. const int MAXN = 200 + 10;
  10. const int N = 1e5 + 10;
  11.  
  12. int n, p;
  13. vector<int> a;
  14.  
  15. //pair<int, int> min_sum(int pos) {
  16. //    int l = pos, sum = 0;
  17. //    bool flag = true;
  18. //    for (int r = pos; r < pos || flag; ++r) {
  19. //        flag = false;
  20. //
  21. //    }
  22. //}
  23.  
  24. signed main() {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(nullptr);
  27.     cout.tie(nullptr);
  28.  
  29.     cin >> n >> p;
  30.     a.resize(n);
  31.     int sum = 0;
  32.     vector<int> pref(n + 1, 0);
  33.     for (int i = 0; i < n; ++i) {
  34.         cin >> a[i];
  35.         sum += a[i];
  36.         pref[i + 1] = pref[i] + a[i];
  37.     }
  38.     int ans = n * (p / sum);
  39.     p %= sum;
  40.     if (p == 0) {
  41.         cout << 1 << ' ' << ans << '\n';
  42.         return 0;
  43.     }
  44.  
  45.     int res = INF, start;
  46.     for (int l = 0; l < n; ++l) {
  47.         for (int r = 0; r < n; ++r) {
  48.             int summ = 0, kol;
  49.             if (l <= r) {
  50.                 summ = pref[r + 1] - pref[l];
  51.                 kol = r - l + 1;
  52.             } else {
  53.                 summ = pref[r + 1] + pref[n] - pref[l];
  54.                 kol = (r + 1) + (n - l);
  55.             }
  56.             if (summ >= p && res > kol) {
  57.                 res = kol;
  58.                 start = l;
  59.             }
  60.         }
  61.     }
  62.     cout << start + 1 << ' ' << ans + res << '\n';
  63. }
Advertisement
Add Comment
Please, Sign In to add comment