akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    H, W = ILI()
    return (H, W)

def solve(H, W):
    ans = INF
    
    if H % 3 == 0 or W % 3 == 0:
        return 0
    else:
        ans = min(ans, H, W)

    if W % 2 == 0:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * W // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * (W // 2)
            num_3 = (H - h) * (W // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))

    if H % 2 == 0:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * H // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * (H // 2)
            num_3 = (W - w) * (H // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))
    
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


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

#ifdef loc
    #include "loc_debug.h"
#else
    #define pr(...)
    #define pra(a,n)
    #define praa(a,n,m)
    #define prl()
#endif

typedef long long ll;
typedef long double ld;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i, s, n)  for(int i = s; i <= n; ++i)
#define rev(i, n, s)  for(int i = n; i >= s; --i)
#define fore(x, a) for(auto &&x : a)
#define fill(a, x) memset((a), (x), sizeof(a))
#define tcase int __t; cin >> __t; rep(tc, 1, __t)
#define F first
#define S second
#define gc getchar

const int mod = 1000000007;
#define _ %mod
const int N = 100005;

int a[N];


int main() {
    fast_io;
    int n;
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
    }
    ll l = 2, r = 2;
    bool p = 1;
    rev(i, n, 1) {
        int x = a[i];
        l = ((l + x - 1) / x) * x;
        r = (r / x) * x + x - 1;
        if(r < l) {
            p = 0;
        }
    }
    if(p) {
        cout << l << ' ' << r;
    } else {
        cout << -1;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 640
S = input()
valid = ['A', 'T', 'C', 'G']
count = 0
max_len = 0

for i in range(len(S)):
    for j in range(i, len(S)):
        if S[j] in valid:
            count += 1
        else:
            break
    if count > max_len:
        max_len = count
    count = 0

print(max_len)


Measured memory_bytes: 2940
#094b
N,M,X = map(int, input().split())

A_list = [int(e) for e in input().split()]

cost_to_zero = 0
cost_to_N = 0

for toll_gate in A_list:
    if toll_gate < X:
        cost_to_zero += 1
    elif toll_gate > X:
        cost_to_N += 1

print(min(cost_to_zero,cost_to_N))

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

using namespace std;

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

    for (int i=0;i<s.size();i++) {
        if (s[i] == '1') s[i]='9';
        else if (s[i] == '9') s[i]='1';
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

#define ll long long
using namespace std;
static ll imin = std::numeric_limits<ll>::min();
static ll imax = std::numeric_limits<ll>::max();
#define rep(i, n) for(int i = 0; i<n; ++i)
#define rep1(i, n) for(int i = 1; i<n; ++i)
#define rev_rep(i, n) for(int i = n - 1; i >= 0; --i)
#define range(a, i, b) for(int i = a; i <b; ++i)
#define dump(x) cout << #x << ":" << x << "\n";
#define all(v) v.begin(), v.end()
#define readl(N) ll N; cin >> N
#define readlv(N, vec) vector<ll> vec(N); rep(i, N){cin >> vec[i];}

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair);
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair){
  os << '(' << pair.first << ',' << pair.second << ')';
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(int i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::set<T>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  readl(N);
  readl(K);
  readlv(N, a);

  vector<ll> dp(N, imax);

  dp[0] = 0;
  range(1, i, N){
    vector<ll> xs;
    auto jinit = max((ll)0, i - K);
    range(jinit, j, i){
      // dump(i);
      // dump(j);
      // dump(dp[j] + abs(a[i] - a[j]));
      xs.push_back(dp[j] + abs(a[i] - a[j]));
    }
    for(auto && x:xs){
      dp[i] = min(x, dp[i]);
    }

  }
  
  // dump(dp);
  cout << dp[N - 1];
}
#endif


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <deque>
using namespace std;

using VI = vector <int> ;
using VVI = vector <VI> ;

int main() {
    int R;
    int C;

    cin >> R >> C;
    vector <string> grid(R)
    ;
    for (int i = 0; i < R; ++i) {
        cin >> grid[i];
    }

    const int INF = 10000000;
    vector<vector<vector<int>>> dp(R, vector<vector<int>>(C, vector<int>(2, INF)));

    dp[0][0][grid[0][0] == '#'] = (grid[0][0] == '#');

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int c = (grid[i][j] == '#');

            if (c) {
                if (i) {
                    dp[i][j][c] = min(dp[i][j][c], dp[i-1][j][c]);
                    dp[i][j][c] = min(dp[i][j][c], dp[i-1][j][c^1] + 1);
                }

                if (j) {
                    dp[i][j][c] = min(dp[i][j][c], dp[i][j-1][c]);
                    dp[i][j][c] = min(dp[i][j][c], dp[i][j-1][c^1] + 1);
                }
            } else {
                if (i) {
                    dp[i][j][c] = min(dp[i][j][c], dp[i-1][j][c]);
                    dp[i][j][c] = min(dp[i][j][c], dp[i-1][j][c^1]);
                }

                if (j) {
                    dp[i][j][c] = min(dp[i][j][c], dp[i][j-1][c]);
                    dp[i][j][c] = min(dp[i][j][c], dp[i][j-1][c^1]);
                }
            }
        }
    }

    int c = (grid[R-1][C-1] == '#');
    cout << dp[R-1][C-1][c] << endl;

    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
vector<int> ny={1,0,-1,0},nx={0,1,0,-1};
int H,W;
vector<vector<int>> A;
queue<P> Q;
P q;
int bfs(int a,int b){
     Q.push(P(a,b));
     P p=P(H-1,W-1);
     while(!Q.empty()){
    q=Q.front();
    Q.pop();
    for(int i=0;i<4;i++){
        int dy=q.first+ny.at(i);
        int dx=q.second+nx.at(i);
        if(dy<0||dy>=H||dx<0||dx>=W)continue;
        if(A.at(dy).at(dx)==0){
        A.at(dy).at(dx)=A.at(q.first).at(q.second)+1;
        if(dy==H-1&&dx==W-1){return A.at(dy).at(dx);} 
        Q.push(P(dy,dx));
        }
    }
    }
     return -1;
}



int main(){
    cin>>H>>W;
    A.assign(H,vector<int>(W,-1));
    int count=0,ans=0;
    char s;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>s;
            if(s=='.'){
                A.at(i).at(j)=0;
            }
            else count++;
        }
    }
    ans=bfs(0,0);
    if(ans!=-1){
        ans=H*W-count-ans-1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))

