akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<long long> a(n);
    for(int i=0;i<n;++i) cin>>a[i];

    sort(a.begin(),a.end(),greater<long long>());
    long long ans=a[0];
    int cur=2;
    int idx=1;
    while(n>cur){
        if(n-cur==1){
            ans+=a[idx++];
            ++cur;
        }
        else{
            ans+=2*a[idx++];
            cur+=2;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 4784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int INF = 0x7f7f7f7f;
//const ll p = 998244353;
#define DEBUG(x) cout << x << '\n'

struct Seg{ int l, r; } e[MAXN];
int n, ans;
int FindL(int k){ return e[k+1].r; }
int FindR(int k){ return e[k+1].l; }
Seg Find(int k){
    sort(e + 1, e + n + 1, [&](const Seg& a, const Seg& b){
         return a.r < b.r;
    });
    int r = FindL(k - 1);
    sort(e + 1, e + n + 1, [&](const Seg& a, const Seg& b){
         return a.l > b.l;
    });
    int l = FindR(n - k);
    return {l, r};
}
int main(){
#ifdef Irene
    freopen("in.txt", "r", stdin);
#endif // Irene
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> e[i].l >> e[i].r;
    if(n & 1){
        auto p = Find(n / 2 + 1);
        ans = max(0, p.r - p.l + 1);
    }
    else{
        auto p1 = Find(n / 2), p2 = Find(n / 2 + 1);
        ans = max(0, p1.r + p2.r - p1.l - p2.l + 1);
    }
    cout << ans;
}


Measured memory_bytes: 5208
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  int A,B;
  cin >> A >> B;
  if(A<=5){
    cout << 0 << endl;
  }else if(A >= 6 && A <= 12){
    cout << B/2 << endl;
  }else{
    cout << B << endl;
  }
  return 0;
}


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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;

const int MAXN = (int)2e5 + 10;
int n, k, l;
VVI connection[2];
void dfs(int here, VI& group, VVI& adj, int comp)
{
	group[here] = comp;
	for(auto there : adj[here]) {
		if(group[there] == -1) {
			dfs(there, group, adj, comp);
		}
	}
}

void countConnectivity()
{
	VI group[2];
	REP(i, 0, 2) group[i].resize(n, -1);

	for(int iter = 0; iter < 2; ++iter)
	{
		int comp = 0;
		for(int i = 0; i < n; ++i)
		{
			if(group[iter][i] == -1) {
				dfs(i, group[iter], connection[iter], comp);
				++comp; 			
			}
		}
	}

	map<PII, int> cnt;
	for(int i = 0; i < n; ++i) {
		//cerr << group[0][i] << " " << group[1][i] << '\n';
		++cnt[{group[0][i], group[1][i]}];
	}
	for(int i = 0; i < n; ++i)
		cout << cnt[{group[0][i], group[1][i]}] << " ";
	cout << flush;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
	cin >> n >> k >> l;

	REP(i, 0, 2) connection[i].resize(n);

	int u, v;
	REP(i, 0, k) {
		cin >> u >> v;
		--u; --v;
		connection[0][u].emplace_back(v);
		connection[0][v].emplace_back(u);
	}

	REP(i, 0, l) {
		cin >> u >> v;
		--u; --v;
		connection[1][u].emplace_back(v);
		connection[1][v].emplace_back(u);
	}

	countConnectivity();

	return 0;
}

Measured memory_bytes: 27776
import copy

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

INF = 10 ** 6
d = copy.deepcopy(c)
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

res = 0
for arr in A:
    for a in arr:
        if a == -1:
            continue
        else:
            res += d[a][1]

print(res)

Measured memory_bytes: 40284
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N = int(input())
uvw = []
for i in range(N - 1):
	uvw.append(list(map(int, input().split())))

tree = [dict() for i in range(N)]
for i in range(N):
	tree[i]["edge"] = []
	tree[i]["color"] = -1
for i in range(N - 1):
	tree[uvw[i][0] - 1]["edge"].append([uvw[i][0], uvw[i][1], uvw[i][2]])
	tree[uvw[i][1] - 1]["edge"].append([uvw[i][1], uvw[i][0], uvw[i][2]])

tansaku = deque([1])
tree[0]["color"] = 0
while len(tansaku) > 0:
	node = tansaku.pop()

	if len(tree[node - 1]["edge"]) == 0:
		continue
	for edge in tree[node - 1]["edge"]:
		if edge[2] % 2 == 0:
			if tree[edge[1] - 1]["color"] == -1:
				tree[edge[1] - 1]["color"] = copy.deepcopy(tree[node - 1]["color"])
				tansaku.append(edge[1])
		else:
			if tree[edge[1] - 1]["color"] == -1:
				tree[edge[1] - 1]["color"] = tree[node - 1]["color"] ^ 1
				tansaku.append(edge[1])
for i in range(N):
	print(tree[i]["color"])

Measured memory_bytes: 122588
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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; }

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;
const double PI = 3.1415926535897932;


int main(void)

