akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <vector>

class DisjointSet
{
public:
	DisjointSet(int n)
	{
		p.resize(n, 0);
		rank.resize(n, 0);
		for (int i = 0; i < n; i++)
			MakeSet(i);
	}

	void MakeSet(int x)
	{
		p[x] = x;
		rank[x] = 0;
	}

	bool Same(int x, int y)
	{
		return FindSet(x) == FindSet(y);
	}

	int FindSet(int x)
	{
		if (p[x] != x)
			p[x] = FindSet(p[x]);
		return p[x];
	}

	void Unit(int x, int y)
	{
		Link(FindSet(x), FindSet(y));
	}

	void Link(int x, int y)
	{
		if (rank[x] > rank[y])
			p[y] = x;
		else
		{
			p[x] = y;
			if (rank[x] == rank[y])
				rank[y]++;
		}
	}

private:
	std::vector<int> p, rank;
};

int main()
{
	int n, q, c, x, y;
	scanf("%d%d", &n, &q);
	DisjointSet ds(n);

	for (int i = 0; i < q; i++)
	{
		scanf("%d%d%d", &c, &x, &y);
		//printf("T %d %d %d\n", c, x, y);
		if (c == 0)
			ds.Unit(x, y);
		else
			printf("%d\n", ds.Same(x, y) ? 1 : 0);
	}

	return 0;
}



Measured memory_bytes: 2804
A, B, C, K = map(int, input().split())

def p(A, B, C, K):
    point = 0

    if K >= A:
        K -= A
        point += A
    else:
        point += K
        return point

    if K >= B:
        K -= B
    else:
        return point
    
    point -= K
    return point


print(p(A, B, C, K))

Measured memory_bytes: 9188
import sys
  
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
  
  
N,M,L = map(int,input().split())
  
A = [list(map(int,input().split())) for i in range(N)] #N*M配列の取得
B = [list(map(int,input().split())) for i in range(M)] #M*L配列の取得
ANS = [[0]*L for i in range(N)] #N*L
  
  
for x in range(N):
    for y in range(L):
        for z in range(M):
            ANS[x][y] += B[z][y]*A[x][z]
  
for row in range(N):
    print("%d"%ANS[row][0],end = "")
    for col in range(1,L):
        print(" %d"%(ANS[row][col]),end = "")
    print()


Measured memory_bytes: 7068
a_list = gets.chomp.chars
b_list = gets.chomp.chars
c_list = gets.chomp.chars

turn = 'a'
while true
  list =
    case turn
    when 'a'
      a_list
    when 'b'
      b_list
    when 'c'
      c_list
    end
  if list.empty?
    puts(turn.upcase)
    exit 0
  end
  turn = list.shift
end


Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int w = sc.nextInt();
        String a = "safe";

        if(w>=s){
            a ="unsafe";
        }

        System.out.print(a);
    }
}

Measured memory_bytes: 35760
#include "bits/stdc++.h"
using namespace std;
//#b?£?f??????r???????????¨?±????v??????????????§??\?±????????????¨??????????????????v?????????????????´??????v????????????????????¨??????????????????
int main() {
	int n, m, sum;
	cin >> n >> m;
	int a[n][m]={};
	int b[m];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			sum += a[i][j] * b[j];
		}
		cout << sum << endl;
		sum = 0;
	}
}

Measured memory_bytes: 3116
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    R = int(input())
    print(2 * R * pi)


def main():
    solve()


if __name__ == '__main__':
    main()


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

int main()
{
  int a,b;
  cin >> a >> b;
  b += a;
  if(b % 2) b++;
  cout << b / 2 << endl;
  
  return 0;
}

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

int main(){
    int n , x;
    cin>>n>>x;
    vector<int> v = {x};
    for(int i = 0;i<n;i++){
        int y;
        cin>>y;
        v.push_back(y);
    }
    sort(v.begin(),v.end());
    int gcd = 0;
    for(int i = 1;i<v.size();i++){
        gcd = __gcd(gcd , v[i]- v[i-1]);
    }
    cout<<gcd;
    return 0;
}

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

int N, D, X, A;

int main() {
  cin >> N >> D >> X;
  for (int i = 1; i <= N; ++i) {
    cin >> A;
    X += (D - 1) / A + 1;
  }
  cout << X << endl;
}


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

void solve(long long H, long long W, long long N, vector<long long> a){
	long long x = 0;
  long long y = 0;
  long long ans[H][W] = { 0 };
  long long count = 0;
  string dir = "right";

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      ans[i][j] = 0;
    }
  }

  while ( count < H * W ) {
    for ( long long i = 0; i < N; i++ ) {
      for ( long long j = 0; j < a[i]; j++ ) {
        ans[y][x] = i + 1;
        count++;
        if (dir == "right") {
          x++;
          if (x + 1 == W || ans[y][x + 1] != 0) dir = "down";
        } else if (dir == "down") {
          y++;
          if (y + 1 == H || ans[y + 1][x] != 0) dir = "left";
        } else if (dir == "left") {
          x--;
          if (x - 1 < 0 || ans[y][x - 1] != 0) dir = "up";
        } else if (dir == "up") {
          y--;
          if (y - 1 < 0 || ans[y - 1][x] != 0) dir = "right";
        }
      }
    }
  }

  for ( long long i = 0; i < H; i++ ) {
    for ( long long j = 0; j < W - 1; j++ ) {
      cout << ans[i][j] << ' ';
    }
    cout << ans[i][W - 1];
    cout << endl;
  }

}

int main(){	
	long long W;
	long long H;
	long long N;
	scanf("%lld",&H);
	scanf("%lld",&W);
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(H, W, N, a);
	return 0;
}



Measured memory_bytes: 512
#include <stdio.h>
 