for k in range(m):
    for i in range(n-1):
        if a[i] % (k+1) > a[i+1] % (k+1):
            tmp = a[i]
            a[i] = a[i+1]
            a[i+1] = tmp
for i in range(n):
    print(a[i])


Measured memory_bytes: 5612
#include <bits/stdc++.h>
#include <string>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
using namespace std;

int main() {
  int n;
  while (cin >> n, n) {
    int ans = 0, key = 0, ke2 = 0;
    string s[n];
    rep(i, n) cin >> s[i];
    for (int i = 0; i < n; i++) {
      ans = 0;
      key = 0;
      for (int j = i; j < n; j++) {
        ans += s[j].size();
        if (ans == 5 && key == 0) {
          key = 1;
          ans = 0;
        } else if (ans > 5 && key == 0 || ans > 7 && key == 1 ||
                   ans > 5 && key == 2 || ans > 7 && key == 3 ||
                   ans > 7 && key == 4) {
          ans = 0;
          key = 0;
          break;
        } else if (ans == 7 && key == 1) {
          key = 2;
          ans = 0;
        } else if (ans == 5 && key == 2) {
          ans = 0;
          key = 3;
        } else if (ans == 7 && key == 3) {
          ans = 0;
          key = 4;
        } else if (ans == 7 && key == 4) {
          cout << i + 1 << endl;
          ke2 = 1;
          break;
        }
      }
      if (ke2 == 1)
        break;
    }
  }
  return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()
//#define LN cerr<<__LINE__<<endl
#define LN 0
using pi=pair<int,int>;
int read(){
	int i;
	scanf("%d",&i);
	return i;
}
void chmin(int&a,int b){
	a=a<b?a:b;
}
void chmax(int&a,int b){
	a=a>b?a:b;
}
struct SegTree{
	vi buf;
	int s;
	SegTree(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,-1);
	}
	void Update(int i,int v){
		i+=s;
		buf[i]=v;
		while((i/=2)>=1)buf[i]=max(buf[i*2],buf[i*2+1]);
	}
	int GetIdx(int b,int e,int t,vi&dst,int l,int r,int i){
		if(buf[i]<=t||e<=l||r<=b)return t;
		if(b<=l&&r<=e){
			if(l+1==r){
				if(t<buf[i])dst.PB(l);
				return max(t,buf[i]);
			}else{
				if(t<buf[i*2])
					t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
				if(t<buf[i*2+1])
					t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
				return t;
			}
		}
		t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
		t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
		return t;
	}
	void GetIdx(int b,int e,vi& dst){
		GetIdx(b,e,-1,dst,0,s,1);
	}
};
inline int xorshift(){
	static int w=1145141919;
	w=w^(w<<17);
	w=w^(w>>13);
	w=w^(w<<5);
	return w;
}
struct Node{
	Node *l,*r;
	int v,s;
} buf[200010];
Node* Merge(Node*a,Node*b){
	if(!a)return b;
	if(!b)return a;
	int s=a->s+b->s,x=xorshift()%s;
	if(x<a->s){
		a->r=Merge(a->r,b);
		a->s=s;
		return a;
	}else{
		b->l=Merge(a,b->l);
		b->s=s;
		return b;
	}
}
using pn=pair<Node*,Node*>;
pn Split(Node*x,int t){
	if(!x)return pn(0,0);
	if(t<=x->v){
		pn c=Split(x->l,t);
		if(c.first)x->s-=c.first->s;
		x->l=c.second;
		return pn(c.first,x);
	}else{
		pn c=Split(x->r,t);
		if(c.second)x->s-=c.second->s;
		x->r=c.first;
		return pn(x,c.second);
	}
}
int MaxValue(Node* x){
	while(x->r)x=x->r;
	return x->v;
}
void Show(Node* x){
	if(!x)return;
	Show(x->l);
	cerr<<x->v<<" ";
	Show(x->r);
}
int main(){
	int n=read();
	SegTree seg(n*2);
	vector<Node*> trs(n*2);
	vi mx(n*2,-1);
	REP(i,n){
		int x=read()-1;
		seg.Update(i,x);
		trs[i]=buf+i;
		trs[i]->v=x;
		trs[i]->s=1;
		mx[i]=x;
	}
	vi idx;
	FOR(i,n,n*2){
		idx.clear();
		seg.GetIdx(0,i,idx);
		int last=-1;
		Node*x=0;
		for(auto j:idx){
			LN;
			pn c=Split(trs[j],last);
			LN;
			last=mx[j];
			LN;
			if(c.first)
				mx[j]=MaxValue(c.first);
			else
				mx[j]=-1;
			LN;
			seg.Update(j,mx[j]);
			LN;
			trs[j]=c.first;
			LN;
			x=Merge(x,c.second);
			LN;
		}
		if(x->s==n){
			cout<<i-n<<endl;
			return 0;
		}
		mx[i]=last;
		seg.Update(i,mx[i]);
		trs[i]=x;
		//Show(x);
	}
}

