akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
input = stdin.readline
n = int(input())
adj = [[] for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
qn, k = map(int,input().split())

from collections import deque
dist = [-1]*(n+1)
dist[k] = 0
Q = deque()
Q.append(k)
while len(Q):
    p = Q.popleft()
    for q,c in adj[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)
for i in range(qn):
    x, y = map(int,input().split())
    print(dist[x]+dist[y])

Measured memory_bytes: 44584
// ITP1_2_C.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>

using namespace std;

int swap(int a, int b)
{
    int s;
    if (a > b)
    {
        s = a;
        a = b;
        b = s;
    }
    return a, b;
}

int main()
{
    int a[3];
    int i, min, mid, max;
    cin >> a[0] >> a[1] >> a[2];
    min = a[0];
    for (i = 1; i < 3; i++)
    {
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    max = a[0];
    for (i = 1; i < 3; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    for (i = 0; i < 3; i++)
    {
        if (a[i] != min && a[i] != max)
        {
            mid = a[i];
            break;
        }
    }
    cout << min << " " << mid << " " << max << endl;
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します



Measured memory_bytes: 3096
#include <bits/stdc++.h>
// #include<iostream>
// #include<vector>
// #include<cmath>
// #include<iomanip>
using namespace std;

const double PI= acos(-1.0);

int gcd_func(int a, int b){
    return b? gcd_func(b, a%b) : a;
} 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
   //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int x,n; cin >> x >> n;
    map<int,int>p;
    for(int i = 0; i < n; i++){
        int ipt;
        cin >> ipt;
        p[ipt] = 1;
    }
    int v1 = x, v2 = x;
    while(true){
        if(p.find(v1)==p.end()){
            cout << v1 << endl;
            break;
        }
        else if(p.find(v2) == p.end()){
            cout << v2 << endl;
            break;
        }
        v1--;
        v2++;
    }
    return 0;
}

Measured memory_bytes: 3576
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.IO.Pipes;
using System.Linq;

namespace AtCoder
{
	public class ABC
	{
		static public void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
			Solve(args);
			Console.Out.Flush();
		}

		private const int mod = 1000000007;  // 10^9+7

		static public void Solve(string[] args)
		{
			//int k = int.Parse(Console.ReadLine());
			//string s = Console.ReadLine();
			//long x = long.Parse(Console.ReadLine());
			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			//long[] vs = Console.ReadLine().Split().Select(long.Parse).ToArray();
			int n = vs[0];
			int m = vs[1];
			List<Room> cave = new List<Room>();
			cave.Add(new Room { No = 0, Guide = 0 });
			for (int i = 1; i <= n; i++) {
				cave.Add(new Room { No = i, Guide = 0 });
			}
			for (int i = 0; i < m; i++) {
				vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
				int a = vs[0];
				int b = vs[1];
				cave[a].Route.Add(b);
				cave[b].Route.Add(a);
			}
			cave[1].Guide = 1;

			Queue<int> queue = new Queue<int>();
			queue.Enqueue(1);
			while (queue.Count > 0) {
				int index = queue.Dequeue();
				foreach (var i in cave[index].Route) {
					if (cave[i].Guide == 0) {
						cave[i].Guide = index;
						queue.Enqueue(i);
					}
				}
			}

			//for (int i = 1; i <= n; i++) {
			//	System.Diagnostics.Debug.WriteLine(cave[i]);
			//}
			//System.Diagnostics.Debug.WriteLine("");

			for (int i = 1; i <= n; i++) {
				if (cave[i].Guide == 0) {
					Console.WriteLine("No");
					return;
				}
			}
			Console.WriteLine("Yes");
			for (int i = 2; i <= n; i++) {
				Console.WriteLine(cave[i].Guide);
			}


		}
	}

	public class Room
	{
		public int No;
		public List<int> Route = new List<int>();
		public int Guide;

		public override string ToString()
		{
			return $"{No},{Guide},({string.Join(",", Route)  })";
		}

	}

}


Measured memory_bytes: 56760
N = int(input())
res = N
for i in range(N+1):
  cc = 0
  t = i
  while t>0:
    cc += t % 6
    t = t // 6
  t = N - i
  while t>0:
    cc += t % 9
    t = t // 9
  if cc < res:
    res = cc
print(res)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;



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


    int numBra = 0, numCket = 0;
    for( int i = 0; i < N; ++i )
    {
        if( S[i] == '(' ) ++numBra;
        if( S[i] == ')' )
        {
            if( numBra > 0 ) --numBra;
            else ++numCket;
        } 
    }

    for( int i = 0; i < numCket; ++i ) cout << '(';
    cout << S;
    for( int i = 0; i < numBra; ++i ) cout << ')';
 
    return 0;
} 

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

int main(){
	string a,b;
	cin >> a >> b;
	int lena = a.size();
	int lenb = b.size();
	if(lena > lenb){
		cout << "GREATER" << endl;
		return 0;
	}
	else if(lena < lenb){
		cout << "LESS" << endl;
		return 0;
	}
	else{
		rep(i,lena){
			if((a[i]) - '0' > (b[i]) - '0'){
				cout << "GREATER" << endl;
				return 0;
			}else if((a[i]) - '0' < (b[i]) - '0'){
				cout << "LESS" << endl;
				return 0;
			}
		}
	}
	cout << "EQUAL" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n,q;
ll a[100010];
ll cum[100010];
ll cumo[100010];//cumo[i]=[0,i)の偶数indexの和

int bs(int x){
	//a[i]>xなる最小のi
	if(a[0]>x)return 0;
	ll l=0,r=n;//lはng,rはok
	while(r-l>1){
		int m=(l+r)/2;
		if(a[m]>x)r=m;
		else l=m;
	}
	return r;
}

int main(){
	scanf("%lld%lld",&n,&q);
	rep(i,0,n)scanf("%lld",a+i);
	rep(i,0,n)cum[i+1]=cum[i]+a[i];
	rep(i,0,n)cumo[i+1]=cumo[i]+(i%2==0?a[i]:0);
	rep(i,0,q){
		ll x;
		scanf("%lld",&x);
		//xがどこにあるかにぶたん
		ll idx=bs(x);
		//相手との衝突位置をにぶたん
		ll l=idx,r=n;//lはありえる、rはありえない
		while(r-l>1){
			int m=(l+r)/2;
			ll temp=llabs(a[m-1]-x);
			int iii=bs(x-temp-1);
			if(m-iii<=n-m)l=m;
			else r=m;
		}
//		printf("%lld ",l);
		//のこりは累積和でえい
		int iii=l-(n-l);
		ll ans=cum[l]-cum[iii];
		//のこりiii個を太郎から取る
		if(iii%2==0)ans+=cumo[iii];
		else ans+=cum[iii]-cumo[iii];
		printf("%lld\n",cum[n]-ans);
	}
}


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    int ans=0;
    rep(i,n){
        if(a[a[i]] == i ){
            ans++;
        }
    }
    cout << ans/2 << endl;
    
    return 0;
}


Measured memory_bytes: 640
s=list(input())
hs=[0]*4
for i in range(4):
    s[i]=int(s[i])
    hs[i]=s[i]

op=[[0],[1]]

for i in range(3):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
    op=tmp

for i in op:
    s=hs
    for j in range(3):
        if i[j]==0:
            s[j+1]=-s[j+1]
    if sum(s)==7:
        break

ans=str(s[0])
for i in range(3):
    if s[i+1]<0:
        ans+="-"
    else:
        ans+="+"
    ans+=str(abs(s[i+1]))
print(ans+"=7")
            
            
    

Measured memory_bytes: 3064
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (int)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
typedef long double ld;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

int dp[3001][3001];
string s, t;

void out(int a, int b) {
	if(!a || !b)
		return;
	if(s[a-1] == t[b-1]) {
		//cout << a << ' ' << b << '\n';
		out(a-1, b-1);
		cout << s[a-1];
	}
	else {
		if(dp[a-1][b] == dp[a][b])
			out(a-1, b);
		else
			out(a, b-1);
	}
}

signed main() {
	EmiliaMyWife

	//string s, t;
	cin >> s >> t;
	for(int i = 1; i <= s.size(); i++) {
		for(int j = 1; j <= t.size(); j++) {
			if(s[i-1] == t[j-1])
				dp[i][j] = dp[i-1][j-1]+1;
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	out(s.size(), t.size());

	return 0;
 }


Measured memory_bytes: 38848
#include<map>
#include<set>
#include<list>
#include<ctime>
#include<cmath>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#define _rep(i,s,t) for(register int i=s;i>=t;--i)
#define Rep(i,s,t) for(register int i=s;i<t;++i)
#define go(x) for(register int e=las[x];e;e=nxt[e])
#define re register
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define is insert
#define es erase
#define pii pair<int,int>
#define ms(f,x) memset(f,x,sizeof f)
#define mc(f,x) memcpy(f,x,sizeof f)
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define gi(x) read(x)
#define gii(x,y) read(x),read(y)
#define giii(x,y,z) read(x),read(y),read(z)
namespace IO{
    #define gc getchar()
    #define pc(x) putchar(x)
    template<typename T>inline void read(T &x){
        x=0;int f=1;char ch=gc;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=gc;}
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc;x*=f;return;
    }
    template<typename T>inline void write(T x=0){
        T wr[51];wr[0]=0;if(x<0)pc('-'),x=-x;if(!x)pc(48);
        while(x)wr[++wr[0]]=x%10,x/=10;while(wr[0])pc(48+wr[wr[0]--]);return;
    }
}
using IO::read;
using IO::write;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const int N=2e6+11;
int n,q,a[N],vis[N];
struct node{
	int l,r,id;
	void in(int i){
		gi(l),gi(r);
		id=i;
	}
	bool operator<(node A)const{
		return r<A.r;
	}
}p[N];
int s[N],ans[N];
void add(int x,int v){
	for(;x>0;x-=x&-x)
		s[x]+=v;
}
int query(int x){
	int ans=0;
	for(;x<=n;x+=x&-x)
		ans+=s[x];
	return ans;
}
int main(){
	gi(n),gi(q);
	rep(i,1,n)
		gi(a[i]);
	rep(i,1,q)
		p[i].in(i);
	sort(p+1,p+q+1);
	int now=1;
	rep(i,1,n){
		if(vis[a[i]])add(vis[a[i]],-1);
		add(i,1);vis[a[i]]=i;
		while(i==p[now].r){
			ans[p[now].id]=query(p[now].l);
			++now;
		}
	}
	rep(i,1,q)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 17456
#include<bits/stdc++.h>
int K,X,Y,i,j,t,x,y,n,xf,yf,xyswap;
int xd[1<<20],yd[1<<20];
void pd(int x,int y){if(xyswap)std::swap(x,y);xd[n]=xf?-x:x,yd[n++]=yf?-y:y;}
main(){
    scanf("%d%d%d",&K,&X,&Y);
    if(X<0)xf=1,X=-X;
    if(Y<0)yf=1,Y=-Y;
    if(X>Y)xyswap=true,std::swap(X,Y);
    if(X+Y&~K&1){puts("-1");exit(0);}
    if(X+Y<K&&X+Y&1)pd(X,-K+X),pd((K+X-Y)/2,K-(K+X-Y)/2),pd(-(K+X-Y)/2,K-(K+X-Y)/2);
    else{
        int U=X+Y,V=-X+Y-K;
        U-=U%K;
        if(X+Y<K||K&1&&((X+Y)/K&1)==(X+Y&1))U+=K;
        int a=(U-V)/2,b=(U+V)/2;
        if((X+Y)%K!=0)pd(X-a,Y-b),X=a,Y=b;
        for(;i<X/K;i++)pd(K,0);
        for(;j<Y/K;j++)pd(0,K);
        if(X%K!=0)pd(X%K,Y%K);
    }
    printf("%d ",n);
    for(;t<n;t++)printf("%d %d ",x=x+xd[t],y=y+yd[t]);
}

Measured memory_bytes: 5120
#define __STDC_FORMAT_MACROS
#define p64 PRId64

#include <bits/stdc++.h>

using namespace std;
using ll = int64_t;

ll A, B;

bool check(ll mid)
{
    ll mx = -1000000001;

    ll mHalf = mid / 2;

    ll x;
    bool flg = false;
    if (mHalf < A)
    {
        flg = true;
        x = mHalf;
    }
    else x = mHalf + 1;

    // mid が 奇数ならば 中央の値
    if (mid % 2 == 1) x++;

    if (x == 0) x++;

    if (x == A) x++;

    ll y;
    if (mHalf < B) y = mHalf + 1;
    else y = mHalf;

    if (y == B && flg) y++;
    else if (y == B) y--;

    mx = max(mx, x * y);

    mx = max(mx, (ll)0);

    // mid が 偶数ならば 中央の 左値 右値
    if (mid % 2 == 0)
    {
        x++;
        if (x == A) x++;

        y--;
        if (y == B) y--;

        mx = max(mx, x * y);

        mx = max(mx, (ll)0);
    }

    return mx < A * B;
}

// Bisection Method
// [left, right]
// to narrow the range
ll BisectionMethod(ll left, ll right)
{
    bool flg = false;

    int times = 0;

    // A * B より小さいという条件を満たさない間は
    // 探索を継続する
    while (1 < abs(right - left) || !flg)
    {
        if (100 < times) break;

        ll mid = (left + right) / 2;

        flg = check(mid);

        if (flg) left = mid;
        else right = mid;

        times++;
    }

    return (left + right) / 2;
}

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

    while (Q--)
    {
        cin >> A >> B;
        if (B < A) swap(A, B);
        cout << BisectionMethod(0, 2 * B) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <list>
#include <stack>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#define m7 1000000007
#define m9 1000000009
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second

using namespace std;
ll dp[405][405], cost[405][405];
pll solve(vector<int>& V, int beg, int end) {
	if (beg > end || beg < 0 || end >= V.size()) return { 0ll,0ll };
	if (beg == end) {
		return { V[beg],0ll };
	}
	if (dp[beg][end] != -1ll) return {dp[beg][end],cost[beg][end]};
	
	pll P = solve(V, beg + 1, end);
	dp[beg][end] = P.first + V[beg]*1ll;

	cost[beg][end] = P.second + dp[beg][end];
	
	for (int i = beg + 1; i < end; i++) {
		pll X = solve(V,beg, i);
		pll Y = solve(V, i + 1, end);
		ll z =  dp[beg][end] + X.second + Y.second;
		if (cost[beg][end] > z) {
			cost[beg][end] = z;
			
		}
	}
	P = solve(V, beg, end - 1);
	if (cost[beg][end] >= dp[beg][end] + P.second) {
		
		cost[beg][end] = P.first + V[end] + P.second;
		
		dp[beg][end] = min(dp[beg][end], P.first + V[end]);
	}
	
	return { dp[beg][end],cost[beg][end] };

}
int main()
{
	int n;
	cin >> n;
	vector<int> V(n);
	
	for (int i = 0; i < n; i++) {
		cin >> V[i];
		for (int j = 0; j < n; j++)
			dp[i][j] = -1;
	}
	cout<<solve(V, 0, n - 1).second;
return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;

#define INF 1e18
#define int long long

int h, w, cnt;
char stage[51][51];
int dist[51][51];

bool IsOut(int y, int x) {
    return (y < 0 || h <= y || x < 0 || w <= x);
}

void bfs() {
    queue<pair<int, int>> q;
    q.push(pair<int, int>(0, 0));
    while(!q.empty()) {
        pair<int, int> yx = q.front(); q.pop();
        int y = yx.first;
        int x = yx.second;
        int dy[] = {0, 1, -1, 0};
        int dx[] = {1, 0 ,0, -1};
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(!IsOut(ny, nx) && stage[ny][nx] == '.' && dist[ny][nx] == 0) {
                dist[ny][nx] = dist[y][x] + 1;
                q.push(pair<int, int> (ny, nx));
            }
        }
    }
}


signed main() {
    cin >> h >> w;
    cnt= 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> stage[i][j];
            if(stage[i][j] == '.') cnt++;
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            dist[i][j] = 0;
        }
    }

    dist[0][0] = 1;
    bfs();

    cout << (dist[h - 1][w - 1] == 0 ? -1 : cnt - dist[h - 1][w - 1]) << endl;
    return 0;
}


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


int main(){
    string S;

    cin >> S;
    
    if(S[0] == S[1]  || S[1] == S[2] || S[2] == S[3]){
        cout << "Bad" <<"\n";
    }else{
        cout << "Good" <<"\n";
    }


    return 0;
}

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

int prime(int x) {
  int i = 2;
  while(x >= i*i) {
    if (x % i == 0) return 1;
    i += 1;
  }
  return 0;
}

int main() {
  int x;
  cin >> x;
  
  while(prime(x)) {
    x += 1;
  }
  
  cout << x << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int d,a,x,cnt;
	scanf("%d %d",&d,&a);
	x=0; cnt=0;
	while(1){
		if(d==x){
			break;
		}
		if(d<x+a){
			x=x+1;
			cnt++;
		}
		else{
			x=x+a;
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}



Measured memory_bytes: 2732
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000

int factorial(int k) {
    int sum = 1, i;
    for (i = 1; i <= k; i++) {
        sum *= i;
    }
    return sum;
}
int main() {
    int N, i, ansA = 0, ansB = 0;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> numA(N);
    vector<int> numB(N);
    for (i = 0; i < N; i++) {
        cin >> A.at(i);
        numA.at(A.at(i) - 1) = A.at(i) - 1;
    }
    for (i = 0; i < N; i++) {
        cin >> B.at(i);
        numB.at(B.at(i) - 1) = B.at(i) - 1;
    }
    for (i = 0; i < N - 1; i++) {
        int cal = factorial(N - i - 1);
        ansA += cal * numA.at(A.at(i)-1);
        ansB += cal * numB.at(B.at(i)-1);
        for (int j = A.at(i); j < N; j++) numA.at(j)--;
        for (int j = B.at(i); j < N; j++) numB.at(j)--;
    }
    cout << abs(ansA - ansB) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> p;
 
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

    ll a, b, x;
    cin >> a >> b >> x;

    if(a == 0)
        a -= x;
    else a--;

    cout << b / x - a / x << endl;
}

Measured memory_bytes: 256
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}
/*
inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
*/
// }}}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;
    cin >> h >> w;
    rep(i,h){
        string s;
        cin >> s;
        cout << s << '\n' << s << '\n';
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define Decimal fixed << setprecision(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}
constexpr int INF = 1100000000;
constexpr long long LLINF = 1100000000000000000LL;
constexpr long long MOD = 1000000007;

typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
  int N, M;
  cin >> N >> M;
  vector<vector<int>> v(M);
  REP(i, M) {
    int k; cin >> k;
    REP(j, k) {
      int s; cin >> s;
      v[i].PB(s - 1);
    }
  }
  vector<int> p(M);
  REP(i, M) cin >> p[i];

  int ans = 0;
  REP(b, 1 << N) {
    vector<int> u(M);
    int cnt = 0;
    REP(i, M) {
      int pt = 0;
      for (auto& s : v[i]) pt += (b >> s) & 1;
      if (pt % 2 == p[i]) cnt++;
    }
    if (cnt == M) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static int gcd(int num1,int num2) {
        if(num2==0) return num1;
        else return gcd(num2,num1%num2);
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String T = sc.next();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T.length(); i++) {
            switch(T.charAt(i)) {
                case '?':
                    sb.append('D');
                    break;
                default:
                    sb.append(T.charAt(i));
                    break;
            }
        }
        System.out.println(sb.toString());
    }
}


Measured memory_bytes: 41484
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    N,S=map(int,input().split())
    A=list(map(int,input().split()))
    dp0=[[0 if i!=0 else 1 for i in range(S+1)] for _ in range(N+1)]
    dp1=[[0]*(S+1) for _ in range(N+1)]
    dp2=[[0]*(S+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(S+1):
            b=int(j==0)
            dp1[i+1][j]+=dp1[i][j]+b
            dp2[i+1][j]+=dp1[i][j]+dp2[i][j]+b
            dp1[i+1][j]%=MOD
            dp2[i+1][j]%=MOD
            if j+A[i]<=S:
                dp1[i+1][j+A[i]]+=dp1[i][j]+b
                dp2[i+1][j+A[i]]+=dp1[i][j]+b
                dp1[i+1][j+A[i]]%=MOD
                dp2[i+1][j+A[i]]%=MOD
    print(dp2[-1][-1])

if __name__ == '__main__':
    main()


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

int main() {
  int a, b, c, d;
  cin>>a>>b>>c>>d;
  if (abs(a-c) <= d) cout<<"Yes"<<endl;
  else if (abs(a-b) <= d && abs(b-c) <= d) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<type_traits>
#include<numeric>
#include<limits>
#include<iomanip>
#include<set>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long int ll;

//define
#define INF 100000000
#define NUM 1000000007
#define all(x) begin(x), end(x)

int main() {
	int r;
	cin >> r;
	if (r < 1200) cout << "ABC" << endl;
	else if (r >= 2800) cout << "AGC" << endl;
	else cout << "ARC" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;
typedef pair<P,P> P2;
typedef pair<int,P2> PP;
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
int d[55][55][1<<10][2],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int main() {
  int n,m;
  cin >> m >> n;
  string s[n];
  for(int i=0; i<n; i++) cin >> s[i];
  int N;
  cin >> N;
  string t[N][n];
  for(int i=0;i<N;i++)for(int j=0;j<n;j++)cin >> t[i][j];
  for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<(1<<N);k++)for(int l=0;l<2;l++) d[i][j][k][l]=1<<29;
  priority_queue<PP,vector<PP>,greater<PP> > que;
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      if(s[i][j]=='%') {
        d[i][j][0][0]=0;
        que.push(PP(0,P2(P(i,j),P(0,0))));
      }
    }
  }
  map<char,int> ma;
  ma['_']=0;ma['^']=1;ma['%']=0;ma['&']=0;
  for(int i=0; i<N; i++) {
    ma[(char)('a'+i)]=0;
    ma[(char)('A'+i)]=1;
  }
  while(!que.empty()) {
    PP p=que.top();que.pop();
    int xx=p.S.F.F,yy=p.S.F.S,tt=p.S.S.F,k=p.S.S.S,cc=p.F;
    if(s[xx][yy]=='&') {
      cout << cc << endl;
      return 0;
    }
    if(d[xx][yy][tt][k]>cc) continue;
    for(int i=0; i<4; i++) {
      int x=xx+dx[i],y=yy+dy[i];
      if(!check(n,m,x,y)||s[x][y]=='#') continue;
      int c=0;
      for(int j=0; j<N; j++) {
        if((tt&(1<<j))&&t[j][x][y]=='*') c++;
      }
      if(ma.count(s[x][y])&&(ma[s[x][y]]^(c%2))!=k) continue;
      if(d[x][y][tt][k]>d[xx][yy][tt][k]+1) {
        d[x][y][tt][k]=d[xx][yy][tt][k]+1;
        que.push(PP(d[x][y][tt][k],P2(P(x,y),P(tt,k))));
      }
    }
    if(isalpha(s[xx][yy])) {
      int r=islower(s[xx][yy])?(s[xx][yy]-'a'):(s[xx][yy]-'A');
      int f=t[r][xx][yy]=='*';
      if(d[xx][yy][tt^(1<<r)][k^f]>d[xx][yy][tt][k]+1) {
        d[xx][yy][tt^(1<<r)][k^f]=d[xx][yy][tt][k]+1;
        que.push(PP(d[xx][yy][tt^(1<<r)][k^f],P2(P(xx,yy),P(tt^(1<<r),k^f))));
      }
    }
    if(s[xx][yy]=='|') {
      if(d[xx][yy][tt][k^1]>d[xx][yy][tt][k]+1) {
        d[xx][yy][tt][k^1]=d[xx][yy][tt][k]+1;
        que.push(PP(d[xx][yy][tt][k^1],P2(P(xx,yy),P(tt,k^1))));
      }
    }
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 24320
n, c, k = map(int, input().split())
t = []
for i in range(n):
  t.append(int(input()))
t.sort()
person = 0
firsttime = 0
ans = 0
for i in range(n):
  if person == 0:
    firsttime = t[i]
    person += 1
  elif person <= c-1 and (firsttime + k) >= t[i]:
    person += 1
  else:
    person = 1
    firsttime = t[i]
    ans += 1
    
if person != 0:
  ans += 1
print(ans)
  
  
  
           


Measured memory_bytes: 7384
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr long long INF = 1LL << 62;
constexpr int MOD = 1e9 + 7;

int N,M;
int a[50],b[50];
bool g[50][50];
bool used[50];

void dfs(int v) {
    used[v] = true;
    for(int i = 0; i < N; ++i){
        if(!g[v][i] || used[i]) continue;
        dfs(i);
    }
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0; i < M; ++i) {
        cin >> a[i] >> b[i];
        --a[i]; --b[i];
        g[a[i]][b[i]] = g[b[i]][a[i]] = true;
    }

    int ans = 0;
    for(int i=0; i < M; ++i) {
        g[a[i]][b[i]] = g[b[i]][a[i]] = false;
        fill(used, used + N, false);
        dfs(0);

        for(int i=0; i < N; ++i){
            if(used[i]==false){
                ++ans; break;
            }
        }

        g[a[i]][b[i]] = g[b[i]][a[i]] = true;
    }
    cout << ans << '\n';
    return 0;
}

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

#if DEBUG && !ONLINE_JUDGE
    #include "header.h"
#else
    #define debug(args...)
#endif

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long lli;
typedef long double ld;

#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(auto i=(a);i<b;i++)

#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
void preprocess(void) {
    return;
}
#define N 100005
lli dp[101][N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(20);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    preprocess();
    int n,W; cin>>n>>W;
    vi w(n+1), v(n+1);
    rep(i,1,n+1) {
        cin>>w[i]>>v[i];
        rep(j,0,N) dp[i][j] = (lli)MOD * 1000;
    }
    rep(i,0,N) dp[0][i] = (lli)MOD*1000;
    rep(i,0,n+1) dp[i][0] = 0;
    //rep(i,0,N) {
        //if(i<=v[1]) dp[1][i] = w[1];
    //}
    //dp[1][v[1]] = w[1];
    rep(i,1,n+1) {
        rep(j,0,N) {
            if(j>=v[i]) {
                dp[i][j] = min(dp[i-1][j-v[i]] + w[i], dp[i-1][j]);
            }
            else dp[i][j] = dp[i-1][j];
        }
    }
    lli ans = 0;
    rep(i,0,N) {
        if(dp[n][i]<=W) {
            ans = i;
            debug(dp[n][i], i);
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 79232
from collections import Counter

n = int(input())
ans = 0

def func(num):
    global ans
    if num > n:
        return 0

    nnn = list(str(num))
    key = Counter(nnn).keys()
    if len(key) == 3:
        if '3' in key:
            if '5' in key:
                if '7' in key:
                    ans += 1

    func(10 * num + 3)
    func(10 * num + 5)
    func(10 * num + 7)

func(0)
print(ans)


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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    cout << setprecision(20) << 1.0 * ((n + 1) / 2) / n;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int k;
    cin>>k;
    cout<<(k/2)*((k+1)/2);
}

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

A = [int(a) for a in input().split() ]
B = [int(a) for a in input().split() ]
C = [int(a) for a in input().split() ]

result = 0
old = -5
for i in range(N):#foodA[i]
    result = result + B[A[i]-1]

    if (A[i]-2 == old):
        result = result + C[old]

    old  = A[i]-1
    #print(result)

print(result)


Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main(void){
    char w[100];
    char t[100];
    int i;
    int cnt=0;
    scanf("%s",w);
    for(i=0;i<strlen(t);i++){
        w[i]=tolower(w[i]);
    }
    while(scanf("%s",t)){
        if(strcmp(t,"END_OF_TEXT")==0) break;
        for(i=0;i<strlen(t);i++){
            t[i]=tolower(t[i]);
        }
        if(strcmp(w,t)==0) cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

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

int main() {
    string s;
    cin >> s;
    int n = s.size();

    string t = s;
    reverse(t.begin(), t.end());
    string s1 =  s.substr(0, ((n-1)/2));
    string t1 = s1;
    reverse(t1.begin(), t1.end());
    string s2 = s.substr(((n+3)/2)-1);
    string t2 = s2;
    reverse(t2.begin(), t2.end());

    if (s == t && s1 == t1 && s2 == t2) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



Measured memory_bytes: 256
import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    s = input().rstrip()

    if (
        len(
            s.replace("eraser", "")
            .replace("erase", "")
            .replace("dreamer", "")
            .replace("dream", "")
        )
        == 0
    ):
        print("YES")
    else:
        print("NO")

    pass


if __name__ == "__main__":
    main()


Measured memory_bytes: 39920
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
using namespace std;
#define INF 1LL << 61
#define MAX 1LL << 30
#define MOD 1000000007
typedef long long ll;
//typedef pair<int,int> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());
//#define int ll
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

int par[420000],es[420000],sep[420000]; //親

// n要素を初期化
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=-1;
  }
}

//木の根を求める
int find(int x){
  if(par[x]<0){
    return x;
  }else{
    return par[x]=find(par[x]);
  }
}

int usize(int x){
  return -par[find(x)];
}

int esize(int x){
    return es[find(x)];
}


//xとyの属する集合を併合
void unite(int x,int y){
  x=find(x);
  y=find(y);
  es[x]++;
  if(x==y) return;

  if(usize(x)<usize(y)) swap(x,y);
  par[x]+=par[y];
  es[x]+=es[y];
  par[y]=x;
}


//xとyが同じ集合に属するか否か
bool same(int x,int y){
  return find(x)==find(y);
}


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

    int N,M;
    cin>>N>>M;
    int x=(N-1)-M;
    if(x-N/2>0){
        cout<<"Impossible"<<endl;
        return 0;
    }else if(x==0){
        cout<<0<<endl;
        return 0;
    }
    ll a[110000];
    init(N);
    for(int i=0;i<N;i++) cin>>a[i];
    for(int i=0;i<M;i++){
        int x,y;
        cin>>x>>y;
        unite(x,y);
    }
    vector<ll> V[110000];
    for(int i=0;i<N;i++){
        V[find(i)].push_back(a[i]);
    }
    vector<ll> one,two;
    for(int i=0;i<N;i++){
        if(V[i].size()==0) continue;
        sort(V[i].begin(),V[i].end());
        one.push_back(V[i][0]);
        for(int j=1;j<(int)V[i].size();j++){
            two.push_back(V[i][j]);
        }
    }
    sort(one.begin(),one.end());
    sort(two.begin(),two.end());
    ll ans=0;
    for(ll i:one){
        ans+=i;
    }
    for(int i=0;i<2*x-(int)one.size();i++){
        ans+=two[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 9464
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	int n,m;
    cin>>n>>m;
    if(n%2==1){
        FOR(i,0,m){
            cout<<i+1<<" "<<n-i<<endl;
        }
    }else{
        FOR(i,0,n/4){
            if(i+1>m)break;
            cout<<i+1<<" "<<n-i<<endl;
        }
        FOR(i,n/4,m){
            cout<<i+1<<" "<<n-i-1<<endl;
        }
    }
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys


def solve(N: int, V: "List[int]", C: "List[int]"):
    result = 0
    for i in range(0, N):
        if V[i] >= C[i]:
            result = result + V[i] - C[i]
    print(result)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    V = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, V, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, d[100], ans = 0;
  
  cin >> n;
  
  for(int i = 0; i < n; i++){
   cin >> d[i];
  }
  
  for(int i = 0; i < n-1; i++){
   for(int j = 1; j < n-i; j++){
    ans += d[i] * d[j+i];
   }
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())
ans_li = []
abcd = [tuple(map(int,input().split())) for _ in range(Q)]
for A in combinations_with_replacement(range(1,M+1),N):
    ans = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            ans += d
    ans_li.append(ans)
print(max(ans_li))


Measured memory_bytes: 12748
#UnionFind
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,k = map(int,input().split())
V = [[] for i in range(n+1)]
W = [0]*(n+1)
uf = UnionFind(n+1)
for _ in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
    uf.union(a,b)
for _ in range(k):
    c,d = map(int,input().split())
    if uf.find(d) == uf.find(c):
        W[c] += 1
        W[d] += 1
    
for i in range(1,n+1):
    ans = uf.size(i) - len(V[i]) - W[i] - 1
    print(ans,end="")
    print(" ",end="")
print()

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int n, m;
int adj[200][200];
bool useE[200][200];
bool used[200];
int pre[200];
int d[200];

void dijkstra(int s){
	fill(d, d+n, INF);
	fill(used, used+n, false);
	for(int i=0; i<n; i++){
		pre[i] = -1;
	}

	d[s] = 0;

	while(1){
		int v = -1;
		for(int i=0; i<n; i++){
			if(!used[i] && (v == -1 || d[v] > d[i])) v = i;
		}
		if(v == -1) break;
		used[v] = true;

		for(int i=0; i<n; i++){
			if(d[i] > d[v] + adj[v][i]){
				d[i] = d[v] + adj[v][i];
				pre[i] = v;
			}
		}

	}
}


/*
void dijkstra(int s){
	fill(d, d + n, INF);
	fill(used, used + n, false);
	for(int i=0; i<n; i++){
		pre[i] = -1;
	}
	d[s] = 0;

	while(true){
		int v = -1;
		for(int u=0; u < n; u++){
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}

		if(v == -1) break;
		used[v] = true;

		for(int u = 0; u < n; u++){
			if(d[u] > d[v] + adj[v][u]){
				d[u] = d[v] + adj[v][u];
				pre[u] = v;
			}
		}
	}
}
*/

vector<int> get_path(int t, int s){
	vector<int> path;
	for(; t != -1; t = pre[t]){
		path.push_back(t);
	}
	reverse(path.begin(), path.end());

	for(int i=0; i < path.size()-1; i++){
		useE[path[i]][path[i+1]] = useE[path[i+1]][path[i]] = true;
	}
	return path;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			adj[i][j] = adj[j][i] = INF;
		}
	}

	for(int i=0; i<m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		adj[a][b] = adj[b][a] = c;
	}


	for(int i=1; i<n; i++){
		dijkstra(i);
		for(int j=0; j<n; j++){
			if(i == j) continue;
			get_path(j, i);
		}
	}

	ll ans = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(adj[i][j] != INF && useE[i][j] == false) ans++;
		}
	}
	/*
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(adj[i][j] != INF){
				printf("%d ", adj[i][j]);
			}else{
				printf("# ");
			}
		}
		puts("");
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			printf("%d ", useE[i][j]);
		}
		puts("");
	}
	*/

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


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    ll n, x;
    cin >> n;
    ll a[n];
    for (ll i = 0; i < n; i++) {
        cin >> x;
        a[i] = x;
    }
    sort(a, a+n);
    ll p = -1, q = -1;
    for (ll i = n - 1; i >= 1 && q == -1; i--) {
        if (a[i] == a[i-1] && p == -1) {
            p = a[i];
            i--;
        }else if(a[i] == a[i-1] && q == -1){
            q = a[i];
            i--;
        }
    }
    if (q != -1) {
        cout << p * q << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}


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

int main(){
   int N;
   std::cin >> N;
   std::vector<int> h(N);
   for (int i=0; i<N; i++){
      std::cin >> h.at(i);
   }
   int cnt = 0;
   int i = 0;
   while (i<N){
      if (h.at(i) == 0){
         i++;
      } else{
         cnt++;
         for (int j=i; j<N; j++){
            if (h.at(j) == 0){
               break;
            } else{
               h.at(j)--;
            }
         }
      }
      //for (auto x : h){
      //   std::cerr << x;
      //}
      //std::cerr << std::endl;
   }
   std::cout << cnt << std::endl;
}



Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<deque>
#include<map>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

int main() {
	int food_num;
	cin >> food_num;
	VE food_order(food_num);
	VE food_point(food_num);
	VE food_bonus(food_num - 1);
	REP(i, food_num) {
		cin >> food_order[i];
	}
	REP(i, food_num) {
		cin >> food_point[i];
	}
	REP(i, food_num-1) {
		cin >> food_bonus[i];
	}
	int sum_point = 0;
	int old_food = 100;
	REP(i, food_num) {
		sum_point += food_point[food_order[i] - 1];
		if (food_order[i] - 1 == old_food + 1) {
			sum_point += food_bonus[old_food];
		}
		old_food = food_order[i] - 1;
	}
	cout << sum_point << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  map<long long, int> mp;
  for (int i = 0; i < n; i++) {
    long long x;
    scanf("%lld", &x);
    mp[x]++;
  }
  for (int i = 0; i < m; i++) {
    int x;
    long long c;
    scanf("%d %lld", &x, &c);
    mp[c] += x;
  }
  long long ans = 0;
  for (map<long long, int>::reverse_iterator it = mp.rbegin(); it != mp.rend(); it++) {
    int pick = min(n, it->second);
    ans += pick * it->first;
    n -= pick;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 12800
from collections import defaultdict
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    S = input()[:-1]
    GX, GY = map(int, input().split())

    S_parsed = []
    prev = S[0]
    seq = 1
    for c in S[1:]:
        if c == "F":
            if c == prev:
                seq += 1
            else:
                prev = c
                if seq % 2 == 0:
                    pass
                else:
                    S_parsed.append("T")
                seq = 1
        elif c == "T":
            if c == prev:
                seq += 1
            else:
                S_parsed.append(seq)
                seq = 1
            prev = c
    else:
        if S[-1] == "F":
            S_parsed.append(seq)

    x_move = []
    y_move = []

    dir_x = True
    for c in S_parsed:
        if c == "T":
            dir_x = not dir_x
        else:
            if dir_x:
                x_move.append(c)
            else:
                y_move.append(c)

    dp_x = defaultdict(bool)
    if len(x_move) > 0:
        if S[0] != "T":
            dp_x[x_move[0]] = True
        else:
            dp_x[x_move[0]] = True
            dp_x[-x_move[0]] = True
    else:
        dp_x[0] = True

    for x in x_move[1:]:
        tmp = defaultdict(bool)
        for key, val in dp_x.items():
            tmp[key+x] = True
            tmp[key-x] = True
        dp_x = tmp

    dp_y = defaultdict(bool)
    if len(y_move) == 0:
        dp_y[0] = True
    else:
        dp_y[y_move[0]] = True
        dp_y[-y_move[0]] = True
    for y in y_move[1:]:
        tmp = defaultdict(bool)
        for key, val in dp_y.items():
            tmp[key+y] = True
            tmp[key-y] = True
        dp_y = tmp

    if dp_x[GX]and dp_y[GY]:
        print("Yes")
    else:
        print("No")


solve()


Measured memory_bytes: 84828