/* Macro definition */
#define MAX 20001
 
/* Struct declaration */
struct pair {
  int x;
  int ar;
};
 
/* Prototype declaration */
void push_stack1(int);
void push_stack2(int, int);
int returnTopElement(void);
int pop_stack1(void);
struct pair pop_stack2(void);
 
/* Grobal variable */
int top_stack1 = 0, top_stack2 = 0;
 
/* Stack */
int stack1[MAX];
struct pair stack2[MAX];
 
int main() {
  int i, j;
  int sum = 0, a;
  struct pair c;
  char input[MAX];
 
  /* Input */
  scanf("%s", input);
 
  /* Process */
  for (i = 0; input[i] != '\0'; i++) {
    if(input[i] == '\\') push_stack1(i);
    else if((input[i] == '/') && (top_stack1 > 0)) {
      j = pop_stack1();
      sum += i - j;
      a = i - j;
      while ((top_stack2 > 0) && stack2[top_stack2 - 1].x > j) {
        a += stack2[top_stack2 - 1].ar ;
        c = pop_stack2();
      }
      push_stack2(j, a);
    }
  }
 
  /* Output */
  printf("%d\n", sum);
  printf("%d", top_stack2);
  for(i = 0; i < top_stack2; i++) {
    if(i < top_stack2) printf(" ");
    printf("%d", stack2[i].ar);
  }
  printf("\n");
 
 
  return 0;
}
 
void push_stack1(int x) {
  stack1[top_stack1] = x;
  top_stack1++;
}
 
void push_stack2(int j, int a) {
  stack2[top_stack2].x = j;
  stack2[top_stack2].ar = a;
  top_stack2++;
}
 
int pop_stack1(void) {
  int r = 0;
 
  top_stack1--;
   
  if(top_stack1 < 0) {
    top_stack1 = 0;
    return 0;
  }
  r = stack1[top_stack1];
  return r;
 
}
 
struct pair pop_stack2(void) {
  struct pair s;
 
  top_stack2--;
   
  if(top_stack2 < 0) {
    top_stack2 = 0;
    return;
  }
  s = stack2[top_stack2];
  return s;
 
}

Measured memory_bytes: 644
#include<stdio.h>

int main() {

	int i, j;

	for (i = 1; i < 10; i++) {
		for (j = 1; j < 10; j++) {
			printf("%dx%d=%d\n", i, j, i*j);
		}
		printf("");
	}

	return 0;
}


Measured memory_bytes: 1904
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp

#define NIL -1

struct Node
{
    int l, r, p;
};

int n;
Node T[100005];

static void print(int i) {
    printf(" %d", i);
}

static void preOrder(int i) {
    if (i==NIL) return;
    print(i);
    preOrder(T[i].l);
    preOrder(T[i].r);
}

static void inOrder(int i) {
    if (i==NIL) return;
    inOrder(T[i].l);
    print(i);
    inOrder(T[i].r);
}

static void postOrder(int i) {
    if (i==NIL) return;
    postOrder(T[i].l);
    postOrder(T[i].r);
    print(i);
}

int main() {
    cin >> n;
    REP(i, n) T[i].p = NIL;

    REP(i, n) {
        int id, l, r;
        cin >> id >> l >> r;
        T[id].l = l;
        T[id].r = r;
        if (l != NIL) T[l].p = id;
        if (r != NIL) T[r].p = id;
    }


    int root = 0;
    REP(i, n) if (T[i].p == NIL) root = i;

    cout << "Preorder" << "\n";
    preOrder(root); cout << "\n";
    cout << "Inorder" << "\n";
    inOrder(root); cout << "\n";
    cout << "Postorder" << "\n";
    postOrder(root); cout << "\n";
    return 0;
}


Measured memory_bytes: 3216
#include<iostream>
#include<cstdio>

using namespace std;

// a = 1のとき
// x = c - by
// d(c-by)*ey=f
// y = (f - dc) / (e - db)

double func1(double y1, double r1, double x2, double y2, double r2) {
	double temp1 = x2 * y1;
	double temp2 = x2 * r1;
	return (r2 - temp2) / (y2 - temp1);
}

int main() {

	double a, b, c, d, e, f;
	while (cin >> a >> b >> c >> d >> e >> f) {
		double x = 0.0, y = 0.0;

		// double型は等価比較してはいけないといわれるが、
		// 一度も計算していないためこのケースは問題なし
		if (a == 1.0) {
			y = func1(b, c, d, e, f);
			x = c - b * y;
		}
		else if (d == 1.0) {
			y = func1(e, f, a, b, c);
			x = f - e * y;
		}
		else if (b == 1.0) {
			x = func1(a, c, e, d, f);
			y = c - a * x;
		}
		else if (e == 1.0) {
			x = func1(d, f, b, a, c);
			y = f - d * x;
		}
		else {
			// aが1となるように計算
			double a_1 = 1.0, b_1 = b / a, c_1 = c / a;
			y = func1(b_1, c_1, d, e, f);
			x = c_1 - b_1 * y;
		}

		printf("%.3f %.3f\n", x, y);
	}

	return 0;
}

Measured memory_bytes: 1236
#include<cstdio>
#include<algorithm>
using namespace std;
int L;
main(){
  while(1){
    scanf("%d",&L);
    if(!L) break;
    int sum=0;
    int res=-1;
    for(int i=1;i<13;i++){
      int M,N;
      scanf("%d %d",&M,&N);
      sum+=(M-N);
      if(sum>=L && res==-1) res=i;
    }
    if(res==-1) puts("NA");
    else printf("%d\n",res);
  }
}

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

