akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

const int inf = INT_MAX;

// RMQ
struct SegTree {
    int n;
    vi v;

    int pow2fit(int sz){
        int ret = 1;
        while(ret < sz) ret *= 2;
        return ret;
    }

    SegTree(int sz){
        n = pow2fit(sz);
        v = vi(2 * n - 1, inf);
    }

    // v[a] := x
    void update(int a, int x){
        int idx = n - 1 + a;
        v[idx] = x;

        while(idx > 0){
            idx = (idx - 1) / 2;
            v[idx] = min(v[2 * idx + 1], v[2 * idx + 2]);
        }
    }

    // get min [a, b)
    int getmin(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;

        if(a >= r or l >= b) return inf;
        if(a <= l and r <= b) return v[k];

        return min(getmin(a, b, 2 * k + 1, l, (l + r) / 2),
                   getmin(a, b, 2 * k + 2, (l + r) / 2, r));
    }
};

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

    int n, Q; cin >> n >> Q;
    SegTree seg(n);

    rep(loop, Q){
        int op, x, y; cin >> op >> x >> y;
        if(op == 0){
            seg.update(x, y);
        }
        else {
            cout << seg.getmin(x, y + 1) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3940
// ABC 154-B
// 2020.2.9 bal4u

#include <stdio.h>
#include <string.h>

char S[105];

int main()
{
	int N;
	
	scanf("%s", S);
	N = strlen(S);
	while (N--) putchar('x');
	putchar('\n');
	return 0;
}


Measured memory_bytes: 128
N = int(input())
S = input()
ans = 0

for pin in range(0,1000):
  counter = 0
  for index in range(0, N):
    if str(pin).zfill(3)[counter] == S[index]:
      counter += 1
    if counter == 3:
      ans += 1
      break
    
print(ans)

Measured memory_bytes: 68128
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,m,u[100005],U[100005];
vector<int> v[100005],e[100005];
void dfs(int x){
    U[x]=1;
    for(int i=0;i<v[x].size();++i){
        int z=v[x][i];
        if(U[z]) continue;
        dfs(z);
    }
    int cnt=0;
    for(int i=0;i<e[x].size();++i)if(u[e[x][i]]!=1)++cnt;
    if(cnt&1)--cnt;
    for(int i=0;i<e[x].size();++i){
        if(u[e[x][i]]==2){
            u[e[x][i]]=1;
            --cnt;
            printf("%d %d\n",x,v[x][i]);
        }
    }
    for(int i=0;i<e[x].size();++i){
        if(u[e[x][i]]==0&&cnt){
            u[e[x][i]]=1;
            --cnt;
            printf("%d %d\n",x,v[x][i]);
            continue;
        }
        u[e[x][i]]=2;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].pb(y),v[y].pb(x);
        e[x].pb(i),e[y].pb(i);
    }
    if(m&1){
        puts("-1");
        return 0;
    }
    dfs(1);
    //system("pause");
    return 0;
}


Measured memory_bytes: 20864
N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 10 ** 5 + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans % MOD)


Measured memory_bytes: 32328
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <math.h>
#include <map>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll INF = 1000000000000000000LL;
using namespace std;

const int MOD = 1000000007;


//https://atcoder.jp/contests/abc047/tasks/abc047_b
int main(){
    int W,H,N;
    cin >> W >> H >> N;
    //塗りつぶす順番はどうでもよさそう
    
    vector <int> nuri(4);
    nuri[0] = 0;
    nuri[1] = W;
    nuri[2] = 0;
    nuri[3] = H;
    REP(i, N)
    {
        int x,y,a;
        cin >> x >> y >> a;
        --a;
        if(a == 0)
        {
            nuri[0] = max(nuri[0], x);
        }
        else if(a == 1)
        {
            nuri[1] = min(nuri[1], x);
        }
        else if(a == 2)
        {
            nuri[2] = max(nuri[2], y);
        }
        else
        {
            nuri[3] = min(nuri[3], y);
        }
    }

    //for(auto t: nuri)
    //{
    //    cout << t << endl;
    //}
    //0 i < nuri[0]まで塗られてる
    int res;

    res = max(0, nuri[1] - nuri[0]) * max(0, nuri[3] - nuri[2]);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
def a_to_b(A):
    c = [0] * N
    for i, a in enumerate(A):
        lb = max(0, i - a)
        c[lb] += 1
        ub = i + a + 1
        if ub < N:
            c[ub] -= 1
    tmp = 0
    B = []
    for ci in c:
        tmp += ci
        B.append(tmp)
    return B


N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = A
for _ in range(K):
    ans = a_to_b(ans)
    if sum(ans) == N ** 2:
        break

print(*ans)

Measured memory_bytes: 176992
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	int N; cin >> N; int M; cin >> M;
	vector<vector<int>>edges(N);
	vector<int>nums(N);
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		a--; b--;
		edges[a].push_back(b);
		nums[b]++;
	}
	queue<int>que;
	for (int i = 0; i < nums.size(); ++i) {
		if (!nums[i]) {
			que.push(i);
		}
	}
	bool flag = false;
	vector<int>anss;
	while (!que.empty()) {
		int now =que.front();
		anss.push_back(now);
		que.pop();
		if (!que.empty())flag = true;
		for (auto e : edges[now]) {
			nums[e]--;
			if (!nums[e]) {
				que.push(e);
			}
		}
	}
	for (auto a : anss) {
		cout << a + 1 << endl;
	}
	cout << flag << endl;
	return 0;
}