{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << ketasitei;

	string s;
	cin >> s;

	ll ans = 0;

	ll tmp = 0;
	ll d[2019];
	ll dd[2019];
	for (int i = 0; i < 2019; i++)
	{
		d[i] = 0;
		dd[i] = 0;
	}

	for (int i = 0; i < s.size(); i++)
	{
		ll num = s[i] - '0';
		for (int j = 0; j < 2019; j++)
		{
			if (i % 2)
			{
				dd[(j * 10 + num) % 2019] = d[j];
			}
			else
			{
				d[(j * 10 + num) % 2019] = dd[j];
			}
		}
		if (i % 2)
		{
			dd[num]++;
			ans += dd[0];
		}
		else
		{
			d[num]++;
			ans += d[0];
		}

	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3808
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000 * 1000 * 1000 + 7;

int main()
{
	int N, M;
	cin >> N >> M;

	vector<int> ok(N + 1, true);
	for (int i = 0; i < M; ++i) {
		int a;
		cin >> a;
		ok[a] = false;
	}

	vector<int> dp(N + 1, 0);
	dp[0] = 1;
	for (int i = 0; i < N; ++i) {
		if (ok[i + 1]) {
			dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
		}
		if (i + 2 <= N && ok[i + 2]) {
			dp[i + 2] = (dp[i + 2] + dp[i]) % MOD;
		}
	}
	cout << dp[N] << endl;
}


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

using namespace std;
int main(){
    int r, d, x;
    cin >> r >> d >> x;
    long long ans = x * r -d;
    rep(i , 10){
        cout << ans << endl;
        ans = ans * r -d;
    }
    return 0;
}


Measured memory_bytes: 3600
#include "bits/stdc++.h"
using ll = long long;
using namespace std;

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  int n;
  cin >> n;

  n %= 1000;

  if(n) n = 1000 - n;

  cout << n;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	long long sum=0;
	int max=a[1];
	for(int i=2;i<=n;i++)
		if(a[i]<=max) sum=sum+max-a[i];
		else max=a[i];
	cout<<sum;
	return 0;
}

Measured memory_bytes: 4328
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

int main()
{
    fast_io
    ll n,m,ans;
    cin>>n>>m;
    ans=n*3+m;
    cout<<ans/2<<endl;



    return 0;
}





Measured memory_bytes: 3560
import os
import sys

import numpy as np


def solve(inp):
    def floor_sum(n, m, a, b):
        result = 0
        while True:
            result += (n - 1) * n * (a // m) // 2 + n * (b // m)
            a %= m
            b %= m

            y_max = (a * n + b) // m
            if y_max == 0:
                break

            x_max = y_max * m - b
            result += (n - (x_max + a - 1) // a) * y_max

            n, m, a, b = y_max, a, m, (a - x_max % a) % a
        return result

    t = inp[0]
    ans = np.zeros(t, np.int64)
    for i in range(t):
        n, m, a, b = inp[i * 4 + 1:i * 4 + 5]
        ans[i] = floor_sum(n, m, a, b)
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))


Measured memory_bytes: 36756
#include<stdio.h>

struct Pai
{
	char h;
	int A;
}; 

void BubbleSort(struct Pai A[],int N);
void SelectionSort(struct Pai A[],int N);
void Show(struct Pai A[],int N);
int isStable(struct Pai pai1[],struct Pai pai2[],int N);

int isStable(struct Pai pai1[],struct Pai pai2[],int N)	//利用冒泡排序恒为稳定可得选择排序是否稳定 
{
	int i,flag=1;
	for(i=0;i<N;i++)
		if(pai1[i].h!=pai2[i].h)
		{
			flag=0;
			break;
		}
	return flag;
}

void BubbleSort(struct Pai A[],int N)
{
	int i,j; 
	for(i=0;i<N;i++)
		for(j=N-1;j>=i+1;j--)
			if(A[j].A<A[j-1].A)
			{
				struct Pai temp;
				temp=A[j];
				A[j]=A[j-1];
				A[j-1]=temp;
			} 
}

void SelectionSort(struct Pai A[],int N)
{
	int i,minj,j;
	for(i=0;i<N;i++)
	{
		minj=i;
		for(j=i+1;j<N;j++)
			if(A[j].A<A[minj].A)
				minj=j;
		if(minj!=i)
		{			
			struct Pai temp;
			temp=A[i];
			A[i]=A[minj];
			A[minj]=temp;	
		}			
	}
}

void Show(struct Pai A[],int N)
{
	int i;
	for(i=0;i<N;i++)
	{
		if(i>0)
		    printf(" ");
		printf("%c",A[i].h);    
		printf("%d",A[i].A);
	}
	printf("\n");
}

int main()
{
	struct Pai pai1[50],pai2[50];
	int N,i;
	scanf("%d",&N); 
	for(i=0;i<N;i++)
	{
		getchar(); 
		scanf("%c",&pai1[i].h);
		scanf("%d",&pai1[i].A);
		pai2[i].h=pai1[i].h;
		pai2[i].A=pai1[i].A;
	}
	BubbleSort(pai1,N);	
	Show(pai1,N);
	printf("Stable\n");		
	SelectionSort(pai2,N);
	Show(pai2,N);
	if(isStable(pai1,pai2,N))
		printf("Stable\n");
	else
		printf("Not stable\n");	
	return 0;
} 


Measured memory_bytes: 2108
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
UF = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    UF.union(a - 1, b - 1)
print(UF.group_count() - 1)


Measured memory_bytes: 75460
#include<bits/stdc++.h>
#define ll          long long int
#define lld          long double
#define pb          push_back
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define vec         vector<ll>
#define all(a)     (a).begin(),(a).end()
#define F           first
#define S           second
#define mod         1000000007
#define nmod         -1000000007
#define N            1000000//31630=sqrt(pow(10,9))
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repi(i,a,b)	for(ll  i=a;i<=b;i++)
#define per(i,a,b)  for(ll i=a;i>=b;i--)
#define mp          make_pair
#define mit         map<ll,ll>::iterator
#define sit         set<ll>::iterator
#define pit         pair<ll,ll>::iterator
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;
ll xo(ll x, ll y) 
{ 
   return (x | y) & (~x | ~y); 
}  
ll bin_Expo(ll x,ll n)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return bin_Expo(x*x,n/2);
    else                             //n is odd
        return x*bin_Expo(x*x,(n-1)/2);
}
ll mod_Expo(ll x,ll n,ll M)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return mod_Expo((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*mod_Expo((x*x)%M,(n-1)/2,M))%M;
 
}
//bool pf[N+1ll];
//vec prim;
//void sieve()
//{
//    repi(i,0,N)
//    pf[i]=true;
//	pf[0] = pf[1] = false;
//    for (int i = 2; i <= N; i++) {
//        if (pf[i]) 
//		{
//            prim.push_back(i);
//            for (int j = i + i; j <= N; j+=i) {
//                pf[j] = false;
//            }
//        }
//    }
//}
bool prime_check(ll x)
{
    bool prime = (x >= 2);
    for (ll i = 2; i * i <= x; i++) 
    {
        if (x % i == 0) 
        {
            prime = false;
            break;
        }
    }
    return prime;
}
ll logg(ll base,ll x) 
{
    return (ll)(log(x) / log(base));
}
pii a[2005];
ll dp[2005][2005],n;
ll ss(ll l,ll r)
{
	if(dp[l][r]!=-1)
	return dp[l][r];
	
	ll ind1 = n-(r-l+1)+1;
	ll no = a[ind1].F; ll ind = a[ind1].S;
	if(l==r)
	return dp[l][r]=no*abs(l-ind);
	else
	return dp[l][r] = max(ss(l+1,r)+no*(abs(l-ind)),ss(l,r-1)+no*abs(r-ind));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS; 
    while(TESTS--)
    {
    	ll m,i,l,h,j,k;
    	cin>>n;
    	repi(i,1,n)
    	{
    		cin>>j;
    		a[i]={-1*j,i};
		}
		sort(a+1,a+1+n);
		repi(i,1,n)
		a[i].F=-1*a[i].F;
    	memset(dp,-1,sizeof(dp));
    	cout<<ss(1,n);
	}
	return 0;
} 