int main() {
  ll a,b,c,d;cin>>a>>b>>c>>d;
  ll ans = a*c;
  ans = max(ans, a*d);
  ans = max(ans, b*c);
  ans = max(ans, b*d);
  cout<<ans;
}


Measured memory_bytes: 3620
n = int(input())
tasks = []
for _ in range(n):
    a,b = map(int,input().split())
    tasks.append((a,b))
tasks.sort(key=lambda x:x[1])
t = 0
for task in tasks:
    t += task[0]
    if t > task[1]:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 31860
#include <bits/stdc++.h>
#define MAX 200005
#define ll long long
#define P ((ll)1e9+7)
#define INF 0x3f3f3f3f
using namespace std;

template<typename T>
void read(T &n){
	n = 0;
	char c = getchar();
	int f = 1;
	while(!isdigit(c) && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(isdigit(c)){
		n = (n<<1)+(n<<3)+c-'0';
		c = getchar();
	}
	n *= f;
}

int n, A, B, o1, o2;
int c[MAX], w[MAX], vis[MAX], a[MAX], cnt[MAX], mn[MAX];
ll fac[MAX], inv[MAX], ans = 1;

ll qpow(ll a, ll n){
	ll res = 1;
	while(n > 0){
		if(n&1) res = (res*a)%P;
		a = a*a%P;
		n >>= 1;
	}
	return res;
}

void init(){
	fac[0] = 1;
	for(int i = 1; i < MAX; i++){
		fac[i] = fac[i-1]*i%P;
	}
	inv[MAX-1] = qpow(fac[MAX-1], P-2);
	for(int i = MAX-2; i >= 0; i--){
		inv[i] = inv[i+1]*(i+1)%P;
	}
}

ll C(ll n, ll m){
	if(n < m) return 0;
	return fac[n]*inv[m]%P * inv[n-m]%P;
}

int main()
{
	init();
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++){
		read(c[i]), read(w[i]);
		cnt[c[i]]++;
		mn[i] = INF;
	}
	for(int i = 1; i <= n; i++){
		mn[c[i]] = min(mn[c[i]], w[i]);
	}
	for(int i = 1; i <= n; i++){
		if(mn[i] == INF) continue;
		if(!o1 || mn[i] < mn[o1]){
			o2 = o1;
			o1 = i;
		}
		else if(!o2 || mn[i] < mn[o2]) o2 = i;
	}
	
	for(int i = 1; i <= n; i++){
		if(mn[c[i]] != w[i] && w[i]+mn[c[i]] <= A) continue;
		if(c[i]==o1 && w[i]+mn[o2] <= B) continue;
		if(c[i]!=o1 && w[i]+mn[o1] <= B) continue;
		cnt[c[i]]--;
	}
	
	ll ans = 1, s = cnt[o1];
	for(int i = 1; i <= n; i++){
		if(i != o1 && mn[i]+mn[o1] <= B){
			s += cnt[i];
			ans = ans * C(s, cnt[i]) % P;
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 7936
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
//<DEFINE>
void Fast() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
}
void File() {
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}
#define ll long long
#define ull unsigned long long
#define mod 1000000007
ll gcd(ll a, ll b) {
	return!b ? a : gcd(b, a % b);
}
#define fix(n) cout << fixed << setprecision(n);
#define numOfOnes(n) __builtin_popcount(n)
#define all(a) a.begin(), a.end()
#define skip continue
#define stop(n) return cout<<n,0
#define pi  acos(-1)
#define endl "\n"
#define ceil(x,y) (x+y-1)/y
//</DEFINE>

/*█▀▀▄░░░░░░░░░░░▄▀▀█
░█░░░▀▄░▄▄▄▄▄░▄▀░░░█
░░▀▄░░░▀░░░░░▀░░░▄▀
░░░░▌░▄▄░░░▄▄░▐▀▀
░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█
░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█
▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█
█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀
░▀▄░░▀░░▀▀▀░░▀░░░▄█▀
░░░█░░░░░░░░░░░▄▀▄░▀▄
░░░█░░░░░░░░░▄▀█░░█░░█
░░░█░░░░░░░░░░░█▄█░░▄▀
░░░█░░░░░░░░░░░████▀
░░░▀█▄▄▄▀▀▀▀▄▄▄█▀*/
int n,k;
vector<int>v;
ll res[100001];
//<FUNCTIONS>
ll solve(int idx = 0) {
	if (idx == n - 1)return 0;
	if (~(res[idx]))return res[idx];
	ll mn = INT_MAX;
	for (int i = 1; i <= k; i++) {
		if (idx + i >= n)break;
		mn = min(mn, solve(idx + i) + abs(v[idx] - v[idx + i]));
	}
	return res[idx] = mn;
}
//</FUNCTIONS>		
int main() {
	Fast();
	cin >> n >> k;
	for (int i = 0; i <= n; i++)
		res[i] = -1;
	v.resize(n);
	for (int i = 0; i < n; i++)cin >> v[i];
	cout << solve() << endl;
}


Measured memory_bytes: 7680
n=int(input())
l=list(map(int,input().split()))


l.sort()

cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            #print(l[i],l[j],l[k])
            if l[i]+l[j]>l[k] and l[i]!=l[j] and l[i]!=l[k] and l[k]!=l[j]:
                cnt+=1
                

print(cnt)

Measured memory_bytes: 9128
import copy
import fractions
from functools import reduce

N = int(input().strip())
A = list(map(int, input().strip().split()))
m = int(1e9 + 7)
#m = 1000000007
#print(m)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

ans = 0
x = lcm(*A)
for i in range(N):
  ans += (x // A[i])
print(ans % m)

Measured memory_bytes: 6200
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

ll dp[10010][110][2];

string k;
int d;

ll rec(int digit, int sumModD, int tight){
    
    if(digit == k.size()){
        return sumModD == 0;
    }

    int num = k[digit] - '0';

    int lim = tight ? 9 : num;

    ll &res = dp[digit][sumModD][tight];

    if(~res) return res;

    res = 0;

    for(int i=0; i<=lim; i++){
        res += rec(digit + 1, (sumModD + i) % d, tight || (i < lim));
        res %= MOD;
    }

    return res;
}

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

    memset(dp, -1, sizeof(dp));

    ll ans = rec(0, 0, 0) - 1 + MOD;

    cout << ans % MOD << endl;
}

Measured memory_bytes: 17792
from sys import stdin,stdout
l,r,d=list(map(int,stdin.readline().strip().split()))
c=0
if l%d==0 and r%d==0:
    stdout.write(str(int(r/d)-int(l/d)+1)+'\n')
else:
    stdout.write(str(int(r/d)-int(l/d))+'\n')


Measured memory_bytes: 9168
N = int(input())
flug = False
cnt = 0
for _ in range(N):
    D1, D2 = list(map(int, input().split())) 
    if D1 == D2:
        cnt += 1
    else:
        cnt = 0
    if cnt >= 3:
        flug = True
if flug:
    print("Yes")
else:
    print("No")

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main()
{
    int N;
    string S;

    cin >> N;
    cin >> S;

    REP(i, S.length()){
        char c = S[i];
        c = ((c - 'A') + N) % 26 + 'A';
        cout << c;
    }
    cout << endl;
    return 0;
}

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

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

  if(a>b){
    ans=a-b-w;
  }
  else{
    ans=b-a-w;
  }
    if(ans>0){
      cout << ans << endl;
    }
    else{
      cout << "0" << endl;
    }
}


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

using namespace std;

vector< vector<int> > v, w; 
vector<int> depth;
vector<bool> was;

void dfs(int nv) {
	was[nv] = true;
	
	for (int i = 0;i < v[nv].size();i++) {
		int to = v[nv][i];
		if (!was[to]) dfs(to);
		depth[nv] = max(depth[nv], depth[to] + 1);
	}
}

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

	v.resize(n); w.resize(n);
	was.assign(n, false);
	depth.assign(n, 0);
	
	for (int i = 0;i < m;i++) {
		cin >> a >> b; a--; b--;
		v[a].push_back(b);				
		w[b].push_back(a);
	}

	for (int i = 0;i < n;i++) 
		if (w[i].size() == 0) dfs(i);

	int D = 0;
	for (int i = 0;i < n;i++) if (D < depth[i]) D = depth[i];
	
	cout << D;
}