Measured memory_bytes: 3776
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 150

int diagonal2(int h, int w) {
	return h * h + w * w;
}

// (h1, w1)?????´????????¢???(h2, w2)?????´????????¢??????????°?????????£??????1????????????????????§???????????°0????????????
int less(int h1, int w1, int h2, int w2) {
	const int d1 = diagonal2(h1, w1);
	const int d2 = diagonal2(h2, w2);
	if(d1 != d2) return d1 < d2;
	return h1 < h2; // ??????
}

int main(void) {
	int h, w;
	int ans_h, ans_w;
	int i, j;

	while(1) {
		scanf("%d %d", &h, &w);
		if(h == 0 && w == 0) break;

		ans_h = MAX_SIZE + 1;
		ans_w = MAX_SIZE + 1;

		for(i = 1; i <= MAX_SIZE; ++i) {
			for(j = i + 1; j <= MAX_SIZE; ++j) {
				int h2 = i;
				int w2 = j;

				if(less(h, w, h2, w2) && less(h2, w2, ans_h, ans_w)) {
					ans_h = h2;
					ans_w = w2;
				}
			}
		}

		printf("%d %d\n", ans_h, ans_w);
	}

	return EXIT_SUCCESS;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vector<int>> vvi;
typedef unordered_map<int,int> uoii;
typedef unordered_map<string,int> uosi;

const int MOD = 1e9+7;

const int INF = 1e10;




int32_t main()
{
   
    IOS
    vi a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int c;
    cin>>c;
    cout<<a[c-1];


    return 0;
}


Measured memory_bytes: 256
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define  mod 998244353
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0};
int dy[8]={0,-1,0,1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(all(a));
    ll sum=0;
    for(int i=0;i<n;i++)
        sum+=a[i]-1;
    cout<<sum<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------






Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
   
    int x, y;
    cin>>x>>y;

    if(y%2==1){
        cout<<"No";
    }
    else{
        if(y< x*2 || y>x*4){
            cout<<"No";
        }
        else{
            cout<<"Yes";
        }
    }
    return 0;
}


Measured memory_bytes: 3636
/**
 * author: BueVonHun
 * More Info: https://github.com/Bue-von-hon
**/
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
int main(void) {
    fast_cin();

    int x;
    cin >> x;

    if (x<600) cout << 8 << endl;
    else if (x < 800) cout << 7 << endl;
    else if (x < 1000) cout << 6 << endl;
    else if (x < 1200) cout << 5 << endl;
    else if (x < 1400) cout << 4 << endl;
    else if (x < 1600) cout << 3 << endl;
    else if (x < 1800) cout << 2 << endl;
    else cout << 1 << endl;


    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FILE freopen("input.txt", "rt", stdin);freopen("output.txt", "wt", stdout);
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
const char nl = '\n';
int main(){
    FAST_IO;
    //FILE;
    int x,n;
    cin>>x>>n;
    int a[n+1];
    bool b[102]={false};
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[a[i]]=true;
    }
    int ans=-1;
    for(int i=x;i>=0;i--){
        if(!b[i]){
            ans=i;
            break;
        }
    }
    for(int i=x+1;i<=101;i++){
        if(!b[i]){
            if(ans==-1 || (i-x)<(x-ans)){
                ans=i;
            }
            break;
        }
    }
    cout<<ans<<nl;
    return 0;
}