Measured memory_bytes: 15744
# import numpy as np
import itertools

if __name__ == "__main__":

	N,K = map(int,input().split())
	P = [ int(p)-1 for p in input().split() ]
	C = list(map(int,input().split()))

	# print(P)
	# 一度計算したサイクル情報をキャッシュしておくための配列
	# cycleIDs = np.full( N, -1, np.int64 )
	cycleIDs = [ -1 for _ in range(N)]
	cycleInfs = []
	cycleID = 0
	procCnt = 0

	for n in range(N):
		v = n

		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleCosts.append( C[v] )
				cycleIDs[v] = cycleID

				v = P[v]
				if cycleIDs[v] != -1:
					# サイクル終了
					# ループを含めない最大の処理回数
					procCnt = K % len( currentCycleCosts )
					# それで足りてるのかわからないが、Last2周分は、ループ合計がプラスでも必ずしもループするとは限らない
					# その部分は、ちゃんと計算する
					# -------------------------------------------------
					# 4 101
					# 2 3 4 1
					# 50 -49 -50 50
					# 上記のようなパターンの場合、
					# 最大25回ループ + 1回処理可能だが、その場合、25 + 50 = 75
					# 24回ループ + 2回処理でやめると、124になる
					# 無条件でループする回数は、ループ可能な最大の回数-1らしい
					# -------------------------------------------------
					# 割り切れて、尚且つサイクル合計がマイナスのパターンで、最低１個は処理するのにもここで対応
					if len( currentCycleCosts ) + procCnt <= K:
						procCnt += len( currentCycleCosts )

					cycleInfs.append( ( procCnt, len(currentCycleCosts), currentCycleCosts * 3 ) )
					cycleID += 1
					break



	# scores = []
	# procCnt = 0
	ans = -10 ** 9
	for procCnt, currentCycleSize, currentCycleCosts in cycleInfs:

		# サイクル内でループしてスコアを稼ぐ場合の考慮
		loopScore = 0
		if sum(currentCycleCosts) > 0:
			cycleLoopCnt =  ( K - procCnt ) // currentCycleSize
			loopScore = cycleLoopCnt * sum(currentCycleCosts[:currentCycleSize])
			# print("loopScore",loopScore,procCnt)

		# このサイクルに属する全頂点分をまとめて計算する
		for i in range(currentCycleSize):
			# print(np.roll( currentCycleCosts, i ).cumsum()[:procCnt])
			score = max( itertools.accumulate( currentCycleCosts[i:i+procCnt] ) )
			if ans < score + loopScore:
				ans = score + loopScore
			# ans = max( ans, score + loopScore )


	print(ans)
	# print(max(scores))


Measured memory_bytes: 9912
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
int main()
{
    int x1,x2,x3,x4,y1,y2,y3,y4,l,r;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    l=x2-x1;
    r=y2-y1;
    x3=x2-r;
    y3=y2+l;
    x4=x3-l;
    y4=y3-r;
    printf("%d %d %d %d\n",x3,y3,x4,y4);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
    long int sum ;
    int i , min, max, n;
    int a[10000] ;
	scanf("%d", &n);
	sum = 0 ;
	for ( i = 0 ; i < n ; i++) {   
		scanf("%d", &a[i]);
	}
	max = a[0] ;
	min = a[0] ;
	for ( i = 0 ; i < n ; i++) {  
		
		if ( max < a[i]) {
			max = a[i] ;
		}
		if (min > a[i] ) {
			min = a[i] ;
		}
	}
  	for ( i = 0 ; i < n ; i++) {
		sum = sum + a[i] ; 
	}
  

	printf("%d %d %ld\n", min, max, sum) ;
return 0;
}

Measured memory_bytes: 636
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ans=float('inf')
for i in range(4**n):
  la,lb,lc=[],[],[]
  for j in range(n):
    if i%4==3:
      lc.append(l[j])
    elif i%4==2:
      lb.append(l[j])
    elif i%4==1:
      la.append(l[j])
    i//=4
  if la and lb and lc:
    synthesize=(len(la)-1)*10+(len(lb)-1)*10+(len(lc)-1)*10
    extend_cutdown=abs(sum(la)-a)+abs(sum(lb)-b)+abs(sum(lc)-c)
    ans=min(ans,synthesize+extend_cutdown)
