akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
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 (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N, K;
  cin >> N >> K;
  K *= 2;
  vec< vec< int > > BT(K, vec< int >(K, 0));
  vec< vec< int > > BTSum(K + 1, vec< int >(K + 1, 0));
  vec< vec< int > > WT(K, vec< int >(K, 0));
  vec< vec< int > > WTSum(K + 1, vec< int >(K + 1, 0));
  REP(i, N) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    if (c == 'B') {
      BT[x % K][y % K]++;
    } else {
      WT[x % K][y % K]++;
    }
  }
  REPS(i, K) {
    REPS(j, K) {
      BTSum[i][j] = BT[i - 1][j - 1] + BTSum[i - 1][j] + BTSum[i][j - 1] -
                    BTSum[i - 1][j - 1];
      WTSum[i][j] = WT[i - 1][j - 1] + WTSum[i - 1][j] + WTSum[i][j - 1] -
                    WTSum[i - 1][j - 1];
    }
  }
  int ans = 0;

  //  DEBUG(BTSum[K][K]);
  //  DEBUG(WTSum[K][K]);

  FORS(i, 0, K / 2) {
    FORS(j, 0, K / 2) {
      int dxx[4] = {0, i, i + K / 2, K};
      int dyy[4] = {0, j, j + K / 2, K};
      int tmpans[2] = {0, 0};
      REP(k, 2) {
        REP(ii, 3) {
          REP(jj, 3) {
            int a0 = dxx[ii];
            int a1 = dyy[jj];
            int a2 = dxx[ii + 1];
            int a3 = dyy[jj + 1];
            if ((k + ii + jj) % 2 == 0)
              tmpans[k] +=
                  BTSum[a2][a3] - BTSum[a2][a1] - BTSum[a0][a3] + BTSum[a0][a1];
            if ((k + ii + jj) % 2 == 1)
              tmpans[k] +=
                  WTSum[a2][a3] - WTSum[a2][a1] - WTSum[a0][a3] + WTSum[a0][a1];
          }
        }
      }

      chmax(ans, tmpans[0]);
      chmax(ans, tmpans[1]);
    }
  }
  print(ans);
}


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