Measured memory_bytes: 3648
#include <iostream>
#define maxn 100010
#define ll long long
const long long mod=1000000007;
#include<map>
using namespace std;
map<ll,ll>M;
ll i,n,k,cc,s=1,j;
ll a[maxn];
int main()
{
    a[0]=1;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>k;
        a[k]++;
    }
    if(n%2==0)
    {
        for(i=1;i<n;i+=2)
        {
            if(a[i]!=2) {cout<<'0'<<endl;break;}
            else if(i==n-1)
            {
                cc=n/2;
               for(j=1;j<=cc;j++)
                s=(s*2)%mod;
                cout<<s<<endl;
            }
        }
    }
    else if(n%2!=0)
    {
        for(i=0;i<n;i+=2)
        {
           if(a[i]!=2) {cout<<'0'<<endl;break;}
            else if(i==n-1)
            {
                cc=(n-1)/2;
                for(j=1;j<=cc;j++)
                      s=(s*2)%mod;
                cout<<s<<endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const double e=0.000025;
int main()
{
	int n;
	scanf("%d",&n);
	for(register double i=1;i<=3500;++i)
		for(register double j=1;j<=3500;++j)
		{
			double ans=(n*i*j/(4*i*j-n*j-n*i));
			if(ans<0)continue;
			if(ans-(double)((int)ans)<e)
			{
				cout<<i<<' '<<j<<' '<<(int)ans;
				return 0;
			}
		}
	return 0;
}

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

int main(){
  int a,b;
  cin>> a >>b;
  int r=0;
  for(int i=0;i<2;i++){
    if(a>b){
  	  r+=a;
      a--;
    }else{
      r+=b;
      b--;
    }
  }
  cout << r;
}

Measured memory_bytes: 256
import itertools as it
 
n=int(input())
A=input().split()
q=int(input())
M=input().split()
ans=[]
cnt=0
 
A=list(map(int,A))
M=list(map(int,M))
 
for i in range(len(A)):
    Ac=list(it.combinations(A,i+1))
    for j in Ac:
        ans.append(sum(j))
 
for i in M:
    flag=0
    for j in ans:
        if i==j:
            print("yes")
            flag=1
            break
    if flag==0:
        print("no")


Measured memory_bytes: 78048
#include<bits/stdc++.h>
using namespace std;
#define h first
#define w second
vector<pair<bool,pair<int,int> > >v;
int n,m,p,q,r,i;
void Vp(bool a,int b,int c){v.push_back(make_pair(a,make_pair(b,c)));}
int main(){
	while(cin>>n&&n){
	cin>>m>>p>>q>>r;v.clear();
	Vp(1,1,r);Vp(0,r+1,n);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		for(i=0;i<v.size();i++){
			int a=v[i].w.h,b=v[i].w.w;bool c=v[i].h;
			if(a<=x&&x<b){Vp(c,x+1,b);b=x;}
			if(a<=y&&y<b){Vp(c,y+1,b);b=y;}
			if(0<a&&b<=x)a+=n-x,b+=n-x;
			else if(x<a&&b<=y)a+=n-x-y,b+=n-x-y;
			else if(y<a&&b<=n)a-=y,b-=y;
			v[i].w.h=a,v[i].w.w=b;
		}
	}n=0;
	for(i=0;i<v.size();i++)if(v[i].h)n+=max(0,1+min(v[i].w.w,q)-max(v[i].w.h,p));
	cout<<n<<endl;
	}
	return 0;
}

Measured memory_bytes: 3280
import math
mod =1000000000+7

n,k = map(int, input().split())

def convcal(a,b):
  kekka = (math.factorial(a) //math.factorial(a-b)  ) // math.factorial(b) 
  return kekka

for i in range(1,k+1):
  #print(i)
  #print(k-1,i-1)
  #print(n-k+1,i)
  if n-k+1-i>=0:
    print(convcal(k-1,i-1)% mod * convcal(n-k+1,i) % mod)
  else:
    print(0)

Measured memory_bytes: 68184
#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(1)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	cnt = {}
	for i in range(len(a)):
		cnt[a[i]-1] = cnt.get(a[i]-1, 0) + 1
	for i in range(n):
		print(cnt.get(i, 0))


	


main()

Measured memory_bytes: 41208
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin>>s>>t;
  int total=0;
  for(int i=0; i<3; ++i) {
    if(s[i]==t[i]) {
      total++;
    }
  }
  cout<<total<<'\n';
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int32_t main()
    {
        IOS;
        ll k,l,n,m,q,m1,m2,flag=0,cnt,flag2,flag3,cnt2;
        int i,j;
        cin>>i>>j;
        cout<<max(0,i-2*j);



        return 0;

    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;
const int INF = 1001001001;


int main() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> b = a;
  sort(b.rbegin(),b.rend());
  rep(i,n){
    int ans = b[0];
    if(b[0]==a[i]) ans = b[1];
    cout << ans << endl;
    }
  return 0;
}

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

#define MAXN (200*1000 + 5)
typedef long long ll;
ll fen[MAXN];

ll get(int i) {
	ll ans = 0;
	for(; i > 0; i -= i & (-i)) {
		ans += fen[i];
	}
	return ans;
}

void upd(int i, ll v) {
	for(; i < MAXN; i += i & (-i)) {
		fen[i] += v;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, rad;
	ll damage;
	cin >> n >> rad >> damage;
	vector<pair<ll, ll>> monsters(n); // (pos, health)
	for(auto& p : monsters) {
		cin >> p.first >> p.second;
	}
	sort(monsters.begin(), monsters.end());
	
	upd(1, monsters[0].second);
	for(int i = 1; i < n; i++) {
		upd(i+1, monsters[i].second - monsters[i-1].second);
	}

	ll ans = 0;
	for(int i = 0; i < n; i++) {
		ll health = get(i+1);
		
		if(health <= 0) continue;
		ll need = (health + damage - 1)/damage;
		ll L = monsters[i].first;
		ll R = L + 2*rad;
		int j = lower_bound(monsters.begin(), monsters.end(), make_pair(R, -1), [](pair<ll, ll> a, pair<ll, ll> b) {
			return a.first < b.first;
		}) - monsters.begin();
		
		j = min(j, n-1);
		
		if(R < monsters[j].first) j--;
		
		upd(j+2, need*damage);
		upd(i+1, -need*damage);
		ans += need;
	}

	
	cout << ans << endl;
}


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

#define LL long long

int N, M;
LL sum = 0;

int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL); 
  cout.tie(NULL);

  cin >> N >> M;

  while(M--) {
    int A;
    cin >> A;
    sum += A;
  }

  (sum <= N) ? cout << N - sum << "\n" : cout << "-1\n";

  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
 
int main()
{
  int stoneNum;
  string stones;
  cin >> stoneNum >> stones;
  
  int iterW,iterR;
  int cntR = 0;
  int ans = 0;
  
  rep(i,stoneNum)
  {
    if(stones[i] == 'R') ++cntR;
  }
  rep(i,cntR)
  {
    if(stones[i] == 'W') ++ans;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main() {
    int N, K, S;
    scanf("%d%d%d", &N, &K, &S);
    for (int i = 1; i <= K; i ++) {
        printf("%d ", S);
    }
    S += S == 1000000000 ? -1 : 1;
    for (int i = K + 1; i <= N; i ++) {
        printf("%d ", S);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 1280
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
B = [A[-1]]
ans = 1
for a in reversed(A[:-1]):
    idx = bisect_right(B, a)
    if idx == ans:
        B.append(a)
        ans += 1
    else:
        B[idx] = a
print(ans)

Measured memory_bytes: 8732
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a == b)
		printf("Draw\n");
	else if(a == 1 || b == 1)
	{
		if(a == 1)
			printf("Alice\n");
		else
			printf("Bob\n");
	}
	else
	{
		if(a > b)
        	printf("Alice\n");
        else
    		printf("Bob\n");
	}
	return 0;
}



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

// macros
#define overload_rep(_1, _2 ,_3 ,name, ...) name
#define re_p(i, n) for(int i = 0; i < (n); ++i)
#define r_ep(i, x, y) for(int i = (x); i < (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, r_ep, re_p,)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do{ cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
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; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << setprecision(20);
    }
} iosetup;

// Let's get AC!
int main(){

    int x;
    cin >> x;

    cout << (x < 1200 ? "ABC\n" : "ARC\n");
    return 0;
    
}

Measured memory_bytes: 256
import sys
from itertools import accumulate
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    A = list(readnums())
    a = list(accumulate(A))
    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        ans += A[i] * (a[-1] - a[i])
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

#define int long long

const int N = (int)3e5, MOD = (int)1e9 + 7, INF = (int)3e18;

int a[N];
int pref[N], suff[N];

main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    int f = 0;
    for (int i = 1; i <= n - 1; ++i) {
        f += (a[i + 1] - a[i]);
    }
    for (int i = 2; i <= n; ++i) {
        pref[i] = pref[i - 1] + (a[i] - a[i - 1]);
    }
    for (int i = n - 1; i >= 1; i--) {
        suff[i] = suff[i + 1] + (a[i + 1] - a[i]);
    } 
    int s = INF;
    for (int i = 2; i <= n; ++i) {
        int res = pref[n] - pref[i];
        res += (k - a[n]) + a[1];
        res += pref[i - 1];   
        s = min(s, res);
    }
    int t = INF;
    for (int i = 1; i <= n - 1; ++i) {
        int res = suff[1] - suff[i];
        res += (k - a[n]) + a[1];
        res += suff[i + 1];
        t = min(t, res);
    }
    cout << min(f, min(s, t));
    return 0;
}

Measured memory_bytes: 6144
S = input()

left_count = [0] * (len(S) + 1)
right_count = [0] * (len(S) + 1)

S = "*" + S + "*"
cur_left_count = 0
cur_right_count = 0
for i in range(len(left_count)):
    if S[i] == "<":
        cur_left_count += 1
    else:
        cur_left_count = 0

    if S[-i-1] == ">":
        cur_right_count += 1
    else:
        cur_right_count = 0
    
    left_count[i] = cur_left_count
    right_count[-i-1] = cur_right_count

a =  [max(l, r) for l, r in zip(left_count, right_count)]

print(sum(a))

Measured memory_bytes: 88192
def main():
  S=input()
  char = list(S)
  char2= list(S)
  num =len(list(S))
  count=0
  
  
  if num ==1:
    print(0)
  
  else:
    for i in range(0,num,2):
      if(char[i]=='0'):
        char[i]='1'
        count=count+1
    for j in range(1,num,2):
      if(char[j]=='1'):
        char[j]='0'
        count=count+1
    count_even=count
  
    count=0
    for i in range(0,num,2):
      if(char2[i]=='1'):
        char2[i]='0'
        count=count+1
    for j in range(1,num,2):
      if(char2[j]=='0'):
        char2[j]='1'
        count=count+1
    count_odd=count

    print(min(count_even,count_odd))
  
main()

Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[3]={0};a[0]=1;
	string s;
	while(cin>>s){
		if(a[s[0]-'A']){
			a[s[0]-'A']=0;
			a[s[2]-'A']++;
		}
		else if(a[s[2]-'A']){
			a[s[2]-'A']=0;
			a[s[0]-'A']++;
		}
	}
	if(a[0])cout<<'A';
	if(a[1])cout<<'B';
	if(a[2])cout<<'C';
	cout<<endl;
}

Measured memory_bytes: 3096
s = int(input())

def func(x):
    if x % 2 == 0:
        return int(x / 2)
    else:
        return int(3 * x + 1)

a = [s]

i = 2
while True:
    b = func(a[i-1-1])
    if b in a:
        break
    a.append(b)
    i += 1
    
print(i)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef double ld;

int main()
{
	fastio
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n;
	cin >> n;

	vi arr(n);

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	// for(auto c : arr) cout<<c<<" ";
	// cout<<endl;

	vi dp(n, 0);

	dp[0] = 0, dp[1] = abs(arr[0] - arr[1]);

	// for(auto c : dp) cout<<c<<" ";
	// cout<<endl;

	for (int i = 2; i < n; i++)
	{
		// dp[i]=dp[i-1]+min(abs(arr[i-2]-arr[i]),abs(arr[i-1]-arr[i]));
		int a = dp[i - 2] + abs(arr[i - 2] - arr[i]), b = dp[i - 1] + abs(arr[i - 1] - arr[i]);

		if (a < b)
		{
			dp[i] = a;
		}
		else
		{
			dp[i] = b;
		}
	}

	cout << dp[n - 1];

	return 0;

}



Measured memory_bytes: 3644
import kotlin.math.sqrt

fun main(){
    val n = readLine()!!.split(" ")[0].toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
    val ansList = mutableListOf<Int>()
    var ans = 0
    for (i in 0 until n){
        if (i != n - 1 && a[i] == a[i + 1]){
            ansList.add(a[i])
            continue
        } else {
            val yakusu = mutableListOf<Int>()
            for (j in 1 until sqrt(a[i].toFloat()).toInt() + 1){
                if (a[i] % j == 0) {
                    yakusu += j
                    if (j != a[i] / j){
                        yakusu.add(a[i] / j)
                    }
                }
            }
            val kosuu = yakusu.size
            fun binary_search(key: Int) :Int {
                var left = -1
                var right = ansList.size
                while (right - left > 1){
                    var mid = (right + left) / 2
                    if (ansList[mid] <= key) left = mid
                    else right = mid
                }
                return left
            }
            var flag = 0
            for (j in 0 until kosuu){
                val x = binary_search(yakusu[j])
                if (x != -1 && ansList[x] == yakusu[j]){
                    flag = 1
                    break
                } else if (x != ansList.size - 1 && ansList[x + 1] == yakusu[j]){
                    flag = 1
                    break
                }
            }
            if (flag == 1){
                continue
            } else {
                ansList.add(a[i])
                ans++
            }
        }
    }
    println(ans)
}



Measured memory_bytes: 74928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N, K;

int main(void){
    
    scanf("%d %d", &N, &K);
    vector<ll> a, b;
    for(int i = 0; i < N; ++i){
        ll x; scanf("%lld", &x);
        if(x >= 0) a.push_back(x);
        else b.push_back(abs(x));
    }
    
    int kk = K;
    ll ans = LLONG_MAX;
    while(kk >= 0){
        int l = kk, r = K - kk; --kk;
        if(b.size() < l || a.size() < r) continue;
        
        if(l == 0) ans = min(ans, a[r - 1]);
        else if(r == 0) ans = min(ans, b[(b.size() - 1) - (l - 1)]);
        else ans = min(ans, min(a[r - 1], b[(b.size() - 1) - (l - 1)]) * 2 + max(a[r - 1], b[(b.size() - 1) - (l - 1)]));
    }
    printf("%lld\n", ans);
    
    return 0;
}

Measured memory_bytes: 1656
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

const int mapSize = 12;
char map[mapSize][mapSize];

void dfs(int w, int h)
{
	//?????????????????¨?????????'0'?????????
	map[w][h] = '0';

	//????????????????????????map???????????????????????°????????°????????????????§????
	if (w - 1 >= 0 && map[w - 1][h] == '1') dfs(w - 1, h);			//???
	if (h - 1 >= 0 && map[w][h - 1] == '1') dfs(w, h - 1);			//???
	if (w + 1 < mapSize && map[w + 1][h] == '1') dfs(w + 1, h);		//???
	if (h + 1 < mapSize && map[w][h + 1] == '1') dfs(w, h + 1);		//???
}

int main()
{
	while (true)
	{
		for (int h = 0; h < mapSize; ++h)
		{
			for (int w = 0; w < mapSize; ++w)
			{
				//??\???
				cin >> map[w][h];
				if (cin.eof()) return 0;
			}
		}

		int ans = 0;

		for (int h = 0; h < mapSize; ++h)
		{
			for (int w = 0; w < mapSize; ++w)
			{
				//map[w][h]????????°????????°??°????????????????????????????????????????????£????????????????????????????????????????????????
				if (map[w][h] == '1')
				{
					++ans;
					dfs(w, h);
				}
			}
		}

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

Measured memory_bytes: 1144
//#![warn(unused_imports)]
use proconio::input;
// use proconio::marker::Usize1;
use std::collections::HashMap;

fn main() {
  input! {
    X: i64,
  }
  
  let mut map: HashMap<i64, i64> = HashMap::new();
  
  for a in -200i64..200i64 {
    let val = a.pow(5);
    map.insert(val, a);
  }
    
  for a in -200i64..200i64 {
    let val = a.pow(5);
    let diff = X - val;
    if let Some(b) = map.get(&diff) {
      println!("{} {}", a, -1 * b);
      return
    }  
  }
}

Measured memory_bytes: 2192
n,k = list(map(int,input().split()))
l = [0]*(n+1)
for _ in range(k) :
    d = int(input())
    a = list(map(int,input().split()))
    for i in a :
        l[i] = l[i] + 1
print(len(list(filter(lambda x:x == 0,l)))-1)


Measured memory_bytes: 9204
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>
#include <stack>

using namespace std;
int z[1050];

int main()
{
	int a,b;
	cin >> a >> b;

	int sum = 1;
	z[0] = 1;
	for (int i = 2; i < 1000; ++i) {
		sum = sum + i;
		z[i - 1] = sum;
	}

	//cout << z[998];
	for (int j = 0; j < 999; ++j) {
		int tmp = z[j] - z[j-1];
		if (tmp == (b - a)) {
			cout << z[j] - b << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  while(true){
    cin >> H >> W;
    if(H==0&&W==0){
      break;
    }
    else{
      for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
          cout << "#";
        }
        cout << endl;
      }
      cout << endl;
    }
  }
  return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<P> w(n);
    rep(i,n) cin >> w[i].second >> w[i].first;
    ll t = 0;
    sort(w.begin(), w.end());
    rep(i,n){
        t += w[i].second;
        if(t > w[i].first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 4828
MOD = 1000000007

n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]

fib = [0, 1]
fa, fb = 0, 1
for _ in range(n):
    fa, fb = fb,(fa + fb) % MOD
    fib.append(fb)

ans = 1
for i in range(m + 1):
   ans *= fib[a[i + 1] - a[i] - 1] % MOD
print(ans%MOD)

Measured memory_bytes: 56792
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  int n, a, b;
  cin >> n >> a >> b;
  
  int res = 0;
  for (int i=1; i<=n; i++) {
    int tmp = i;
    int wa = 0;
    while (tmp > 0) {
      wa += tmp % 10;
      tmp /= 10;
    }
    if (wa >= a && wa <= b)
      res += i;
  }
  cout << res << endl;
}

Measured memory_bytes: 384
s = input()
ans = 0
for bit in range(2**(len(s)-1)):
    lis = s[0]
    for i in range(len(s)-1):
        
        if ((bit>>i) & 1):
            lis += "+"
        lis += s[i+1]
    
    ans += sum(map(int,lis.split("+"))) 
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110];
int main()
{
	cin>>n;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
		if(a[i] & 1)
			continue;
		if(a[i] % 3 && a[i] % 5)
		{
			cout<<"DENIED"<<endl;
			return 0;
		}
	}
	cout<<"APPROVED"<<endl; 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,T;
int d[1000001];
signed main()
{
	scanf("%lld%lld",&n,&T);
	for(int i=0;i<n;i++)
		scanf("%lld",&d[i]);
	while(T--)
	{
		int m,x,mod;
		scanf("%lld%lld%lld",&m,&x,&mod);
		m--;
		int u=0,tot=0;
		for(int i=0;i<n;i++)
		{
			u+=d[i]%mod;
			if(d[i]%mod==0)
				tot++;
		}
		tot*=m/n;
		u=u*(m/n)+x%mod;
		for(int i=0;i<m%n;i++)
		{
			u+=d[i]%mod;
			if(d[i]%mod==0)
				tot++;
		}
		printf("%lld\n",m-tot-u/mod);
	}
	return 0;
}


Measured memory_bytes: 384
import heapq

x, y, z, k = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
b = sorted(map(int, raw_input().split()))
c = sorted(map(int, raw_input().split()))

q = []
memo = set()
def qpush(q, ai, bi, ci):
    t = (-(a[ai] + b[bi] + c[ci]), ai, bi, ci)
    if not t in memo:
        memo.add(t)
        heapq.heappush(q, t)

qpush(q, len(a) - 1, len(b) - 1, len(c) - 1)
for _ in range(k):
    s, ai, bi, ci = heapq.heappop(q)
    if ai > 0:
        qpush(q, ai - 1, bi, ci)
    if bi > 0:
        qpush(q, ai, bi - 1, ci)
    if ci > 0:
        qpush(q, ai, bi, ci - 1)
    print -s


Measured memory_bytes: 4460
s = input()
ans = 0
for i in range(len(s)-1):
    if s[i] == "A":
        a = i
        break
    
for j in range(len(s)-1, 0, -1 ):
    if s[j] == "Z":
        b = j
        break
ans = b - a + 1
print(ans)

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

using namespace std;

int main(){
  int n;
  cin >> n;
  string s,t;
  cin >> s >> t;

  int res=2*n;
  for(int i=1;i<=n;i++){
    if(s.substr(s.length()-i,i)==t.substr(0,i)) res=min(res,2*n-i);
   }
 cout << res << endl;
}

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

using namespace std;

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

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

    ll A, B, M;
    cin >> A >> B >> M;

    Vl a(A), b(B);
    for (int i = 0; i < A; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < B; i++) {
        cin >> b[i];
    }

    Vl x(M), y(M), c(M);
    for (int i = 0; i < M; i++) {
        cin >> x[i] >> y[i] >> c[i];
        --x[i], --y[i];
    }



    Vl prices(M);
    for (int i = 0; i < M; i++) {
        prices[i] = a[x[i]] + b[y[i]] - c[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(prices.begin(), prices.end());

    ll ans = min(a[0] + b[0], prices[0]);

    cout << ans << endl;

    return 0;
}

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

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}

inline void chkmax(int &a,int b){if(a<b)a=b;}
inline void chkmin(int &a,int b){if(a>b)a=b;}

typedef long long ll;
const int N=5009;
const int md=1e9+7;

int n,root[3],fa[N],rtop;
vector<int> g[N];
ll fac[N],inv[N],c[N][N];
ll f[N],siz[N];

inline ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%md;
		a=a*a%md;
		b>>=1;
	}
	return ret;
}

inline void dfs(int u)
{
	siz[u]=1;int mx=0;
	for(int i=0,e=g[u].size();i<e;i++)
		if(g[u][i]!=fa[u])
		{
			fa[g[u][i]]=u;
			dfs(g[u][i]);
			siz[u]+=siz[g[u][i]];
			chkmax(mx,siz[g[u][i]]);
		}
	chkmax(mx,n-siz[u]);
	if(mx*2<=n)root[++rtop]=u;
}

inline void init()
{
	fac[0]=1;
	for(ll i=1;i<N;i++)
		fac[i]=fac[i-1]*i%md;
	inv[N-1]=qpow(fac[N-1],md-2);
	for(ll i=N-1;i>=1;i--)
		inv[i-1]=inv[i]*i%md;

	c[0][0]=1;
	for(int i=1;i<N;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%md;
	}
}

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}

	init();
	n=read();
	for(int i=1,u,v;i<n;i++)
	{
		u=read();v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);
	if(rtop==2)
	{
		printf("%lld\n",fac[n/2]*fac[n/2]%md);
		return 0;
	}
	
	memset(fa,0,sizeof(fa));

	rtop=0;
	dfs(root[1]);

	f[0]=1;
	for(int x=0,e=g[root[1]].size();x<e;x++)
	{
		ll cur=siz[g[root[1]][x]];
		for(int i=n;i;i--)
			for(int j=i-1;j>=0 && i-j<=cur;j--)
				(f[i]+=f[j]*c[cur][i-j]%md*c[cur][i-j]%md*fac[i-j]%md)%=md;
	}

	ll ans=0;
	for(int i=0;i<=n;i++)
		ans=(ans+(i&1?-1:1)*f[i]*fac[n-i]%md+md)%md;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 195072
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main(){
  int n;
  cin>>n;
  ll d[100][100];
  rep(i,n){
    rep(j,n){
      cin>>d[i][j];
    }
  }


  ll ans=0;
  rep(i,n-1){
    FOR(j,i+1,n){
      ans+=min(d[i][j],d[j][i]);
    }
  }

  cout<<ans<<endl;
}