Measured memory_bytes: 35260
#include<bits/stdc++.h>
using namespace std;
#define int long long

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

  vector<int> v(5);
  for(int i = 0; i < 5; i++){
    cin >> v[i];
  }
  int k; cin >> k;
  for(int i = 0; i < 5; i++){
    for(int j = 0; j < 5; j++){
      if(abs(v[i] - v[j]) > k){
        cout << ":(" << endl;
        return 0;
      }
    }
  }
  cout << "Yay!" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(){
    int n, score_taro=0, score_hanako=0;
    cin >> n;
    string card_taro, card_hanako;
    for(int i = 0; i != n; ++i){
        cin >> card_taro >> card_hanako;
        if (card_taro > card_hanako){
            score_taro += 3;
        }else if (card_taro < card_hanako){
            score_hanako += 3;
        }else{
            score_taro += 1;
            score_hanako += 1;
        }
    }
    cout << score_taro << ' ' << score_hanako << endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, init, n) for (int i = init; i < (n); i++)
#define fi first
#define se second

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to, cost;
};

const int MOD = 1e9 + 7;
const int iINF = 1e9;
const long long int llINF = 1e18;
const double PI = acos(-1.0);

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

int main()
{
    int N;
    while (cin >> N && N)
    {
        vector<ll> m(N), a(N), b(N), times;
        vector<int> weight(2 * N + 1, 0);
        map<ll, ll> zip;
        rep(i, N)
        {
            cin >> m[i] >> a[i] >> b[i];
            times.push_back(a[i]);
            times.push_back(b[i]);
        }

        sort(times.begin(), times.end());
        times.erase(unique(times.begin(), times.end()), times.end());

        rep(i, times.size())
        {
            zip[times[i]] = i;
        }

        rep(i, N)
        {
            weight[zip[a[i]]] += m[i];
            weight[zip[b[i]]] -= m[i];

            // cout << zip[a[i]] << " " << zip[b[i]] << endl;
        }

        rep(i, 2 * N + 1) weight[i + 1] += weight[i];

        string ans = "OK";

        // rep(i, 2 * N + 1) cout << weight[i] << " ";
        
        rep(i, 2 * N + 1) if(150 < weight[i]) ans = "NG";

        cout << ans << endl;


    }
    return 0;
}


