Advertisement
karupayun

tap17/c.cpp

Oct 22nd, 2017
235
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None
  1. #include <iostream>
  2. #include <algorithm>
  3. #define dprint(v) cerr << #v"=" << v << endl
  4.  
  5. using namespace std;
  6. #define forn(i,n) for(int i=0;i<int(n);i++)
  7. #define MAXN 100000
  8. int persona[MAXN];
  9. typedef int ll;
  10.  
  11. int n, k, m, v;
  12. ll suma;
  13.  
  14. ll f (int i){
  15.     return persona[(i+1)%n] - persona[i];
  16. }
  17.  
  18. bool solve(){
  19.     m = __gcd(n,k);
  20.     v = n / m;
  21.     ll acumtotal = 0;
  22.     forn (i,m){
  23.         ll acum = 0, mini = 0, actual = 0, pos = i;
  24.         forn (j,v){
  25.             actual += f(pos);
  26.             acum += actual;
  27.             mini = min (actual, mini);
  28.             pos = (pos + k)%n;
  29.         }
  30.         if (actual != 0) return false; // No es cíclico.
  31.         acum -= mini * v;
  32.         acumtotal += acum;
  33.     }
  34.     if (acumtotal*k > suma) return false; // Necesitamos Negativos
  35.     if ((suma) % k != 0) return false; // Necesitamos racionales
  36.     return true;
  37. }
  38.  
  39.  
  40. int main(){
  41.     cin >> n >> k;
  42.     suma = 0;
  43.     forn (i,n) {
  44.         cin >> persona[i];
  45.         suma += persona[i];
  46.     }
  47.     if (solve ()) cout << "S" << endl;
  48.     else cout << "N" << endl;
  49.  
  50.     return 0;  
  51. }
Advertisement
RAW Paste Data Copied
Advertisement