Measured memory_bytes: 3160
using System;

class Program
{
  static void Main(String[] args)
  {
    var firstLine = Console.ReadLine().Split(' '); 
    int x = int.Parse(firstLine[0]) + 2;
    int y = int.Parse(firstLine[1]) + 2;
    int cnt1,cnt2,cnt3 = 0;
    String strBuff;
    char[,] mass = new char[x,y];
    bool result = true;

    Array.Clear(mass,0,mass.Length);

    for( cnt1 = 1; cnt1 < (x-1); cnt1++ )
    {
      strBuff = Console.ReadLine();
      
      for( cnt2 = 1; cnt2 < (y-1); cnt2++ )
      {
        mass[cnt1,cnt2] = strBuff[cnt2-1];
      }
    }
    
    for( cnt1 = 1; cnt1 < (x-1); cnt1++ )
    {
      for( cnt2 = 1; cnt2 < (y-1); cnt2++ )
      {
        if( mass[cnt1,cnt2] == '#' )
        {
          if( mass[(cnt1-1),cnt2] == '#' )
          {
            continue;
          }
          if( mass[cnt1,cnt2-1] == '#' )
          {
            continue;
          }
          if( mass[cnt1,cnt2+1] == '#' )
          {
            continue;
          }
          if( mass[(cnt1+1),cnt2] == '#' )
          {
            continue;
          }
          
          result = false;
          break;
        }
        else
        {
         /* 無処理 */ 
        }
      }
      
      if( result == false )
      {
        break;
      }
    }
    
    Console.WriteLine("{0}",(result?"Yes":"No"));
  }
}

