akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
const double PI = acos(-1);
const long long INF = (1LL << 60);
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;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}

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

  ll n;
  cin >> n;
  vector<ll> a(n);
  for(ll i = 0; i < n; i++) cin >> a[i];

  for(ll i = 0; i < n; i++){
    if(i < a[i]){
      cout << -1 << endl;
      return 0;
    }
  }

  ll ans = 0;
  for(ll i = 0; i < n-1; i++){
    if(a[i]+1 == a[i+1]) continue;
    else{
      if(a[i]+1 < a[i+1]){
        cout << -1 << endl;
        return 0;
      }
      ans += a[i];
    }
  }
  ans += a[n-1];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


n,a,b = readints()

if (b-a)%2==0:
    print((b-a)//2)
else:
    print(min(n-b+(b-a)//2+1,a-1+(b-a)//2+1))





Measured memory_bytes: 61704
#include<iostream>
using namespace std;
int n,a[1<<17];
main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int s=1;
	for(int i=1;i<=n;i++)
	{
		if(2==(s=a[s]))
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int N,MOD,Pow[MAXN];char s[MAXN];
int POW(int x,int k)
{
	int ans=1;
	for (;k;k>>=1,x=1LL*x*x%MOD) if (k&1) ans=1LL*ans*x%MOD;
	return ans;
}
map<int,int> Cnt;
int main()
{
	cin>>N>>MOD;
	scanf("%s",s+1);
	if (MOD==2)
	{
		long long ans=0;
		for (int i=1;i<=N;++i)
			if ((s[i]-'0')%2==0)
				ans+=i;
		cout<<ans<<endl;
		return 0;
	}
	if (MOD==5)
	{
		long long ans=0;
		for (int i=1;i<=N;++i)
		{
			int v=s[i]-'0';
			if (v==0 || v==5) ans+=i;
		}
		cout<<ans<<endl;
		return 0;
	}
	Pow[0]=1;
	for (int i=1;i<=N;++i) Pow[i]=1LL*Pow[i-1]*10%MOD;
	for (int i=1;i<=N;++i) Pow[i]=POW(Pow[i],MOD-2);
	Cnt[0]++;
	long long Ans=0;
	int Hash=0;
	for (int i=1;i<=N;++i)
	{
		Hash=1LL*Hash*10%MOD+s[i]-'0';
		Hash%=MOD;
		int v=1LL*Hash*Pow[i]%MOD;
		Ans+=Cnt[v];
		Cnt[v]++;
	}
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<queue>
#include<string>
#include<sstream>
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
char a[510000];
int p[3];
int main()
{
	scanf("%s", a);
	int len = strlen(a);
	for (int i = 0; i < len; i++)
	{
		if (a[i] == 'a')p[0]++;
		else if (a[i] == 'b')p[1]++;
		else p[2]++;
	}
	int maxs=-1, mins=9999999;
	for (int i = 0; i < 3; i++)
	{
		maxs = max(maxs, p[i]);
		mins = min(mins, p[i]);
	}
	if (maxs - mins > 1)printf("NO");
	else printf("YES");
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

struct fl{
	int x;
	int y;
	int d;
};

int main() {
	int n; cin >> n;
	vector<VVI> dr(4,VVI(410000,VI(0))), dl(4,VVI(410000,VI(0)));
	VVI xr(210000,VI(0)), xl(210000,VI(0)), yu(210000,VI(0)), yd(210000,VI(0));
	vector<fl> f(n);
	int x, y; char u;
	REP(i,n){
		cin >> x >> y >> u;
		int d;
		if(u=='L'){
			d=0;
			xl[y].push_back(x);
		}
		else if(u=='R'){
			d=1;
			xr[y].push_back(x);
		}
		else if(u=='U'){
			d=2;
			yu[x].push_back(y);
		}
		else{
			d=3;
			yd[x].push_back(y);
		}
		f[i]={x,y,d};
		dr[d][x-y+200000].push_back(x);
		dl[d][x+y].push_back(x);
	}
	REP(i,200001){
		sort(ALL(xl[i]));
		sort(ALL(xr[i]));
		sort(ALL(yu[i]));
		sort(ALL(yd[i]));
	}
	REP(i,400001){
		REP(j,4){
			sort(ALL(dr[j][i]));
			sort(ALL(dl[j][i]));
		}
	}
	ll ans=INF;
	REP(i,n){
		fl now=f[i];
		int p;
		if(now.d==0){
			p=lower_bound(ALL(xr[now.y]),now.x)-xr[now.y].begin();
			if(p!=0)
				ans=min(ans,(now.x-xr[now.y][p-1])*5);
			p=lower_bound(ALL(dr[2][now.x-now.y+200000]),now.x)-dr[2][now.x-now.y+200000].begin();
			if(p!=0)
				ans=min(ans,(now.x-dr[2][now.x-now.y+200000][p-1])*10);
			p=lower_bound(ALL(dl[3][now.x+now.y]),now.x)-dl[3][now.x+now.y].begin();
			if(p!=0)
				ans=min(ans,(now.x-dl[3][now.x+now.y][p-1])*10);
		}
		else if(now.d==1){
			p=upper_bound(ALL(xl[now.y]),now.x)-xl[now.y].begin();
			if(p!=xl[now.y].size())
				ans=min(ans,(xl[now.y][p]-now.x)*5);
			p=upper_bound(ALL(dr[3][now.x-now.y+200000]),now.x)-dr[3][now.x-now.y+200000].begin();
			if(p!=dr[3][now.x-now.y+200000].size())
				ans=min(ans,(dr[3][now.x-now.y+200000][p]-now.x)*10);
			p=upper_bound(ALL(dl[2][now.x+now.y]),now.x)-dl[2][now.x+now.y].begin();
			if(p!=dl[2][now.x+now.y].size())
				ans=min(ans,(dl[2][now.x+now.y][p]-now.x)*10);
		}
		else if(now.d==2){
			p=upper_bound(ALL(yd[now.x]),now.y)-yd[now.x].begin();
			if(p!=yd[now.x].size())
				ans=min(ans,(yd[now.x][p]-now.y)*5);
			p=upper_bound(ALL(dr[0][now.x-now.y+200000]),now.x)-dr[0][now.x-now.y+200000].begin();
			if(p!=dr[0][now.x-now.y+200000].size())
				ans=min(ans,(dr[0][now.x-now.y+200000][p]-now.x)*10);
			p=lower_bound(ALL(dl[1][now.x+now.y]),now.x)-dl[1][now.x+now.y].begin();
			if(p!=0)
				ans=min(ans,(now.x-dl[1][now.x+now.y][p-1])*10);
		}
		else{
			p=lower_bound(ALL(yu[now.x]),now.y)-yu[now.x].begin();
			if(p!=0)
				ans=min(ans,(now.y-yu[now.x][p-1])*5);
			p=lower_bound(ALL(dr[1][now.x-now.y+200000]),now.x)-dr[1][now.x-now.y+200000].begin();
			if(p!=0)
				ans=min(ans,(now.x-dr[1][now.x-now.y+200000][p-1])*10);
			p=upper_bound(ALL(dl[0][now.x+now.y]),now.x)-dl[0][now.x+now.y].begin();
			if(p!=dl[0][now.x+now.y].size())
				ans=min(ans,(dl[0][now.x+now.y][p]-now.x)*10);
		}
	}
	if(ans!=INF)
		cout << ans << endl;
	else
		cout << "SAFE" << endl;
	return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,q;

int main(){
  cin >> n >> q;
  string prev = "kogakubu10gokan";
  bool fin = false;
  rep(i,n){
    int year; string name;
    cin >> year >> name;
    if( q < year && !fin ) {
      cout << prev << endl;
      fin = true;
    }
    prev = name;
  }
  if( !fin ) cout << prev << endl;
  return 0;
}

Measured memory_bytes: 1208
table = []
while True:
    w = list(input())
    if w[0] == '-':
        break
    string = ''
    number = int(input())
    for i in range(number):
        shuffle = int(input())
        for j in range(shuffle):
            w.append(w.pop(0))
    for k in range(len(w)):
        string += w.pop(0)
    table.append(string)
for i in table:
    print(i)



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

using namespace std;
using ll=long long;
int main(){
   int n;cin >> n;
   int co=0;
   int k=1;
   for(int i=0;i<n;i++){
    int a;
    cin >> a;
    if(a==k){
            co++;
            k++;
    }
   }
   if(co==0)cout << -1<< endl;
   else cout << n-co<< endl;
    return 0;
}


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

int main() {
	int n, k, tmp;
	cin >> n >> k;
	string s = "[^";
	for(int i=0; i<k; ++i) {
		cin >> tmp;
		s += to_string(tmp);
	}
	s += "]+";
	regex re(s);
	while(!regex_match(to_string(n), re)) ++n;
	cout << n << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m,p,countWA=0,countAC=0;
    string s;
    cin>>n>>m;
    std::deque<int> deq(n+1,0);
    std::vector<vector<int>> vec(n+1,vector<int>(1,0));
    for (int i=0;i<m;i++) {
        cin>>p>>s;
        if (deq[p]==0&&s=="AC") {
            countAC++;
            countWA+=vec[p][0];
            deq[p]=1;
        } else if (deq[p]==0&&s=="WA") {
            vec[p][0]++;
        }
    }
    cout<<countAC<<" "<<countWA<<endl;
}


Measured memory_bytes: 6144
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int mode = 998244353;
const int maxn = 3e3  + 7;
int dp[maxn],a[maxn];
int main()
{
	int n,s;
	cin >> n >> s;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	ll ans = 0;
	for(int i = 1;i <= n;i++){
		dp[0]++;
		for(int j = s;j >= a[i];j--){
			dp[j] = (dp[j] + dp[j - a[i]]) % mode;
		}
		ans = (ans + dp[s]) % mode;
	}
	cout << ans << endl;
	return 0;
 } 

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

  typedef long long int ll;
  typedef pair<int,int> pi;
  typedef pair<ll,ll> pll;
  typedef vector<int> vi;
  typedef vector<ll> vll;
  typedef vector<pi> vpi;
  typedef vector<pll> vpll;

  #define  ff           first
  #define  ss           second
  #define  pb           push_back
  #define  IOS          ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  #define  D(x)         cout << #x << " - " << x << endl;
  #define  D2(x)        cout << "[" << #x << ": "; for(auto it:x) cout << it << " "; cout << "]" << endl;
  #define  all(x)       (x).begin(), (x).end()
  #define  D2p(x)       cout << #x << " ~ [ "; for(auto n: x) cout << n.first << "-" << n.second << " / "; cout << "]" << endl;
  #define  ps(x,y)      fixed<<setprecision(y)<<x
  #define  rep(i,a,b)   for(ll i=a ; i<b ; ++i)

  const ll MOD = 1e9 + 7;
  const ll INF = 1e18;
  const ll maxn = 1e6 + 4;


  void solve(){
    ll a,b;
    cin >> a >> b;
    ll ansa = 0,ansb=0;
    ansa = (b%4==0?b:(b%4==1?1:((b%4==2)?b+1:0)));
    b = a-1;
    ansb = (b%4==0?b:(b%4==1?1:((b%4==2)?b+1:0)));
    cout << (ansa^ansb);
  }

  int main(){
    IOS
    solve();
    cerr <<endl <<"[ Time : " << (float)clock() / CLOCKS_PER_SEC << " secs ]" << endl;
  }

// integer overflow
// remember to clear visited array
// take input as vector<string> while using grid
// don't assign after modifying


Measured memory_bytes: 3772
// AOJ 0593
#include <iostream>
#include <cstdio>

using namespace std;

int main(void)
{
	int n, m, b;
	int cost[1280] = {0}, vote[1280] = {0};

	cin >> n >> m;
	for (int i = 0; i < n; i++){
		scanf("%d", &cost[i]);
	}
	for (int i = 0; i < m; i++){
		scanf("%d", &b);
		for (int j = 0; j < n; j++){
			if (b >= cost[j]){
				vote[j]++;
				break;
			}
		}
	}

	int ret[2] = {-1, -1};
	for (int i = 0; i < n; i++){
		if (ret[0] < vote[i]){
			ret[0] = vote[i];
			ret[1] = i + 1;
		}
	}
	cout << ret[1] << endl;

	return 0;
}

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

using int64 = long long;

int main() {
  int64 q, h, s, d;
  cin >> q >> h >> s >> d;
  if (q * 2 < h)
    h = q * 2;
  if (h * 2 < s)
    s = h * 2;
  int64 n;
  cin >> n;
  if (s * 2 < d) {
    cout << n * s << "\n";
  } else {
    cout << (n / 2) * d + (n % 2) * s << "\n";
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,k;
	cin>>n>>k;
	puta(n-k+1);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;

int gcd(int a,int b) {
    if(a < b) swap(a,b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

int main() {
    int n;
    cin >> n;
    int ans;
    cin >> ans;
    rep(i,n-1) {
        int a;
        cin >> a;
        ans = gcd(ans,a);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
const int MAXN = 40;

using namespace std;

struct Card
{
	char suit;
	int value;
};

void BubbleSort(Card C[], int N);
void SelectionSort(Card C[], int N);
bool is_stable(Card C1[], Card C2[], int N);
void printCards(Card C[], int N);

int main()
{
	int n;
	scanf("%d", &n);
	while (getchar() != '\n')
	{
		continue;
	}

	Card C1[MAXN];
	Card C2[MAXN];

	for (int i = 0; i < n; i++)
	{
		C1[i].suit = getchar();
		scanf("%d", &C1[i].value);
		getchar();
		C2[i].suit = C1[i].suit;
		C2[i].value = C1[i].value;
	}

	BubbleSort(C1, n);
	SelectionSort(C2, n);

	printCards(C1, n);
	printf("Stable\n");
	printCards(C2, n);
	if (is_stable(C1, C2, n))
	{
		printf("Stable\n");
	}
	else
	{
		printf("Not stable\n");
	}
	

	return 0;
}

void BubbleSort(Card C[], int N)
{
	Card temp;

	for (int i = 0; i < N; i++)
	{
		for (int j = N - 1; j > i; j--)
		{
			if (C[j].value < C[j - 1].value)
			{
				temp = C[j];
				C[j] = C[j - 1];
				C[j - 1] = temp;
			}
		}
	}
}

void SelectionSort(Card C[], int N)
{
	Card temp;

	for (int i = 0; i < N; i++)
	{
		int minj = i;
		for (int j = i; j < N; j++)
		{
			if (C[j].value < C[minj].value)
			{
				minj = j;
			}
		}
		temp = C[i];
		C[i] = C[minj];
		C[minj] = temp;
	}
}

bool is_stable(Card C1[], Card C2[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (C1[i].suit != C2[i].suit)
		{
			return false;
		}
	}

	return true;
}

void printCards(Card C[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (i != N - 1)
		{
			printf("%c%d ", C[i].suit, C[i].value);
		}
		else
		{
			printf("%c%d\n", C[i].suit, C[i].value);
		}
	}
}



Measured memory_bytes: 2712
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}


struct SegTree{
     vector<int> data_;
     static int operation(int op1, int op2){
         return max(op1 , op2);
     }
     SegTree(const vector<ll>& src){
         data_.resize(src.size() * 2);
         for(size_t i = 0; i < src.size(); i++) update(i, src[i]);//ここ大きい順に作ればO(n)でいける
     }
     int query(size_t begin, size_t end, int init) const{
         begin += data_.size()/2; end += data_.size()/2;
         for(; begin < end; begin /= 2, end /= 2){
             if(begin & 1) init = operation(init, data_[begin++]);
             if(end & 1) init = operation(init, data_[end-1]);
         }
         return init;
     }
     void update(size_t pos, int val){
         pos += data_.size()/2;
         data_[pos] = val;
         while((pos /= 2) > 0){
             data_[pos] = operation(data_[pos*2], data_[pos*2+1]);
         }
     }
 };

/*
繋がってるロボが連鎖的に反応する

8
1 2
2 2
3 1
4 2
5 1
6 1
7 2
8 1
*/

ll n,mod=998244353,dp[200010]={};
V<ll> r(200010);
pair<ll,ll> p[200010];
set<pair<ll,ll>> s;

int main(void){
	// SegTree sgt(vector<ll>(3,0));
	// sgt.update(0,10);
	// sgt.update(1,20);
	// sgt.update(2,15);
	// cout<<sgt.query(0,1,0)<<endl;
	// cout<<sgt.query(1,2,0)<<endl;
	cin>>n;
	rep(i,n){
		ll a,b;
		cin>>a>>b;
		p[i] = {a,b};
	}
	sort(p,p+n);
	rep(i,n)r[i]=n-1;
	rep(i,n){
		for(auto itr = s.begin(); itr != s.end(); itr++){
			auto a = *itr;
			if(a.first <= p[i].first){
				r[a.second] = i-1;
				s.erase(itr);
			}else{
				break;
			}
		}
		s.insert({p[i].first+p[i].second, i});
	}
	SegTree sg(r);
	irep(i,n){
		ll r2=r[i];
		while(1){
			ll r3=sg.query(i,r2+1,0);
			if(r2==r3)break;
			r2=r3;
		}
		sg.update(i,r2);
		r[i]=r2;
	}
	dp[n]=1;
	irep(i,n)dp[i] = (dp[i+1]+dp[r[i]+1]) % mod;

	// rep(i,n)cerr<<r[i]<<" ";
	// cerr<<endl;
	// rep(i,n)cerr<<dp[i]<<" ";
	// cerr<<endl;
	cout<<dp[0]<<endl;
	return 0;
}

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

typedef long long ll;
#define MAXN 200010
#define X first
#define Y second

priority_queue<ll> Q;

int main()
{
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);
	
	int N; ll del = 0, res = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
	{
		ll x;
		scanf("%lld", &x);
		Q.push(x);
	}
	while (true)
	{
		ll x = Q.top() + del;
		Q.pop();
		if (x  < N) break;
		
		ll k = x / N;
		del += k, res += k;
		Q.push(x - k * N - del);
	}
	printf("%lld\n", res);
	
	return 0;
}

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

ll w[310];
ll dp[310][310];
vector<ll> v;

void solve(){

    while(true){
    ll n;
    cin >> n;
    if(n==0) break;
    rep(i,n){
        cin >> w[i];
    }
    rep(i,310){
        rep(j,310){
            dp[i][j]=0;
        }
    }

    for(ll i=1; i<n; i++){
        for(ll j=0; j<n-i; j++){
            ll x=j;
            ll y=i+j;
            if(dp[x+1][y-1]==y-x-1&&abs(w[x]-w[y])<=1){
                dp[x][y]=y-x+1;
            }
            else{
                ll ans = 0;
                rep(k,y-x){
                    ans=max(ans, dp[x][x+k]+dp[x+k+1][y]);
                }
                dp[x][y]=ans;
            }
        }
    }

    /*
    rep(i,n){
        rep(j,n){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    v.emplace_back(dp[0][n-1]);


    }

    for(auto e:v){
        cout << e << endl;
    }

}


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



Measured memory_bytes: 3880
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define day_start 360
#define day_end 1080
#define one_day 1440


char can_weekday[10],can_time[10];
int egg_time,num_egg,stage_time,NUM,num_stage;
bool ok_week[7];

bool is_OK(int weekday,int time,int add_time){

	if(!ok_week[weekday])return false;

	int start_time = time,start_day = weekday;
	int end_time,end_day;
	end_time = start_time+add_time;

	if(end_time >= one_day){
		end_time -= one_day;
		end_day = weekday+1;
		end_day %= 7;
	}else{
		end_day = weekday;
	}

	switch(can_time[0]){
	case 'A':
		return ok_week[end_day];
	case 'D':
		if(start_time < day_start || start_time >= day_end)return false;
		if(end_time < day_start || end_time >= day_end)return false;
		if(end_day != start_day)return false;

		return true;
	case 'N':
		if(start_time >= day_start && start_time < day_end)return false;
		if(end_time >= day_start && end_time < day_end)return false;

		if(start_time >= day_end){
			if(ok_week[end_day] == false)return false;
		}else{ //start_time < day_start
			if(end_time > day_end || start_day != end_day)return false;
		}
		return true;
	}
}

void func(){

	//孵化可能な曜日を設定する
	for(int i = 0; i < 7; i++)ok_week[i] = false;

	switch(can_weekday[0]){
	case 'A':
		for(int i = 0; i < 7; i++)ok_week[i] = true;
		break;
	case 'S':
		if(can_weekday[1] == 'u'){ //日曜
			ok_week[0] = true;
		}else{
			ok_week[6] = true;
		}
		break;
	case 'M':
		ok_week[1] = true;
		break;
	case 'T':
		if(can_weekday[1] == 'u'){
			ok_week[2] = true;
		}else{
			ok_week[4] = true;
		}
		break;
	case 'W':
		ok_week[3] = true;
		break;
	case 'F':
		ok_week[5] = true;
		break;
	}

	double P = 1.0/(double)NUM;
	double all_NOT = pow(1.0-P,num_egg); //孵化可能な状態で、全ての卵が孵化しない確率
	double ans = 0.0,tmp_sum;

	int day,current_time;

	for(int start_day = 0; start_day < 7; start_day++){
		for(int start_time = 0; start_time < one_day; start_time++){

			tmp_sum = 1.0;
			day = start_day;
			current_time = start_time;

			for(int i = 0; i < num_stage; i++){

				if(is_OK(day,current_time,egg_time)){
					tmp_sum *= all_NOT;
				}

				current_time += stage_time;
				if(current_time >= one_day){
					day++;
					day %= 7;
					current_time -= one_day;
				}
			}
			ans = max(ans,1.0-tmp_sum);
		}
	}
	printf("%.10lf\n",ans);
}

int main(){

	while(true){
		scanf("%d %d %d %s %s %d %d",&egg_time,&num_egg,&stage_time,can_weekday,can_time,&NUM,&num_stage);
		if(egg_time == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int l,r;
  int n = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> l >> r;
    n += r - l + 1;
  }
  
  cout << n << endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())

s = []
for i in range(m):
    tmp = list(map(int, input().split()))
    s.append(tmp[1:])

p = list(map(int, input().split()))

ans = 0
for j in range(2**n):
    tmp_sw = bin(j)[2:].zfill(n)
    #print(tmp_sw)

    break_on = 0
    for k in range(m):
        tmp = 0
        #print(s[k])
        for h in s[k]:
            if tmp_sw[h-1] == '1':
                tmp += 1
        #print(tmp)
        if tmp % 2 != p[k]:
            break_on = 1
    
    if break_on == 0:
        ans += 1

print(ans)



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

void fnInput(int& rnShtHand, int& rnLngHand, int& rnHour, int& rnMinute)
{
  cin >> rnShtHand >> rnLngHand >> rnHour >> rnMinute;
}

double fnClockHandsDist(int nShtHand, int nLngHand, int nHour, int nMinute)
{
  static const double pi = 3.141592653589793;

  double nShtAngl = (nHour + (nMinute / 60.0)) / 12.0 * 360;
  double nLngAngl = (nMinute / 60.0) * 360;
  double nDiffAngl = abs(nShtAngl - nLngAngl);
  if (nDiffAngl > 180)
    nDiffAngl = 360 - nDiffAngl;

  double nHandsDist = nShtHand * nShtHand + nLngHand * nLngHand 
                      - 2 * nShtHand * nLngHand * cos(2 * pi * nDiffAngl / 360);
  return sqrt(nHandsDist);
}
  
int main()
{
  int nShtHand, nLngHand, nHour, nMinute;

  fnInput(nShtHand, nLngHand, nHour, nMinute);
  cout << fixed << setprecision(10) << fnClockHandsDist(nShtHand, nLngHand, nHour, nMinute);
  cout << endl;

  return 0;
}

Measured memory_bytes: 4264
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 5005
#define lowbit(o) o&(-o)
using namespace std;
int i,j,k,l,s,n,m,R[N],L[N],q[N],ans,G[N],r;
int a[N],b[N],test,qq[N],f[N];
char c[N];
inline bool cmp(int x,int y) {
	return R[x]<R[y];
}
inline void Sort() {
	for (int i=0;i<=n+1;i++) f[i]=0;
	for (int i=1;i<=r;i++) f[R[q[i]]+1]++;
	for (int i=1;i<=n+1;i++) f[i]+=f[i-1];
	for (int i=1;i<=r;i++) qq[++f[R[q[i]]]]=q[i];
	for (int i=1;i<=r;i++) q[i]=qq[i];
}
int main() {
test=1;
	while (test--) {
		scanf("%s",c+1);
		n=strlen(c+1);
		for (i=1;i<=n;i++) a[i]=c[i]-48,L[i]=R[i]=100000000;
		scanf("%s",c+1);
		for (i=1;i<=n;i++) b[i]=c[i]-48;
		for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (b[j]) L[i]=min(L[i],(i-j+n)%n),R[i]=min(R[i],(j-i+n)%n);
		int s1=0,s2=0;
		for (i=1;i<=n;i++) s1|=a[i],s2|=b[i];
		if (!s2) {
			if (!s1) puts("0");
			else puts("-1");
			continue;
		}
		ans=100000000;
		for (i=1;i<=n;i++) {
			r=0; k=i;
			for (j=1;j<=n;j++) {
				if (a[k]!=b[j]) q[++r]=k;
				k%=n; k++;
			}
			//sort(q+1,q+1+r,cmp);
			Sort();
			G[r+1]=0;
			for (k=r;k;k--) G[k]=max(G[k+1],L[q[k]]);
			for (k=0;k<=r;k++) {
				//workL:
				ans=min(ans,(R[q[k]]+max((i-j+n)%n,G[k+1]))*2-(i-j+n)%n+r);
				//workR:
				ans=min(ans,(G[k+1]+max((j-i+n)%n,R[q[k]]))*2-(j-i+n)%n+r);
			}
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>
#include <sstream>
#include <iomanip>

using namespace std;

#define PI 3.14159265359

int main()
{
	string S;
	cin >> S;

	int N = S.length() + 1;

	vector<int> Us(N,0);
	vector<int> Ds(N,0);

	int u = 0;
	int d = 0;

	for(int ni = 0; ni < N - 1; ni++){
		if(S[ni] == '<'){
			u++;
		}else{
			u = 0;
		}
		Us[ni+1] = u;
	}

	for(int ni = N - 2 ; ni >= 0; ni--){
		if(S[ni] == '>'){
			d++;
		}else{
			d = 0;
		}
		Ds[ni] = d;
	}

	vector<int> As(N,0);
	long long sum = 0;
	for (int ni = 0; ni < N; ni++){
		As[ni] = max(Us[ni], Ds[ni]);
		sum += As[ni];
	}


	cout << sum;

	return 0;
}



Measured memory_bytes: 6788
#include <cstdio>
#include <cstring>

int N,Q;
int map[300005]={};
int  cal[300005]={};
int main(void){
	memset(cal,-1,sizeof(cal));
	int i,j,a,b,c;
	scanf("%d%d",&N,&Q);
	for(i=0;i<N;i++){
		scanf("%d",&a);
		map[a]=1;
	}
	a=-1;
	for(i=0;i<300005;i++){
		if(map[i]==1)a=i;
		cal[i]=a;
	}

	int ma,q;
	for(c=0;c<Q;c++){
		scanf("%d",&q);
		ma=0;
		i=300000;
		while(cal[i]!=-1 && i>=0){
			i=cal[i];
			ma=(ma<(i%q))?(i%q):ma;
			i=i-(i%q)-1;
		}
		printf("%d\n",ma);
	}
	return 0;
}
			

Measured memory_bytes: 3376
#include <iostream>
#include <vector>
using namespace std;
 
class Dice{
public:
    long r[6];
    Dice(){};
    void roll(long a, long b, long c, long d){swap(r[a], r[b]);swap(r[b], r[c]);swap(r[c], r[d]);}
    void spin(char c){if (c == 'W') roll(0, 2, 5, 3); else roll(0, 1, 5, 4);}
};
 
int main(){
    char SWS[8]={"NNNWNNN"};
    int n;
    cin >> n;
    vector<Dice> D(n);
    for (int i = 0; i < n ; i++) for (int j = 0; j < 6; j++) cin >> D[i].r[j];
    for (int i = 0; i < n - 1; i++){
        for (int j = i + 1; j < n; j++){
            for (int k = 0; k < 8; k++){
                if (D[i].r[1] == D[j].r[1]) break;
                D[j].spin(SWS[k]);
            }
            for (int k = 0; k < 4; k++){
                if (D[i].r[0] == D[j].r[0]){
                    if (D[i].r[1] == D[j].r[1] && D[i].r[2] == D[j].r[2] && D[i].r[3]==D[j].r[3] && D[i].r[4] == D[j].r[4] && D[i].r[5] == D[j].r[5]){
                        cout << "No" << endl; return 0;
                    }
                }
                D[j].spin('W');
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define PB push_back
#define MP make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<29)
#define LLINF (1LL<<60)
#define MOD 1000000007
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;
typedef pair<int, int> P;

int main() {
    string s;
    ll c1 = 0, c2 = 0;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'W') {
            c1 += i;
            c2++;
        }
    }
    if (c2 == 0)cout << 0 << endl;
    else cout << c1 - (c2 - 1)*c2 / 2 << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
int main(void){
   char s[200003];
   int i;
   
   scanf("%s", s);
   for (i = 0; s[i] != 0; i++)
   {
       if (s[i] == '?')
        s[i] = 'D';
   }
   printf("%s", s);
   return (0);
}


Measured memory_bytes: 1880
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb(x) push_back(x)
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a); i>=(b);i--)
 
const int maxn = 2e5 + 5;
const int maxm = 5000 + 5;
const int MOD = 1e9 + 7;

vector<int>v[maxn];
ll qi[maxn];
int n,q;
  
void  dfs(int u, int father)
{
    rep(i,0,v[u].size() - 1){
        int vv = v[u][i];
        if(vv != father) {
            qi[vv] += qi[u];
            dfs(vv, u);
        }
    }
}

int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   //#ifndef ONLINE_JUDGE 
   //freopen("input.txt", "r", stdin);
   //#endif // ONLINE_JUDGE  
   cin >> n >> q;
   rep(i,1,n - 1){
      int a,b;
      cin >> a >> b;
      v[a].push_back(b);
      v[b].push_back(a);
   }
   rep(i,1,q) {
        int a,b;
        cin >> a >> b;
        qi[a] += b;
   }
   dfs(1,0);
   rep(i,1,n){
      cout << qi[i] <<" ";
   }
   return 0;
}

Measured memory_bytes: 27392
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    return


def main():
    A, B = map(int, input().split())
    if 1 <= A <= 9 and 1 <= B <= 9:
        print(A * B)
    else:
        print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3952
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k;
    cin >> k;
    cout << 50 << endl;//0,1,...49 0..47,48,50 0...47,49,50
    rep(i,50){
        cout << i+k/50+(k%50+i>=50? 1 : 0) << (i==50? '\n' : ' ' );
    }
}

Measured memory_bytes: 3660
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ProgEdu solver = new ProgEdu();
        solver.solve(1, in, out);
        out.close();
    }

    static class ProgEdu {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();

            if (n == 1) {
                out.println("Hello World");
            } else {
                int a = in.nextInt();
                int b = in.nextInt();
                out.println(a + b);
            }
        }

    }
}



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

int n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int val;
        cin >> val;
        ans += (val % 2 && i % 2);
    }
    cout << ans << '\n';
    return 0;
}


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

int n,m;
int adj[305][305];
int idx[305];

int cnt[305];
bool uda[305];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&adj[i][j]);
			if(j==1) cnt[adj[i][j]]++;
		}
		idx[i] = 1;
	}
	int ans = 3000;
	for(int i=1;i<=m;i++){
		int tmp = 0;
		int idd = 0;
		for(int j=1;j<=m;j++){
			if(tmp < cnt[j]){
				tmp = cnt[j];
				idd = j;
			}
		}
//		cout << ">> " << tmp << " idd " << idd << endl;
		ans = min(ans,tmp);
		uda[idd] = 1;
		if(i==m) break;
		for(int j=1;j<=n;j++){
			if(uda[adj[j][idx[j]]]){
				cnt[adj[j][idx[j]]]--;
				while(uda[adj[j][idx[j]]]){
					idx[j]++;
				}
				cnt[adj[j][idx[j]]]++;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 640
class Daise:
    def __init__(self, info_list):
        self.T = info_list[0]
        self.S = info_list[1]
        self.E = info_list[2]
        self.W = info_list[3]
        self.N = info_list[4]
        self.B = info_list[5]
    
    def change(self, axis):
        if axis == 'S':
            self.T, self.B, self.S, self.N = self.N, self.S, self.T, self.B
        
        elif axis == 'E':
            self.T, self.B, self.E, self.W = self.W, self.E, self.T, self.B
        
        elif axis == 'W':
            self.T, self.B, self.W, self.E = self.E, self.W, self.T, self.B
        
        elif axis == 'N':
            self.T, self.B, self.N, self.S = self.S, self.N, self.T, self.B
        
        elif axis == 'Turn':
            self.S, self.E, self.N, self.W = self.E, self.N, self.W, self.S
    

    def output(self):
        return [self.T, self.S, self.E, self.W, self.N, self.B]
    

    def set_info(self, top, front):
        if front in (self.T, self.B):
            self.change("S")

        while self.S != front:
            self.change('Turn')
 
        while self.T != top:
            self.change('E')


def compair(A, B):
    for _ in range(4):
        for _ in range(4):
            if A.output() == B.output():
                return 'Yes'
            for _ in range(4):
                if A.output() == B.output():
                    return 'Yes'
                B.change('Turn')
            B.change('S')
        B.change('W')
    return 'No'


if __name__ == '__main__':
    inputs = int(input())
    
    all_daise = [Daise(list(map(str, input().split()))) for _ in range(inputs)]
    result = [compair(all_daise[0], i) for i in all_daise[1:]]

    if 'Yes' in result:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 5620
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, a, b; cin >> n >> a >> b;
    ll sum = 0;
    sum += n / (a + b) * a;
    n -= n / (a + b) * (a + b);
    if (n <= a) {
        sum += n;
    } else {
        sum += a;
    }
    cout << sum << endl;
    return 0;
}

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

long long N, A[100009], B[100009], dp[100009], fact[5009], ans[5009][5009][2], mod = 1000000007;
vector<int> X[100009]; int nr[5009][5009];

void dfs(int pos) {
	dp[pos] = 1;
	for (int i = 0; i < X[pos].size(); i++) {
		if (dp[X[pos][i]] >= 1) continue;
		dfs(X[pos][i]);
		dp[pos] += dp[X[pos][i]];
	}
}

void init() {
	fact[0] = 1; for (int i = 1; i <= N; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			if (i == 0 || j == 0) nr[i][j] = 1;
			else nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % mod;
		}
	}
}

long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return nr[r][n - r];
}

int main() {
	cin >> N; init();
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	dfs(1); vector<int> vec;
	for (int j = 1; j <= N; j++) {
		int sum = N - 1; bool flag = true;
		for (int k = 0; k < X[j].size(); k++) {
			if (dp[j] <= dp[X[j][k]]) continue;
			if (dp[X[j][k]] > (N / 2)) flag = false;
			sum -= dp[X[j][k]];
		}
		if (sum > (N / 2)) flag = false;
		if (flag == true) vec.push_back(j);
	}

	if (vec.size() == 2) {
		cout << (fact[N / 2] * fact[N / 2]) % mod << endl;
	}
	else {
		vector<int> D; int sum = N - 1;
		for (int i = 0; i < X[vec[0]].size(); i++) {
			if (dp[X[vec[0]][i]] < dp[vec[0]]) { D.push_back(dp[X[vec[0]][i]]); sum -= D[D.size() - 1]; }
		}
		D.push_back(sum);

		ans[0][0][0] = 1;
		for (int i = 0; i < D.size(); i++) {
			for (int j = 0; j <= N; j++) {
				if (ans[i][j][0] + ans[i][j][1] == 0) continue;
				for (int k = 0; k <= D[i]; k++) {
					long long K = ncr(D[i], k); K *= K; K %= mod; K *= fact[k]; K %= mod;
					int L = 0; if (k >= 1) L = 1;
					ans[i + 1][j + k][(k + 0) & 1] += ans[i][j][0] * K; ans[i + 1][j + k][(k + 0) & 1] %= mod;
					ans[i + 1][j + k][(k + 1) & 1] += ans[i][j][1] * K; ans[i + 1][j + k][(k + 1) & 1] %= mod;
				}
			}
		}

		long long ret = 0;
		for (int i = 0; i <= N; i++) {
			ret += ans[D.size()][i][0] * fact[N - i];
			ret -= ans[D.size()][i][1] * fact[N - i];
			ret += mod * mod; ret %= mod;
		}
		cout << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 494080
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

pair<int, int> dir[8] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { 0, 1 } };

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

	int W, H, N;
	cin >> W >> H >> N;

	vector<vector<int>> map_info(W, vector<int>(H, 1));

	for (int i = 0; i < N; i++)
	{
		int x, y, a;
		cin >> x >> y >> a;

		if (a == 1)
		{
			for (int i = 0; i < x; i++)
			{
				for (int j = 0; j < H; j++)
				{
					map_info[i][j] = 0;
				}
			}
		}
		else if (a == 2)
		{
			for (int i = x; i < W; i++)
			{
				for (int j = 0; j < H; j++)
				{
					map_info[i][j] = 0;
				}
			}
		}
		else if (a == 3)
		{
			for (int i = 0; i < W; i++)
			{
				for (int j = 0; j < y; j++)
				{
					map_info[i][j] = 0;
				}
			}
		}
		else if (a == 4)
		{
			for (int i = 0; i < W; i++)
			{
				for (int j = y; j < H; j++)
				{
					map_info[i][j] = 0;
				}
			}
		}
	}

	int result = 0;
	for (int i = 0; i < W; i++)
	{
		for (int j = 0; j < H; j++)
		{
			result += map_info[i][j];
		}
	}

	cout << result;

	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        int max = Math.max(a, Math.max(b, c));

        int ans = 0;
        int r = 0;
        if (a < max) {
            int d = max - a;
            ans += d / 2;
            r += d % 2;
        }

        if (b < max) {
            int d = max - b;
            ans += d / 2;
            r += d % 2;
        }

        if (c < max) {
            int d = max - c;
            ans += d / 2;
            r += d % 2;
        }

        if (r == 0) {
            System.out.println(ans);
        } else if (r == 1) {
            System.out.println(ans + 2);
        } else {
            System.out.println(ans + 1);
        }
    }
}


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

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

void ex() {
	cout << 0 << "\n";
	exit(0);
}

const ll MOD = 1e9 + 7;
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
const int MAXN = 120000;

int was[MAXN];
int fl[MAXN];
vector<int> vv;
int go[MAXN * 2];
vector<int> beds[MAXN];
int a[MAXN];
int cc[MAXN];
ll fc[MAXN];
ll bfc[MAXN];
int n;
int tm1;
int lst[MAXN];

void dfs1(int v) {
	if (was[v]) {
		if (lst[v] == tm1)
			fl[v] = 1;
		return;
	}
	was[v] = 1;
	lst[v] = tm1;
	dfs1(a[v]);
}

void dfs2(int v) {
	vv.push_back(v);
	was[v] = 1;
	if (!was[a[v]])
		dfs2(a[v]);
}

int dfs3(int v) {
	if (beds[v].size() >= 2)
		ex();
	int a = 1;
	for (int u: beds[v])
		a += dfs3(u);
	return a;
}

int main() {
	scanf("%d", &n);
	fc[0] = bfc[0] = 1;
	for (int i = 1; i <= n; ++i)
		fc[i] = (fc[i - 1] * i) % MOD, bfc[i] = pw(fc[i], MOD - 2);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i), --a[i];
		beds[a[i]].push_back(i);
	}
	for (int i = 0; i < n; ++i) {
		if (was[i])
			continue;
		++tm1;
		dfs1(i);
	}
	memset(was, 0, sizeof(was));
	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		if (was[i] || !fl[i])
			continue;
		vv.clear();
		dfs2(i);
		int f = 0;
		for (int i = 0; i < vv.size(); ++i) {
			if (beds[vv[i]].size() > 2)
				ex();
			go[i] = 0;
			for (int j: beds[vv[i]])
				if (!was[j])
					f = 1, go[i] = dfs3(j);
		}
		if (!f) {
			++cc[vv.size()];
		}
		else {
			for (int i = 0; i < vv.size(); ++i)
				go[i + vv.size()] = go[i];
			int lst = 0;
			for (int i = 0; i < vv.size(); ++i)
				if (go[i])
					lst = i;
			for (int i = vv.size(); i < 2 * vv.size(); ++i) {
				if (!go[i])
					continue;
				if (i - lst < go[i])
					ex();
				if (i - lst > go[i])
					ans = (ans * 2) % MOD;
				lst = i;
			}
		}
	}
	ll B2 = pw(2, MOD - 2);
	for (int i = 1; i <= n; ++i) {
		if (!cc[i])
			continue;
		ll go = 0;
		if (i != 1 && i % 2 == 1) {
			for (int j = 0; j * 2 <= cc[i]; ++j) {
				go = (go + pw(2, cc[i] - j * 2) * pw(i, j) % MOD * fc[cc[i]] % MOD * bfc[cc[i] - j * 2] % MOD * pw(B2, j) % MOD * bfc[j] % MOD) % MOD;
			}
		}
		else {
			for (int j = 0; j * 2 <= cc[i]; ++j) {
				go = (go + pw(i, j) % MOD * fc[cc[i]] % MOD * bfc[cc[i] - j * 2] % MOD * pw(B2, j) % MOD * bfc[j] % MOD) % MOD;
			}
		}
		ans = (ans * go) % MOD;
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 14072
# 数値の取得
c_list = list(map(int,input().split()))
l_cnt = len(c_list)

# 各計算結果の中で最大値を出力
calc_dic = {"add":int(c_list[0]),
            "sub":int(c_list[0]),
            "mul":int(c_list[0])}
for cnt in range(1,l_cnt,1):
    calc_dic["add"] = calc_dic["add"] + c_list[cnt]
    calc_dic["sub"] = calc_dic["sub"] - c_list[cnt]
    calc_dic["mul"] = calc_dic["mul"] * c_list[cnt]
print(max(calc_dic.values()))

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

int main(){
    long N, D, A; cin >> N >> D >> A;
    vector<pair<long, long>> monster;
    vector<long> damage(N+1, 0);
    for(int i=0; i<N; i++){
        long x, h; cin >> x >> h;
        monster.push_back(make_pair(x, h));
    }
    long count = 0;
    sort(monster.begin(), monster.end());
    for(int i=0; i<monster.size(); i++){
        if(damage[i]<monster[i].second){
            long pos = upper_bound(monster.begin(), monster.end(), 
                make_pair(monster[i].first+2*D+1, numeric_limits<long>::min()))
                - monster.begin();
            long d = ((monster[i].second - damage[i]) + A - 1)/A;
            damage[i] += d * A;
            damage[pos] -= d * A;
            count += d;
        }
        damage[i+1] += damage[i];
    }
    cout << count << endl;
}


Measured memory_bytes: 7536
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    string SA, SB, SC;
    cin >> SA >> SB >> SC;
    int SAL = SA.size();
    int SBL = SB.size();
    int SCL = SC.size();
    int x = 0, y = 0, z = 0;
    int winA = 0, winB = 0, winC = 0;
    char next = 'a';

    while(1) {
        if(next == 'a') {
            x++;
            if(SAL < x) {
                winA = 1;
                break;
            }
            next = SA[x-1];
        }
        else if(next == 'b') {
            y++;
            if(SBL < y) {
                winB = 1;
                break;
            }
            next = SB[y-1];
        }
        else if(next == 'c') {
            z++;
            if(SCL < z) {
                winC = 1;
                break;
            }
            next = SC[z-1];
        }
    }

    if(winA == 1) {
        cout << 'A';
    }
    else if(winB == 1) {
        cout << 'B';
    }
    else if(winC == 1) {
        cout << 'C';
    }
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<ll> vl;
typedef queue<int> qi;
typedef queue<ll> ql;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define pq priority_queue
#define rep(i,n) for (int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
int n,ans=0;
map<int,int> m;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++){
    	int x;
    	cin>>x;
    	if (m[x]==0){
    		m[x]=1;
    		ans++;
    	}
    	else{
    		m[x]=0;
    		ans--;
    	}
    }
    cout<<ans;
}

Measured memory_bytes: 4992
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;



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

	string s;
	cin >> s;
	while (s.back() == '0')s.pop_back();
	vector<vector<int>>dp(s.size() + 1, vector<int>(2, MOD));
	dp[0][0] = 0;
	dp[0][1] = 1;
	for (int i = 0; i < s.size(); i++) {
		dp[i + 1][0] = min(dp[i][0] + s[i] - '0',dp[i][1]+1+s[i]-'0');
		dp[i + 1][1] = min({ dp[i][1] + 9 - (s[i] - '0'), dp[i][0] + s[i] - '0' + 1 ,dp[i][1] + 1 + s[i] - '0' + 1 });
	}
	cout << min(dp.back()[0], dp.back()[1] + 1) << endl;
	return 0;
}


Measured memory_bytes: 55964
#N = int(input())
N,K = map(int,input().split())
a_list = list(map(int,input().split()))
mod = 10**9+7
ans_cnt = 0
for i in range(N):
    cnt_x = 0
    cnt_y = 0
    for j in range(N):
        if a_list[i] > a_list[j]:
            cnt_y += 1
            if j > i:
                cnt_x += 1
    ans_cnt += cnt_x*K
    ans_cnt = ans_cnt % mod
    ans_cnt += cnt_y*(K*(K-1))//2
    ans_cnt = ans_cnt % mod
print(ans_cnt)

Measured memory_bytes: 3188