print(ans)

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

//マクロ
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD ll(1e9+7)     //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second



int n;
ll dp[100005][13];



int main(int argc, char const *argv[])
{

    string s;
    cin >> s;
    n = SIZE(s);
    dp[0][0] = 1 ;
    REP(i,n) 
    {
        int tmp;
        if (s[i] == '?')
            tmp = -1;
        else
            tmp = s[i] - '0';

        REP(j,10)
        {
            if (tmp != -1 && tmp != j) 
                continue;

            REP(k,13) 
            {
                dp[i+1][(10*k+j)%13] += dp[i][k];
            }

            REP(k,13) dp[i+1][k] %= MOD;
        }
    }
    cout << dp[n][5] << "\n";

    return 0;
}


Measured memory_bytes: 10624
n=int(input())

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

a=divisor(n)
a.sort()

c=[]
for i in range(len(a)//2+1):
    d=a[i]-1+a[-i-1]-1
    c.append(d)

print(min(c))

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T> inline T gcd(T t) {
  return t;
}

template<typename T, typename... S> inline T gcd(T t, S... s) {
  return __gcd(t, gcd(s...));
}

template<typename T> inline T lcm(T t) {
  return t;
}

template<typename T, typename... S> inline T lcm(T t, S... s) {
  T l = lcm(s...);
  return t / gcd(t, l) * l;
}

template<typename T> inline T floor(T a, T b) {
  return a / b * b <= a ? a / b : a / b - 1;
}

template<> inline float floor(float a, float b) {
  return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;
}

template<> inline double floor(double a, double b) {
  return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;
}

template<> inline long double floor(long double a, long double b) {
  return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;
}

template<typename T> inline T ceil(T a, T b) {
  return floor(a + b - 1, b);
}

template<typename T> inline T round(T a, T b) {
  return floor(a + b / 2, b);
}

template<typename T> inline T mod(T a, T b) {
  return a - floor(a, b) * b;
}

template<typename T> inline T factorial(T n) {
  return n <= 1 ? 1 : factorial(n - 1) * n;
}

template<typename T> inline T square(T n) {
  return n * n;
}

template<typename T> inline T cube(T n) {
  return n * n * n;
}

template<typename T> inline T norm(T x1, T y1, T x2, T y2) {
  return square(x1 - x2) + square(y1 - y2);
}

inline long long sqrt(long long n) {
  return sqrt((long double)n);
}

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  a = max(a, c) - min(a, c);
  b = max(b, d) - min(b, d);
  if (a == 0 || b == 0) {
    cout << 0 << endl;
    return 0;
  }
  int g = gcd(a, b);
  a /= g;
  b /= g;
  cout << (a + b - 1) * g << endl;
}


Measured memory_bytes: 256
N = int(input())

if N == 0:
  print(2)
elif N == 1:
  print(1)
else:
  
  n_2 = 2
  n_1 = 1
  
  for _ in range(N-1):
    n_0 = n_1 + n_2
    n_2 = n_1
    n_1 = n_0
    
  
  print(n_0)

Measured memory_bytes: 9084
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int N, D;
    cin >> N >> D;
    cout << (int)ceil(1.0 * N / (2 * D + 1)) << endl;
    return 0;
}

Measured memory_bytes: 256
a,b = gets.chomp.split(" ").map(&:to_i)
ans = -1
(1..1000).each{|elem|
  taxa = (elem*0.08).floor
  taxb = (elem*0.1).floor
  if (taxa == a) and (taxb == b)
    ans = elem
    break
  else
  end
  }
puts ans


Measured memory_bytes: 3836
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=4999999996000000001;


int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=0;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                int b=a[i];
                int c=a[j];
                int d=a[k];
                if(b==c || c==d || d==b) continue;
                if(b>abs(c-d) && b<c+d) ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3156
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# N <= 50
N = int(stdin.readline().rstrip())
v = [int(x) for x in stdin.readline().rstrip().split()]

x = 0
y = 0

while (True):
    minn = INF
    for i in range(len(v)):
        for j in range(i+1, len(v)):
            tmp = (v[i] + v[j]) / 2
            if minn > tmp:
                x = v[i]
                y = v[j]
                minn = tmp

    v.remove(x)
    v.remove(y)
    v.append(minn)
    
    if len(v) == 1:
        print(v[0])
        exit()

Measured memory_bytes: 66156
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int N=s.size();
  int a=0,A,b=0,B;
  for(int i=0;i<N;i++){
    if(s.at(i)=='A'){
      a=1;
      A=i;
      break;
    }
  }
  for(int i=N-1;i>-1;i--){
    if(s.at(i)=='Z'){
      b=1;
      B=i;
      break;
    }
  }
  cout<<B-A+1<<endl;
}

Measured memory_bytes: 3704
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<ll(n); i++)

