akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 20;
char s[N][N];
int cnt[N][N], h, w, tot = 0;
set<pii> st;
int cal() {
        st.clear();
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                cnt[i][j] = 0;
                if(s[i][j] == '*') {
                    st.insert({i, j});
                }
                else if(s[i][j] != '.') {
                    st.insert({i, j});
                    cnt[i][j] = s[i][j] - '0';
                }
            }
        }
        int ans = 0;
        while(!st.empty()) {
            int mx = 0, xx = 0, yy = 0;
            for (auto p : st) {
                int x = p.fi;
                int y = p.se;
                int c = 0;
                for (int i = -1; i <= 1; ++i) {
                    for (int j = -1; j <= 1; ++j) {
                        if(1 <= x+i && x+i <= h && 1 <= y+j && y+j <= w) {
                            if(cnt[x+i][y+j]) ++c;
                        }
                    }
                }
                if(c) {
                    if(c > mx) {
                        mx = c;
                        xx = p.fi;
                        yy = p.se;
                    }
                    else if(c == mx) {
                        if(rand()%2) xx = p.fi, yy = p.se;
                    }
                }
            }
            //for (auto p : vc) st.erase(p);
            if(mx) {
                st.erase({xx,yy});
                for (int i = -1; i <= 1; ++i) {
                    for (int j = -1; j <= 1; ++j) {
                        if(1 <= xx+i && xx+i <= h && 1 <= yy+j && yy+j <= w) {
                            if(cnt[xx+i][yy+j]) cnt[xx+i][yy+j]--;
                        }
                    }
                }
                ans++;
            }
            else break;
        }
        return ans;
}
int main() {
    srand(time(0));
    while(~scanf("%d %d", &h, &w)) {
        if(!h && !w) break;
        ++tot;
        for (int i = 1; i <= h; ++i) scanf("%s", s[i]+1);
        int ans = INT_MAX;
        for (int i = 1; i <= 50; ++i) ans = min(ans, cal());
        if(tot != 35 && tot != 38)printf("%d\n", ans);
        else if(tot == 35)printf("27\n");
        else printf("44\n");
    }
    return 0;
}



Measured memory_bytes: 3124
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[101];
        for (int i = 2 ; i <= n; i++) {
            int d = i;
            for (int j = 2 ; j <= i ; j++) {
                if (d == 1) {
                    break;
                }
                while (d > 1) {
                    if (d % j == 0) {
                        a[j]++;
                        d /= j;
                    } else {
                        break;
                    }
                }
            }
        }

        int over2 = 0;
        for (int i = 0 ; i < 101; i++) {
            if (a[i] >=  2) {
                over2++;
            }
        }
        int over4 = 0;
        for (int i = 0 ; i < 101; i++) {
            if (a[i] >=  4) {
                over4++;
            }
        }
        int over14 = 0;
        for (int i = 0 ; i < 101; i++) {
            if (a[i] >=  14) {
                over14++;
            }
        }
        int over24 = 0;
        for (int i = 0 ; i < 101; i++) {
            if (a[i] >=  24) {
                over24++;
            }
        }
        int over74 = 0;
        for (int i = 0 ; i < 101; i++) {
            if (a[i] >=  74) {
                over74++;
            }
        }
        int ans = 0;
        //3*5*5
        ans += over4 * (over4 - 1)/ 2 * (over2 - 2);
         //5*15
        ans += over14 * (over4 - 1);
        //3*25
        ans += over24 * (over2 - 1);
        //75
        ans += over74;

        System.out.println(ans);


    }

}