Measured memory_bytes: 13140
// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 631441;

int n, ptot = 1, ans[MAX_N], triple[MAX_N];
char str[MAX_N];

struct node
{
    int ch[3], val, pos;
    bool tag;
} nodes[MAX_N << 1];

void pushdown(int p)
{
    if (nodes[p].tag)
    {
        swap(nodes[p].ch[1], nodes[p].ch[2]), nodes[p].tag = false;
        for (int i = 0; i < 3; i++)
            if (nodes[p].ch[i])
                nodes[nodes[p].ch[i]].tag ^= 1;
    }
}

void update(int p)
{
    if (p == 0)
        return;
    pushdown(p);
    int tmp = nodes[p].ch[2];
    nodes[p].ch[2] = nodes[p].ch[1], nodes[p].ch[1] = nodes[p].ch[0], nodes[p].ch[0] = tmp;
    update(nodes[p].ch[0]);
}

void insert(int x, int ps)
{
    int p = 1;
    for (int i = 0; i < n; i++)
    {
        int b = x % 3;
        if (nodes[p].ch[b] == 0)
            nodes[p].ch[b] = ++ptot;
        p = nodes[p].ch[b], x /= 3;
    }
    nodes[p].pos = ps;
}

void collect(int u, int acc, int dep)
{
    if (dep == n)
        return (void)(ans[nodes[u].pos] = acc);
    pushdown(u);
    for (int i = 0; i < 3; i++)
        if (nodes[u].ch[i])
            collect(nodes[u].ch[i], acc + triple[dep] * i, dep + 1);
}