Measured memory_bytes: 16256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  int sx,sy,tx,ty;
  cin >> sx >> sy >> tx >> ty;
  int tate=ty-sy,yoko=tx-sx;
  for(int i=0; i<yoko; i++) {
    cout << 'R';
  }
  for(int i=0; i<tate; i++) {
    cout << 'U';
  }
  for(int i=0; i<yoko; i++) {
    cout << 'L';
  }
  for(int i=0; i<tate; i++) {
    cout << 'D';
  }
  cout << 'D';
  for(int i=0; i<yoko+1; i++) {
    cout << 'R';
  }
  for(int i=0; i<tate+1; i++) {
    cout << 'U';
  }
  cout << 'L';
  cout << 'U';
  for(int i=0; i<yoko+1; i++) {
    cout << 'L';
  }
  for(int i=0; i<tate+1; i++) {
    cout << 'D';
    
  }
  cout << 'R' << endl;
}

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define Rep(i,n) for(ll i = 0; i <= n; i++)
#define REp(i,n) for(ll i = 1; i < n; i++)
#define REP(i,n) for(ll i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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;
  cin >> n;
  if(n == 25) cout << "Christmas" << endl;
  if(n == 24) cout << "Christmas Eve" << endl;
  if(n == 23) cout << "Christmas Eve Eve" << endl;
  if(n == 22) cout << "Christmas Eve Eve Eve" << endl;
}

Measured memory_bytes: 3568
#include <stdio.h>

void bubble(int *arr, int size){
	int count = 0;
	for(int i=0; i< size;i++){
		for(int j = size-1; j>i; j--){
			if(arr[j] < arr[j-1]){
				int tmp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = tmp;
				count++;
			}
		}
	}
	for(int k=0; k<size; k++){
		if(k!=size-1){
			printf("%d ", arr[k]);
		}
		else if(k==size-1){
			printf("%d\n", arr[k]);
		}
	}
	printf("%d\n", count);
}

int main(){
	int size=0;
	scanf("%d", &size);
	int num[size];
	for(int i=0;i<size; i++){
		scanf("%d", &num[i]);
	}
	bubble(num, size);
	return 0;
}


Measured memory_bytes: 1968
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string A, B, C;
    cin >> A >> B >> C;
    int i = A.length();
    int j = B.length();
    int k = C.length();

    if (A[i-1] == B[0] && B[j-1] == C[0]){
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>

#define INF 1<< 29

typedef unsigned long long LL;

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int>a;
	for (int i = 0; i < N * 3; i++) {
		int t;
		cin >> t;
		a.push_back(t);
	}
	vector<LL>up_check(N+3, 0);
	vector<LL>lo_check(N+3, 0);
	priority_queue<int,std::vector<int>, std::greater<int>> uq;
	priority_queue<int> lq;
	LL upper_sum = 0;
	for (int i = 0; i < N; i++) {
		upper_sum += a[i];
		uq.push(a[i]);
	}
	LL lower_sum = 0;
	for (int i = N * 2; i < N * 3; i++) {
		lower_sum += a[i];
		lq.push(a[i]);
	}
	up_check[0] = upper_sum;
	for (int i = 0; i < N; i++) {
		int j = i + N;
		if (uq.top() < a[j]) {
			up_check[i + 1] = up_check[i] - uq.top() + a[j];
			uq.pop();
			uq.push(a[j]);
		}
		else {
			up_check[i + 1] = up_check[i];
		}
	}
	
	lo_check[0] = lower_sum;
	for (int i = 0; i < N; i++) {
		int j = (2 * N) - 1 - i;
		if (lq.top() > a[j]) {
			lo_check[i + 1] = lo_check[i] - lq.top() + a[j];
			lq.pop();
			lq.push(a[j]);
		}
		else {
			lo_check[i + 1] = lo_check[i];
		}
	}
	long long answer = up_check[0] - lo_check[N];
	for (int i = 0; i < N+1; i++) {
		int j = N - i;
		answer = max(answer, (long long)(up_check[i] - lo_check[j]));
	}
	cout << answer << endl;
	
}

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