Measured memory_bytes: 3184
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define incm(x,y) {x=((x)+(y))%mod;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int lg=32;
int n,m,i,j,cnt,pw[69];
int gpw(int a,int b) // a * 2^b
{
	int i;
	while(b--){
		printf("+ %d %d %d\n",a,a,a); 
	}
	return a;
}
int gand(int a,int b) // a & b
{
	int c=++cnt;
	printf("< %d %d %d\n",a,b,c);
	int d=++cnt;
	printf("< %d %d %d\n",c,a,d);
	int e=++cnt;
	printf("< %d %d %d\n",c,b,e);
	int f=++cnt;
	printf("+ %d %d %d\n",d,e,f);
	int g=++cnt;
	printf("< %d %d %d\n",pw[0],f,g);
	return g;
}
void add(int c,int a,int b) // c += a * b
{
	int i,lst=++cnt;
	fd0g(i,lg*2-1){
		int nxt=++cnt;
		printf("+ %d %d %d\n",lst,pw[i],nxt); 
		int f=++cnt;
		printf("< %d %d %d\n",a,nxt,f);
		printf("< %d %d %d\n",f,pw[0],f);
		int g=++cnt;
		printf("+ %d %d %d\n",f,g,g); 
		f=gpw(f,i);
		printf("+ %d %d %d\n",lst,f,lst); 
		g=gand(g,b);
		g=gpw(g,i);
		printf("+ %d %d %d\n",c,g,c); 
	}
}
void divmod(int a,int b,int c) // a / 2 = b ...... c
{
	int i;
	fd0k(i,lg){
		int nxt=++cnt;
		printf("+ %d %d %d\n",b,pw[i],nxt);
		printf("+ %d %d %d\n",nxt,nxt,nxt);
		int f=++cnt;
		printf("< %d %d %d\n",a,nxt,f);
		printf("< %d %d %d\n",f,pw[0],f);
		int g=++cnt;
		printf("+ %d %d %d\n",f,g,g);
		f=gpw(f,i);
		printf("+ %d %d %d\n",b,f,b);
	}
	int nxt=++cnt;
	printf("+ %d %d %d\n",b,b,nxt);
	printf("+ %d %d %d\n",nxt,pw[0],nxt);
	printf("< %d %d %d\n",a,nxt,c);
	printf("< %d %d %d\n",c,pw[0],c);
}
void solve(int a,int b,int c,int l) // c = a * b
{
	if(l==0){
		return;
	}
	int t1=++cnt,t2=++cnt;
	divmod(a,t1,t2);
	add(c,b,t2);
	printf("+ %d %d %d\n",b,b,b);
	solve(t1,b,c,l-1);
}
int main()
{
//	freopen("1.txt","w",stdout);
//	cnt=1;int t=gand(0,1);printf("! %d 0 0\n",t);
	puts("173793"); 
	puts("+ 0 1 3");
	puts("< 2 3 3");
	cnt=3;
	pw[0]=3;fz1(i,lg*2-1){
		pw[i]=++cnt;
		printf("+ %d %d %d\n",pw[i-1],pw[i-1],pw[i]); 
	}
	solve(0,1,2,lg);
	return 0;
}

Measured memory_bytes: 3672
#include <stdio.h>
#include <string.h>

int main(void)
{
	int i, j;
	int a[2][1000];
	int n, m;
	int num;
	int max[2];
	
	memset(a, 0, sizeof(a));
	
	scanf("%d %d", &n, &m);
	
	for (i = 0; i < n; i++){
		scanf("%d", &a[0][i]);
	}
	
	max[0] = max[1] = 0;
	for (i = 0; i < m; i++){
		scanf("%d", &num);
		
		j = -1;
		while (a[0][++j] > num);
		
		if (++a[1][j] > max[0]){
			max[0] = a[1][j];
			max[1] = j;
		}
	}
	
	printf("%d\n", max[1] + 1);
	
	return (0);
}

Measured memory_bytes: 604
#include <cstdio>

int main() {
	int n, m, Ai, Bj, max;
	int A[1000];
	int B[1000];
	int count[1000] = {0};
	int maxcount = 0;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		scanf("%d", &Ai);
		A[i] = Ai;
	}
	for(int j = 0; j < n; j++) {
		scanf("%d", &Bj);
		B[j] = Bj;
	}
	for(int j = 0; j < m; j++) {
		for(int i = 0; i < n; i++) {
			if(A[i] <= B[j]) {
				count[i]++;
				break;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		if(count[i] > maxcount) {
			maxcount = count[i];
			max = i + 1;
		}
	}
	printf("%d\n", max);
	return 0;
}

Measured memory_bytes: 1036
#include<iostream>
#include<vector>
#define rep(i,n) for (int i=0; i< (n); i++)
using namespace std;

int main(void){

    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];

    A.push_back(A[0]+K);//円周K+原点～最初の家までの距離の和を追加
    int L=0;//2点間のパスが最大のものを格納する
    rep(i,A.size()){

        if(L<A[i+1]-A[i]){
            L=A[i+1]-A[i];
        }
    }
    cout << K-L << endl;

    return 0;
}

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

#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;++i)
#define R(i,a,b) for(int i=a;i<=b;++i)

int n,m,x;
int a[1001000];

int main()
{
    cin>>n>>m>>x;
    F(i,0,n)F(j,0,m) a[(n-i)*j+i*(m-j)]=1;
    if(a[x]==0) puts("No");else puts("Yes");
    return 0;
}


Measured memory_bytes: 4096
A, B = gets.split(' ').map(&:to_i)
if B > A
  a, b = B, A
else
  a, b = A, B
end
r = a % b
if r == 0
  puts a
  exit
end
while b != 0 do
  a, b = b, a % b
end
gcd = a
puts A * B / gcd

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
const long long INF = INT64_MAX;

#define REP(i, n) for(ll i=0;i<n;i++)
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).rbegin(), (v).rend())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define DESC(v) sort((v).rbegin(), (v).rend())
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);erase(unique(v.begin(), v.end()), v.end())
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);