int main()
{
    scanf("%d%s", &n, str + 1);
    int upper = triple[0] = 1;
    for (int i = 1; i <= n; i++)
        upper *= 3, triple[i] = upper;
    for (int i = 0; i < upper; i++)
        insert(i, i);
    for (int i = 1; str[i]; i++)
        if (str[i] == 'S')
            nodes[1].tag ^= 1, pushdown(1);
        else
            update(1);
    collect(1, 0, 0);
    for (int i = 0; i < upper; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

Measured memory_bytes: 25092
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; ++i)
#define RREP(i, n) for (int i = n; 0 <= i; --i)
#define FOR(i, start, end) for (int i = start; i < end; ++i)
#define RFOR(i, start, end) for (int i = start; end <= i; --i)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
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; }


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

    string S; cin >> S;
    ll ans;
    if (S == "SUN") ans = 7;
    else if (S == "MON") ans = 6;
    else if (S == "TUE") ans = 5;
    else if (S == "WED") ans = 4;
    else if (S == "THU") ans = 3;
    else if (S == "FRI") ans = 2;
    else if (S == "SAT") ans = 1;
    cout << ans << '\n';
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

const ll BIG = 1000000007LL;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int A, B, C;

int main(int argc, const char * argv[]) {
    cin >> A >> B >> C;
    if (A > C && B < C) output("Yes");
    else if (B > C && A < C) output("Yes");
    else output("No");

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll n,m;cin>>n>>m;
    ll k;cin>>k;
    vector<ll>a(n+1),b(m);
    rep(i,n)cin>>a[i+1];
    rep(i,m)cin>>b[i];
    REP(i,1,n+1){
        a[i]+=a[i-1];
    }
    REP(i,1,m){
        b[i]+=b[i-1];
    }
    ll ans=0;
    rep(i,n+1){
        if(k<a[i])continue;
        ll cnt=i;
        ll d=k-a[i];
        auto itr=upper_bound(all(b),d);

        ans=max(ans,cnt+(itr-b.begin()));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6420
def is_kaibun(s):
    return s == s[::-1]
S = input()
if is_kaibun(S) and is_kaibun(S[:int((len(S)-1)/2)]) and is_kaibun(S[int((len(S)+3)/2-1):]):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int v[105], p[105];
signed main(void)
{
	while(true) {
		int n, w, ma = -1, mm = -1;
		cin >> n >> w;
		if(!n && !w) break;
		memset(p, 0, sizeof(p));
		REP(i, n) {
			cin >> v[i];
			p[v[i]/w]++;
			ma = max(ma, p[v[i]/w]);
			mm = max(mm, v[i]/w);
		}
		double ans = 0;
		REP(i, mm+1) {
			ans += (double)(mm-i)*p[i]/mm/ma;
		}
		ans += 0.01;
		cout << fixed << setprecision(9) << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3208