int main(){
    ll a;
    cin >> a;
    ll ans = 0;
    for(int i=1;i<=a;i++){
        if(i % 3 != 0 && i % 5 != 0){ans += i;}
        else{continue;}
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3152
#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, k, x;
ll dp[109][100009], m = 1e9 + 7;
ll add(ll x, ll y)
{
	return(x % m + y % m + 2 * m) % m;
}
int main()
{
	cin >> n >> k;
	for(int i = 0; i <= k; i++)
		dp[n][i] = 1;
	for(int i = n - 1; i >= 0; i--)
	{
		cin >> x;
		for(int leftk = 0; leftk <= k; leftk++)
		{
			dp[i][leftk] = add(dp[i + 1][leftk], leftk - x? - dp[i + 1][leftk - x-1] : 0);
			if(leftk)
				dp[i][leftk] += dp[i][leftk - 1];
		}
	}
	cout << (dp[0][k] % m - dp[0][k - 1] % m + 2 * m) % m;
}


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

//  a^b % m
long long powmod(long long a, long long b, long long m)
{
    long long r = 1;
    for (; b>0; b>>=1, a=a*a%m)
        if (b&1)
            r = r*a%m;
    return r;
}

int main()
{
    long long r1, c1, r2, c2;
    cin>>r1>>c1>>r2>>c2;

    long long M = 1000000007;
    vector<long long> F(2000002);
    F[0] = 1;
    for (int i=1; i<=2000001; i++)
        F[i] = F[i-1]*i%M;

    auto C = [&](long long x, long long y)
    {
        return F[x]*powmod(F[y], M-2, M)%M*powmod(F[x-y], M-2, M)%M;
    };

    long long ans = 0;
    for (long long r=r1; r<=r2; r++)
    {
        ans += C(r+c2+1, c2) - C(r+c1, c1-1);
        ans = (ans%M+M)%M;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 16000
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    int n; cin >> n;
    priority_queue<P> plus, minus;
    rep(k,n){
        string s; cin >> s;
        int last = 0;
        int mini = 0;
        rep(i, s.length()){
            if(s[i] == '(') last++;
            else last--;
            chmin(mini, last);
        }
        if(last >= 0) plus.push({mini, last});
        else minus.push({mini - last, -last});
    }

    int p = 0;
    int m = 0;
    while(plus.size()){
        auto val = plus.top(); plus.pop();
        if(p + val.first < 0){
            cout << "No" << endl;
            return 0;
        }
        p += val.second;
    }

    while(minus.size()){
        auto val = minus.top(); minus.pop();
        if(m + val.first < 0){
            cout << "No" << endl;
            return 0;
        }
        m += val.second;
    }

    if(p != m){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 11340
#include<cstdio>
#include<iostream>
#define maxn 3*100000+5
#define mod 998244353
using namespace std;
long long int a[maxn],in[maxn];
long long pow(long long x, long long n) {
    long long ret = mod!= 1;
    for (x %= mod; n; n >>= 1, x = x * x % mod)
        if (n & 1) ret = ret * x % mod;
    return ret;
}
 long long int mate( long long int m,  long long int n)
{
    if(m==0) return 1;
    if(n<m) return 0;
    if(n==m)  return 1;
        return a[n]*in[m]%mod*in[n-m]%mod;

}
int main()
{
    long long int sum=0,A,B,K,x,t,N,j,r,i;
    scanf("%lld%lld%lld%lld",&N,&A,&B,&K);
    a[0]=1;
    for(i=1;i<=N;i++)
        a[i]=(a[i-1]*i)%mod;
        in[N]=pow(a[N],mod-2);
        for(i=N-1;i>=0;i--)
            in[i]=in[i+1]*(i+1)%mod;
    if(K==0)
        {
            printf("1\n");
            return 0;
        }
    t=0;
    x=0;
    while(t<=N)
    {
        if((K-t*A)%B) {t++;continue;}
        x=(K-t*A)/B;
        if(x<=N&&t>=0&&x>=0)
        {
            sum=(sum+(mate(t,N)*mate(x,N))%mod)%mod;
        }
       t++;
    }
    printf("%lld\n",sum%mod);
}


Measured memory_bytes: 4992
#include <iostream>
#include <stdio.h>

using namespace std;

int main(int argc, char *argv[])
{
    int n, x;
  //  int res = 0;
    while (true)
    {
        scanf("%d %d", &n, &x);
        if (n == 0 && x == 0)
        {
            break;
        }

        int p, q, res = 0;
        for (int i = 1; i <= n; i++)
        {
            p = i + 1;
            q = n;
            while (p < q)
            {
                if (p + q < x - i)
                {
                    p++;
                }
                else if (p + q > x - i)
                {
                    q--;
                }
                else
                {
                    res++;
                    p++;
                    //break;
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}




Measured memory_bytes: 3212
//Author rahuliitkgp

/*A thing of beauty is a joy forever,
Its loveliness increases,
it will never pass into nothingness.*/
//Men at Work :)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;

#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void cpp(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int main(){
    cpp();
    ll n;
    cin>>n;
    map<ll, ll> mapp;
    for(ll i=1; i<=100; i++){
        for(ll j=1; j<=100; j++){
            for(ll k=1; k<=100; k++){
                ll x = i*i+j*j+k*k+i*j+j*k+k*i;
                mapp[x]++;
            }
        }
    }
    for(ll i=1; i<=n; i++){
        cout<<mapp[i]<<endl;
    }
    return 0;
}





Measured memory_bytes: 5988
#include <iostream>
using namespace std;
int main(){
    long long a,b,k;
    cin>>a>>b>>k;
    if(k>=a+b){
        cout<<0<<" "<<0<<endl;
    }else if(a>=k){
        cout<<a-k<<" "<<b<<endl;
    }else if(k>a){
        cout<<0<<" "<<b-(k-a)<<endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int N, a[99999];
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", a + i);
    }
    int next = a[0] - 1, count = 1;
    for (; next != 1 && count <= N + 1; count++) {
        next = a[next] - 1;
    }
    if (next == 1) printf("%d\n", count);
    else printf("-1\n");

    return 0;
}

Measured memory_bytes: 512
/**
 * File    : B.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-10-31 22:31:10
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

int H, W;
string S[110];
bool valid[110][110];

int main()
{
  cin >> H >> W;
  for (auto i = 0; i < H; i++)
  {
    cin >> S[i];
  }
  fill(&valid[0][0], &valid[0][0] + 110 * 110, true);
  for (auto i = 0; i < H; i++)
  {
    bool ok = true;
    for (auto j = 0; j < W; j++)
    {
      if (S[i][j] == '#')
      {
        ok = false;
      }
    }
    if (ok)
    {
      for (auto j = 0; j < W; j++)
      {
        valid[i][j] = false;
      }
    }
  }
  for (auto j = 0; j < W; j++)
  {
    bool ok = true;
    for (auto i = 0; i < H; i++)
    {
      if (S[i][j] == '#')
      {
        ok = false;
      }
    }
    if (ok)
    {
      for (auto i = 0; i < H; i++)
      {
        valid[i][j] = false;
      }
    }
  }
  for (auto i = 0; i < H; i++)
  {
    string X = "";
    for (auto j = 0; j < W; j++)
    {
      if (valid[i][j])
      {
        X = X + S[i].substr(j, 1);
      }
    }
    if (X != "")
    {
      cout << X << endl;
    }
  }
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int i,t,s;
  s=0;
  for(i=0;i<4;i++){
    scanf("%d",&t);
    s=s+t;
  }
  printf("%d\n",s/60);
  printf("%d\n",s%60);
  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
#include <set>
#include <string>
#include <bitset>
#include <fstream>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> T;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define revrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define f first
#define s second
#define pb push_back

ll mod = 1000000007;
const ll INF = 100000000000010000;
//const ull B = 998244353;
//ll kai[3010];

//void pres(double A, ll x = 20) { printf("%.20f\n", x); }

vector<ll> dx = { 0, 1, 0, -1, 1, -1, 1, -1, 0};
vector<ll> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0};

void chmin(ll& x, ll y) {
	x = min(x, y);
}

void chmax(ll& x, ll y) {
	x = max(x, y);
}

ll pow_long(ll x, ll y) {
	ll res = 1;
	while (y > 0) {
		if (y % 2 == 1) res *= x;
		x *= x;
		y /= 2;
	}
	return res;
}

void test() {
	cout << "888888888888888888888888" << endl;
}

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll k) {
	x %= mod;
	ll res = 1;
	while (k > 0) {
		if (k % 2) {
			res *= x; res %= mod;
		}
		x *= x; x %= mod;
		k /= 2;
	}
	return res;
}

ll div_mod(ll x) {
	return pow_mod(x, mod - 2);
}

//コンビネーション
const int MAXcomb = 1000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAXcomb; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
ll comb(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * finv[k] % mod * finv[n - k] % mod;
}

string S;

void solve() {
	cin >> S;
	if (S[2] == S[3] && S[4] == S[5]) cout << "Yes" << endl;
	else cout << "No" << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll T = 1;
	//cin >> T;
	rep(i, T) solve();
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, x) = readLine()!!.split(" ").map{ it.toInt() }
    val lList = readLine()!!.split(" ").map{ it.toInt() }

    var distant = 0
    var bounceCount = 1
    for (i in 0 until n) {
        distant += lList[i]
        if (distant <= x) bounceCount++
    }

    println(bounceCount)
}


Measured memory_bytes: 37904
#include<cstdio>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
int main(void)
{
	LL d,w,h,i,j,k,in,n;
	LL dis1,dis2,dis3,T;

	while(1) {	
		cin>>d>>w>>h;
		if(!d&&!w&&!h) break;
		cin>>n;
		for(i=0;i<n;i++) {
			cin>>in;
			T=(in*2)*(in*2);
			dis1=(w*w)+(h*h);
			dis2=(w*w)+(d*d);
			dis3=(h*h)+(d*d);
			if(dis1<T||dis2<T||dis3<T) cout<<"OK\n";
			else cout<<"NA\n";
		}
	}
}

Measured memory_bytes: 3052
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

vector<int> g[100005];
int main() {
  int n,m;
  cin >> n >> m;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> ans(n,-1);
  ans[0] = 0;
  queue<int> q;
  auto push = [&](int u, int v){
    if(ans[v]>=0) return;
    ans[v] = u;
    q.emplace(v);
  };
  q.emplace(0);
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int v:g[u]){
      push(u,v);
    }
  }

  rep(i,n-1){
    if(ans[i+1]==-1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  rep(i,n-1){
    cout << ans[i+1]+1 << endl;
  }
}

Measured memory_bytes: 10124
program AGC006A
    implicit none
    integer(8)::N,i,j,dupe,flg
    character(100)::s,t
    dupe=0
    read(5,*)N,s,t

    do i=1,N
        flg=1
        do j=1,i
            if(s(N-i+j:N-i+j)/=t(j:j))flg=0
        end do
        if(flg==1)dupe=max(dupe,i)
    end do
    print'(i0)',2*N-dupe
end program AGC006A

Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var org = "CODEFESTIVAL2016";
        var s = Console.ReadLine().Trim();
        var res = 0;
        for (int i = 0; i < 16; i++)
            if (org[i] != s[i]) res++;
        Console.WriteLine(res);
    }
}


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

int main(){
    string s,p;
    cin >> s >> p;
    s += s;
    bool ans = false;
    for(int i=0; i<s.size()/2; i++){
        if(s.substr(i,p.size()) ==p ) ans = true;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a,int b){
  while(b!=0){
    int r=a%b;
    a=b;
    b=r;
  }
  return a;
}
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n){
    cin >> a.at(i);
  }
  int ans=gcd(a.at(0),a.at(1));
  rep(i,n){
    ans=gcd(a.at(i),ans);
     
  }
  cout << ans;
}
  
  

Measured memory_bytes: 3768
//--- pD ---//
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Reader reader;
	PrintWriter out;
	public Solution() {
		reader = new Reader();
		out = new PrintWriter(System.out);
		while (reader.hasNext()) {
			run_case();
		}
		out.flush();
	}

	private void run_case() {
		long a = reader.nl();
		long b = reader.nl();
		long n = reader.nl();

		double res = 0.0;
		double pv = -1e9;

		if (n >= b-1) {
			long x = b-1;
			double t = Math.floor(1.0*a*x/b) - a*Math.floor(1.0*x/b);
			out.println((long)t);
		} else {
			long x = n;
			double t = Math.floor(1.0*a*x/b) - a*Math.floor(1.0*x/b);
			out.println((long)t);
		}

		// for (long x=1; x<=n; x++) {
		// // long x = Math.max(n, b-1;
		// 	double t = Math.floor(1.0*a*x/b) - a*Math.floor(1.0*x/b);
		// 	System.out.println(t + " x = " + x);
		// 	// if (t < pv) {
		// 	// 	out.println((long)t);
		// 	// 	return;
		// 	// }
		// // 	pv = t;
		// }
		// out.println(pv);
		return;
	}
}
// floor(Ax/B) - A * floor(x/B);

// 3.33 - 3 = 0.33


class Reader {
	BufferedReader br;
	StringTokenizer st;
	public Reader(){
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	public String next() {
		if (st.hasMoreTokens()) return st.nextToken();
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return st.nextToken();
	}
	public boolean hasNext() {
		try {
			if (!st.hasMoreTokens() && !br.ready()) return false;
			else return true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}
	public int ni() {return Integer.parseInt(this.next());}
	public long nl() {return Long.parseLong(this.next());}
	public String ns() {return this.next();}
}


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

#define  __  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  int  long long
#define  endl  '\n'
const double pi = acos(-1);
const int mod = 1e9 + 7;
//______________________



int32_t main()
{ 
  __
 
  
  
  int n,m,x;
  cin>>n>>m;
  int b[m],c[m],a[n];
  
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  sort(a,a+n);
  vector<pair<int,int> > C;

  for(int i=0;i<m;i++)
  {
    cin>>b[i]>>c[i];
    C.push_back({c[i],i});
  }

  sort(C.begin(), C.end());
  reverse(C.begin(), C.end());
  int j=0;
  for(auto it: C)
  {
    x=it.first;
    int idx = it.second;

    for(;j<n and b[idx];j++,b[idx]--)
    {
      if(a[j]<x)
        a[j]=x;
    }

    if(j>=n)
      break;
  }
  int sum=0;
  for(int i=0;i<n;i++)
    sum+=a[i];

  cout<<sum<<endl;
  
 return 0;
}

Measured memory_bytes: 4596
#include<iostream>
#include <cmath>

using namespace std;

typedef long long ll;

void swap(ll i, ll j, ll *a) {
    ll tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void b_sort(ll n, ll *x, ll *y, ll *h) {
    ll i, j;
    for (i = 0; i < n; i++) {
        for (j = n-1; j > i; j--) {
            if (h[j-1] < h[j]) {
                swap(j, j-1, x);
                swap(j, j-1, y);
                swap(j, j-1, h);
            }
        }
    }
}

int main() {
    ll n;  cin >> n;
    ll *x = new ll[n], *y = new ll[n], *h = new ll[n];
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> h[i];
    
    b_sort(n, x, y, h);
    
    bool can = true;
    for (int c_x = 0; c_x <= 100; c_x++) {
        for (int c_y = 0; c_y <= 100; c_y++) {
            can = true;
            int H = h[0] + abs(x[0]-c_x) + abs(y[0]-c_y);
            for (int k = 1; k < n; k++) {
                if (h[k] != max(H-abs(x[k]-c_x)-abs(y[k]-c_y), (ll)0))
                    can = false;
            }
            if (can == true) {
                cout << c_x << " " << c_y << " " << H << endl;
                return 0;
            }
        }
    } 
}

Measured memory_bytes: 256
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

    def get_combination(self, n, r):
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod



import math
Big = BigCombination()
s = 0
m = 10**9+7


N,M,K = map(int,input().split())

res =0
for i in range(N-1):
  res += (i+1)*(N-i-1)*(M**2)
for i in range(M-1):
  res += (i+1)*(M-i-1)*(N**2)
if K>2:
  anp = Big.get_combination(N*M-2,K-2)
else:anp = 1
print((res*anp)%m)

Measured memory_bytes: 90112
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int T,n,m,N,M,a,b;
map<pi,int> dp;
string s;
struct E{int from;char c;E(int a,char b):from(a),c(b){}};
vc<E> e[3010],f[3010];

int F(int a,int b){
	if(dp.find(pi(a,b))!=dp.end())return dp[pi(a,b)];
	int& res=dp[pi(a,b)];
	if(!a&&!b)return res=1;
	rep(i,e[a].sz)rep(j,f[b].sz)if(e[a][i].c==f[b][j].c){
		res=(res+F(e[a][i].from,f[b][j].from))%MOD;
	}
	return res;
}

int main(){
	cin>>T;
	rep(tc,T){
		rep(i,3010)e[i].clear(),f[i].clear();
		cin>>n>>m;
		int cur=n;
		rep(i,m){
			cin>>a>>b>>s;
			if(s.sz==1)e[b].pb(E(a,s[0]));
			else rep(j,s.sz){
				if(j==0)e[cur].pb(E(a,s[j])),cur++;
				else if(j==s.sz-1)e[b].pb(E(cur-1,s[j]));
				else e[cur].pb(E(cur-1,s[j])),cur++;
			}
		}
		cin>>N>>M;
		cur=N;
		rep(i,M){
			cin>>a>>b>>s;
			if(s.sz==1)f[b].pb(E(a,s[0]));
			else rep(j,s.sz){
				if(j==0)f[cur].pb(E(a,s[j])),cur++;
				else if(j==s.sz-1)f[b].pb(E(cur-1,s[j]));
				else f[cur].pb(E(cur-1,s[j])),cur++;
			}
		}
		dp.clear();
		cout<<F(n-1,N-1)<<endl;
	}
}

Measured memory_bytes: 0
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class ABC
	{
		static readonly int mod = 1000000007;  // 10^9+7

		static void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });


			//string s = Console.ReadLine();
			//int n = int.Parse(Console.ReadLine());
			//long x = long.Parse(Console.ReadLine());
			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int n = vs[0];
			int m = vs[1];

			if (n == m) {
				Console.WriteLine("Yes");
			} else {
				Console.WriteLine("No");
			}


			Console.Out.Flush();
		}
	}
}


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

int main(){
  string a[3];
  cin >> a[0] >> a[1] >> a[2];
  string small="abcdefghijklmnopqrstuvwxyz";
  string big="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  for(int i=0;i<3;i++){
    for(int j=0;j<26;j++){
      if(a[i].at(0)==small.at(j)){
        cout << big.at(j);
      }
    }
  }
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int, input().split()))
l = []
for i in range(N):
    if i == 0:
        l.append(0)
    elif H[i - 1] >= H[i]:
        l.append(l[i - 1] + 1)
    elif H[i - 1] < H[i]:
        l.append(0)
print(max(l))


Measured memory_bytes: 20508
s = input()
t = input()

count = 0
ind = -1
if set(t) <= set(s):
    for i in range(len(t)):
        ind = s.find(t[i], ind+1)
        if ind == -1:
            count += 1
            ind = s.find(t[i], ind+1)
    print(count*len(s) + ind+1)

else:
    print(-1)

Measured memory_bytes: 3316
#include<iostream>
using namespace std;
 
int main()
{
    int n,ans;
    n=0;
    while(cin>>n){
        ans=0;
        for(int a=0;a<10;a++){
            for(int b=0;b<10;b++){
                for(int c=0;c<10;c++){
                    for(int d=0;d<10;d++){
                        if(a+b+c+d==n)
                            ans++;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 1160
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main(){
    ll n,a,b;cin>>n>>a>>b;
    if((b-a)%2==0) cout<<(b-a)/2<<endl;
    else{
        ll d_to1=min(a-1,b-1);
        ll d_ton=min(n-a,n-b);
        if(d_to1<d_ton){
            cout<<d_to1+1+(b-a-1)/2;
        }
        else{
            cout<<d_ton+1+(b-a-1)/2;
        }
    }
}

Measured memory_bytes: 3636
#!/snap/bin/pypy3

MOD = 10 ** 9 + 7

def main():
    global MOD

    H, W = map(int, input().split())
    strings = [list(input()) for _ in range(H)]

    dp = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
    dp[1][1] = 1

    for i, line in enumerate(strings):
        for j, data in enumerate(line):
            if strings[i][j] == '#':
                continue
            dp[i+1][j+1] += dp[i][j+1] % MOD if dp[i][j+1] != '#' else 0
            dp[i+1][j+1] += dp[i+1][j] % MOD if dp[i+1][j] != '#' else 0


    print(dp[-1][-1] % MOD)

if __name__ == '__main__':
    main()


Measured memory_bytes: 89820