void solve() {
    str S;
    ll ctr = 0;
    cin >> S;
    for(int i = 0; i < S.size(); i++) {
        if(i == 0) {
            if(S[i] != 'A') {
                cout << "WA" << endl;
                return;
            }   
        }else {
            if(S[i] == 'C' && i >= 2 && i <= S.size() - 2) {
                ctr++;
                if(ctr >= 2){
                    cout << "WA" << endl;
                    return;
                }
            }else if(!(S[i] >= 'a' && S[i] <= 'z')) {
                cout << "WA" << endl;
                return;
            }
        }
    }
    if(ctr == 1)
    cout << "AC" << endl;
    else
    cout << "WA" << endl;

    return;
}

int main() {
    FIO;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef pair<string,string> Pstring;
typedef pair<double,double> Pdouble;


#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define Precision13 cout << fixed << setprecision(13)
const double PI=3.14159265358979323846;
const int MAX = 510000;
const int MOD = 1000000007;
const int INF = 1<<29;
using Graph = vector<vector<int>>;


map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}


int main() {
  
  ll N;
  cin >> N;

  vector<ll> so;
  map<ll,ll> Map;

  for(auto p : prime_factor(N)) {
    while(p.second--){
      so.push_back(p.first);
    }
  }
  ll count = 0;
  ll ans = 0;
  ll cd = 1;

  REP(i,so.size()){
    Map[so[i]]++;
    if(i==0 || (i>=1 && so[i]!=so[i-1])){
      Map[so[i]] = 0;
      cd = 2;
      ans++;
    }else{
      if(Map[so[i]]==cd){
        Map[so[i]] = 0;
        cd++;
        ans++;
      }
    }
  }

  cout << ans << endl;
  
}


Measured memory_bytes: 3632
#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<ll,ll>;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}


int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll b=a[1],c=0,d=a[0];
  if(n==2) {
    c=max(d,b);
      pt(c);
    return 0;
  }
  for(int i=2; i<n; i++) {
      if(i%2==0) {
          b=max(d,b);
          c+=a[i];
          d+=a[i];
      }
      else {
          c=max(b,c);
          b+=a[i];
      }
  }
  if(n%2==1) {
      c=max(c,b);
      pt(c);
  }
  if(n%2==0) {
    c=max(d,b);
      pt(c);
  }
  
  return 0;
}



Measured memory_bytes: 4796
// created_by  Rishi_Mohan

#include<bits/stdc++.h>

#define    ll           long long
#define    db1(x)       cout<<#x<<"="<<x<<'\n'
#define    db2(x,y)     cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define    db3(x,y,z)   cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

using namespace std;

void solve()
{
   string s1,s2;
   cin >> s1 >> s2;
   s2.erase(s2.begin()+s2.size()-1);
   if(s1==s2) cout << "Yes";
   else cout << "No";
}

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


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N, T;
ll A[MAX_N] = {};
ll MaxVal[MAX_N] = {};  // [i, N-1] の最大値