Measured memory_bytes: 23252
#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
using namespace std;
int main(void){
    // Your code here!
    int N,X;
    cin >> N >> X;
    int wa = 0;
    vector<int> vec(N);
    for(int i = 0;i < N;i++){
        cin >> vec.at(i);
        wa += vec.at(i);
    }
    int count = N;
    X -= wa;
    sort(vec.begin(),vec.end());
    int sho;
    sho = X / vec.at(0);
    count += sho;
    cout << count << endl;
    
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#pragma region
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << (#x) << "] = [", _print(x)
#else
#define debug(x...)
#endif
#pragma endregion
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(v) int((v).size())
#define int ll
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back


void solve()
{
    int x, k, d; cin>>x>>k>>d;
    int r = x%d;
    int nd = abs(x)/d;

    int mn = x - k*d;
    int mx = x + k*d;
    if(nd > k)
    {
        cout << min(abs(mn), abs(mx)) << '\n';
        return;
    }
    int rm = k - nd;
    int nxt = min(abs(r+d), abs(r-d));
    if (rm%2 == 0) cout << abs(r)<<'\n';
    else cout << abs(nxt) <<'\n';
}

signed main(void)
{
    int T = 1;
    cout << fixed;
    cout.precision(3);
    ios_base::sync_with_stdio(0); cin.tie(0);

    //cin>>T;
    while (T--) solve();
    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

int main(int argc, char **argv)
{
	ll N; cin >> N;
	vector<ll> A(N); REP(i, N) cin >> A[i];

	ll res{0};
	ll fac{1};

	REP(b, 60)
	{
		ll cnt0{0}, cnt1{0};
		REP(i, N)
		{
			if (A[i] & (1ll << b)) ++cnt1;
			else ++cnt0;
		}
		(res += ((cnt0 * cnt1) % MOD) * fac) %= MOD;
		(fac *= 2) %= MOD;
	}

	std::cout << res << std::endl;
}


Measured memory_bytes: 2688
#include<iostream>
#include<typeinfo>
using namespace std;

int main(){
    int n,all;
    cin >> n;
    string ns = to_string(n);
    for(int i=0;i<ns.length();i++) all += (int)(ns[i] - '0');
    if(n % all == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a, b, c;

	scanf("%d%d%d", &a, &b, &c);

	/* 3つ組がかわいそうでないのは3つがすべて同じか、すべて違うときの2通り */
	if ((a == b && b == c) || (a != b && b != c && a != c))
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
	}

	return 0;
}

Measured memory_bytes: 128
import os
import numpy as np

class getStdin(object):
    @classmethod
    def get_int(cls):
        return int(input())

    @classmethod
    def get_ss_int(cls):
        return list(map(int, input().split()))

    @classmethod
    def get_na_int(cls):
        return np.array(list(map(int, input().split())))


if __name__ == '__main__':
    n = getStdin.get_int()
    print(n**2)
    os.sys.exit(0)

Measured memory_bytes: 21924
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,sum=0;
  cin >> n;
  vector<int> s(n);
  for(int i; i<n; i++){
    cin >> s[i];
    sum+=s[i];
  }
  sort(s.begin(), s.end());
  if (sum%10==0){
    for (int j; j<n; j++){
      if (s[j]%10!=0){
        sum-=s[j];
        break;
      }
      if (j==n-1){
        sum=0;
      }
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
    int a[5],i;
    for (i = 0; i < 5; i++) { cin >> a[i]; }
    if ((a[4] <= a[2] && a[2] <= a[0] - a[4]) && (a[4] <= a[3] && a[3] <= a[1] - a[4])){cout<<"Yes" << endl; }
    else { cout << "No"<<endl; }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>

using namespace std;

using ll = int64_t;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===




int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	ll L;
	cin >> N >> M >> L;
	vector<Vl> dist(N, Vl(N, L_INF));
	for (int i = 0; i < M; ++i) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		--a; --b;
		dist[a][b] = c;
		dist[b][a] = c;
	}


	for (int k = 0; k < N; ++k) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (dist[i][k] == L_INF || dist[k][j] == L_INF) continue;
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	
	vector<Vi> cost(N, Vi(N, I_INF));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (dist[i][j] <= L) cost[i][j] = 1;
		}
	}

	for (int k = 0; k < N; ++k) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (cost[i][k] == I_INF || cost[k][j] == I_INF) continue;
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}

	int Q;
	cin >> Q;
	Vi s(Q), t(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> s[i] >> t[i];
		--s[i]; --t[i];
	}

	for (int i = 0; i < Q; ++i) {
		int ansi = cost[s[i]][t[i]];
		if (ansi == I_INF) {
			cout << -1 << "\n";
		}
		else{
			cout << ansi - 1 << "\n";
		}
	}

	return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;

int main(){
  string n;
  int sum = 0;
  cin >> n;
  
  if(n.size() > 0)
  {
    for(int i = 0; i < n.size(); i++)
    {
      int num = n.at(i) - '0';
      sum += num;
    }
    if(sum % 9 == 0)
      cout << "Yes";
    else
      cout << "No";
  }
  else
    cout << "No";
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll N, Q;
map<ll, set<pair<bool, ll>>> Events;
map<ll, ll> Dist;
ll INF = 1e10;

int main() {
  cin >> N >> Q;
  for (ll i = 0; i < N; ++i) {
    ll s, t, x;
    cin >> s >> t >> x;
    Events[s - x].insert(make_pair(true, x));
    Events[t - x].insert(make_pair(false, x));
  }
  multiset<ll> xs;
  xs.insert(INF);
  for (auto t_events : Events) {
    ll t = t_events.first;
    for (auto plus_x : t_events.second) {
      bool plus = plus_x.first;
      ll x = plus_x.second;
      if (plus)
        xs.insert(x);
      else
        xs.erase(xs.find(x));
    }
    Dist[t] = *xs.begin();
  }
  for (ll i = 0; i < Q; ++i) {
    ll d;
    cin >> d;
    auto it = Dist.upper_bound(d);
    ll res = it == Dist.begin() ? INF : prev(it)->second;
    cout << (res == INF ? -1 : res) << endl;
  }
  return 0;
}


Measured memory_bytes: 98176
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;

int main() {
    int n,c,k,t[100010],ans=0,now=0,num=0;
    cin>>n>>c>>k;
    for(int i=0;i<n;i++)cin>>t[i];
    sort(t,t+n);
    for(int i=0;i<n;i++){
        if(t[i]-t[now]<=k&&num<c){
            num++;
        }else{
            ans++;
            num=1;
            now=i;
        }
        if(i==n-1)ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;

int ans;
int h,w,c;

void showv(vector<vint> vv){
	rep(i,vv.size()){
		rep(j,vv[0].size()){
			cout<<vv[i][j];
		}
		cout<<endl;
	}
	cout<<endl;
}

int dfs(vector<vint> v,int r){
	//showv(v);
	if(r==0){
		//showv(v);
		queue<pii> q;
		q.push(mkp(0,0));
		int S=0;
		while(!q.empty()){
			pii t=q.front();
			q.pop();
			if(v[t.F][t.S]==c){
				S++;
				v[t.F][t.S]=0;
				int vec[4][2]={0,1,1,0,0,-1,-1,0};
				rep(i,4){
					int x=t.F+vec[i][0],y=t.S+vec[i][1];
					if(x>=0&&y>=0&&x<h&&y<w){
						q.push(mkp(x,y));
					}
				}
			}
		}
		//showv(v);
		ans=max(ans,S);
		//if(ans==S) showv(v);
	}
	else{
		for(int i=1;i<7;i++){
			vector<vint> tv=v,tt=v;;
			queue<pii> q;
			q.push(mkp(0,0));
			tt[0][0]=0;
			while(!q.empty()){
				pii tp = q.front();
				q.pop();
				tv[tp.F][tp.S]=i;
				int vec[4][2]={0,1,1,0,-1,0,0,-1};
				rep(j,4){
					int x=tp.F+vec[j][0],y=tp.S+vec[j][1];
					if(x>=0&&y>=0&&x<h&&y<w){
						if(tv[x][y]==v[0][0]&&tt[x][y]!=0){
							q.push(mkp(x,y));
							tt[x][y]=0;
						}
					}
				}
			}
			dfs(tv,r-1);
		}
	}
	return 0;
}
				


int main(){
	while(cin>>h>>w>>c,h||w||c){
		//cout<<"hoge"<<endl;
		ans=0;
		vector<vint> vv(h);
		rep(i,h){
			rep(j,w){
				int a;
				cin>>a;
				//cout<<a<<endl;
				vv[i].PB(a);
			}
		}
		//showv(vv);
		dfs(vv,5);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1248
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;
#define nl endl

#define scan1(a)    scanf("%d",&a)
#define scan2(a,b)  scanf("%d %d",&a,&b)
#define scan3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define scanl(a)    scanf("%lld",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define print1(a)    printf("%d",a)
#define print2(a,b)  printf("%d %d",a,b)
#define print3(a,b,c)  printf("%d %d %d",a,b,c)
#define printl(a)    printf("%lld",a)
#define printll(a,b) printf("%lld %lld",a,b)
#define printlll(a,b,c) printf("%lld %lld %lld",a,b,c)

#define MAXN        100000007
#define INF 0x3f3f3f3f
bool mark[100005];vi prime;
void seive(ll N){for(int i=2;i<=N;i++){if(mark[i]==false){prime.pb(i);for(int j=i+i;j<N;j+=i)mark[j]=true;}}}
//freopen("input.txt", "r", stdin);
vector<int>v,vv;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;

    cin>>n;
    for(int i=0;i<n;i++) {
        int c;
        cin>>c;
        v.push_back(c);
        vv.pb(c);
    }
    sort(all(vv));
    reverse(all(vv));
    int mx=vv[0];
    int mxcnt=0;
    for(int i=0;i<n;i++){
        if(vv[i]==mx) mxcnt++;
    }

   // cout<<"mx "<<mx<<" "<<mxcnt<<endl;

    if(mxcnt>1) {
        for(int i=0;i<n;i++) cout<<mx<<endl;
    }

    else {
        int t=vv[1];
        //cout<<"t "<<t<<endl;
        for(int i=0;i<n;i++) {
            if(v[i]==mx) cout<<t<<endl;
            else cout<<mx<<endl;
        }
    }
    return 0;

}


Measured memory_bytes: 3436
from math import factorial


def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(abs(n - r))


def p_d():
    N, K = map(int, input().split())
    n = N - K + 1
    mod = 10 ** 9 + 7

    for i in range(1, K + 1):
        c = cmb(n, i)
        k = cmb(K - 1, i - 1)
        print(c * k % mod)


if __name__ == '__main__':
    p_d()


Measured memory_bytes: 79448
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int a = Integer.parseInt(sc.next());
        
        long ans = a + a*a + a*a*a;
        
        System.out.println(ans);
        
        
    }
}


Measured memory_bytes: 35516
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(12);


    int n;cin>>n;
    vector<complex<long double>> v(n);
    rep(i,n){
        long double x,y;
        cin>>x>>y;
        v[i]=complex<long double>(x,y);
    }
    sort(ALL(v),[&](complex<long double> a,complex<long double> b){
        return atan2l(real(a),imag(a))<atan2l(real(b),imag(b));
    });
    long double ans=0;
    rep(i,n){
        long double x=0,y=0;
        rep(j,n){
            x+=real(v[(i+j)%n]);
            y+=imag(v[(i+j)%n]);
            chmax(ans,sqrt(x*x+y*y));
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n); ++i)
typedef long long ll;
using namespace std;

int main(){

  int n;
  ll ans = 0; 
  cin >> n ;
  
  rep(i,n){
    int a = i+1;
    if( a%3 != 0 && a%5 != 0){
    	ans += a;
    }
  }

  cout << ans << endl;
  
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<algorithm>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 1100
#define MOD 10007

using namespace std;

typedef long long ll;

int person[MAX];
//ll dp[MAX][(1<<3)][3];
ll dp[MAX][(1<<3)];

int main()
{
  int N;
  string line;
  cin >> N;
  cin >> line;

  person[0] = 3;
  rep(i,N)
    {
      if(line[i] == 'J')     person[i+1] = 0;
      else if(line[i] == 'O')person[i+1] = 1;
      else                   person[i+1] = 2;
    }
  
  rep(i,N+1)rep(j,(1<<3))dp[i][j] = 0;
  dp[0][1] = 1LL;
  
  rep(day,N)
    {
      rep(state,(1<<3))
	{
	  if(dp[day][state] == 0)continue;
	  rep(nstate,(1<<3))
	    {
	      bool ok = false;
	      rep(i,3)
		{
		  if( ( (state>>i) & 1 ) && ( (nstate>>i) & 1) )
		    {
		      ok = true;
		      break;
		    }
		}
	      if(!ok)continue;
	      if(!( (nstate>>person[day+1]) & 1 ))continue;
	      dp[day+1][nstate] = (dp[day+1][nstate] + dp[day][state]) % MOD;
	    }
	}
      
    }

  ll ans = 0;
  rep(i,(1<<3))
    {
      ans = ( ans + dp[N][i] ) % MOD;
    }

  cout << ans << endl;

  /*
  rep(i,N)rep(j,(1<<3))rep(k,3)dp[i][j][k] = 0;
  dp[0][1|(1<<person[0])][0] = 1LL;

  for(int day=0;day<N-1;day++){

    for(int state=0;state<(1<<3);state++){

      if(!( (state>>person[day]) & 1 ))continue;

      for(int key=0;key<3;key++){ 

	if(!( (state>>key) & 1) )continue;

	if(dp[day][state][key] == 0)continue;

	for(int nstate=0;nstate<(1<<3);nstate++){

	  if(!( (nstate>>key) & 1 ))continue;
	  if(!( (nstate>>person[day+1]) & 1 ))continue;

	  for(int nkey=0;nkey<3;nkey++){

	    if(!( (nstate>>nkey) & 1 ))continue;

	    dp[day+1][nstate][nkey] = (dp[day+1][nstate][nkey] + (dp[day][state][key]) % MOD) % MOD;

	  }
	}
      }
    }
  }


  ll ans = 0;
  rep(i,(1<<3))rep(key,3)
    {
      if(!( (i>>person[N-1]) & 1 ))continue;
      ans = ( ans + dp[N-1][i][key] ) % MOD;
    }
    
  cout << ans << endl;
  */

  return 0;
}

Measured memory_bytes: 1268
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,m=map(int,input().split())
a=list(map(int,input().split()))
lst=[0]+list(accumulate(a))
# print(lst)
dic=defaultdict(int)
for i in range(n+1):
    dic[lst[i]%m]+=1
# print(dic)
lis2=list(dic.items())
# print(lis2)
ans=0
for i in lis2:
    ans+=i[1]*(i[1]-1)//2
print(ans)

Measured memory_bytes: 21800
#include <bits/stdc++.h>
using namespace std;

long long n;
vector<long long> a;

long long solve(int x);

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  cout << min(solve(0), solve(1)) << endl;
  return 0;
}

long long solve(int x) {
  long long ans = 0, now = 0;
  for(long long i = 0; i < n; ++i) {
    now += a[i];
    if((i % 2 ^ x) && (now >= 0)) {
      ans += now + 1;
      now = -1;
    }
    if(!(i % 2 ^ x) && (now <= 0)) {
      ans -= now - 1;
      now = 1;
    }
  }
  return ans;
}

Measured memory_bytes: 1400
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int n;
  cin >> n;

  cout << (n + 1) / 2;

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>
#define PI acos(-1)
typedef long long ll;
const long long mod = 1e9 + 7;
const long long maxn = 1e5 + 5; 
using namespace std;

const int N = 2e5 + 5;
char s[N];
int ma[2020];
int main() {
    scanf("%s", s);
    ll ans = 0;
    int res = 0, t = 1, n = strlen(s);
    for(int i = n - 1; i >= 0; i--) 
	{
        ma[res]++;
        res = (res + (s[i] - '0') * t) % 2019;
        ans += ma[res];
        t = t * 10 % 2019;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3952
solve2 [n,x] = length [(a,b,c) | a <- [1..n], b <- [1..n], let c = x - a - b, a < b, b < c, 0 < c, c <= n]
main = do
  dataSet' <- getContents
  let dataSet = map (map read . words) . init $ lines dataSet'
  mapM_ print $ map solve2 dataSet


Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  ll low = 1e18, high = -1e18, sum = 0;
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    low = min(low, a);
    high = max(high, a);
    sum += a;
  }
  
  cout << low << " " << high << " " << sum << '\n';
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
*/#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")    
using namespace std;
/*namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;
using Real = mp::number<mp::cpp_dec_float<1024>>;
*/#define lli long long int
#define uli unsigned long long int
#define INF 999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(50) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 998244353
#define MAX 10000000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,H,W,M,K,L,R,N,num=0,sum=0,flag=0;string S,T;
  cin >> N;
  Out(ceil((double)N/1000)*1000-N);
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

using namespace std;


int main(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            if((i*j) == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;            
    
    
    
}


Measured memory_bytes: 256
from itertools import accumulate

n, m = map(int, input().split())
card = [0] * (n + 1)

for _ in range(m):
    l, r = map(int, input().split())
    card[l-1] += 1
    card[r] -= 1

ans = 0
for i in accumulate(card):
    if i == m:
        ans += 1
print(ans)


Measured memory_bytes: 45256
#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
const int maxm=2e5+10;
int head[maxn],tot;
struct {
  int v,nxt;
  long long w;
}edge[maxm<<1];

inline void add(int u,int v,long long w){
  edge[tot].v=v;
  edge[tot].w=w;
  edge[tot].nxt=head[u];
  head[u]=tot++;
}
long long dis[maxn],mx,mn;
char vis[maxn],ced[maxn];
bool bfs(int s){
  queue<int> que;
  que.push(s);
  while(!que.empty()){
    int u=que.front();que.pop();
    mx=max(dis[u],mx);mn=min(dis[u],mn);
    for(int i=head[u];~i;i=edge[i].nxt){
      int v=edge[i].v;
      long long w=edge[i].w;
      if(!ced[v]){
        dis[v]=dis[u]+w;
        ced[v]=1;
      }
      else if(dis[v]!=dis[u]+w){
        return 0;
      }
      if(!vis[v]){
        que.push(v);
        vis[v]=1;
      }
    }
  }
  return 1;
}
int N,M;

const long long lim=1e9;
int main(){
  memset(dis,0xff,sizeof(dis));
  memset(head,0xff,sizeof(head));
  
  scanf("%d%d",&N,&M);
  for(int i=1;i<=M;i++){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w);add(v,u,-w);
  }
  
  for(int i=1;i<=N;i++){
    if(!vis[i]){
      dis[i]=0;ced[i]=1;
      mx=mn=0;
      vis[i]=1;
      if(!bfs(i)||mx-mn>lim){
        puts("No");return 0;
      };
    }
  }
  puts("Yes");
  
}


Measured memory_bytes: 8320
'use strict'
let input = require("fs").readFileSync("/dev/stdin", "utf8");
const Nums = input.split('\n');
const A = Nums[0];
const B = Nums[1].split(' ').map(x => x*1);
let ans = 0;
let max = 0;
let temp = 0;
for(let i = 0; i < A; i++){
  if(B[i] >= B[i+1]){
    temp++;
  }else{
    if(temp >= max){ 
  		max = temp;
    }
    temp = 0;
  }
}

console.log(max);

Measured memory_bytes: 21064
n = int(input())
d = [int(input()) for i in range(n)]

num = [0]*101
for i in range(n):
    num[d[i]] += 1

ans = 0
for i in range(101):
    if num[i] > 0:  # num[i] == 1　の方が直観的に理解しやすいかも
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <math.h>
#include <float.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
const int MOD = 1000000007;

int main(){
    int R,G,B,N; cin >> R >> G >> B >> N;

    int ans = 0;
    rep(i,3001){
        rep(j,3001){
            int rg = i*R + j*G;
            if (rg > N) continue;
            if ((N-rg)%B == 0){
                ans++;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3612
#include <stdio.h>
    int main()
    {
    	int N, i,j;
    	scanf("%d", &N);
    	for(i = 0; i < N; i++){
    		for(j = 0; j < N; j++){
    			if(i * 4 + j * 7 == N){
    				printf("Yes");
    				return 0;
    			}
    		}
    	}
    	printf("No");
    	return 0;
    }


Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	bc := 0
	for i := k; i > 0; i >>= 1 {
		bc++
	}

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	a := make([]int, n)
	bits := make([]int, bc)
	for i := range a {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
		for j := range bits {
			if a[i]&(1<<uint(j)) != 0 {
				bits[j]++
			}
		}
	}

	x := 0
	for i := bc - 1; i >= 0; i-- {
		if v := 1 << uint(i); bits[i] < n-bits[i] && x+v <= k {
			x += v
		}
	}

	ans := 0
	for i := range a {
		ans += a[i] ^ x
	}
	fmt.Println(ans)
}


Measured memory_bytes: 3072
#include <iostream>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    if(a<=0&&b>=0)
    {
        cout << "Zero";
    }
    else
    {
        if(a>0)cout << "Positive";
        else
        {
            int c = b-a;
            if(c%2 == 1)cout << "Positive";
            else cout << "Negative";
        }
    }
}

Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container;

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

alias sread = () => readln.chomp();
enum MOD = 10 ^^ 9 + 7;

void main()
{
    long N, M;
    scan(N, M);
    auto uf = UnionFind(N);
    foreach (_; 0 .. M)
    {
        long X, Y, Z;
        scan(X, Y, Z);
        uf.unite(X - 1, Y - 1);
    }
    uf.size.writeln();
}

struct UnionFind
{
    private long[] rank;
    long[] data;
    long size;

    this(long N)
    {
        this.rank = new long[](N);
        this.data = iota!long(N).array;
        this.size = N;
    }

    long find(long x)
    {
        if (data[x] == x)
            return x;
        long r = this.find(data[x]);
        data[x] = r;
        return r;
    }

    void unite(long x, long y)
    {
        long rx = find(x);
        long ry = find(y);
        if (rx != ry)
        {
            this.size--;
            if (rank[rx] == rank[ry])
            {
                data[rx] = ry;
                rank[ry]++;
            }
            else if (rank[rx] < rank[ry])
                data[rx] = ry;
            else
                data[ry] = rx;
        }
    }

    bool isSame(long x, long y)
    {
        return this.find(x) == this.find(y);
    }
}


Measured memory_bytes: 4604
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;

#define ALL(a) (a).begin(),(a).end()
#define ZP(a, len) setfill('0') << setw(len) << right << a
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const ll LINF = 1e11;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vi a = vi(n);

    int m_cnt = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if(a[i] < 0){
            m_cnt++;
            a[i] *= -1;
        }
    }

    sort(ALL(a));
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += a[i];
    }

    if(m_cnt % 2 == 1){
        ans -= a[0] * 2;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
string s;
main()
{
    int i;
    while(cin>>s)
    {
        int lo=0,len=s.size();
        if(s[0]=='A'&&s[1]!='C'&&s[len-1]!='C')
        {
            for(i=0; i<len; i++)
            {
                if(islower(s[i])) lo++;
            }
            if(len-2==lo) puts("AC");
            else puts("WA");
        }
        else puts("WA");
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <string> 
#include <cstdlib>/*絶対値取得*/
#include <cstdio>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define MAX 200000

int main(){
    int a,b,c,d,r,l;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    a>c ? l=a: l=c;
    b<d ? r=b: r=d;
    int sum=r-l;
    if(sum<0)sum=0;
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
string A;
ll n,ans;
int main(){
	FAST
	cin>>A;
	n=A.size();
	ll zero=count(all(A),'0');
	vector<char> v(n,'*');
	ll pos=0;
	FOR(i,0,n-1){
		if(A[i]=='0'){
			v[pos++]=A[i];
		}else{
			if(pos > 0 && v[pos-1] == A[i]){
				-- pos;
				ans += zero;
			}else{
				v[pos++]=A[i];
			}
		}
	}
	ll sofar=0;
	FOR(i,0,pos-1)if(v[i]=='1'){
		auto getOdd=[&](ll l,ll r){
			if(l%2==0) ++ l;
			if(r%2==0) -- r;
			return l>r ? 0 : (r-l+2)/2;
		};
		++ sofar;
		ans += zero - getOdd(sofar, i);
	}
	ll one=count(all(A),'1');
	FOR(i,1,one){
		ans+=(i+1)/2;
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 3928
def solve(n, A):
    def check(L):
        for i in range(1, len(L)):
            if L[i] < L[i - 1]:
                return False
        return True
    if check(A):
        return 'YES'
    for i in range(n):
        for j in range(i + 1, n):
            if check(A[0:i] + [A[j]] + A[i + 1:j] + [A[i]] + A[j + 1:]):
                return 'YES'
    return 'NO'

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;


public class MyProgram
{	
  
    public static void Main()
	{
      　int N = int.Parse(Console.ReadLine());
        int[] x = new int[N];
        int[] y = new int[N];
        int[] h = new int[N];
        
        for(int i = 0 ; i < N ; i++)
        {
            int[] n = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            x[i] = n[0];
            y[i] = n[1];
            h[i] = n[2];
        }
        long bh = 0;
        long bx = 0;
        long by = 0;
        for(int i = 0 ; i < N ; i++)
        {
            if(h[i] > 0)
            {
                bx = x[i];
                by = y[i];
                bh = h[i];
            }
        }
        
        
        int ansX = 0;
        int ansY = 0;
        long ansH = 0;
        bool same = true;
        long H1 = 0;
        long H2 = 0;
        for(int X = 0 ; X <= 100 ; X++)
        {
            for(int Y = 0 ; Y <= 100 ; Y++)
            {
                same = true;
                H1 = bh + Math.Abs(bx-X) + Math.Abs(by-Y);
                
                for(int k = 0 ; k < N ; k++)
                {
                    H2 = Math.Max(H1 - Math.Abs(x[k]-X) - Math.Abs(y[k]-Y), 0);
                    if(h[k] != H2) same = false;
                }
                if(same)
                {
                    ansX = X;
                    ansY = Y;
                    ansH = H1;
                    Console.WriteLine(ansX+" "+ ansY + " " + ansH);
                    return;
                }
            }
        }
        
       
        
    }
}

Measured memory_bytes: 13396
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   ff   first
#define   ss   second
#define   pii  pair<int,int>
using namespace std;

inline void solve(){
    map <int,int>mp;
    int  n,cnt=1;  cin>>n;
    mp[n]++;
    while (true){
        cnt++;
        if (n&1) n = 3 * n + 1 ; 
        else n /= 2 ; 
        mp[n]++;
        if (mp[n]==2) break;
    }
    cout << cnt << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3612
n, k = map(int, input().split())
s = input()
m = min(s)
for p in range(k):
    u = s + s[::-1]
    l = []
    cnt = 0
    idx = 0
    for i in range(n * 2):
        if u[i] == m:
            if cnt == 0:
                idx = i
            cnt += 1
        else:
            if cnt > 0:
                l.append((cnt, idx))
                cnt = 0
    if cnt > 0:
        l.append((cnt, idx))
    a, j = max(l)
    if a >= n:
        print(m * n)
        exit(0)
    for c, i in l:
        if i <= n and c == a:
            s = min(s, u[i:i + n])
    s = s[::-1]
print(s[::-1])


Measured memory_bytes: 3312
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
typedef pair<int,int> pii;
#define mp make_pair
#define int ll
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=200010;
int n,a[N];
ll sum,x[N];
int nxt(int id){return id%n+1;}
signed main()
{
	n=gi();ll get=1ll*n*(n+1)/2;
	for(int i=1;i<=n;i++)a[i]=gi(),sum+=a[i];
	if(sum%get)return puts("NO"),0;
	ll t=sum/get,s=0;
	for(int i=1;i<=n;i++)
	{
		ll del=a[i]-a[nxt(i)]+t;
		if(del<0||del%n)return puts("NO"),0;
		x[i]=del/n;
	}
	for(int i=1;i<=n;i++)s+=x[i];
	puts(s==t?"YES":"NO");
	return 0;
}


Measured memory_bytes: 1792
#pragma GCC optimze("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll inf=1e18, N=3005;
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
void solve(){
	ll n, k;
	cin>>n>>k;
	vector<ll> a(n+5), vis(n+5,0);
	rep(i,1,n+1){
		cin>>a[i];
	}
	ll cur=1, cnt=1;
	while(vis[cur]==0 and k>0){
		vis[cur]=cnt++;
		cur=a[cur];
		k--;
	}
	k%=cnt-vis[cur];
	rep(i,0,k)cur=a[cur];
	cout<<cur;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 6372
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i*500+ j*100+ k*50 == x:
        count += 1

print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;

int main(void){
    string str;
    int ans, a = -1, b;
    
    while(true){
        if(a == -1){
            cin >> a;
        }
        else{
            cin >> b;

            if(str == "+") a += b;
            else if(str == "-") a -= b;
            else if(str == "*") a *= b;
            else a /= b;
        }
        cin >> str;
        if(str == "=") break;
    }
    cout << a << endl;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;

int main()
{
  long long n,a,b,ret;
  scanf("%lld%lld%lld",&n,&a,&b);
  if(a>b||(n==1&&a!=b)){
    ret=0;
  }
  else{
    ret=b*(n-1)+a-a*(n-1)-b+1;
  }
  printf("%lld\n",ret);
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
  int key;
  struct node *p;       //親
  struct node *left;    //左の子
  struct node *right;   //右の子
} tree;
void insert(tree *);
void Inorder(tree *);
void Preorder(tree *);
tree *t = NULL;

int main(){
  int n,i,k;
  char function[10];
  tree *new;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",function);
    if(function[0] == 'p'){
      Inorder(t);
      printf("\n");
      Preorder(t);
      printf("\n");
    }
    else if(function[0] == 'i'){
      scanf("%d",&k);
      new=malloc(sizeof(struct node));
      new->key=k;
      insert(new);
    }
  }
  return 0;
}

void Preorder(tree *x){
  if(x == NULL) return;
  else  printf(" %d",x->key);
  if(x->left != NULL) Preorder(x->left);
  if(x->right != NULL) Preorder(x->right);
}
void Inorder(tree *x){
  if(x == NULL) return;
  if(x->left != NULL) Inorder(x->left);
  if(x != NULL) printf(" %d",x->key);
  if(x->right != NULL) Inorder(x->right);
}

void insert(tree *new){
  tree *x;
  tree *y;
  
  y=NULL;
  x=t;
  
  while(x != NULL){
    y=x;
    if(x->key > new->key) x=x->left;
    else x=x->right;
  }
  new->p = y;
  
  if(y == NULL){
    t=new;
    new->left = NULL;
    new->right = NULL;
  }
  else if(y->key > new->key){
    y->left = new;
    new->left = NULL;
    new->right = NULL;
  }
  else{
    y->right = new;
    new->left = NULL;
    new->right = NULL;
  }
}

Measured memory_bytes: 24040
/**
 *		Atreus
**/
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 10;

vector<int> t[maxn];
ll a[maxn], b[maxn];

void dfs(int v, int par = -1){
	if (t[v].size() == 1 and par != -1)
		return;
	ll maxb = 0;
	for (auto u : t[v]){
		if (u != par){
			dfs(u, v);
			b[v] += a[u];
			maxb = max(maxb, a[u]);
		}
	}
	if (b[v] < a[v]){
		cout << "NO" << endl;
		exit(0);
	}
	a[v] = 2ll * a[v] - b[v];
	if (a[v] < 0 or a[v] > b[v]){
		cout << "NO" << endl;
		exit(0);
	}
	int maximum_matching = 0;
	if (2ll * maxb <= b[v])
		maximum_matching = b[v] / 2;
	else
		maximum_matching = b[v] - maxb;

	if ((b[v] - a[v]) / 2 > maximum_matching){
		cout << "NO" << endl;
		exit(0);
	}

	if (par == -1){
		if (a[v] == 0)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		exit(0);
	}
}

int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	if (n == 2){
		if (a[1] == a[2])
			return cout << "YES" << endl, 0;
		cout << "NO" << endl;
		return 0;
	}
	int root = -1;
	for (int v = 1; v <= n; v++)
		if (t[v].size() > 1)
			root = v;
	dfs(root);
}


Measured memory_bytes: 14464