#define debug(x) cout << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

const int maxn = 3e5 + 5;
ll fat[maxn], inv[maxn];

ll C(int n, int k)
{
  if(n < k) 
    return 0;
  if(n < 0 || k < 0) 
    return 0;
  return (((fat[n] * inv[k]) % mod) * inv[n - k]) % mod;
}

void initFactorials()
{
  fat[0] = 1;
  inv[0] = 1;
  for(int i = 1; i < maxn; i++)
  {
    fat[i] = (i * fat[i-1]) % mod;
    inv[i] = exp(fat[i], mod - 2);
  }
}

ll f[maxn], a[maxn], c[maxn], d[maxn];
int n;

bool check(ll val, ll k)
{
  bool ok = true;
  for(int i = 0; i < n ; i++)
  {
    if(f[i] * a[i] > val)
    {
      ll qt = val / f[i];
      ll b = min(k, a[i] - qt);
      a[i] -= b;
      k -= b;
    }
    ok &= f[i] * a[i] <= val;
  }
  return ok;
}

int main()
{
  ios::sync_with_stdio(false);
  ll k;
  cin >> n >> k;
  
  for(int i = 0; i < n ; i++)
  {
    cin >> a[i];
    c[i] = a[i];
  }
  for(int i = 0; i < n ; i++)
  {
    cin >> f[i];
    d[i] = f[i];
  }

  sort(c, c + n, greater<ll>());
  sort(d, d + n);
  
  
  ll lo = 0;
  ll hi = 1e17 + 5;
  ll ans = -1;

  while(lo <= hi)
  {
    ll mid = (lo + hi) >> 1;
    
    for(int i = 0; i < n ; i++)
    {
      a[i] = c[i];
      f[i] = d[i];
    }

    if(check(mid, k))
    {
      ans = mid;
      hi = mid - 1;
    }
    else
    {
      lo = mid + 1;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9872
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+7;

bool v[8000000];

int main() {
    while (true) {
       int m, n;
       cin >> m >> n;
       if (m == 0) break;
       memset(v, 0, sizeof(v));
       int i = m;
       while (n >= 0) {
           if (v[i]) {
               i++;
               continue;
           }
           for (int j = 1; j * i <= 7400000; j++) v[i * j] = true;
           i++;
           n--;
       }
       dump(i - 1);
    }
    return 0;
} 



Measured memory_bytes: 10892
/*╔═══╗──╔╗╔╗───────────────────╔╗────────╔═══╦═══╗
  ║║─║╠╗╠╗╔╣╚═╦══╦═╗╔╦╗╔═╗╔══╦══╣╚═╦╦══╦══╣║─║║║─╚╝
  ║╔═╗║╚╝║╚╣║║║╚╝║║─╔╦╗║║║║╚╝║╚╝║╚╝║║║═╬══║╔═╗║╚╩═║
  ╚╝─╚╩══╩═╩╝╚╩══╩╝─╚╩╝╚╝╚╩══╩══╩══╩╩══╩══╩╝─╚╩═══╝*/
#include<bits/stdc++.h>
#define mod 1000000007
#define modc 998244353
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
using namespace std;
void solve()
{
	int i,j;
	ll sum = 0,prod= 1;
	int x,y,z;
	cin >> x >> y >> z;
	cout << z << " " << x << " " << y << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t = 1;
	while(t--)
	{
		solve();
	}
}


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

#define ll long long int
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(i,x,n)  for(int i=x;i<n;i++)
#define FASTIO cin.tie(0); cout.tie(0);

int main()
{
	FASTIO;
	ll n,k;
	 cin>>n>>k;
	 vector<ll>vect(n);
	 f(i,0,n)
        cin>>vect[i];


    //dp[i]-> is true if the player with first turn wins if the pile
    //contains i stones.

    vector<bool>dp(k+1,0);

    for(int stones=0;stones<=k;stones++)
    {
        for(int x:vect)
            if(x<=stones && !dp[stones-x])
                dp[stones]=true;
    }

    if(dp[k])
        cout<<"First\n";
    else
        cout<<"Second\n";



	return 0;
}













Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define Se second
#define Fi first
#define rep(i, n) for(int i=0;i<n;i++)
#define pb(x) push_back(x)

const int MX = 1<<16 | 5;
const int MM = 1000000007;

ll F[MX], I[MX], FI[MX];

ll P(int x, int y){
	if(x < y || y < 0) return 0;
	return F[x] * FI[x-y] % MM;
}

int A[MX];
ll dp[MX], tdp[MX];
int main()
{
	F[0] = FI[0] = I[1] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - MM/i) * I[MM%i] % MM;
	for(int i = 1; i < MX; i++){
		F[i] = F[i-1] * i % MM;
		FI[i] = FI[i-1] * I[i] % MM;
	}
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++) scanf("%d", A+i);
	A[0] = 1; A[M+1] = (1<<N)+1;

	for(int i = 0; i < 1<<N; i++){
		int c = 0;
		for(int j = 0; j < N; j++) if(i&1<<j) c++;
		if((N-c)&1) dp[i] = MM - 1;
		else dp[i] = 1;
	}
	int used = 0;
	for(int x = 1; x <= M+1; x++){
		int t = A[x] - A[x-1] - 1;
		for(int j = 0; j < 1<<N; j++){
			dp[j] = dp[j] * P(j-used, t) % MM;
		}
		used += t;
		if(x == M+1) break;

		for(int j = (1<<N)-1; j >= 0; j--){
			for(int k = 0; k < N; k++){
				if(~j&1<<k);
				else continue;
				dp[j|1<<k] = (dp[j|1<<k] + dp[j] * (1<<k)) % MM;
			}
			dp[j] = (dp[j] * max(j-used, 0)) % MM;
		}
		used++;
	}
	printf("%lld\n", dp[(1<<N)-1] * (1<<N) % MM);
}


Measured memory_bytes: 2304
import java.nio.file.*;
import java.nio.charset.*;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int m = Integer.parseInt(s.substring(5, 7));
        if(m<=4){
            System.out.println("Heisei");
        }else{
            System.out.println("TBD");
        }
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX (300001)

bool is_prime[MAX+1];
vector<long long> prime;
int size;

void Sieve() {
  fill(is_prime, is_prime+MAX, true);
  
  is_prime[0] = is_prime[1] = false;
  
  for(long long i=2; i<=MAX; i++) {
    if(is_prime[i]) {
      prime.push_back(i);
      for(long long j=i*i; j<=MAX; j+=i) {
	is_prime[j] = false;
      }
    }
  }
}

int main() {
  int n, p;
  
  Sieve();
  
  while(cin >> n >> p, !(n == -1 && p == -1)) {
    int st = upper_bound(prime.begin(), prime.end(), n) - prime.begin();
    vector<long long> vec;
    for(int i=st; i<=st+p; i++) {
      for(int j=i; j<=st+p; j++) {
	vec.push_back(prime[i]+prime[j]);
      }
    }
    sort(vec.begin(), vec.end());
    cout << vec[p-1] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1636
import math
if __name__ == "__main__":
    N, K = map(int, input().split())
    if N == 0:
        ret = 0
        print(int(ret))
        exit(0)
    ret =  N % K
    while ret > abs(ret-K):
        ret = abs(ret-K)
    print(int(ret))

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  for(int i=0; i<s.length(); i++){
    s[i]=(s[i]-'A'+n)%26+'A';
  }
  cout << s;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1002;
#define int long long
const int mod=1e9 + 7;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
int h, w, depth[N][N];char grid[N][N];
	queue< pii > q;
void add(int i, int j, int dst)
{
	if(depth[i][j]==mod) 
	{
		depth[i][j]=dst;q.push(mp(i, j));
	}
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>h>>w;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++) depth[i][j]=-1;
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++) cin>>grid[i][j];
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(grid[i][j]=='#') {q.push(mp(i, j));depth[i][j]=0;}
			else depth[i][j]=mod;
		}
	}
	while(!q.empty())
	{
		pii cur=q.front();q.pop();
		int dst=depth[cur.f][cur.s]+1;
		add(cur.f+1, cur.s, dst);
		add(cur.f-1, cur.s, dst);
		add(cur.f, cur.s+1, dst);
		add(cur.f, cur.s-1, dst);
	}
	int ans=0;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			ans=max(ans, depth[i][j]);
		}
	}
	cout<<ans;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  if(A==1){
    if(B==2){
      cout << "3" << endl;
    }
    else if(B==3){
      cout << "2" << endl;
    }
  }else if(A==2){
    if(B==1){
      cout << "3" << endl;
    }
    else if(B==3){
      cout << "1" << endl;
    }
  }else if(A==3){
    if(B==1){
      cout << "2" << endl;
    }
    else if(B==2){
      cout << "1" << endl;
    }
  }
}

Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 100001
S = sum(A)
for a in A:
    X[a] += 1