signed main()
{
    cin >> N >> T;
    REP(i, N) { cin >> A[i]; }

    ll cur = 0;
    ll max_sub = 0;
    for(int i = N-1; i >= 0; --i) {
        cur = max(cur, A[i]);
        MaxVal[i] = cur;
        max_sub = max(max_sub, MaxVal[i] - A[i]);
    }

    ll ans = 0;
    REP(i, N) {
        if(MaxVal[i] - A[i] == max_sub) { ans++; }
    }
    printf("%lld\n", ans);
    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
string S;

vint G[222222];

int cntA[222222],cntB[222222];
bool used[222222];

signed main(){
    cin>>N>>M>>S;
    rep(i,M){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    rep(v,N)for(auto u:G[v]){
        if(S[u]=='A')cntA[v]++;
        else cntB[v]++;
    }

    queue<int>que;
    rep(v,N)if(cntA[v]==0||cntB[v]==0){
        used[v]=true;
        que.push(v);
    }
    while(que.size()){
        int v=que.front();que.pop();
        for(auto u:G[v]){
            if(used[u])continue;
            if(S[v]=='A')cntA[u]--;
            else cntB[u]--;
            if(cntA[u]==0||cntB[u]==0){
                used[u]=true;
                que.push(u);
            }
        }
    }

    if(count(used,used+N,false)!=0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 16644
import sys
from sys import stdin,stdout
import math
import time
from functools import lru_cache
from collections import Counter
import heapq
#@lru_cache(maxsize=None) #for optimizing the execution time of callable objects/functions(placed above callable functions)
try:
    for _ in range(1):
        n=int(input())
        arr=[int(i) for i in input().split()]
        ans=0
        mx=arr[0]
        for i in range(n):
            if arr[i]<mx:
                ans+=mx-arr[i]
                mx=max(arr[i],mx)
            else:
                mx=arr[i]
        print(ans)
except EOFError as e:
    print(e)


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

long long n;
map <long long,int> m;

int f(int x)
{
	int i=1,s=0;
	while(s<x) s+=i,i++;
	return s==x?i-1:i-2;
}

int main()
{
	cin>>n;

	int r=sqrtl(n);
	for(int i=2;i<=r;i++)
		while(n%i==0) m[i]++,n/=i;

	if(n!=1) m[n]++;

	int ans=0;
	for(auto i:m) ans+=f(i.second);
	cout<<ans;
}

Measured memory_bytes: 3656
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = sorted([int(input()) for _ in range(n)])

    # See:
    # https://img.atcoder.jp/abc115/editorial.pdf
    print(sum(p) - max(p) // 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
random_device rnd;
mt19937 mt(rnd());

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

map<int, ll> D;
map<int, ll> C;

vector<ll> dijkstra(map<int, vector<pair<int, pair<ll, ll>>>> &g, int v, int start, ll startmoney) //{行き先,{通行時間,銀貨}}
{
    vector<ll> cost(v, INF);
    vector<ll> money(v, 0);

    int cur = start;
    priority_queue<pair<ll, pair<int, ll>>, vector<pair<ll, pair<int, ll>>>, greater<pair<ll, pair<int, ll>>>> pque; //{コスト, 今いるとこ, お金}
    rep(i, 250)
    {
        pque.push({0ll + D[start] * i, {start, startmoney + C[start] * i}});
    }
    while (!pque.empty())
    {

        cur = pque.top().second.first;
        ll curmoney = pque.top().second.second;
        assert(cur >= 0);
        ll curcost = pque.top().first;
        pque.pop();
        if ((curcost >= cost[cur] && curmoney <= money[cur]) || curmoney < 0)
        {
            continue;
        }
        chmin(cost[cur], curcost);
        chmax(money[cur], curmoney);

        for (auto x : g[cur])
        {
            int to = x.first;
            ll costtime = x.second.first;
            ll costmoney = x.second.second;
            ll curchangenum = 0;
            while (curmoney + C[cur] * curchangenum - costmoney <= 250 || curchangenum == 0)
            {
                pque.push({curcost + costtime + D[cur] * curchangenum, {to, curmoney - costmoney + C[cur] * curchangenum}});
                curchangenum++;
            }
        }
    }
    return cost;
}

int main()
{
    ll n, m, s;
    cin >> n >> m >> s;
    map<int, vector<pair<int, pair<ll, ll>>>> g;
    rep(i, m)
    {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        g[u].push_back({v, {b, a}});
        g[v].push_back({u, {b, a}});
    }
    rep(i, n)
    {
        int t1, t2;
        cin >> t1 >> t2;
        C[i] = t1;
        D[i] = t2;
    }
    auto ans = dijkstra(g, n, 0, s);
    rep(i, 1, n)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 9376
#include<bits/stdc++.h>
using namespace std;
int h,a,cnt=0,flag=1;
int main()
{
	cin>>h>>a;
	while(flag){
		h=h-a;
		if(h==0||h<0){
			flag=0;
		}
		cnt++;
	}
	cout<<cnt;
	
	
	return 0;
 } 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#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 mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    string s;cin>>s;
    ll k=s.size();
    rep(i,s.size()-1){
        if(s[i]!=s[i+1])k=min(k,max((ll)s.size()-1-i,(ll)i+1));
    }
    cout<<k<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n, m;
  cin >> n >> m;
  map<int, set<P>> pres;
  rep(i, m) {
    int p, y;
    cin >> p >> y;
    pres[p].insert(P(y, i));
  }
  vector<P> ans(m);
  for(auto pre : pres) {
    int i = 1;
    for(auto p : pre.second) {
      P np = P(pre.first, i);
      ans[p.second] = np;
      i++;
    }
  }
  for(auto p : ans) {
    printf("%06d%06d\n", p.first, p.second);
  }
}

Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e15;

using namespace std;
signed main(){
  int n,K;
  cin>>n>>K;
  vector<int> x(n),y(n),ox(n),oy(n);
  rep(i,n){
    cin>>x[i]>>y[i];
    ox[i]=x[i];
    oy[i]=y[i];
  }
  sort(all(ox));
  sort(all(oy));

  int ans=(oy.back()-oy[0])*(ox.back()-ox[0]);
  rep(i,n){
    loop(j,i+1,n){
      rep(k,n){
        loop(l,k+1,n){
          int left=ox[i];int right=ox[j];
          int low=oy[k];int high=oy[l];
          int area=abs(right-left)*abs(high-low);
          int cnt=0;
          rep(m,n)if(left<=x[m]&&x[m]<=right&&low<=y[m]&&y[m]<=high)cnt++;
          if(cnt>=K)ans=min(ans,area);
        }
      }
    }
  }

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


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

using namespace std;

int main(){

	int x, tmp;

	cin>> x;

	if (2000 <= x) {
		cout << "1" << endl;
		return 0;
	}

	for (int a = 0;a < 21;a++) {
		for (int b = 0;b < 21;b++) {
			for (int c = 0;c < 21;c++) {
				for (int d = 0;d < 21;d++) {
					for (int e = 0;e < 21;e++) {
						tmp = a * 100 + b * 101 + c * 102 + d * 103 + e * 104;
						if (x >= tmp && (x - tmp) % 105 == 0) {
							cout << "1" << endl;
							return 0;
						}
					}
				}
			}
		}
	}

	cout<< "0" << endl;


}


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

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

    bool n = false, w = false, s = false, e = false;
    for(int i=0; i<S.size(); ++i) {
        switch(S[i]) {
            case 'N': n = true; break;
            case 'W': w = true; break;
            case 'S': s = true; break;
            case 'E': e = true; break;
        }
    }
    if(n == s && w == e) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,d,a,q,l,r,i,j;
  cin>>h>>w>>d;
  vector<int> x(h*w),y(h*w);
  vector<vector<int>> z(d,vector<int>(0));
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin>>a;
      x.at(a-1)=i;
      y.at(a-1)=j;
    }
  }
  for(i=0;i<h*w;i++){
    if(i/d==0) z.at(i%d).push_back(0);
    else z.at(i%d).push_back(z.at(i%d).at(i/d-1)+abs(x.at(i)-x.at(i-d))+abs(y.at(i)-y.at(i-d)));
  }
  cin>>q;
  for(i=0;i<q;i++){
    cin>>l>>r;
    l--;
    r--;
    cout<<z.at(r%d).at(r/d)-z.at(l%d).at(l/d)<<endl;
  }
}

Measured memory_bytes: 8548
using System;

namespace A___AtCoder_Beginner_Contest_999
{
    class Program
    {
        static void Main(string[] args)
        {
            var n =Console.ReadLine();
            for(var i=0; i<n.Length; i++)
            {
                if(n[i]=='1')
                {
                    Console.Write('9');
                }
                else
                {
                    Console.Write('1');
                }
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 11092
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    m, n, K = map(int, input().split())
    m -= 1; n -= 1
    mf = modfact(m + n)
    block = [None] * K
    for k in range(K):
        i, j = map(int, input().split())
        i -= 1; j -= 1
        block[k] = (i, j)
    block.append((m, n))
    K += 1
    block.sort(lambda tup : tup[0] + tup[1])

    dp = [0] * K
    for k in range(K):
        i, j = block[k]
        dp[k] += mf.comb(i + j, i)
        for k0 in range(k):
            pi, pj = block[k0]
            dp[k] -= dp[k0] * mf.comb((i - pi) + (j - pj), i - pi)
            dp[k] %= MOD

    print(dp[-1])
resolve()

Measured memory_bytes: 46572
#include<bits/stdc++.h>
using namespace std;
long long int n2;
int m,q,ct,n;
int f[111111][7];
bool g[111111];
void dfs(int x,int y){
	if(x<0 || x>=n || y<0 || y>=7 || f[x][y]!=-2)return;
	f[x][y] = ct;
	dfs(x-1,y);
	dfs(x,y-1);
	dfs(x+1,y);
	dfs(x,y+1);
}

set<int> S;
set<pair<int,int> > E;
int ace[99];
int ancestor(int x){return x-ace[x]?ace[x]=ancestor(ace[x]):x;}
int calc(){
	map<int,int> Map;
	int z = 0;
	for(set<int>::iterator it = S.begin(); it!=S.end(); it++){
		Map[*it] = z++;
	}
	for(int i=0; i<z; i++)
		ace[i] = i;
	for(set<pair<int,int> >::iterator it = E.begin(); it!=E.end(); it++){
		ace[ancestor(Map[it->first])]=ancestor(Map[it->second]);
	}
	int res = 0;
	for(int i=0; i<z; i++){
		if(ancestor(i) == i)
			res++;
	}
	return z - res;
}

int main(){
	cin>>n2>>m>>q;
	if(m%7==0)
		n=m/7;
	else
		n=m;

	for(int i=0; i<q; i++){
		int x;
		cin>>x;
		g[x] = true;
	}
	memset(f,-1,sizeof(f));
	for(int i=0; i<n; i++)
		for(int j=0; j<7; j++)
			if(!g[(i*7+j)%m])
				f[i][j] = -2;
	for(int i=0; i<n; i++)
	for(int j=0; j<7; j++)
	if(f[i][j] == -2){
		dfs(i,j);
		ct++;
	}
	for(int j=0; j<7; j++){
		int x = f[0][j], y=f[n-1][j];
		if(x!=-1)S.insert(x);
		if(y!=-1)S.insert(y+ct);
		if(x!=-1 && y!=-1){
			E.insert(make_pair(x,y+ct));
		}
	}
	int dec = calc();
	cout << (n2 / n) * ct - (n2/n-1)*dec << endl;
	return 0;
}


Measured memory_bytes: 11520
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

s = arr_data[0][1][0]

print("A"+s+"C")


Measured memory_bytes: 3068
# D - Checker

N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

print(ans)

Measured memory_bytes: 55384
# (()(()))  level
# (      ) --  0
#  ()(  )  -- -1
#     ()   -- -2
# 変化を計算して、
# - 最後0で終わる
# - 途中で0より大きくなることがない
# 変化量の合計は並べる順番に依存しない。
# 0より大きくならないようにするには、できるだけ深く潜るようにすればいい。

n = gets.to_i

level_sum = 0
downs = Array.new
equals = Array.new
ups = Array.new
n.times do
  s = gets.chomp
  level = 0
  highest = 0
  s.each_char do |c|
    if c == '('
      level -= 1
    else
      level += 1
      highest = level if level > highest
    end
  end
  level_sum += level
  if level < 0
    downs.push [level, highest]
  elsif level == 0
    equals.push [level, highest]
  else
    ups.push [level, highest]
  end
end

# 変化の合計量のチェック
if level_sum != 0
  puts 'No'
  exit(0)
end

# できるだけ0より大きくならないように並べ替える
downs = downs.sort_by{|level, highest| highest}
ups = ups.sort_by{|level, highest| - highest + level}

level_sum = 0
[downs, equals, ups].each do |sub|
  sub.each do |level, highest|
    if level_sum + highest > 0
      puts 'No'
      exit(0)
    end
    level_sum += level
  end
end

puts 'Yes'


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

#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi 3.14159265
#define oo 1000000007
#define loo 10000000000000007

#define prime 1000000007

#define W(x) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << "\n";
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, k; cin >> n >> k;
    cout << min(n%k, k-n%k) << endl;


    return 0;
}

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

inline void solve(){
    int a,b; 
    cin>>a>>b; 
    for (int i=1;i<=10000;i++){
        if (((int)(i*0.08)==a) and ((int)(i*0.1)==b)) {
          cout << i << endl;
          return;
        }
    }
    cout << -1 << endl;
}

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


Measured memory_bytes: 3644
a=input()
M=int(a[0]+a[1])
Y=int(a[2]+a[3])

if(M==0):
  if(Y==0):
    print('NA')
  else:
    print('YYMM')
elif(M>12):
  if(Y==0):
    print('NA')
  elif(Y>12):
    print('NA')
  else:
    print('YYMM')
else:
  if(Y==0):
    print('MMYY')
  elif(Y<13):
    print('AMBIGUOUS')
  else:
    print('MMYY')

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

#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define revp(i,a,b)     for(int i=b;i>=a;i--)

int a;
int main()
{
    
    cin>>a;
    if(a<1200)
        cout<<"ABC";
    else
        cout<<"ARC";
}




Measured memory_bytes: 256
from heapq import heapify,heappop,heappush

class Graph:
    def __init__(self,V,E):
        self.V = V
        self.E = E

    def dijkstra(self,st):
        INF = 10**9+1
        D = [INF for i in range(len(self.V))]
        #D[i]:頂点iまでの距離
        D[st] = 0
        Q = [[0,st]]
        Used = set()
        #既に最短距離が確定した頂点の集合
        
        while len(Used) < len(self.V):
            p = heappop(Q)
            p_dist,p_ind = p[0],p[1]
            for e in self.E[p_ind]:
                to,cost = e[0],e[1]
                if to not in Used:
                    if D[to] > D[p_ind] + cost:
                        D[to] = D[p_ind] + cost
                        heappush(Q,[D[to],to])
            Used.add(p_ind)

        return D

def main():
    n = int(input())
    V = [i for i in range(n)]
    E = [set() for _ in range(n)]
    #E[i]:頂点iからの向かう先と重みの組
    #(to,cost) in E[i]は辺(i,to)の重みがcostであることを意味する
    for i in range(n):
        I = list(map(int,input().split()))
        for j in range(2,len(I)):
            if j % 2 == 0:
                E[i].add((I[j],I[j+1]))

    G = Graph(V,E)

    ans = G.dijkstra(0)
    for i in range(n):
        print(i,ans[i])

if __name__ == "__main__":
    main()



Measured memory_bytes: 95612
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

vector<int> g[100005];
int dp[100005];
bool vis[100005];

int dfs(int u){
    if(dp[u] != -1)return dp[u];
    vis[u] = 1;
    int ans = 0;
    for(auto & v : g[u]){
        ans = max(ans, dfs(v) + 1);
    }
    return dp[u] = ans;
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
    }
    memset(vis, 0, sizeof vis);
    memset(dp, -1, sizeof dp);
    int mmax = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            mmax = max(mmax, dfs(i));
        }
    }
    cout << mmax << endl;
    return 0;
}


Measured memory_bytes: 8192