akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

factorial = [1]
for i in range(1, N+1):
	factorial.append(factorial[i-1] * i % mod)

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * (N+1)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(N-1, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

for i in range(1, K+1):
	if N-K >= i-1:
		print((C(K-1, i-1)*C(N-K+1, i))%mod)
	else:
		print(0)


Measured memory_bytes: 5576
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

// aoj DPL_2_A Traveling Salesman Problem
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 

		int v = sc.nextInt();
		int e = sc.nextInt();

		@SuppressWarnings("unchecked")
		List<Edge>[] edges = new List[v];
		for (int i = 0; i < v; i++) {
			edges[i] = new ArrayList<Edge>();
		}

		for (int i = 0; i < e; i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			int d = sc.nextInt();
			edges[s].add(new Edge(s, t, d));
		}

		final int INF = Integer.MAX_VALUE;
		int min = INF;
		for (int s = 0; s < v; s++) {
			int[][] dp = new int[v][1 << v];
			for (int[] tmp : dp) {
				Arrays.fill(tmp, INF);
			}
			dp[s][1 << s] = 0;
			
			for (int S = 1; S < 1 << v; S++) {
				for (int j = 0; j < v; j++) {
					if ((S & (1 << j)) == 0 || dp[j][S] == INF) {
						continue;
					}

					for (Edge i : edges[j]) {
						if ((S & (1 << i.v)) != 0) {
							continue;
						}
						
						dp[i.v][S | (1 << i.v)] = Math.min(dp[i.v][S | (1 << i.v)], dp[j][S] + i.w);
					}
				}
			}
			
			for (int i = 0; i < v; i++) {
				for (Edge j : edges[i]) {
					if (j.v != s || j.w == INF || dp[i][(1 << v) - 1] == INF) {
						continue;
					}

					min = Math.min(min, dp[i][(1 << v) - 1] + j.w);
				}
			}
		}

		if (min != INF) {
			System.out.println(min);
		} else {
			System.out.println(-1);
		}

		sc.close();
	}

	private static class Edge {
//		int u; // from
		int v; // to
		int w; // cost
		
		Edge(int u, int v, int w) {
//			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
}

Measured memory_bytes: 61192
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int D, N; cin >> D >> N;
    int n;
    n = pow(100, D);
    if (N != 100){
        cout << n * N << endl;
    }else{
        cout << (N + 1) * n << endl;
    }
    
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 100005

void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}
LL GCD(LL a,LL b){LL c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int POW(int a,int n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return (int)ans;}
int icmp(const void* a,const void* b){return *(int*)a-*(int*)b;}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int scmp(const void* a,const void* b){return strcmp(*(char**)a,*(char**)b);}
LL fac[NUM],finv[NUM],inv[NUM];
void comi(){int i;fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fac[i]=fac[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
int com(int n,int k){if(n<k||n<0||k<0)return 0;return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;}

int main(){
  LL N,i,ans=0;
  scanf("%lld",&N);
	if(N%2==0){
		N/=2;
		while(N>0)ans+=N/=5;
	}
	/*else{
		N+=5;
		N/=10;
		while(N>0){
			ans+=N;
			N+=2;
			N/=5;
		}
	}*/

	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC043A
{
	class Program
	{
		static void Main(string[] args)
		{
			int n, s;
			n = int.Parse(Console.ReadLine());
			s = 0;

			for (int i = 1; i <= n; i++)
				s = s + i;
			Console.WriteLine(s);

			Console.ReadKey();		



		}
	}
}

Measured memory_bytes: 11092
while (True):
    a,op,b = input().split()
    if op == '+':
        print(int(a)+int(b))
    elif op == '-':
        print(int(a)-int(b))
    elif op == '*':
        print(int(a)*int(b))
    elif op == '/':
        print(int(a)//int(b))
    elif op =='?':
        break


Measured memory_bytes: 5596
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int D;
    cin >> D;
    int repeat = 25 - D;
    cout << "Christmas";
    while(repeat--)
        cout << " Eve";
    return 0;
}




Measured memory_bytes: 256
import bisect
n = int(input())
A = []
for i in range(n):
    num  = int(input())
    if A == []:
        A.append(num)
    elif num > A[-1]:
        A.append(num)
    else:
        j = bisect.bisect_left(A, num)
        A[j] = num
print(len(A))

Measured memory_bytes: 11564
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const ll INF64 = 3e18;
const double INFD = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
template <typename T>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int MAXN = 500005;
const int MAXV = 10000005;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE = 1;
ll fact[MAXN];
void extgcd(ll a, ll b, ll& d, ll& x, ll& y) {
    if (!b) {
        d = a;
        x = 1;
        y = 0;
    } else {
        extgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

inline ll getInv(ll x, ll mod) {
    ll g, a, b;
    extgcd(x, mod, g, a, b);
    return (a % mod + mod) % mod;
}
int fastExp(ll x, ll p, int mod) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans = ans * x % mod;
        x = x * x % mod;
        p >>= 1;
    }
    return ans;
}

ll choose(int n, int k) {
    if (n < k) return 0;
    return fact[n] * getInv(fact[k] * fact[n - k] % MOD, MOD) % MOD;
}
ll P(int n, int k) {
    if (n < k) return 0;
    return fact[n] * getInv(fact[n - k], MOD) % MOD;
}

int main() {
#ifdef LOCALLL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    fact[0] = 1;
    for (int i = 1; i <= m; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
    ll ans = P(m, n) * P(m, n) % MOD;
    for (int i = 1; i <= n; i++) {
        ll c = P(m, i) * choose(n, i) % MOD;
        ll p = P(m - i, n - i) * P(m - i, n - i) % MOD;
        ans += ((i & 1) ? -1LL : 1LL) * p * c % MOD;
        ans = (ans % MOD + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 7604
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;


int main(){
	ll x,y; cin >> x >> y;

    if(abs(x-y)>1){
        cout << "Alice" << endl;
    }
    else{
    	cout << "Brown" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int n,b,f,r,v;
    int building[4][3][10] = {};
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> b;
        cin >> f;
        cin >> r;
        cin >> v;
        building[b-1][f-1][r-1] += v;
    }

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            cout << " ";
            for (int k = 0; k < 10 - 1; k++) {
                cout << building[i][j][k] << " ";
            }
            cout << building[i][j][10-1] << endl;
        }
        if( i < 3 ) {
            cout << "####################" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
void solve(){
	ll n;
	cin >> n;
	vector<ll> a(n), dp(61, 0);
	for(int i=0;i<n;i++) cin >> a[i];
	string s;
    cin >> s;
    for(int i=n-1;i>=0;i--){
    	for(int j=60;j>=0;j--) if(a[i] >> j & 1){
    	    if(s[i] == '1' || dp[j] >> j & 1) a[i] ^= dp[j];
    	    else dp[j] = a[i], j = -1;
        }
        if(s[i] == '1' && a[i]){
        	cout << 1 << endl;
        	return;
        }
    }
    cout << 0 << endl;
    return;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}


Measured memory_bytes: 3608
#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;
#define int long long
#define pbds tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define mod 1000000007
#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n"                   \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x) \
  int x;     \
  cin >> x;  \
  while (x--)

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int t = 0;
  while (1)
  {
    if (a <= 0)
    {
      cout << "No";
      return 0;
    }
    if (c <= 0)
    {
      cout << "Yes";
      return 0;
    }
    if (t % 2)
      a -= d;
    else
    {
      c -= b;
    }
    t++;
  }

  return 0;
}

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

using namespace std;

typedef long long ll;
// typedef pair<ll, ll> P;
typedef pair<string, int> P;
typedef pair<P, int> P2;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int N;
  cin >> N;
  vector<P2> vc;
  REP(i, N) {
    string s;
    int p;
    cin >> s >> p;
    p *= -1;
    vc.push_back(make_pair(make_pair(s, p), i + 1));
  }
  sort(ALL(vc));
  REP(i, vc.size()) cout << vc[i].second << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define debug(x) cerr << #x << " " << x << endl;
#define debug_p(x) cerr << #x << " [" << x.fi << " " << x.se << "]"<<endl;
#define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
#define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.fi << " " << ioi.se << ']'; cerr << endl;}
#define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
#define gen_clock(x) ll x = clock(); cerr << "Clock " << #x << " created" << endl;
#define check_clock(x) cerr << "Time spent in " << #x << ": " << (double)(clock() - x)/CLOCKS_PER_SEC << endl; x = clock();
#define reset_clock(x) x = clock()

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

void solve()
{
	long double a,b,h,m;
	cin>>a>>b>>h>>m;
	h*=5;
	h+=m/12;
	cout<<fixed;
	//cout<<set_precision(9);
	long double angleh,anglem,ans,pi=acosl(0)*2;
	//cout<<angle<<'\n';
	angleh=h/30.0*pi;
	anglem=m/30.0*pi;
	if(angleh>=anglem)
	angleh-=anglem;
	else
	angleh=anglem-angleh;
	ans=a*a+b*b-cosl(angleh)*2*a*b;
	ans=sqrtl(ans);
	cout<<setprecision(10)<<ans<<'\n';
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 4184
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//みんなどんだけ頭いいの

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


	int N = 0;
	char c;
	while ((c = getchar_unlocked()) >= '0') N = N * 10 + c - '0';

	int L = 0;
	ll kotae = 1;
	ll mod = 1e9 + 7;
	rep1(i, N) kotae = kotae * i % mod;
	rep(i, N + N) {
		if (getchar_unlocked() == 'B' ^ (i & 1)) {
			L++;
		}
		else {
			kotae = kotae * L % mod;
			L--;
		}
	}

	if (L == 0) printf("%ld", kotae);
	else printf("0");

	Would you please return 0;
}

Measured memory_bytes: 128
import Data.List

sum' [] [] = []
sum' (x:xs) (y:ys) = (x+y):(sum' xs ys)

sumup' s [] = s
sumup' s (x:xs) = sumup' (sum' s x) xs

sumup (x:xs) = sumup' x xs

ans' :: [[Int]] -> [Int]
ans' x =
  let s = sumup x
      z = zip [1..] s
      s'= sortBy (\(a,b) (c,d) -> compare d b) z
  in
    map fst s'

ans [] = []
ans ([0,0]:_) = []
ans ([n,m]:x) = 
  let d = take n x
      r = drop n x
  in
    (ans' d):(ans r)

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = ans i
  mapM_ putStrLn $ map unwords $ map (map show) o

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

int main()
{
  int N, K;
  cin >> N >> K;
  vector< int > a(N);
  for (int i = 0; i < N; ++i) cin >> a[i];
  sort(a.begin(), a.end(), [](const int x, const int y) { return x > y; } );
  int sum = 0;
  for (int i = 0; i < K; ++i) sum += a[i];
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct RMQ{
  int n;
  vector<vector<int>> dat;
  RMQ(){}
  RMQ(int n_,int* c){init(n_,c);}
  void init(int n_,int *c){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1);
    construct(n_,c);
  }
  void construct(int n_,int *c){
    for(int i=0;i<n_;i++) dat[n-1+i].push_back(c[i]);
    for(int i=n-2;i>=0;i--){
      for(int j:dat[i*2+1]) dat[i].push_back(j);
      for(int j:dat[i*2+2]) dat[i].push_back(j);
      sort(dat[i].begin(),dat[i].end());
    }
  }
  int query(int a,int b,int x,int k,int l,int r){
    if(r<=a||b<=l) return 0;
    if(a<=l&&r<=b){
      int res=0;
      auto latte=lower_bound(dat[k].begin(),dat[k].end(),x);
      res=dat[k].end()-latte;
      //cout<<res<<endl;
      return res;
    }
    int vl=query(a,b,x,k*2+1,l,(l+r)/2);
    int vr=query(a,b,x,k*2+2,(l+r)/2,r);
    return vl+vr;
  }
  int query(int a,int b,int x){
    return query(a,b,x,0,0,n);
  }
};
signed main(){
  int n,k;
  cin>>n>>k;
  int a[n],c[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int sum=0;
  for(int i=0;i<n;i++){
    sum+=a[i];
    c[i]=sum-k*(i+1);
  }
  RMQ rmq(n,c);
  int ans=0,tmp=0;
  for(int i=0;i<n;i++){
    ans+=rmq.query(i,n,tmp);
    tmp+=a[i]-k;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 54004
n = gets.chomp
k = gets.to_i
digit = n.length
dp = Array.new(digit+1).map{Array.new(2).map{Array.new(k+1,0)}}
dp[0][0][0] = 1
dp[0][1][0] = 0
1.upto(digit) do |i|
  (k+1).times do |j|
    if j == 0
      dp[i][0][j] = n[i-1] == "0" ? dp[i-1][0][j] : 0
      dp[i][1][j] = dp[i-1][1][j] + dp[i-1][0][j]
    else
      dp[i][0][j] = n[i-1] == "0" ? dp[i-1][0][j] : dp[i-1][0][j-1]
      if n[i-1] == "0"
        dp[i][1][j] = dp[i-1][1][j-1] * 9 + dp[i-1][1][j]
      else
        dp[i][1][j] = dp[i-1][1][j-1] * 9 + dp[i-1][1][j] + dp[i-1][0][j-1] * (n[i-1].to_i - 1) + dp[i-1][0][j]
      end
    end
  end
end
p dp[digit][0][k] + dp[digit][1][k]

Measured memory_bytes: 1788
#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 <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
using namespace std;
#define eps 0.000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 65536*16
#define REP(i,n) for(long long i = 0;i < n;++i)
long long dp[5000][5000] = {};
int main() {
	string s;
	cin >> s;
	long long blue = 0;
	long long red = 0;
	dp[0][0] = 1;
	for (int i = 0; i < 2*s.length(); ++i) {
		if (i < s.length()) {
			if (s[i] == '0') red += 2;
			else if (s[i] == '1') {
				red++;
				blue++;
			}
			else {
				blue += 2;
			}
		}
		for (int blue_got = 0;blue_got <= i; ++blue_got) {
			int red_got = i - blue_got;
			if (blue_got == blue) {
				dp[blue_got][red_got + 1] += dp[blue_got][red_got];
				dp[blue_got][red_got + 1] %= MOD;
			}
			else if (red_got == red) {
				dp[blue_got + 1][red_got] += dp[blue_got][red_got];
				dp[blue_got + 1][red_got] %= MOD;
			}
			else {
				dp[blue_got + 1][red_got] += dp[blue_got][red_got];
				dp[blue_got + 1][red_got] %= MOD;
				dp[blue_got][red_got + 1] += dp[blue_got][red_got];
				dp[blue_got][red_got + 1] %= MOD;
			}
		}
	}
	cout << dp[blue][red] << endl;
	return 0;
}

Measured memory_bytes: 157824
from collections import defaultdict
from heapq import heappush, heappop

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        #u = heappop(q)
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                #heappush(q, v[0])
                q.append(v[0])


    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Measured memory_bytes: 106796
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

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

const int MOD=1000000007;
int INF=100100100100100;

signed main(){
  string s,t;cin>>s>>t;
  int n=s.length()+t.length();
  rep(i,n){
    if(i%2==0)cout<<s[i/2];
    else cout<<t[i/2];
  }
  cout<<endl;
  return 0;
}

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

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
// #define pb push_back
#define ll long long
#define endl "\n"
using namespace std;



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









Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string S;
    cin >> S;

    int N = S.length();

    vector<string> s(N+1);

    for (int i = 0; i < N+1; i++){
        s.at(i) = S.substr(i, 1);
    }

    sort(s.begin(), s.end());

    int count = 0;
    for (int i = 0; i < N; i++){
        if (s.at(i) == s.at(i+1)){
            count++;
        }
    }

    if (count > 0){
        cout << "no" << endl;
    }
    else {
        cout << "yes" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
 int a,b;
 int keta,sum;
 while(scanf("%d %d",&a,&b)!=EOF)
 {
   for(sum=a+b,keta=1;sum/10!=0;sum/=10)keta++;
   printf("%d\n",keta);
 }
 return 0;
}

Measured memory_bytes: 600
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::io::Read;
use std::io::{stdout, BufWriter, Write};
 
fn main() {
    let mut buf = String::new();
    
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
 
    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
 
    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();
 
    
    let n: usize = iter.next().unwrap().parse().unwrap();
    let k: usize = iter.next().unwrap().parse().unwrap();
    
    let ans:usize  = (0..n).map(|_| {
        iter.next().unwrap().parse().unwrap()
    }).filter(|x: &usize| *x >= k).map(|_| 1).sum();
    
    //println!("{:?}",colors);
    println!("{}", ans);
}

Measured memory_bytes: 4352
def linearSearch(key, list, N):
    l = list + [key]
    i = 0
    while l[i] != key:
        i += 1
    return int(i != N)


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([linearSearch(key, arr1, N1) for key in arr2]))



Measured memory_bytes: 6552
///                                                     ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
#include <bits/stdc++.h>
#define off  exit( 0 )
#define cn   continue
#define rt   return
#define sc   scanf
#define pr   printf
#define pb   push_back
#define pf   push_front
#define p_f  pop_front
#define p_b  pop_back
#define ff   first
#define ss   second
#define vec  vector
#define gcd  __gcd
#define pi   acos( -1 )
#define ll   long long
#define ld   long double
#define N    100256
#define M    1000000007
#define I    1000000000000000000
#define pdd  pair < ld, ld >
#define pll  pair < ll, ll >
#define pii  pair < int, int >
#define rep( a, b, c, d )  for( int a = b; a <= c; a += d )
#define rvv( a, b, c, d )  for( int a = b; a >= c; a -= d )
#define en                 printf( "\n" )
#define sqr( a )           a * a
#define all( c )           c.begin(), c.end()
#define srt( c )           sort( all( c ) )
#define rev( c )           reverse( all( c ) )
#define srtr( c )          sort( c.rbegin(), c.rend() )
#define numcounts          __builtin_popcount
#define mxn( x, y, z )     max( x, min( y, z ) )
#define mnx( x, y, z )     min( x, max( y, z ) )
const int dx[ ] = { 1, -1, 0, 0 };
const int dy[ ] = { 0, 0, -1, 1 };
using namespace std;
ll ttt = 1;
ll n, m, dp[N], ans, x, y;
vector < ll > g[N];

ll dfs( ll v )
{
    if( dp[v] != -1 )rt dp[v];
    dp[v] = 0;
    for( ll i: g[v] )
        dp[v] = max( dp[v], dfs(i) + 1 );
    ans = max( ans, dp[v] );
    rt dp[v];
}

void solve()
{
    cin >> n >> m;
    for( int i = 0; i < m; i ++ )
    {
        cin >> x >> y;
        g[x].pb(y);
    }
    memset( dp, -1, sizeof dp );
    for( int i = 1; i <= n; i ++ )
        dfs(i);
    cout << ans;
}
int main()
{
    //sc( "%I64d", &ttt );
    for( int i = 0; i < ttt; i ++ )
        solve();
}














Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
int main(){long long int n,k,ans=0,mx,mn,m=1000000007,i;
cin>>n>>k;
for(i=k;i<=n+1;i++){
    mn=(i*(i-1))/2;
    mx=((2*n-i+1)*i)/2;
    ans+=mx-mn+1;
    ans%=m;
    //cout<<mn<<" "<<mx<<" ";
}cout<<ans;
    return 0;}

Measured memory_bytes: 3616
//AtCoder 5329 (ABC 153 E) 
//https://www.luogu.com.cn/problem/AT5329 
#include<bits/stdc++.h>
using namespace std;
int f[1010][20010],a[1010],b[1010];
int main()
{
	int h,n;cin>>h>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int j=1;j<=20000;j++)f[0][j] = 1e9;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=20000;j++){
			if(j>=a[i])f[i][j] = min(f[i-1][j],f[i][j-a[i]]+b[i]);
			else f[i][j] = f[i-1][j];
		}
	}
	int ans = 1e9;
	for(int j=h;j<=20000;j++)
		ans = min(ans,f[n][j]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 78464
#include<bits/stdc++.h>
using namespace std;
#define bitCount(num)  __builtin_popcount(num)
#define pb push_back
#define ll long long
#define bye return 0;
#define f(i,a,b) for( long long i=a;i<b;i++)
#define testCases long long t;cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define newLine <<"\n"
#define all(x) (x).begin(), (x).end()
#define vll vector<long long>

// void memo(int currDay, int prvsJob, vector<vector<int>> p, vector<vector<int>> dp)
// {
	
// 	for(int i=0;i<3;i++)
// 	{
// 		if(i==prvsJob) continue;
// 		if(currDay==n-1) 
// 		{
// 			dp[currDay][prvsJob]=p[currDay][prvsJob];
// 			continue;
// 		}
// 		memo(currDay+1, i, p,dp);
		
// 	}
	
// }




int main()
{
    fast
   int n;
   cin>>n;
   vector<vector<int>> p(n,vector<int>(3,0));
   f(i,0,n)
   {
   int a ,b,c;
   cin>>a>>b>>c;
   p[i][0]=a;
   p[i][1]=b;
   p[i][2]=c;
   }
int ans=0;
vector<vector<int>> dp(n,vector<int>(3,0));
     dp=p;



// for(int i=0;i<3;i++)
// {
//   memo(i+1,i,p,dp,p[0][i]);
// }





for(int i=n-2;i>=0;i--)
{
	for(int j=0;j<3;j++)
	{
	int max_=INT_MIN;
       for(int k=0;k<3;k++)
       {
         if(k==j) continue;
         max_=max(max_,dp[i+1][k]);
       }
     dp[i][j]+=max_;
	}
}
ans=max(max(dp[0][0],dp[0][1]),dp[0][2]);
cout<<ans<<endl;

    bye
}

Measured memory_bytes: 14264
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int w;

int main(){
	while (cin >> w&&w != -1){
		int sum = 1150;
		if (w > 30){
			sum += (w - 30) * 160;
		}
		if (w > 20){
			sum += min(10, w - 20) * 140;
		}
		if (w > 10){
			sum += min(10, w - 10) * 125;
		}
		cout << 4280 - sum << endl;
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;




int main(){
    int N,A,B;
    cin >>N>>A>>B;
    string S;
    cin >> S;
    string y = "Yes";
    string n = "No";
    int a=0;
    int rank =0;
    for(int i= 0;i<S.size();i++){
        if(S[i] == 'a'){
            if(a < A+B){
                cout<<y<<endl;
                a++;
            }
            else
                cout<<n<<endl;
        }
        if(S[i] == 'b'){
            if(a < A+B && rank < B){
                cout<<y<<endl;
                a++;
                rank++;
            }
            else
                cout<<n<<endl;
            
        }
        if(S[i] == 'c'){
            cout<<n<<endl;
        }
        
        
        
    }
    
    
    return 0;
}


Measured memory_bytes: 896
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <stdio.h>
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// tree<key, mapped = null_type, cmp = less<key>, rb_tree_tag, tree_order_statistics_node_update> name; order_of_key find_by_order

using namespace std;

#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fs first
#define sc second
#define abs(a) ((a) < 0 ? -(a) : (a))
#define sqr(a) ((a) * (a))

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

inline pair<pair<bool, bool>, pair<string, bool> > useinout();

#ifdef SOL
double starttime;
#endif

void initialization() {
#ifdef SOL
	starttime = 1000. * clock() / CLOCKS_PER_SEC;
	if (useinout().fs.fs)
		freopen("input.txt", "r", stdin);
	if (useinout().fs.sc)
		freopen("output.txt", "w", stdout);
#else
	srand(__rdtsc());
	const string file = useinout().sc.fs;
	if (!file.empty()) {
		freopen((file + ".in").c_str(), "r", stdin);
		freopen((file + ".out").c_str(), "w", stdout);
	} else
	if(useinout().sc.sc) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
#endif
}

int solution();

void finish(int exitval) {
	fflush(stdout);
#ifdef SOL
	fprintf(stderr, "\n-----------------\nexit value: %d\ntime: %.3lf ms\n-----------------\n", exitval, 1000. * clock() / CLOCKS_PER_SEC - starttime);
#endif
}

int main() {
	initialization();
	finish(solution());
	return (0);
}

const double eps = 1e-9;
const int mod = (int) 1e+9 + 7;
const double pi = acos(-1.);
const int maxn = 100100;

int n, c1, c2;
vector<int> vc, rb[maxn];
int c[maxn];

bool dfs(int u, int p = -1) {
	vc.pb(u);
	if(u == n - 1) {
		return(1);
	}
	for(int v : rb[u]) {
		if(v != p)
			if(dfs(v, u)) {
				return(1);
			}
	}
	vc.ppb();
	return(0);
}

void dfs2(int u) {
	for(int v : rb[u]) {
		if(c[v] == 0) {
			if(c[u] == 1)c1++; else c2++;
			c[v] = c[u];
			dfs2(v);
		}
	}
}

int solution() {

	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		rb[u].pb(v);
		rb[v].pb(u);
	}

	dfs(0);

	for(int i = 0; i < (int) (vc.size() - vc.size() / 2); i++) {
		c[vc[i]] = 1;
		c1++;
	}
	for(int i = (int) (vc.size() - vc.size() / 2); i < (int)vc.size(); i++) {
		c[vc[i]] = 2;
		c2++;
	}

	for(int i = 0; i < n; i++) {
		if(c[i] != 0) {
			dfs2(i);
		}
	}
	if(c1 > c2) {
		printf("Fennec");
	} else {
		printf("Snuke");
	}

	return (0);
}

inline pair<pair<bool, bool>, pair<string, bool> > useinout() {
	return (mp(mp(0, 0), mp("", 0)));
}

//by Andrey Kim


Measured memory_bytes: 9208
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  int n;
  cin >> n;
  vi d(n);
  for (int i = 0; i < n-1; ++i) {
    int a,b,c;
    cin >> a >> b >> c;
    d[a] ^= c;
    d[b] ^= c;
  }
  vi c(16);
  for (int i = 0; i < n; ++i) c[d[i]]++;
  int s = 0;
  vi a(1 << 16, 1e9);
  a[0] = 0;
  for (int i = 1; i < 16; ++i) {
    if (c[i]) cerr << i << ' ' << c[i] << endl;
    s += c[i] / 2;
    if (c[i] % 2 == 0) continue;
    vi na(a.size(), 1e9);
    int B = 1 << i;
    for (int mask = 0; mask < a.size(); ++mask) {
      if (mask & B) {
        na[mask ^ B] = min(na[mask ^ B], a[mask] + 1);
      } else {
        na[mask ^ B] = min(na[mask ^ B], a[mask]);
      }
      for (int b = 1; b < 16; ++b) if (mask & (1 << b)) {
        int xr = (1 << (b ^ i));
        int nmask = mask ^ (1 << b) ^ xr;
        if (mask & xr) {
          na[nmask] = min(na[nmask], a[mask] + 2);
        } else {
          na[nmask] = min(na[nmask], a[mask] + 1);
        }
//        if (nmask == 0 && a[mask] == 0) cerr << i << ' ' << b << ' ' << mask << ' ' << a[mask] << endl;
      }
    }
    a.swap(na);
    cerr << a[2] << ' ' << a[8] << ' ' << a[0] << endl;
  }
  cout << s + min(a[0], a[1]) << endl;
  return 0;
}

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

#mapの使い方
#map(functon,sequence_object)
#第一引数が関数第二引数がシーケンス
#mapを使うと一つの要素に対する処理をリスト全体に対して行ってくれる
#input.splitではinput（入力）をスペース区切りのリストにしている。その要素に対してmapで数字をintに変換

l = list(map(int, input().split()))

#降順にソート
l.sort(reverse=True)

#スライスの使い方l(strt:stop:step)
#strt,stopは0から始まる
print(sum(l[0::2]) - sum(l[1::2]))



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

int main(void) {
    int a1, a2, a3;

    cin >> a1 >> a2 >> a3;

    string str = (a1 + a2 + a3) >= 22 ? "bust" : "win";
    cout << str << endl;

    return 0;
}

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

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

    bool ans = false;
    for(int i=0; i<3; i++){
        if(s.at(i) == s.at(i+1)) ans = true;
    }
    if(ans) cout << "Bad" << endl;
    if(!ans) cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
a = int(S[0:2])
b = int(S[2:4])
if 13<=a<=99 and 1<=b<=12 :
    print('YYMM')
elif a == 0 and 1<=b<=12:
    print('YYMM')
elif 1<=a<=12 and 13<=b<=99:
    print('MMYY')
elif 1<=a<=12 and b ==0:
    print('MMYY')
elif 1<=a<=12 and 1<=b<=12:
    print('AMBIGUOUS')

else:
    print('NA')


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

int main () {
	int N;
	cin >> N;
	long *A = new long[N];
	long *B = new long[N];
	long a, b, anext;
	for (int i=0; i<N+1; ++i) {
		cin >> A[i];
	}
	for (int i=0; i<N; ++i) {
		cin >> B[i];
	}

	long long sum = 0;
	anext = A[0];
	for (int i=0; i<N; ++i) {
		b = B[i];
		a = anext;
		anext = A[i+1];
		if (b <= a) {
			sum += b;
		} else {
			if (b > a+anext) {
				sum += a+anext;
				anext = 0;
			} else {
				sum += b;
				anext -= b-a;
			}
		}
		//cout << b << " " << a << " "<< anext << endl;
	}
	cout << sum << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll; ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);
ll fac(ll x){if(x==0) return 1;  return x*fac(x-1);}

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

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

  int a=0, b=0;
  int cnt=0;

  scanf("%d %d", &a, &b);

  if(a==1){
    cnt=1;
    printf("%d", cnt);
    return 0;
  }

  if(b>=a){
    cnt=a;
  }else{
    cnt=a-1;
  }

  printf("%d", cnt);

  return 0;
}


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

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); }

#ifdef LOCAL
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0) cout
#endif

// ********************** CODE ********************** //

const int N = 207;
const LL INF = 1e15 + 7;

int n, m, r;
LL d[N][N];
vector < int > V;

int main()
{
    _upgrade
    cin >> n >> m >> r;
    for(int i = 0; i < r; i++)
    {
        int x; cin >> x;
        V.push_back(x);
    }
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            d[i][j] = d[j][i] = INF;
    for(int i = 0; i < m; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        d[a][b] = d[b][a] = c;
    }
    for(int k = 1; k <= n; k++)
        for(int v = 1; v <= n; v++)
            for(int u = 1; u <= n; u++)
                if(d[v][u] > d[v][k] + d[k][u])
                    d[v][u] = d[v][k] + d[k][u];
    LL mn = INF;
    sort(all(V));
    do
    {
        LL res = 0;
        for(int i = 1; i < r; i++)
        {
            res += d[V[i - 1]][V[i]];
        }
        mn = min(mn, res);
    } while(next_permutation(V.begin(), V.end()));
    cout << mn << "\n";
    return 0;
}


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

int  main(){
  cout<<"Christmas";
  int d; cin>>d;
  if(d<25)cout<<" Eve";
  if(d<24)cout<<" Eve";
  if(d<23)cout<<" Eve";

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    
#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl
    
using namespace std;
    
typedef long long ll;
typedef pair<ll, ll> Pll;

bool used[100000];
int n,m;
vector< pair<int, ll> > G[100000];
set<Pll> f[100000]; // at+b の形の1次式を (a, b) の形で保持する
    
int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int x,y;
    ll cost;
    rep(m){
        cin >> x >> y >> cost;
        x--; y--;
        G[x].emplace_back(y, cost);
        G[y].emplace_back(x, cost);
    }

    queue<int> que;
    que.push(0);
    f[0].insert(Pll(1, 0));
    used[0] = true;
    ll a,b;
    while(!que.empty()){
        int node = que.front(); que.pop();
        a = (f[node].begin())->first;
        b = (f[node].begin())->second;
        for(pair<int, ll> p: G[node]){
            int child = p.first;
            cost = p.second;
            ll aa = -a, bb = cost - b;
            f[child].insert(Pll(aa, bb));
            if(!used[child]){
                que.push(child);
                used[child] = true;
            }
        }
    }

    ll lower_lim = 0, upper_lim = LLONG_MAX;
    ll t = LLONG_MAX;
    rep(n){
        int fisize = int(f[i].size());
        set<Pll>::iterator itr = f[i].begin();
        Pll f0 = *itr;
        ++itr;
        Pll f1 = *itr;
        if(fisize >= 3){
            cout << 0 << endl;
            return 0;
        }else if(fisize == 2){
            if(f0.first * f1.first < 0){
                if((f1.second - f0.second) % 2 != 0){
                    cout << 0 << endl;
                    return 0;
                }
                ll tt = (f1.second - f0.second) / (f0.first - f1.first);
                if(t != LLONG_MAX && t != tt){
                    cout << 0 << endl;
                    return 0;
                }
                t = tt;
            }else{
                cout << 0 << endl;
                return 0;
            }
        }else{
            if(f0.first > 0){
                lower_lim = max(lower_lim, -f0.second);
            }else{
                upper_lim = min(upper_lim, f0.second);
            }
        }
    }

    if(t != LLONG_MAX){
        if(t > 0 && upper_lim > t && t > lower_lim){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }else{
        if(upper_lim <= lower_lim || upper_lim <= 0){
            cout << 0 << endl;
        }else{
            cout << upper_lim - lower_lim - 1LL << endl;
        }
    }
}

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

int main()
{
    ll n,t,a,b,c,d,e,p,q,cnt=0;
    map<ll,ll>mp;
    vector<ll>vec;
    string s,s1,s2;
    cin>>a>>b>>c>>d;
    while(1){
        c-=b;
        if(c<=0){
            break;
        }
        a-=d;
        if(a<=0){
            break;
        }
    }


    //cout<<a<<" "<<c<<endl;
    if(a>=c){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }



}


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


int main(void) {
  ll x, k, d;
  cin >> x >> k >> d;
  x = abs(x);
  ll ans = 0;
  if (x/d > k) {
    ans = x - d*k;
  } else {
    ll e = x/d;
    k -= e;
    x -= e*d;

    if (k % 2 == 1) x = abs(x-d);
    ans = x;
  }

  cout << ans << endl;

  
  return 0;
}

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

int main() {
  int a, b;
  std::string str;
  std::cin >> a >> b;
  if (a < b) {
    for (int i = 0; i < b; i++)
      str.push_back((char)('0' + a));
  } else {
    for (int i = 0; i < a; i++)
      str.push_back((char)('0' + b));
  }
  std::cout << str << std::endl;
}

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

using namespace std;

const int N = 2e5 + 5, INF = 1e9 + 5;

int arr[N], dp[N];

int main(){
	int n, k;	scanf("%d%d",&n,&k);
	for(int i = 1; i <= n; i++)	scanf("%d",&arr[i]);
	for(int i = 2; i <= n; i++){
		dp[i] = INF;
		for(int j = 1; j <= k && i - j >= 1; j++)
			dp[i] = min(dp[i], dp[i - j] + abs(arr[i] - arr[i - j]));
	}
	cout << dp[n] << "\n";
}


Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i += 2)
    {
        int tmp = 0;
        for(int j = 1; j <= i; j++)
        {
            if(i % j == 0) tmp++;
        }
        if(tmp == 8) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#59c
n = int(input())
a_list = [int(e) for e in input().split()]

#print("#####################################")

first_minus_pettern_ans = 0
first_plus_pettern_ans = 0
first_minus_pettern_cumsum = 0
first_plus_pettern_cumsum = 0

for i in range(n): #n<10**5
    
    first_minus_pettern_cumsum += a_list[i]
    first_plus_pettern_cumsum += a_list[i]
    #print(i,":",a_list[i],"  ",first_minus_pettern_cumsum,"/",first_plus_pettern_cumsum)
    
    if i%2 == 0:
        if first_minus_pettern_cumsum >=0:
            #print("初項が負で奇数項なのに正!")
            first_minus_pettern_ans += abs(first_minus_pettern_cumsum) + 1
            first_minus_pettern_cumsum -= abs(first_minus_pettern_cumsum) + 1
        if first_plus_pettern_cumsum <=0:
            #print("初項が正で奇数項なのに負!")
            first_plus_pettern_ans += abs(first_plus_pettern_cumsum) + 1
            first_plus_pettern_cumsum += abs(first_plus_pettern_cumsum) + 1
        
    if i%2 == 1:
        if first_plus_pettern_cumsum >=0:
            #print("初項が正で偶数項なのに正!",)
            first_plus_pettern_ans += abs(first_plus_pettern_cumsum) + 1
            first_plus_pettern_cumsum -= abs(first_plus_pettern_cumsum) + 1
        if first_minus_pettern_cumsum <=0:
            #print("初項が負で偶数項なのに負!")
            first_minus_pettern_ans += abs(first_minus_pettern_cumsum) + 1
            first_minus_pettern_cumsum += abs(first_minus_pettern_cumsum) + 1
            
    #print(i,":",a_list[i],"  ",first_minus_pettern_cumsum,"/",first_plus_pettern_cumsum)
            
print(min(first_plus_pettern_ans,first_minus_pettern_ans))

Measured memory_bytes: 14468
mod = 998244353

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

ans = 0


class Mint(object):
    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)


mint = Mint()
mint.cmb_prep(N-1, mod)

for k in range(K+1):
    ans += (mint.cmb(N-1, k, mod) * M * pow(M-1, N-k-1, mod)) % mod

print(ans % mod)


Measured memory_bytes: 117924
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
		   int a,b;
           cin>>a>>b;
           if((a+b)%3==0||a%3==0||b%3==0)cout<<"Possible"<<endl;
           else cout<<"Impossible"<<endl;
}

Measured memory_bytes: 3620
// package app;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);

        final int a = sc.nextInt();
        final int b = sc.nextInt();

        int result = a <= b ? a : a - 1;

        System.out.println(result);

    }
}

Measured memory_bytes: 23764
#include <iostream>
#define maxn 200005

using namespace std;

struct edge{
    int to,next;
}edge[maxn*2];
int head[maxn];int top = 1;
int n;

void add(int s,int t)
{
    edge[top].next = head[s];
    edge[top].to = t;
    head[s] = top;
    top++;
}

int maxx,ii;
bool vis[maxn];
void DFS(int s,int step)
{
    if(step > maxx){
        maxx = step;
        ii = s;
    }
    vis[s] = 1;
    for(int i = head[s];i;i = edge[i].next)
        if(!vis[edge[i].to])DFS(edge[i].to,step+1);
}

int main()
{
    int a,b;
    cin >> n;
    for(int i = 1;i < n;i++)
    {
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    DFS(1,0);
    for(int i = 0;i <= n;i++)
        vis[i] = 0;
    DFS(ii,0);
    maxx++;
    if(maxx % 3 == 2)cout << "Second" << endl;
    else cout << "First" << endl;
    return 0;
}


Measured memory_bytes: 10624