int main(){
  int a,b,c,d,e,f,g,sum;
  sum=0;
  for(int i=0;i<3;i++){
    cin >> a >> b >> c >>d >>f >>g;
    sum=d*3600+f*60+g-a*3600-b*60-c;
    a=sum/3600;
    sum%=3600;
    b=sum/60;
    sum%=60;
    c=sum;
    cout << a <<" " << b<<" "<<c<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    N = int(input())
    A = list(map(int, input().split()))

    all_prime = set()
    is_pairwise = True
    for a in A:
        facts = set(prime_factorize(a))
        if len(facts & all_prime) != 0:
            is_pairwise = False
            break

        all_prime |= facts

    if is_pairwise:
        print('pairwise coprime')
        return

    _gcd = A[0]
    is_setwise = False
    for a in A[1:]:
        _gcd = gcd(a, _gcd)
        if _gcd == 1:
            is_setwise = True
            break
    
    if is_setwise:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Measured memory_bytes: 204536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 5;
const ll INF = 1e18;
int N, M, ls[MAXN], rs[MAXN];
ll a[MAXN], dp[MAXN], tree[4 * MAXN], lz[4 * MAXN];
vector<int> st[MAXN], en[MAXN];

void lazy(int node) {
	lz[2 * node] += lz[node];
	tree[2 * node] += lz[node];
	lz[2 * node + 1] += lz[node];
	tree[2 * node + 1] += lz[node];
	lz[node] = 0;
}

void update(int l, int r, int ql, int qr, ll val, int node) {
	if (ql > qr) {
		return;
	}
	if (ql > r || qr < l) {
		return;
	}
	if (ql <= l && qr >= r) {
		tree[node] += val;
		lz[node] += val;
		return;
	}
	lazy(node);
	int mid = l + (r - l) / 2;
	update(l, mid, ql, qr, val, 2 * node);
	update(mid + 1, r, ql, qr, val, 2 * node + 1);
	tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

ll query(int l, int r, int ql, int qr, int node) {
	if (ql > qr) {
		return -INF;
	}
	if (ql > r || qr < l) {
		return -INF;
	}
	if (ql <= l && qr >= r) {
		return tree[node];
	}
	lazy(node);
	int mid = l + (r - l) / 2;
	return max(query(l, mid, ql, qr, 2 * node), query(mid + 1, r, ql, qr, 2 * node + 1));
}

int main() {
	ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> ls[i] >> rs[i] >> a[i];
		st[ls[i]].push_back(i);
		en[rs[i]].push_back(i);
	}
	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int u : st[i]) {
			update(0, N, 0, i - 1, a[u], 1);
		}
		dp[i] = query(0, N, 0, i - 1, 1);
		update(0, N, i, i, dp[i], 1);
		for (int v : en[i]) {
			update(0, N, 0, ls[v] - 1, -a[v], 1);
		}
	}
	ll ans = 0;
	for (int i = 0; i <= N; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 38360
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n,i;
  cin >> n;
  vector<long long> a(n+1,0),b(n+1,0),m(n+1,0);
  for(i=0;i<n+1;i++){
    cin >> a.at(i);
    b.at(i)=a.at(i);
  }
  
  for(i=n;i>=1;i--){
    b.at(i-1) += (b.at(i)+1)/2;
  }
  if(b.at(0)>1){
    cout << -1 << endl;
    return 0;
  }
  
  int P=0;
  long long inf=20000000000000;
  m.at(0)=1;
  for(i=1;i<=n;i++){
    if(P==0){
      m.at(i)=(m.at(i-1)-a.at(i-1))*2;
      if(m.at(i)>inf){
        P=1;
      }
    }else{
      m.at(i)=inf;
    }
  }
  
  P=0;
  long long sum=0,v=0;
  for(i=n;i>=0;i--){
    if(P==1){
      v += m.at(i);
    }else{
      sum += a.at(i);
      if(sum>=m.at(i)){
        P=1;
        v += m.at(i);
      }else{
        v += sum;
      }
    }
  }
  
  cout << v << endl;
}

Measured memory_bytes: 5632
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=INF;
  string s="",t="";
  //

  // ここから
  IN2(n,x);
  Vi H(n);
  VIN(H)
  SORT(H);
  REP(i,n-x+1){
    z = min(z, H[i+x-1] - H[i]);
  }
  OUT(z);
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>

int main()
{
    int n, l[10] = {0}, max = 0, total= 0;
    std::cin >> n;
    for (int i = 0;i < n;i++){
        std::cin >> l[i];
        max = std::max(max, l[i]);
        total += l[i];
    }
    total -= max;
    if(max < total){
        std::cout << "Yes";
    }
    else {
        std::cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------


int main(){
  int N,M,Q;
  cin >> N >> M >> Q;
  vector<vector<int>> a(510, vector<int> (510,0));
  for(int i=0; i<M; i++){
    int l,r;
    cin >> l >> r;
    a[l][r]++;
  }
  vector<vector<int>> S(510, vector<int> (510,0));
  for(int i=0; i<505; i++){
    for(int j=0; j<505; j++){
      S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + a[i][j];
    }
  }
  for(int i=0; i<Q; i++){
    int p,q;
    cin >> p >> q;
    cout << S[q+1][q+1] - S[q+1][p] - S[p][q+1] + S[p][p] << endl;
  }
  return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <list>
#include <math.h>
#include <map>
using namespace std;
#define REP(i, k, n) for(int i = k;i < n; i++)
#define rep(i, n) REP(i,0,n)
int dx[4] = {0,-1,1,0};
int dy[4] = {-1,0,0,1};
struct Point{
	int x, y;
};

int dist(Point p1, Point p2){
	return abs(p1.x-p2.x) + abs(p1.y - p2.y);
}
int main(void){
	int n, m;
	cin >> n >> m;
	Point student[51];
	rep(i,n){
		cin >> student[i].x >> student[i].y;
	}
	Point pos[51];
	rep(i,m){
		cin >> pos[i].x >> pos[i].y;
	}

	rep(i,n){
		Point now = student[i];
		int mini = 1000000000;
		int index = -1;
		rep(j,m){
			if(mini > dist(now, pos[j])){
				index = j;
				mini = min(mini, dist(now, pos[j]));
			}
		}
		cout << index + 1 << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	int a,s=0;
	cin>>a;
	int b=a;
	while(a>=10) 
	{
		s+=(a%10);
		a/=10;
	}
	s+=a;
	if((b%s)==0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(a<b){
		if(b<c){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <iostream>

using namespace std;

class Rect{
	public:
		int w;
		int h;
		int diagonal;
};

void swap(int *a,int *b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(){
	
	Rect rect[11180];
	for(int i=0;i<11180;i++){
		rect[i].diagonal=1000000;
	}

	int cnt=0;
	for(int i=1;i<=150;i++){
		for(int j=1;j<i;j++){
			rect[cnt].w=i;
			rect[cnt].h=j;
			rect[cnt].diagonal =i*i+j*j;
			cnt++;
		}
	}

	for(int i=0;i<11180;i++){
		for(int j=11180-1;j>i;j--){
			if(rect[j].diagonal<=rect[j-1].diagonal){
				swap(&rect[j].h,&rect[j-1].h);
				swap(&rect[j].w,&rect[j-1].w);
				swap(&rect[j].diagonal,&rect[j-1].diagonal);
			}
		}
	}

	for(int i=0;i<11180;i++){
		for(int j=11180-1;j>i;j--){
			if(rect[j].diagonal==rect[j-1].diagonal && rect[j].h<=rect[j-1].h){
				swap(&rect[j].h,&rect[j-1].h);
				swap(&rect[j].w,&rect[j-1].w);
				swap(&rect[j].diagonal,&rect[j-1].diagonal);
			}
		}
	}
	/*
	for(int i=0;i<=10100;i++){
		cout<<"i="<<i<<endl;
		cout<<"h="<<rect[i].h<<"w="<<rect[i].w<<"diagonal="<<rect[i].diagonal<<endl;
	}
	*/	
	

	int inH,inW;
	while(cin>>inH>>inW){
		if(inH==0 && inW ==0)break;

		for(int i=0;i<11180;i++){
			if(rect[i].h == inH && rect[i].w == inW){
				/*
				cout<<"rectH="<<rect[i].h<<"rectW="<<rect[i].w<<endl;
				cout<<"inH ="<<inH<<"inW="<<inW<<endl;
				cout<<i<<" "<<i+1<<endl;
				*/
				cout<<rect[i+1].h<<" "<<rect[i+1].w<<endl;
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1288
#include<stdio.h>
   
int gcd(long long, long long);
int gcd(long long a, long long b) {
  if(b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  };
}
   
int main() {
  long long a, b, temp, gcdr, lcmr;
   
  while(scanf("%lld %lld", &a, &b) != EOF) {
    if(a < b) {
      temp = b;
      b = a;
      a = temp;
    };
   
    gcdr = gcd(a , b);
    lcmr = a * b / gcdr;
   
    printf("%lld %lld\n", gcdr, lcmr);
  };  
  return 0;
}

Measured memory_bytes: 596
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
double dot(complex<double> a, complex<double> b) {
	return a.real() * b.real() + a.imag() * b.imag();
}
double gyaku_dot(complex<double> a, complex<double> b) {
	return a.real() * b.imag() - a.imag() * b.real();
}
double leng(complex<double> a) {
	return sqrt(a.real() * a.real() + a.imag() * a.imag());
}
double angles(complex<double> a, complex<double> b) {
	double cosine = dot(a, b) / (leng(a) * leng(b));
	double sine = gyaku_dot(a, b) / (leng(a) * leng(b));
	double kaku = acos(cosine);
	if (sine <= 0) {
		kaku = 2 * Ma_PI - kaku;
	}
	return kaku;
}
vector<int> convex_hull(vector<complex<double>> a) {
	vector<int> ans;
	double now_minnest = a[0].real();
	int now_itr = 0;
	REP(i, a.size()) {
		if (now_minnest > a[i].real()) {
			now_minnest = a[i].real();
			now_itr = i;
		}
	}
	ans.push_back(now_itr);
	complex<double> ba(0, 1);
	while (true) {
		int now_go = 0;
		double now_min = 0;
		int starter = ans[ans.size() - 1];
		for (int i = 0; i < a.size(); ++i) {
			if (i != starter) {
				double goa = angles(ba, a[i] - a[starter]);
				if (goa > now_min) {
					now_min = goa;
					now_go = i;
				}
			}
		}
		if (now_go == ans[0]) break;
		ans.push_back(now_go);
		ba = complex<double>(a[now_go] - a[starter]);
	}
	return ans;
}
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main(){
	int a, b;
	cin >> a >> b;
	if (a + b < 10) {
		cout << a + b;
	}
	else {
		cout << "error";
	}
}


Measured memory_bytes: 256
import fractions
import math

A, B = map(int, input().split())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False
        prime += step
        step = 6 - step
    return True

def solve():
    gcd = fractions.gcd(A, B)
    divisors = make_divisors(gcd)
    l = [x for x in divisors if is_prime(x)]
    print(len(l)+1)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 5304
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
#include<limits.h>


#define MOD 1000000007

using namespace std;

long long int modpow(long long int a, long long int n) {
	if (n == 0)return 1;
	if (n == 1)return (a % MOD);

	long long int hanbun = n / 2;
	long long int amari = n % 2;

	long long int ans = (a * a) % MOD;
	ans = modpow(ans, hanbun);

	if (amari == 1)ans *= a;

	ans %= MOD;

	return ans;

}

long long int gcd(long long int a, long long int b) {
	if (a < b) {
		long long int tmp = a;
		a = b;
		b = tmp;
	}

	long long int amari = a % b;

	if (amari == 0)return b;

	return gcd(b, amari);
}

long long int lcm(long long int a, long long int b) {
	long long int ans = (a * b) % MOD;
	long long int wari = modpow(gcd(a, b), MOD - 2);
	ans = (ans * wari) % MOD;
	return ans;
}

long long int factElement[10000] = { 0 };

long long int factrial(int n) {

	if (factElement[n] != 0)return factElement[n];

	if (n == 0) {
		factElement[0] = 1;
		return factElement[n];
	}

	long long int ans = n * factrial(n - 1);
	factElement[n] = ans;
	return factElement[n];

}





int main()
{

	string s, t, u;
	cin >> s >> t;

	int a, b;
	cin >> a >> b;
	cin >> u;

	if (s == u)a--;
	else b--;

	cout << a << " " << b << endl;



	


	return 0;



}



Measured memory_bytes: 764
# ABC 120 D

from collections import deque

class UnionFind():
    # n : 要素数
    def __init__(self, n):
        self.n = n
        # root[x] < 0 ならそのノードが根かつその値が木の要素数
        # root[x] > 0 ならそのノードが根
        self.root = [-1] * (n+1)
        # 木の高さの管理
        self.rnk = [0] * (n+1)

    # x が所属するグループの根を返す
    def findRoot(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])  # 経路圧縮
            return self.root[x]

    # x と y がそれぞれ所属するグループを結合する
    def unite(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            # 既に同じグループに所属していれば何もしない
            return
        elif self.rnk[x] > self.rnk[y]:    # x の方が高さがある場合
            self.root[x] += self.root[y]   # x の要素数に y の要素数を足す
            self.root[y] = x               # y の親を x にする
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    def count(self, x):
        return -self.root[self.findRoot(x)]

def resolve():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    AB = AB[::-1]

    ret = []

    uf = UnionFind(N)

    for a, b in AB:
        if uf.isSameGroup(a-1, b-1):
            ret.append(0)
        else:
            ret.append(uf.count(a-1) * uf.count(b-1))
            uf.unite(a-1, b-1)

    ans = 0
    for i in range(M-1, -1, -1):
        ans += ret[i]
        print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 37776
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

long long betsum(long long a, long long b);

int main(){
    long long N, K;
    cin >> N >> K;
    long long c=(N-K)*(N-K+1)/2;
    if(K==0)c -= N;
    for(int b=K+1; b<=N; b++){
        int rmin=K, rmax=b-1;
        long long ctmp=betsum((N-rmin)/b, (N-rmax)/b)*b;
        int rrmin=(N-rmin)%b, rrmax=(N-rmax)%b;
        ctmp -= ((N-rmax)/b)*rrmax;
        ctmp -= ((N-rmin)/b)*(b-rrmin-1);
        c += ctmp;
    }
    cout << c;
    return 0;
}

long long betsum(long long a, long long b){
    long long n=abs(b-a);
    long long m=min(a, b);
    return m*(n+1)+(n*(n+1))/2;
}

Measured memory_bytes: 256
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = map(int, input().split())
K_to = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

def dfs(v, p, d):
    K_to[v] = d
    if not visited[p]:
        for to, c  in G[v]:
            if to == p:
                continue
            dfs(to, v, c + d)
    else:
        visited[p] = True
    return

dfs(K, K, 0)
for _ in range(Q):
    x, y = map(int, input().split())
    print(K_to[x] + K_to[y])

Measured memory_bytes: 140940
#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define rf(i,a,b) for(ll i=a; i>=b; i--)
typedef std::vector<long long > vi ;
#define F first
#define S second
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define PB push_back
#define MP make_pair
#define PI 3.14159265358979323846
#define all(a) a.begin(),a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
#define endl '\n'
#define show(a) for(auto el:a)cout<<el<<" "
const ll INF=LLONG_MAX/2;
const ll N=2e5+1;
#define yesno(f) yes(f);no(f);
#define yes(f) if(f)cout<<"YES\n";
#define no(f) if(!f)cout<<"NO\n";
using  namespace std;
int main()
{
    fast;
   ll t=1;
   //std::cin >> t;
   while(t--)
   {
       ll n,i,j=0,x,b;
       std::cin >> n>>x;
       ll a[n+1],d[n+2]={0};
       fr(i,1,n+1)
       std::cin >> a[i];
       fr(i,2,n+2)
       {
           d[i]=d[i-1]+a[i-1];
           if(d[i]>x)
           {
               j=1;
               cout<<i-1<<"\n";
               break;
           }
       }
       if(j==0)
       cout<<n+1<<"\n";
   }
}

Measured memory_bytes: 3620
// Problem : B - Multiplication 2
// Contest : AtCoder - AtCoder Beginner Contest 169
// URL : https://atcoder.jp/contests/abc169/tasks/abc169_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include    <bits/stdc++.h>
#include    <ext/pb_ds/assoc_container.hpp>
#include    <ext/pb_ds/tree_policy.hpp>
using       namespace            std;
using       namespace            __gnu_pbds;
using       ll=                  int64_t ;
using       ull=                 unsigned long long ;
using       ld=                  long double;
#define     int                  int64_t
#define     mem(a,val)           memset( a,  val,  sizeof(a) )
#define     b_s                  binary_search
#define     u_b                  upper_bound
#define     l_b                  lower_bound
#define     nl                   cout<<endl
#define     pb                   push_back
#define     pf                   push_front
#define     ppb                  pop_back
#define     ppf                  pop_front
#define     in                   insert
#define     fi                   first
#define     se                   second
#define     pqueue               priority_queue
#define     rr                   return
typedef     tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;


/*#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;*/

const int   N=                   1e6+7;
const int   MOD=                 (int)1e9 + 7;
const int   MOD1=                (int)1e9 + 9;
const int   MOD2=                998244353;
const ld    pi=                  atan2(0, -1);
const ld    eps=                 1e-9;
int         tests=               1;

template<class x,class y>x max(x a,y b){return (a>b)?a:b;}
template<class x,class y>x min(x a,y b){return (a<b)?a:b;}
template<class x,class y>x log(x n,y r){return (n>r-1)?1+log(n/r,r):0;}

vector<int> adj[N],subset;
int vis[N]={0};
///.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.


int32_t main() 
{
	auto start = clock();
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);	

//	cout<<fixed;
//	cout<<scientific;
	cout<<fixed<<setprecision(12);
	// cin>>tests;
	for(int test=1;test<=tests;test++) 
	{
//		cout<<"Case #"<<test<<": ";
///.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.

		
		int n;
		cin>>n;
		int a[n];
		ld ans=1;
		for(int i=0;i<n;i++)
		{
		    cin>>a[i];
		    if(a[i]==0)
		    ans=0;
		    if(ans!=-1)
		    ans=ans*a[i];
		    if(ans>1000000000000000000)
		    ans=-1;
		    // cout<<ans<<endl;
		}
		cout<<(int)ans;
		
		
		
		
		
		
		
		
		
		
		
		
		
		
///.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.
		
	}
	cerr<<endl<<endl<<endl<< "Time : " << double(clock() - start) / CLOCKS_PER_SEC <<endl;
	return 0;
}


Measured memory_bytes: 27960
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
  int n, m;
  int o;
  cin >> n >> m;
 
  vector<int>x[4];
  for(int i = 0; i < n; i++) {
    int a,b;
    cin >> a >> b;
    if(i == 0) o = a;
    x[a-o].push_back(b);
  }
  for(int i = 0; i < 4; i++) {
    sort(begin(x[i]), end(x[i]));
    x[i].push_back(0);
    reverse(begin(x[i]), end(x[i]));
    for(int j = 1; j < x[i].size(); j++) {
      x[i][j] += x[i][j - 1];
    }
  }
 
  int ans = 0;
  for(ll i = 0; i < x[0].size(); i++) {
    for(ll j = 0; j < x[1].size(); j++) {
      for(ll k = 0; k < x[2].size(); k++) {
        for(ll l = 0; l < x[3].size(); l++) {
          ll ann = o * i + (o + 1) * j + (o + 2) * k + (o + 3) * l;
          if(ann <= m) {
            ans = max(ans,x[0][i]+x[1][j]+x[2][k]+x[3][l]);
          }
        }
      }
    }
  }
 
  cout << ans << endl;
}


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

int main(){
    int a,b,c,sum;
    cin>>a>>b>>c;
    sum=a+b+c;
    int ans=max(a,max(b,c));
    while((3*ans-sum)%2!=0){
        ans++;
    }
    cout<<(3*ans-sum)/2<<"\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; }
template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) {
	inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; }
	return s;
}

template<typename T> using IPQ = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using DPQ = priority_queue<T, vector<T>,    less<T>>;

int main() {
	IN(int, x, y, A, B, C);
	vector<LL> a(A), b(B), c(C);
	cin >> a >> b >> c;
	sort(RALL(a));
	sort(RALL(b));
	sort(RALL(c));
	
	LL s = 0;
	IPQ<LL> q;
	inc(i, x) { q.push(a[i]); s += a[i]; }
	inc(i, y) { q.push(b[i]); s += b[i]; }
	inc(i, C) {
		if(q.top() < c[i]) { s += c[i] - q.top(); q.pop(); q.push(c[i]); }
		else { break; }
	}
	OUT(s);
}


Measured memory_bytes: 4724
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
/*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
int main() {
    string s;
    cin >> s;
    vector<int>a(3,0);
    for(int i=0;i<s.size();i++){
        if(s.at(i)=='a')a.at(0)++;
        else if(s.at(i)=='b')a.at(1)++;
        else a.at(2)++;
    }
    bool ans =1;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            ll che =abs(a.at(i)-a.at(j));
            if(che>1)ans=0;
        }
    }
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
    



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

ll gcd(ll x,ll y){
    if(y==0)return x;
    x=x%y;
    gcd(y,x);
}
int main()
{
    ll n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    vector<ll>a(q);
    vector<ll>b(q);
    rep(i,q){
        cin>>a[i]>>b[i];
    }
    ll ans=0;
    vector<ll>c(n);
    rep(i,n) c[i]=0;
    for(int i=0;i<=n;i++){
        c[i+1]+=c[i];
        if(s[i]=='A'&&s[i+1]=='C'){
        c[i+1]++;
        }
    }
    rep(i,q){
        ans=c[b[i]-1]-c[a[i]-1];
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}

Measured memory_bytes: 3456
import bisect
 
n = int(input())
s = input()
 
RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
len_B=len(RGB[2])
for r in RGB[0]:
    for g in RGB[1]:
        dif = abs(r - g)
        up = max(r,g)+dif
        down = min(r,g)-dif
        up_posi=bisect.bisect_left(RGB[2],up)
 
        if up_posi < len_B:
            if RGB[2][up_posi]==up:
                total-=1
        down_posi=bisect.bisect_left(RGB[2],down)
        if down_posi < len_B:
            if RGB[2][down_posi]==down:
                total-=1
        if dif % 2 == 0:
            center = (r+g)/2
            center_posi=bisect.bisect_left(RGB[2], center)
            if center_posi < len_B:
                if RGB[2][center_posi]==center:
                    total-=1
print(total)

Measured memory_bytes: 77068
#include <stdio.h>
long dat[1005] = {};
int main() {
    int n;
    long ans = 1;
    scanf("%d", &n);
    for (int k=2, t=2; t<=n; t++, k=t)
        for (int i=2; i<=1001 && k > 1; i++)
            while (k % i == 0)
                k /= i, dat[i]++;
    for (int i=1; i<=1002; i++) {
        ans *= dat[i]+1;
        ans %= 1000000007;
    }
    printf("%ld\n", ans);
}

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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






int main() {
    ll n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    REP(i, n){
        cin >> w[i] >> v[i];
    }
    
    vector<vector<ll>> dp(n + 1, vector<ll>(100005, INF));
    dp[0][0] = 0;
    REP(i, n){
        REP(j, 100005){
            if(j + v[i] < 100005){
                dp[i + 1][j + v[i]] = min(dp[i + 1][j + v[i]], dp[i][j] + w[i]);
            }
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
    }
    ll ans = 0;
    REP(i, 100005){
        if(dp[n][i] <= W) ans = max(ans, i);
    }
    cout << ans << endl;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  string a, b;
  cin >> a >> b;
  if (a.size() > b.size()) dump("GREATER");
  else if (a.size() < b.size()) dump("LESS");
  else {
    if (a > b) dump("GREATER");
    else if (a < b) dump("LESS");
    else dump("EQUAL");
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int e,y;
  cin>>e>>y;
  if(e==0){
    if(1868<=y && y<=1911){
      cout<<"M"<<y-1867<<endl;
    }else if(1912<=y && y<=1925){
      cout<<"T"<<y-1911<<endl;
    }else if(1926<=y && y<=1988){
      cout<<"S"<<y-1925<<endl;
    }else if(1989<=y && y<=2016){
      cout<<"H"<<y-1988<<endl;
    }
  }else if(e==1){
    cout<<y+1867<<endl;
  }else if(e==2){
    cout<<y+1911<<endl;
  }else if(e==3){
    cout<<y+1925<<endl;
  }else if(e==4){
    cout<<y+1988<<endl;
  }
  return 0;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
// scanf("%d %d %d %d",&w,&b,&d,&s); %lld
// printf("%d\n" ,points);
// const double PI=acos(-1);
const int MAX = INT_MAX;

int main(){
	int n, k;
	cin >> n >> k;
	int dp[n], h[n];
	
	for(int i = 0; i<n; i++){
		cin >> h[i];
		dp[i] = MAX;
	}
	
	dp[n-1] = 0;
	
	for(int i = n-2; i>=0; i--){
		for(int j = 1; j<=k && i+j<n; j++)
				dp[i] = min(dp[i], abs(h[i] - h[i+j]) + dp[i+j]);
	}
	
	cout << dp[0] << endl;
	return 0;
}

Measured memory_bytes: 4356
import sys
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n, k,*h = map(int,read().split())

# k回必殺技を使って敵を減らす
# 強い敵から殺したい, sortする
h.sort()

for i in range(k):
  if h != []:
    h.pop()

print(sum(h))

Measured memory_bytes: 26020
#include<stdio.h>

int main(void){
  	int s;
 	scanf("%d",&s);
  	
  	int YY,MM;
  	YY = s/100;
  	MM = s%100;

  	if(MM==0||MM>12){
      if(YY==0||YY>12){
       	printf("NA");
      }else{
      	printf("MMYY");
      }
    }else{
     if(YY>0&&YY<13){
       printf("AMBIGUOUS");
    	}else{
       printf("YYMM");
     }
    }
}

Measured memory_bytes: 128
n,m = gets.split.map(&:to_i)
x = Array.new(n+1,0)

ans0 = 0
ans1 = 0
m.times do
    pp,s = gets.chomp.split
    pp = pp.to_i
    next if x[pp] == -1

    if s == "AC"
        ans0 += 1
        ans1 += x[pp]
        x[pp] = -1
    else
        x[pp] += 1
    end
end

puts "#{ans0} #{ans1}"

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

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

int main() {
    int N, min = 1001, max = -1, a;
    cin >> N;
    rep(i, N) {
        cin >> a;
        if (a < min) {
            min = a;
        } 
        if (a > max) {
            max = a;
        }
    }
    cout << max - min << endl;

    return 0;
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);

int32_t main() {
    string s; cin >> s;
    int len = s.length();
    if(s[len-1] == 's') {
        string ans;
        ans = s + "es";
        cout << ans<< endl;
    }
    else {
        string ans;
        ans = s + 's';
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
    int m,f,r;
    while(1){
        cin>>m>>f>>r;
        if(m==-1 && f==-1 && r==-1)break;
        if(m==-1||f==-1){
            cout<<"F"<<endl;
        }
        else if(m+f>=80){
            cout<<"A"<<endl;
        }
        else if(m+f>=65 && m+f<80){
            cout<<"B"<<endl;
        }
        else if(m+f>=50 && m+f<65){
            cout<<"C"<<endl;
        }
        else if(m+f>=30 && m+f<50 && r>=50){
            cout<<"C"<<endl;
        }
        else if (m+f>=30 && m+f<50 && r<50){
            cout<<"D"<<endl;
        }
        else if(m+f<30){
            cout<<"F"<<endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3044
H,W=map(int,input().split())
N=int(input())
A=[int(i) for i in input().split()]
List=[]
for i in range(N):
  List=List+[str(i+1)]*A[i]
for h in range(H):
  a=W*h
  b=W*(h+1)
  l=List[a:b]
  if h%2==1:
    l.sort(key=lambda x:-int(x))
  print(" ".join(l))

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

using namespace std;

struct dat{
    int a, b, c, d;
};

int n, m, q;
vector<dat> input(50);
vector<int> cur_v(10);

int f(){
    int out = 0;
    for(int i = 0; i!=q; i++){
        if(cur_v.at(input.at(i).b-1) - cur_v.at(input.at(i).a-1) == input.at(i).c) out += input.at(i).d;
    }
    return out;
}

int dfs(int max_num, int next_ind){
    if(n == next_ind) return f();
    else{
        max_num++;
        if(max_num <= m){
        int out = dfs(max_num, next_ind);
        for(int i = next_ind; i!=n; i++){
            cur_v.at(i) = max_num;
            out = max(out, dfs(max_num, i+1));
        }
        return out;
        }else{ return 0;}
    }
}




int main(){
    cin >> n >> m >> q;
    input.resize(q);
    cur_v.resize(n);
    for(auto& in : input) cin >> in.a >> in.b >> in.c >> in.d;

    int out = 0;
    out = dfs(0, 0);
    cout << out << endl;
    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}
int gcd(int a, int b){
    // a > b
    if(b == 0) return a;
    else return  gcd(b, a%b);
}

int main(){
    int k; cin >> k;
    ll sum = 0;
    for(int i = 1; i <= k; i++){
        for(int j = 1; j <= k; j++){
            for(int l = 1; l <= k; l++){
                sum += gcd(i, gcd(j,l));
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <limits>
#include <bits/stdc++.h>
#include <queue>
#include <type_traits>
#include <cstdint>
using namespace std;
const int INF = 7+(1e+9);
typedef int Weight;
struct Edge {  //src:辺の始点,dst:辺の終点,weight:辺の重さ
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : //辺は重さが重いものを"小さい"と定義する
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
//引数 g:隣接リスト,s:始点,dist:各頂点までの距離が入る(負閉路を含む場合,-INF),prev:最短路木の親頂点が入る
//戻値 負閉路が存在しない場合:true,そうでないとき:false
bool shortestPath(const Graph &g,int s,vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF+INF); dist[s] = 0;
  prev.assign(n, -2);
  bool negative_cycle = false;
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(auto e=g[i].begin();e!=g[i].end();e++){
        if(dist[e->dst] > dist[e->src] + e->weight) {
          dist[e->dst] = dist[e->src] + e->weight;
          prev[e->dst] = e->src;
          if (k == n-1) {
            dist[e->dst] = -INF;
            negative_cycle = true;
          }
        }
      }
    }
  }
  return !negative_cycle;
}

//引数 prev:最短路木の親頂点集合,t:終点
//戻値 path:sからtへの最短経路
vector<int> buildPath(const vector<int> &prev, int t) {
  vector<int> path;
  for (int u = t; u >= 0; u = prev[u])
    path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}
int main(){
    int n;
    cin >> n;
    Graph g(n);  
    for(int i=0;i<n;i++){
        int u,k;
        cin >> u >> k;
        for(int j=0;j<k;j++){
            int v,c;
            cin >> v >> c ;
            g[u].push_back(Edge(u,v,c));
        }
    }
    
  // ...
  //頂点数vの空隣接リストgを生成
  // ...
      //隣接リストgにsからtに向かう重さwの辺を追加
  // ...
  vector<Weight> dist;
  vector<int> prev;
  bool negative_cycle=shortestPath(g,0,dist,prev);
  for(int i=0;i<n;i++){
      cout << i <<" ";
      cout << dist[i]<<endl;
  } 
  // ...
}


Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define rlp(i,a,b) for(int i=a;i>b;i--)
#define ft first
#define sd second
#define pii pair<int,int>
#define all(vect) vect.begin(),vect.end()
#define rall(vect) vect.rbegin(),rend() 
const int num = 101;
typedef long long ll;
ll dp[num][100001],w[num],v[num];
int main()
{
	ll n,W;
	cin >> n >> W;
	rep(i,1,n+1)
		cin >> w[i] >> v[i];
	rep(i,1,n+1)
	{
		rep(j,1,W+1)
		{
			if(j>=w[i])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	cout << dp[n][W] << "\n";

	return 0;
}

Measured memory_bytes: 78336
def main():
    while True:
        N = int(input())
        if N==0:
            exit()

        (W, H) = [int(x) for x in input().split()]
        persimmon = [[0 for j in range(100)] for i in range(100)]
        for _ in range(N):
            (x, y) = [int(x) for x in input().split()]
            persimmon[x][y] = 1

        cumsum = [[0 for j in range(100)] for i in range(100)]
        for x in range(1, 100):
            for y in range(1,100):
                cumsum[x][y] = cumsum[x-1][y] + cumsum[x][y-1] - cumsum[x-1][y-1] + persimmon[x][y]

        (S, T) = [int(x) for x in input().split()]
        max_persimmon = 0
        for x in range(S, W+1):
            for y in range(T, H+1):
                max_persimmon = max(max_persimmon, cumsum[x][y]+cumsum[x-S][y-T]-cumsum[x][y-T]-cumsum[x-S][y])
        print(max_persimmon)

if __name__ == '__main__':
    main()

Measured memory_bytes: 6976
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = 1234567;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int n,a,b;
	cin>>n>>a>>b;
	cout<<min(a*n,b)<<endl;
	return 0;
}


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

#define INFTY (1 << 30);
typedef long long ll;

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

  if (S.size() == 1) {
    cout << 0 << endl;
    return 0;
  }

  // generate two candidate
  string cand[2];
  cand[0] = "";
  cand[1] = "";

  for (int i = 0; i < S.size(); i++) {
    if (i % 2 == 0) {
      cand[0] = cand[0] + "0";
      cand[1] = cand[1] + "1";
    } else {
      cand[0] = cand[0] + "1";
      cand[1] = cand[1] + "0";
    }
  }

  int counter[2] = {0, 0};
  for (int i = 0; i < S.size(); i++) {
    if (cand[0][i] == S[i])
      counter[0]++;
    if (cand[1][i] == S[i])
      counter[1]++;
  }

  if (counter[0] < counter[1])
    cout << counter[0] << endl;
  else
    cout << counter[1] << endl;
  
  return 0;
}


Measured memory_bytes: 872
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 2;

int n, m, k, a[N], dir[N], b[N];

inline int Collide(int i, int j)
{
    if (dir[i] == dir[j]) return false;
    if (dir[i] == -1) swap(i, j);
    int dist = (a[j] - a[i] + m) % m;
    if (k * 2 < dist) return 0;
    else return 1 + (k * 2 - dist) / m;
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &a[i], &dir[i]);
        dir[i] = (dir[i] == 1 ? 1 : -1);
        b[i] = ((a[i] + dir[i] * k) % m + m) % m;
    }
    sort(b, b + n);
    int rot = lower_bound(b, b + n, ((a[0] + dir[0] * k) % m + m) % m) - b;

    if (rot + 1 < n && b[rot] == b[rot + 1] && dir[0] == 1)                // special case: two ants have same position after T seconds
        ++rot;

    for (int i = 1; i < n; ++i)
    {
        rot += Collide(0, i) * -dir[0];
        rot = (rot % n + n) % n;
    }
    rotate(b, b + rot, b + n);
    for (int i = 0; i < n; ++i)
        printf("%d\n", b[i]);
    return 0;
}


Measured memory_bytes: 2304