for _ in range(int(input())):
    b, c = map(int, input().split())
    S += (c - b) * X[b]
    X[c] += X[b]
    X[b] = 0
    print(S)

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

int N,M,X[100010],count[100010] = {0},mod_count[100010] = {0};

int main(){
	cin >> N >> M;
	for(int i=1;i<=N;i++){
		cin >> X[i];
		count[X[i]]++;
		mod_count[X[i]%M]++;
	}
	int ans = 0;
	for(int i=0;i<M;i++){
		if(i==0){
			ans += mod_count[i]/2;
			mod_count[i] %= 2;
		}else{
			if(i!=M-i) ans += min(mod_count[i],mod_count[M-i]);
			else ans += mod_count[i]/2;
			if(mod_count[i]>=mod_count[M-i]){
				mod_count[i] -= mod_count[M-i];
				mod_count[M-i] = 0;
			}else{
				mod_count[M-i] -= mod_count[i];
				mod_count[i] = 0;
			}
		}
	}
//	cout << ans << endl;
	for(int i=1;i<=1e5;i++){
		if(count[i]>=2){
			if(mod_count[i%M]>=2){
				while(count[i]>=2 && mod_count[i%M]>=2){
					ans++;
					count[i] -= 2;
					mod_count[i%M] -= 2;
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
#define INF 99999999

using namespace std;

int main(void) {
	int n, c, sum=0, ans;
	int p[100];
	cin >> n >> c;
	REP(i, c)cin >> p[i], sum += p[i];
	ans = int(sum / (n + 1));
	if (sum == ans * (n + 1))cout << ans << endl;
	else cout << (ans + 1) << endl;
	return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

ll a[100001],c[100001];
ll b[100001];
P1 d[100001]={};

int main() {

	ll n,m;
	ll total=0;

	cin>>n>>m;
	rep(i,n){
		cin>>a[i];
	}
	sort(a,a+n);
	rep(i,m){
		cin>>b[i]>>c[i];
		d[i].first=c[i];
		d[i].second=b[i];
	}
	sort(d, d + m, greater<P1>());
	ll s=0;
	ll e=0;
	rep(i,n){
		if(d[s].first>a[i]){
			a[i]=d[s].first;
			e++;
		}
		if(e==d[s].second){
			s++;
			e=0;
		}
		total+=a[i];
	}
	cout<<total<<endl;

	return 0;

}


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

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

int main() {
  string s;cin >> s;
  string ans="";
  rep(i,s.size()){
    if(s[i]=='0'){
      ans+="0";
    }else if(s[i]=='1'){
      ans+="1";
    }else if(s[i]=='B'){
      if (0<ans.size()){
        ans.pop_back();
      }
    }
  }
  cout<<ans<<endl;
}


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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... Args> void rd(Args&... args) {((cin >> args), ...);}
template<typename... Args> void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}

int n,m,q;
vector<array<int,4>> v;
vector<int> ans;
int mx;
void dfs(int x,int num){
    if(x==n){
        ans[x]=num;
        int sum=0;
        for(auto [d,a,b,c]:v){
            if(ans[b]-ans[a]==c) sum+=d;
        }
        mx=max(mx,sum);
        return;
    }
    ans[x]=num;
    for(int i=ans[x];i<=m;i++) dfs(x+1,i);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rd(n,m,q);
    v.resize(q);
    ans.resize(n+1);
    for(auto& [d,a,b,c]:v){
        cin>>a>>b>>c>>d;
    }
    dfs(0,1);
    cout<<mx;
    return 0;
}



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

typedef pair<double, double> P;
int N;
P A[500000];
int x, y;

bool compare_y(P a, P b) {
	return a.second < b.second;
}

double closest_pair(P *a, int n) {
	if (n <= 1) return INF;
	int m = n / 2;
	double x = a[m].first;
	double d = min(closest_pair(a, m), closest_pair(a + m, n - m));
	inplace_merge(a, a + m, a + n, compare_y);

	vector<P> b;
	rep(i,n) {
		if (fabs(a[i].first - x) >= d) continue;

		rep(j,b.size()) {
			double dx = a[i].first - b[b.size() - j - 1].first;
			double dy = a[i].second - b[b.size() - j - 1].second;
			if (dy >= d) break;
			d = min(d, sqrt(dx * dx + dy * dy));
		}
		b.push_back(a[i]);
	}

	return d;
}

signed main()
{
	cin >> N;
	rep(i,N) {
		scanf("%d%d", &x, &y);
		A[i].first = x; A[i].second = y;
	}
	sort(A, A + N);
	printf("%.0f\n", pow(closest_pair(A, N), 2));
}

Measured memory_bytes: 20512
/*input
4 150
150 140 100 200
*/
#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;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define sz(_a) (ll)(_a.size())
#define FILL(n) memset(n,0,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
const ll maxn=2505;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int32_t main(){
    int n,k;
    cin>>n>>k;
    int cnt=0;
    REP(i,n){
        int x;
        cin>>x;
        cnt+=(x>=k);
    }
    cout<<cnt;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	int res_2 = 0, res_4 = 0;
	rep(i, n) {
		if (a[i] % 4 == 0) {
			res_4++;
			continue;
		}
		if (a[i] % 2 == 0) res_2++;
	}

	vector<ll> jud(n, 1);
	if (res_4 >= 1) {
		jud[1] = 4;
		if (res_4 >= 2) {
			jud[n - 2] = 4;
			res_4--;
		}
		res_4--;
	}
	//4の配布
	rrep(i, n) {
		if (res_4 == 0) break;
		if (jud[i - 1] * jud[i] % 4 != 0) {
			jud[i] = 4;
			res_4--;
		}
	}
	bool elf = true;
	//2の配布
	rrep(i, n) {
		if (res_2 == 0) break;
		if (jud[i - 1] * jud[i] % 4 != 0) {
			if (jud[i - 1] % 2 != 0 && jud[i] % 2 != 0) {
				jud[i - 1] = 2;
				jud[i] = 2;
				res_2 -= 2;
			}
			else {
				if (jud[i] % 2 == 0) jud[i - 1] = 2;
				else jud[i] = 2;
				res_2--;
			}
		}
		if (res_2 < 0) {
			puts("No");
			return 0;
		}
	}
	rrep(i, n) {
		if (jud[i - 1] * jud[i] % 4 != 0) elf = false;
	}

	puts(elf ? "Yes" : "No");

	return 0;
}


Measured memory_bytes: 1792
using System;
public class Program {
  public static void Main() {
    int N = int.Parse(Console.ReadLine());
    int lowest = 0;
    int lowestScore = 0;
    for (int i = 0; i < N; i++) {
      string[] input = Console.ReadLine().Split(' ');
      if (int.Parse(input[0]) > lowest) {
        lowest = int.Parse(input[0]);
        lowestScore = int.Parse(input[1]);
      }
    }
    Console.WriteLine(lowest+lowestScore);
  }
}


Measured memory_bytes: 17332
use proconio::input;

fn main() {
    input!{
        n: usize,
        a: [i32; n],
    }
    
    let mut a = a;
    a.sort_by(|x, y| x.cmp(y).reverse());
    let mut alice = 0;
    let mut bob = 0;

    for (i, &x) in a.iter().enumerate() {
        if i % 2 == 0 {
            alice += x;
        } else {
            bob += x;
        }
    }

    println!("{}", alice - bob);
}


Measured memory_bytes: 2184
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc125_c
import fractions, functools, itertools

# input
n = int(input())
A = [int(s) for s in input().split()]
# get ans
gcd = fractions.gcd
L = list(itertools.accumulate(A, gcd))
R = list(itertools.accumulate(A[::-1], gcd))
R = R[::-1]
L.append(0)
R.append(0)
gs = [gcd(L[i-1], R[i+1]) for i in range(n)]
ans = max(gs)
# output
print(ans)



Measured memory_bytes: 16120
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 5000+10;
int u[maxn],v[maxn],c[maxn];
LL d[maxn];
int main(void)
{
	int n,m,p;cin>>n>>m>>p;
	for(int i = 2;i <= n;++i)
		d[i] = -inf;
	for(int i = 1;i <= m; ++i){
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		c[i] -= p;
	}
	for(int i = 1;i <= 2*n; ++i){
		for(int j = 1;j <= m; ++j){
			if(d[u[j]]==-inf) continue;
			if(d[v[j]] < d[u[j]]+c[j]) d[v[j]] = i <= n?d[u[j]]+c[j]:1e18;
		}
	}
    if(d[n] == inf)
    	cout<<-1<<endl;
    else
    	cout<<max(0LL,d[n])<<endl;

   return 0;
}

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

vector<string> nums;

void gen(string& curr, int digitsLeft) {
  if (nums.size() >= 100000) return;
  if (digitsLeft == 0) {
    nums.push_back(curr);
    return;
  }
  char last = curr.back();
  int from = max('0', (char)(last-1));
  int to = min('9', (char)(last+1));
  for(char c = from; c <= to; c++) {
    curr.push_back(c);
    gen(curr, digitsLeft-1);
    curr.pop_back();
  }
}

void precalc() {
  int len = 1;
  while(nums.size() < 100000) {
    for(char c = '1'; c <= '9'; c++) {
      string s = "";
      s.push_back(c);
      gen(s, len-1);
    }
    len++;
  }
}

int main() {
  precalc();
  int k;
  cin >> k;
  cout << nums[k-1] << endl;
}

Measured memory_bytes: 6900
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

class Program
{
    public static void Main()
    {
        string[] fs = Console.ReadLine().Split(' ');
        int N = int.Parse(fs[0]);
        int K = int.Parse(fs[1]);

        int[] h = new int[N];

        for (int i = 0; i < N; i++)
            h[i] = int.Parse(Console.ReadLine());

        Array.Sort(h);

        int min = int.MaxValue;
        for (int i = 0; i <= N - K; i++)
            min = Math.Min(min, h[i + K - 1] - h[i]);
        Console.WriteLine(min);
    }
}

Measured memory_bytes: 15452
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

using P = pair<int, int>;
int main() {
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    cout << (char)(s1[0] + 'A' - 'a');
    cout << (char)(s2[0] + 'A' - 'a');
    cout << (char)(s3[0] + 'A' - 'a');
    cout << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<long long,long long> mp;
vector<long long> v;
int main()
{
	ios_base::sync_with_stdio(false);
	long long N,Ai,ans,i;
	cin>>N;
	for(i=0;i<N;i++)
	{
		cin>>Ai;
		mp[Ai]++;
	}	
	while(!mp.empty()&&mp.rbegin()->second<2)
		mp.erase(--mp.end());
	if(!mp.empty())
	{
		mp.rbegin()->second-=2;
		v.push_back(mp.rbegin()->first);
		if(mp.rbegin()->second==0)
			mp.erase(--mp.end());
	}
	while(!mp.empty()&&mp.rbegin()->second<2)
		mp.erase(--mp.end());
	if(!mp.empty())
	{
		mp.rbegin()->second-=2;
		v.push_back(mp.rbegin()->first);
	}
	ans=0;
	if(v.size()==2)
		ans=v[0]*v[1];
	cout<<ans<<"\n";
	return 0;
}


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

int main() {
  int n; cin>>n;
  if(n<2) cout<<"1"<<endl;
  else if(n>=2&&n<4) cout<<"2"<<endl;
  else if(n>=4&&n<8) cout<<"4"<<endl;
  else if(n>=8&&n<16) cout<<"8"<<endl;
  else if(n>=16&&n<32) cout<<"16"<<endl;
  else if(n>=32&&n<64) cout<<"32"<<endl;
  else cout<<"64"<<endl;
}

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

int tb[1112],ans[1112],N;

int nr(int a)
{
	int ret=1;
	for(int i=2; i<1112; i++)
	{
		if(tb[i]>a) break;
		ret=i;
	}
	return tb[ret];
}

int calc(int z)
{
	int z3=z*z*z, ret=z3;
	for(int i=1; i<z; i++)
	{
		int i3=i*i*i, j3=nr(z3-i3);
		if(i3>j3) break;
		if(i3+j3>=z3) break;
		
		ret=min(ret, z3-i3-j3);
	}
	return ret;
}

int main()
{	
	for(int i=1; i<1112; i++)
		tb[i]=i*i*i;
		
	for(int i=1; i<1112; i++)
		ans[i]=calc(i);
		
	while(cin >> N, N)
		cout << ans[N] << endl;
}

Measured memory_bytes: 760
def printdp(dp):
    return
    print({i:v for i, v in enumerate(dp) if v < 10000})

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(N)]
    V = sum(v for _, v in wv)
    dp = [0] + [float('inf')] * V
    for wi, vi in wv:
        for i in range(V, vi - 1, -1):
            t = dp[i - vi] + wi
            if t < dp[i]:
                dp[i] = t
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            return


if __name__ == '__main__':
    main()


Measured memory_bytes: 5740