akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
const int N = 100000 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int main()
{
    int n;
    scanf("%d", &n);
    int cnt2 = 0, cnt4 = 0, sb = 0;
    for(int i = 1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] % 4 == 0)
            cnt4++;
        else if(a[i] %2 == 0)
            cnt2++;
            else sb ++;
    }
    int ok  = 0;
    if(cnt4 >= sb || (sb == cnt4+1 && cnt2 == 0))
        puts("Yes");
    else puts("No");
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

int const INF = 1<<28;

int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    int H, W; cin >> H >> W;
    vector<vector<char> > a(H+2, vector<char>(W+2));
    vector<int> minX(128, INF), minY(128, INF);
    vector<int> maxX(128, -INF), maxY(128, -INF);
    vector<int> vec;
    for(int i=0; i<H; i++) {
      for(int j=0; j<W; j++) {
        cin >> a[i][j];
        if(!isalpha(a[i][j])) continue;
        int b = a[i][j];
        vec.push_back(b);
        maxX[b] = max(maxX[b], j);
        maxY[b] = max(maxY[b], i);
        minX[b] = min(minX[b], j);
        minY[b] = min(minY[b], i);
      }
    }
    if(vec.empty()) {
      cout << "SAFE" << endl;
      goto EXIT;
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    
    do {
      bool good = true;
      vector<vector<char> > work(a);
      
      for(int I=0; I<vec.size(); I++) {
        bool ok = true;
        for(int i=minY[vec[I]]; i<=maxY[vec[I]]; i++) {
          for(int j=minX[vec[I]]; j<=maxX[vec[I]]; j++) {
            if(work[i][j] == '#') {
            }
            if(work[i][j] != '#' && work[i][j] != (char)vec[I]) {
              ok = false;
              break;
            }
          }
          if(!ok) break;
        } // for i
        if(!ok) { good = false; break; }
        for(int i=minY[vec[I]]; i<=maxY[vec[I]]; i++)
          for(int j=minX[vec[I]]; j<=maxX[vec[I]]; j++) {
            work[i][j] = '#';
          }
      }
      
      if(good) {
        cout << "SAFE" << endl;
        goto EXIT;
      }
    } while(next_permutation(vec.begin(), vec.end()));
    
    cout << "SUSPICIOUS" << endl;
    
  EXIT:;
  }
  
  return 0;
}

Measured memory_bytes: 1244
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace aizu1
{
public class Solution
    {
        public static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] s = Array.ConvertAll<string, int>(Console.ReadLine().Split(' '), tmp=>int.Parse(tmp));
            int q = int.Parse(Console.ReadLine());
            int[] t = Array.ConvertAll<string, int>(Console.ReadLine().Split(' '), tmp => int.Parse(tmp));
            int c = 0;

            Dictionary<int,int> map = new Dictionary<int,int>();

            for(int i=0;i<n;i++)
            {
                if (!map.ContainsKey(s[i])) map.Add(s[i],i);
            }

            for(int j=0;j<q;j++)
            {
                if (map.ContainsKey(t[j])) c++;
            }

            Console.WriteLine(c);
        }
    }
}

Measured memory_bytes: 10064
import java.util.Scanner;


	public class Main {
		
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			long n = sc.nextLong();
			long a = sc.nextLong();
			long b = sc.nextLong();
			long c = sc.nextLong();
			long d = sc.nextLong();
			long e = sc.nextLong();
			
			long[] x = new long[6];
			
			x[0] = n;
			
			for(int i=1;i<6;i++) {
				x[i] = 0L;
			}
			
			long ret = 0L;
			
			ret = Math.min(e, Math.min(d, Math.min(c, Math.min(b, a))));
			
			
			System.out.println((n+ret-1)/ret+4);
			
		}
		
	}
	


Measured memory_bytes: 35652
#include <stdio.h>

#define N_MAX 100

int main(void)
{
    int n, A[N_MAX];
    int i, j, v;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    for (i = 0; i < n-1; i++) {
        printf("%d ", A[i]);
    }
    printf("%d\n", A[i]);

    for (i = 1; i< n; i++) {
        v = A[i];
        j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        for (j = 0; j < n-1; j++) {
            printf("%d ", A[j]);
        }
        printf("%d\n", A[j]);
    }

    return 0;
}


Measured memory_bytes: 2752
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
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; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double PI = acos(-1);

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double theta = fmod((60 * h + m) * 5.5, 360);
    theta = min(theta, 360 - theta) * 2 * PI / 360;
    double c = sqrt(a * a + b * b - 2 * a * b * cos(theta));
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 4156
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    char a[105],b[105];
    scanf("%s %s",a,b);
    getchar();
    if(strlen(a) > strlen(b))   printf("GREATER\n");
    else if(strlen(a) < strlen(b)) printf("LESS\n");
    else if(strcmp(a,b) > 0) printf("GREATER\n");
    else if(strcmp(a,b) < 0) printf("LESS\n");
    else printf("EQUAL\n");
	return 0;
	}

Measured memory_bytes: 256
S=input()
l=len(S)
A=[0]*l
c=0
for i in range(l-1):
    if S[i]=='R':
        c+=1
    if S[i+1]=='L'or (i==l-1 and S[-1]=='R'):
        if i==l-1 and S[-1]=='R':
            c+=1
        A[i]+=(c+1)//2
        A[i+1]+=c//2
        c=0
c=0
for i in range(l-1,0,-1):
    if S[i]=='L':
        c+=1
    if S[i-1]=='R' or (i==0 and S[0]=='L'):
        if i==0 and S[0]=='L':
            c+=1
        A[i]+=(c+1)//2
        A[i-1]+=c//2
        c=0
print(' '.join(map(str,A)))

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

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

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

int main() {
    int n = 0;
    int cnt_taro = 0;
    int cnt_hanako = 0;
    string taros, hanakos;
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> taros >> hanakos;
        if (taros > hanakos) cnt_taro+=3;
        else if (taros < hanakos) cnt_hanako+=3;
        else{
            ++cnt_taro;
            ++cnt_hanako;
        }
    }
    cout << cnt_taro << " " << cnt_hanako << endl;
    
    return 0;
}


Measured memory_bytes: 3188
program sample
implicit none

integer :: n, m
integer, allocatable :: h(:), a(:), b(:)
integer :: i, j
integer :: number
integer, allocatable :: test(:)

read(*,*) n, m
allocate(h(n))
read(*,*) h
allocate(a(m))
allocate(b(m))

do i = 1, m
read(*,*) a(i), b(i)
end do

number = 0
allocate(test(n))
test = 1

do i = 1, m
if (h(a(i)) <= h(b(i))) then
test(a(i)) = test(a(i)) * 0
end if
if (h(b(i)) <= h(a(i))) then
test(b(i)) = test(b(i)) * 0
end if
end do

do i = 1, n
if (test(i) > 0) then
number = number + 1
end if
end do

write(*,*) number
stop
end program sample

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

int f(int arr[], int n) {
    int max = arr[0];
    int idx = 0;
    for(int i = 1; i < n; i++) {
        if(max < arr[i]) {
            max = arr[i];
            idx = i;
        }
    }
    return idx;
}

int main() {
    // 制約見て！！！デカかったらlong longにすること！
    int N;
    cin >> N;
    int A[N], B[N];
    rep(i, N) { cin >> A[i] >> B[i]; }
    int idx = f(A,N);

    int minB = B[idx];
    
    cout << A[idx]+minB << endl;
}

Measured memory_bytes: 4372
def combination(n, r)
  (r + 1 .. n).reduce(&:*) / (1 .. (n - r)).reduce(&:*)
end
(n, m, r) = gets.split(' ').map{|i|i.to_i}

if (r < n * m)
   puts 0
else
   puts combination(r - n * m + n - 1, n - 1)
end


Measured memory_bytes: 79764
void main() {
  problem();
}

int mod(string x, int d) {
  int r;
  auto xs = x.length;
  foreach(i; 0..xs) {
    r = (r * 2 + (x[i] - '0')) % d;
  }

  return r;
}

int mod(BigInt b, int popcount) {
  BigInt q, r;
  b.divMod(BigInt(popcount), q, r);
  return r.toInt;
}

void problem() {
  int calc(BigInt x, int popcount) {
    if (x == 0) return 0;

    int m = x.mod(popcount);
    int ans = 1;
    while(m > 0) {
      ans++;
      m %= m.popcnt;
    }

    return ans;
  }

  auto N = scan!int;
  auto X = scan;

  void solve() {
    const basePopCount = cast(int)X.count('1');
    const baseFirstModPlus = X.mod(basePopCount + 1);
    const baseFirstModMinus = basePopCount == 1 ? 0 : X.mod(basePopCount - 1);

    foreach(i; 0..N) {
      const deltaPlus = X[i] == '0';
      const popCount = basePopCount + (deltaPlus ? 1 : -1);
      if (popCount == 0) {
        writeln(0);
        continue;
      }

      int firstMod;
      auto deltaMod = powmod(2U, (N - i - 1).unsigned, popCount.unsigned);
      if (deltaPlus) {
        firstMod = (baseFirstModPlus + deltaMod) % popCount;
      } else {
        firstMod = baseFirstModMinus - deltaMod;
        firstMod = firstMod < 0 ? popCount + firstMod : firstMod;
      }

      int ans = 1;
      while(firstMod > 0) {
        ans++;
        firstMod %= firstMod.popcnt;
      }
      ans.writeln;
    }
  }

  solve();
}

// ----------------------------------------------

import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons, std.numeric;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(T t){ debug writeln(t); }
alias Queue = Tuple!(long, "from", long, "to");
import std.bigint, std.functional, core.bitop;

// -----------------------------------------------


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

int main(){
  int n;
  cin >> n;
  
  int a[n];
  for(int i = 0; i<n;i++){
    cin >> a[i];
  }
  
  sort(a, a + n, greater<int>());
  
  cout << a[0] - a[n-1] << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int sum(int x, int y)
{
	return x+y;
}
int sub(int x, int y)
{
	return x-y;
}
int mul(int x, int y)
{
	return x*y;
}
 
int main(void)
{
	int a, b, sm, sb, ml, gr;
	scanf("%d %d", &a, &b);
	
	sm = sum(a, b);
	sb = sub(a, b);
	ml = mul(a, b);
	
	if(sm > sb && sm > ml) gr = sm;
	else if(sb > sm && sb > ml) gr = sb;
	else if(ml > sm && ml > sb) gr = ml;
	
	printf("%d\n", gr);
}

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

int main(){
	long long n,i,min,max,sum;
	int a[COUNT];
	sum = 0;

	cin >> n;
	max =-1000000 ;
	min = 1000000;
	
	for (i = 0; i < n; i++) {
		cin >> a[i];
	

			if (max < a[i]) {
				max = a[i];
			}
			if (min > a[i]) {
				min = a[i];
			}
		
		sum = sum + a[i];
	}
	cout << min << " " << max << " " << sum<< endl;
	return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;


int main(){
    int n;
    cin >> n;
    int i;
    bool flag = false;
    
    for(i=1;i<10;i++){
        if(n%i == 0){
            if(n/i > 0 && n/i <10)
               flag = true;
        }
    }
    
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}
    
    


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int main(){
int n;
int a[100001]={0};
cin>>n;
int ans=0;
int s=0;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
a[0]=a[1];
for(int i=1;i<=n+1;i++){
	if(a[i]==a[i-1])s++;
	else {
		if(s%2==1)ans++;
		s=1;
	}
}
cout<<ans;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string S;
    cin >> S;
    bool kaibun = true;
    int N = S.size();
    for(int i = 0; i < N / 4 + 1; i++){
        int p = S.at(i);
        if(p== S.at(N / 2 - 1 - i) && p == S.at(N / 2 + 1 + i) && p == S.at(N - 1 -  i)){
            kaibun = true;
        }else{
            kaibun = false;
            break;
        }
    }
    if(kaibun == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append((a,b))
L = [x for x in L if x[1] > maxi]
L = sorted(L,key = lambda x:x[1],reverse=True)
throw = 0
for i in range(len(L)):
    throw += L[i][1]
    if throw >= H:
        print(i + 1)
        quit()
from math import ceil
print(ceil((H - throw) / maxi) + len(L))
    


Measured memory_bytes: 18648
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<(n); i++)
#define int long long
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;
signed main(void){
    vector<int>v(100010);
    v[0]=1;
    rep(i,100009){
        v[i+1]=v[i]*3%mod;
    }
    string s;cin>>s;
    int n=s.size();
    int dp[n+1];dp[0]=1;
    reverse(all(s));
    rep(i,n){
        if(s[i]=='0')dp[i+1]=dp[i];
        else dp[i+1]=(dp[i]*2+v[i])%mod;
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 2048
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int N = sc.nextInt();
    int M = sc.nextInt();
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    for (int i = 0; i < M; i++) {
      list.add(new ArrayList<>());
    }
    for (int i = 0; i < N; i++) {
      int X = Integer.parseInt(sc.next());
      list.get(X % M).add(X);
    }
    int ans = list.get(0).size() / 2;
    if (M % 2 == 0) ans += list.get(M / 2).size() / 2;
    for (int i = 1; i < (M + 1) / 2; i++) {
      ArrayList<Integer> l1 = list.get(i);
      ArrayList<Integer> l2 = list.get(M - i);
      ans += Math.min(l1.size(), l2.size());
      ArrayList<Integer> l = l1.size() < l2.size() ? l2 : l1;
      HashSet<Integer> exist = new HashSet<>();
      int dup = 0;
      for (int v : l) {
        if (exist.contains(v)) {
          ++dup;
          exist.remove(v);
        } else {
          exist.add(v);
        }
      }
      ans += Math.min(dup, Math.abs(l1.size() - l2.size()) / 2);
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 48212
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <ctime>
#include <random>
#include <bitset>
#include <climits>
#include <cstring>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
#define ll long long
#define eps 1e-8
#define inf 1e17
using namespace std;

int main() {
	speed;
	ll a, b, q, x, v;
	cin >> a >> b >> q;
	set<ll>s, t;
	for (int i = 0; i < a; ++i) {
		cin >> v;
		s.insert(v);
	}
	for (int i = 0; i < b; ++i) {
		cin >> v;
		t.insert(v);
	}
	for (int i = 0; i < q; ++i) {
		cin >> x;
		auto q = s.lower_bound(x), w = t.lower_bound(x), pq = q, pw = w;
		if (q == s.begin())
			pq = s.end();
		else
			--pq;
		if (w == t.begin())
			pw = t.end();
		else
			--pw;
		ll ans = inf;
		if (q != s.end() && pw != t.end())
			ans = min({ans, min(*q - x, x - *pw) + *q - *pw, });
		if (pq != s.end() && w != t.end())
			ans = min({ ans, min(*w - x, x - *pq) + *w - *pq });
		if (q != s.end() && w != t.end())
			ans = min(ans, max(*w - x, *q - x));
		if (pq != s.end() && pw != t.end())
			ans = min(ans, max(x - *pw, x - *pq));
		cout << ans << '\n';
	}
}

Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int N = 3238;

int dp[N][N];
pii back[N][N];

int main() {
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    s = "?" + s;
    t = "!" + t;
    int ns = s.size();
    int nt = t.size();
    int a=0, b=0;
    for (int i=1; i<ns; i++) {
        for (int j=1; j<nt; j++) {
            if (s[i] == t[j]) {
                dp[i][j] = 1 + dp[i-1][j-1];
                back[i][j] = pii(i, j);
                if (dp[i][j] > dp[a][b]) {
                    tie(a, b) = pii(i, j);
                }
            }
            else {
                if (dp[i-1][j] > dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j];
                    back[i][j] = back[i-1][j];
                }
                else {
                    dp[i][j] = dp[i][j-1];
                    back[i][j] = back[i][j-1];
                }
            }
        }
    }
    string ans;
    while (dp[a][b] > 0) {
        ans.push_back(s[back[a][b].first]);
        tie(a, b) = back[a-1][b-1];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}


Measured memory_bytes: 116992
#include<bits/stdc++.h>
 
using namespace std;
 
#define For(i,a,b) for(int i = a; i <= b; ++ i)
#define pb push_back
#define fi first
#define se second
 
const int N = 1e5 + 5;
typedef pair < int, int > ii;

int t, n, A = 1, newA;
vector < int > adj[N];
 

int dfs(int u, int pa, int lim) {
    multiset < int > s;
    multiset < int > :: iterator it;
    for (int i = 0; i < adj[u].size() ; ++ i){
		int v = adj[u][i];
		if (v == pa) continue;
        int cur = dfs(v, u, lim) + 1; s.insert(cur);
    }
    vector < int > data;
    while(s.size()) {
        it = s.end(); --it; int x = (*it);
        s.erase(it);
        it = s.upper_bound(lim - x);
        if (it == s.begin()) data.pb(x);
        else --it, s.erase(it), ++newA;
    }
    reverse(data.begin(), data.end());
    while(data.size() && data.back() == lim) ++ newA, data.pop_back();
    if (data.empty()) return 0;
    else { newA += data.size() - 1; return data[0]; }
}
bool check(int lim){
	newA = 0;
    newA += dfs(1, 1, lim) != 0;
    return newA <= A;
}
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	For(i, 1, n - 1){
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);  adj[v].pb(u);
	}
	For(i, 1, n)  A += (adj[i].size() - 1) / 2;
	int l = 1, r = n, ans;
	while(l <= r){
		int mid = (l + r)/2;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << A << ' ' << ans;
}

Measured memory_bytes: 20352
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const ll MOD = 1e9+7;
const double EPS = 1e-9;



int main(int argc, const char * argv[]) {
  int N; cin >> N;
  vector<int> a(N);
  int ai;
  for(int i=0; i<N; i++){
    cin >> ai;
    a[i] = -ai;
  }
  
  vector<int> chains;
  chains.push_back(a[0]);
  for(int i=1; i<N; i++){
    auto it = lower_bound(chains.begin(), chains.end(), a[i]+1);
    if (it == chains.end()){
      chains.push_back(a[i]);
    }else {
      *it = a[i];
    }
  }
  cout << chains.size() << endl;
  return 0;
}

Measured memory_bytes: 1276
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using uint64 = unsigned long long;
using vi = std::vector<int>;
using vl = std::vector<int64>;
using pii = std::pair<int, int>;
using pii = std::pair<int, int>;
using pll = std::pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(_) (_).begin(), (_).end()
#define rall(_) (_).rbegin(), (_).rend()
#define print(_) std::cout << (_) << '\n'
#define debug(_) std::cerr << #_ << ": " << (_) << '\n'
#define dbg(vec) for (size_t _ = 0; _ < vec.size(); ++_){std::cerr << #vec << "[" << _ << "] : " << vec[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;  // 1.073741823e9
const int64 INF64 = (1LL<<62) - 1;  // 4.611686018427387903e18
const int MOD = 1000000007;

const int MAX_V = 101010;
//const int64 INF64 = (1LL<<62) - 1;

struct edge {
  int64 to, cost;
};

int n;
std::vector<edge> G[MAX_V];
int64 dis[MAX_V];

void dijkstra(int s){
  std::priority_queue<std::pair<int64, int64>,
                      std::vector<std::pair<int64, int64>>,
                      std::greater<std::pair<int64, int64>>> pq;
  std::fill(dis, dis + n, INF64);
  dis[s] = 0;
  pq.push(std::pair<int64, int64>(0, s));

  while (!pq.empty()){
    std::pair<int64, int64> p = pq.top(); pq.pop();
    int v = p.second;
    if (dis[v] < p.first) continue;
    for (size_t i = 0; i < G[v].size(); ++i){
      edge e = G[v][i];
      if (dis[e.to] > dis[v] + e.cost){
        dis[e.to] = dis[v] + e.cost;
        pq.emplace(std::pair<int64, int64>(dis[e.to], e.to));
      }
    }
  }
}

int main(){
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; ++i) {
    int u, k; cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      int64 v, c; cin >> v >> c;
      G[u].push_back({v, c});
    }
  }

  dijkstra(0);

  for (int i = 0; i < n; ++i) {
    cout << i << " " << dis[i] << '\n';
    //if (i != n - 1) cout << '\n';
  }

  return 0;
}


Measured memory_bytes: 5580
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout() cout << std::fixed << std::setprecision(20);
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
typedef complex<double> cd;
static const double pi = 3.141592653589793;

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

  int n,k,s; cin >> n >> k >> s;

  rep(i, k) {
    cout << s;
    if(k != n || i != k - 1) cout << " ";
  }
  int none = s == 1 ? 2 : s - 1;
  rep(i, n - k) {
    cout << none;
    if(i != n - k - 1) cout << " ";
  }
  cout << endl;
}


Measured memory_bytes: 1280
def single_battle(a_card, b_card)
  if a_card>b_card
    return "a"
  elsif b_card>a_card
    return "b"
  else
    return "draw"
  end
end

def battle(a_card_array, b_card_array)
  length = a_card_array.length
  a_score = 0
  b_score = 0
  for i in 0..(length-1)
    if single_battle(a_card_array[i], b_card_array[i]) == "a"
      a_score += 3
    elsif single_battle(a_card_array[i], b_card_array[i]) == "b"
      b_score += 3
    else
      a_score += 1
      b_score += 1
    end
  end
  return [a_score, b_score]
end


n = gets.chomp.to_i
a_card_array = []
b_card_array = []
n.times do
  hand = gets.chomp.split
  a_card_array.push(hand[0])
  b_card_array.push(hand[1])
end

puts battle(a_card_array, b_card_array).join(' ')

Measured memory_bytes: 8752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=7+1e9;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
ll qpow(ll a,ll b,ll p){a%=p; ll ret=1;for(;b;b>>=1,a=a*a%p) if(b&1) ret=ret*a%p; return ret;}
ll getInv(ll x,ll p){return qpow(x,p-2,p);}
const int N=5+2e3;
ll a[N];
//240900502
int main(){
    ll n,k; scanf("%lld%lld",&n,&k);
    ll res=0;
    for(ll i=k;i<=n+1;i++){
        ll up=(2*n-i+1)*i/2;
        ll down=(i-1)*i/2;
        (res+=(up-down+1)%mod)%=mod;
    }
    printf("%lld",res);
}

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

int main()
{
    int a,b;

    while(scanf("%d %d",&a,&b)!=EOF)
    {
        if((a%2==0)||(b%2==0))
            printf("Even\n");
        else
            printf("Odd\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}


int main() {
    ll n, h;
    cin >> n >> h;
    vector<ll> z(n);
    vector<ll> zz(n);
    for (int i = 0; i < n; i++) {
        cin >> z.at(i) >> zz.at(i);
    }
    sort(z.begin(), z.end());
    sort(zz.begin(), zz.end());
    reverse(zz.begin(), zz.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (z.at(n - 1) >= zz.at(i))break;
        h -= zz.at(i);
        ans++;
        if (h <= 0) {
            h = 0;
            break;
        }
    }
    ans += (h + z.at(n - 1) - 1) / z.at(n - 1);
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<strstream>
#include<stack>
#include<utility>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<climits>
#include<map>
#include<string>
#include<sstream>

using namespace std;

#define mp make_pair
#define rep(i,n) for( int i = 0; i < n; i++ )
typedef vector<int,int> v;
typedef long long int ll;

int main()
{
	string str;
	while( getline( cin,str ) )
	{
		stack<char> stc;
		if( str[0] == '.' ) break;
		rep( i,str.size() )
		{
			if( str[i] == '(' || str[i] == '[' )
				stc.push( str[i] );
			if( str[i] == ')' || str[i] == ']' )
			{
                if ( stc.empty() ) {
                    goto owari;
                }
                if( stc.top() == '(' && str[i] == ')' ){
					stc.pop();}
				else if( stc.top() == '[' && str[i] == ']' )
					stc.pop();
				else
					goto owari;
                
			}
		}
		if( stc.empty() )
			puts("yes");
		else{
        owari:
			puts("no");
		}
	}
    
	return 0;
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)
using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;

int n,q;
char s1[100001],s2[100001];
int a1[100001],a2[100001];

int main(){
	scanf("%s%s",s1+1,s2+1);
	for(int i=1;s1[i];++i) a1[i]=a1[i-1]+s1[i]-'A'+1;
	for(int i=1;s2[i];++i) a2[i]=a2[i-1]+s2[i]-'A'+1;
	scanf("%d",&q);
	F(i,1,q){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		puts((a1[b]-a1[a-1])%3==(a2[d]-a2[c-1])%3?"YES":"NO");
	}
	return 0;
}

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

int main() {
  int A, B, C, K;
  scanf("%d%d%d%d", &A, &B, &C, &K);

  printf("%d", A + B + C + max(C, max(A, B)) * ((1 << K) - 1));
  return 0;
}


Measured memory_bytes: 256
N = int(input())
C, S, F = [], [], []
for _ in range(N - 1):
    c, s, f = map(int, input().split())
    C.append(c)
    S.append(s)
    F.append(f)
for i in range(N - 1):
    T = S[i] + C[i]
    for j in range(i + 1, N - 1):
        if S[j] >= T:
            T = S[j] + C[j]
        else:
            tmp = S[j]
            while tmp < T:
                tmp += F[j]
            T = tmp + C[j]
    print(T)
print(0)

Measured memory_bytes: 43612
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
constexpr int MOD = 998244353;

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

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}

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

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

    int n,k;
    cin >> n >> k;
    vector<int> a(n),f(n);

    rep(i,n){
        cin >> a[i];
    }
    rep(i,n){
        cin >> f[i];
    }

    sort(all(a));
    sort(all(f),greater<int>());

    auto isOK = [&](int maxc){
        int lim = k;
        rep(i,n){
            int tmp = maxc / f[i];
            if(tmp < a[i]) lim -= a[i] - tmp;
            if(lim < 0) return false;
        }
        return true;
    };

    int ng = -1,ok = 1e12 + 1;
    while(ok - ng > 1){
        int mid = (ok + ng) / 2;
        if(isOK(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';

	return 0;
}


Measured memory_bytes: 3328
import sys

sys.setrecursionlimit(10**9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

def comb(n, k):
    if n < k:
        return 0

    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = m * (n - i + 1) // i    
    return m

N = INT()

s = []

for _ in range(N):
    s.append(sorted(input()))

s = sorted(s)
s.append("")

ans = 0

i = 0
while i < N:
    j = i + 1

    while s[i] == s[j]:
        j += 1

    ans += comb(j - i, 2)

    i = j

print(ans)


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

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int P = 1000000007;

int H, W, T, n, m;

int qpow(int a, int b) {
	int s = 1;
	for (; b; b >>= 1) {
		if (b & 1) {
			s = 1ll * s * a % P;
		}
		a = 1ll * a * a % P;
	}
	return s;
}

int main() {
	read(H), read(W), read(T);
	n = H / std::__gcd(H, T);
	m = W / std::__gcd(W, T);
	print(qpow((qpow(2, n) + qpow(2, m) - 1ll + qpow(2, std::__gcd(n, m)) - 2) % P, 1ll * (H / n) * (W / m) % (P - 1)));
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include<bitset>

using namespace std;
#define loop(i,n) for(int i = 0; i < (n); ++i)
#define loops(i,f,n) for(int i = (f); i < (n); ++i)
#define INF 9999999
#define lint long long int
#define in(a) cin>>a
#define out(a) cout<<a<<endl

int main()
{
	lint n;
	cin >> n;

	int ans = to_string(n).length();

	for (lint i = 1; i*i <= n; ++i)
	{
		if (n%i == 0)
		{
			ans = min(ans, (int)max(to_string(i).length(), to_string(n / i).length()));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

bool isValid(string s) {
	int n = s.size();
	if(s[n-1] == '1') {
		return false;
	} else if(s[0] == '0') {
		return false;
	}
	rep(i,0,n/2) {
		if(s[i] != s[n-2-i]) {
			return false;
		}
	}
	return true;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	string s;
	cin >> s;
	int n = s.size();
	if(!isValid(s)) {
		cout << -1 << '\n';
		return 0;
	}
	vi v;
	rep(i,0,n) {
		if(s[i] == '1') {
			v.pb(i);
		}
	}
	v.pb(v.back()+1);
	vector<pii> ret;
	rep(i,0,sz(v)-1) {
		ret.pb(mp(i,i+1));
	}
	int t = sz(v);
	rep(i,1,sz(v)) {
		int x = v[i] - v[i-1] - 1;
		rep(j,0,x) {
			ret.pb(mp(i,t));
			t++;
		}
	}
	rep(i,0,sz(ret)) {
		cout << ret[i].F+1 << " " << ret[i].S+1 << '\n';
	}
	return 0;
}


Measured memory_bytes: 2756
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

class UnionFind
{
    std::vector<int> data;

public:
    UnionFind(int size) : data(size, -1) {}
    bool unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
                std::swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y)
    {
        return root(x) == root(y);
    }
    int root(int x)
    {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x)
    {
        return -data[root(x)];
    }
};

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

    ll n, m, q;
    cin >> n >> m >> q;
    set<vector<int>> ones, zeros;
    UnionFind uf(n);
    vector<int> a(q), b(q), c(q);
    int one = 0, zero = 0;
    for (int i = 0; i < q; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        if (c[i] == 0)
        {
            if (uf.find(a[i], b[i]) == false)
            {
                zero++;
                zeros.emplace(vector<int>{a[i], b[i], c[i]});
                uf.unite(a[i], b[i]);
            }
        }
        else
        {
            one++;
            ones.emplace(vector<int>{a[i], b[i], c[i]});
        }
    }
    if (m == n - 1 && one)
    {
        cout << "No" << endl;
        return 0;
    }
    for (int i = 0; i < q; i++)
    {
        if (c[i] == 0)
            continue;
        if (uf.find(a[i], b[i]))
        {
            cout << "No" << endl;
            return 0;
        }
    }
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        st.insert(uf.root(i));
    }
    ll sz = st.size(), ma = sz * (sz - 1) / 2 + (int)zeros.size();
    if (sz <= 2 && one)
    {
        cout << "No" << endl;
        return 0;
    }
    if (m > ma)
    {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 15872
import java.util.*;
import static java.lang.Math.*;

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

		// 入力
		int a = sc.nextInt();// Alice A秒
		int b = sc.nextInt();// Alice B秒
		int c = sc.nextInt();// Bob C秒
		int d = sc.nextInt();// Bob D秒

		// 計算
		int t = 0;

		// abcd
		if(b <= c) t = 0;
		// acbd
		if(a <= c && c <= b && b <= d) t = b - c;
		// cabd
		if(c <= a && b <= d) t = b - a;
		// acdb
		if(a <= c && d <= b) t = d - c;
		// cadb
		if(c <= a && a <= d && d <= b) t = d - a;
		// cdab
		if(d <= a) t = 0;

		// 出力
		System.out.println(t);

	}
}




Measured memory_bytes: 24020
check=dict()
N,z,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    z=list(zip([2,3,5],b))
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Measured memory_bytes: 120468
#https://atcoder.jp/contests/ddcc2020-qual/submissions/8587774

M = int(input())
dc = [list(map(int, input().split())) for _ in range(M)]
 
d = [dc[i][0] for i in range(M)]
c = [dc[i][1] for i in range(M)]
 
ans = sum(c) - 1
s = 0
 
for i in range(M):
    s += c[i] * d[i]
    if s % 9 != 0:
        ans += s // 9
        s = s % 9
    else:
        ans += s//9 - 1 
        s = 9
print(ans)

Measured memory_bytes: 48700
t = input().rstrip().split(' ')
switch = int(t[0])
lamp = int(t[1])
s = [list(map(int, input().split())) for _ in range(lamp)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

for i in range(2 ** switch):
  ptn = bin(i)[2:].rjust(switch, "0")
  light = True;
  for j in range(lamp):
    temp = 0
    for n in range(1, s[j][0] + 1):
      if ptn[s[j][n] - 1] == "1":
        temp += 1
    if temp % 2 != p[j] %2:
      light = False
  if light:
    ans += 1
print(ans)
        

  

Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
typedef long long LL;
using namespace std;
LL ans[100005];
const int MOD=1e9+7;
int main()
{
    int n;cin>>n;
    ans[1]=1;
    for(int i=2;i<=n;i++) ans[i]=(ans[i-1]*i)%MOD;
    cout<<ans[n]<<endl;
    return 0;
}


Measured memory_bytes: 1024
using System;
class Program
{
	static void Main(string[] args)
	{
      // スペース区切りの整数の入力
      var n = int.Parse(Console.ReadLine());
      var inputs = Array.ConvertAll(
        Console.ReadLine().Split(' '), 
        x => int.Parse(x));
      var max=inputs[0];
      var sum=0;
      foreach(var input in inputs){
        if(input>=max){
          sum++;
          max=input;
        }
      }
      Console.WriteLine(sum);
    }
}


Measured memory_bytes: 11092
n = gets.to_i

li = []
sa = {}
n.times do
  li << gets.split.map(&:to_i)
end

if n == 1
  puts 1
else
  li.each_with_index do |v, i|
    if i+1 == n
      break
    end
    (i+1..n-1).each do |l|
      a = v[0]-li[l][0]
      b = v[1]-li[l][1]
      s = [a,b].join(' ')
      if sa.has_key?(s)
        sa[s] += 1
      else
        sa[s] = 1
      end
      s = [-a,-b].join(' ')
      if sa.has_key?(s)
        sa[s] += 1
      else
        sa[s] = 1
      end
    end
  end

  sb = sa.max {|a,b| a[1] <=> b[1]}

  puts n - sb[1]
end


Measured memory_bytes: 2428
#include <stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	int t=0,r=0;
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'R')t++;
		else t = 0;
		if (t >= r)r = t;
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+5;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    if(a[a.length()-1] == b[0] && b[b.length()-1] == c[0])
        puts("YES");
    else
        puts("NO");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include <algorithm>
#include<cstring>
#include <math.h>
#include <iomanip>
using namespace std;

struct tr{
  char m;
  int value;
};

void BubbleSort(tr *C,int N)
{
  for(int i = 0;i<N;i++){
    for(int j = N-1; j>i;j--){
      if(C[j].value < C[j-1].value){
	tr a=C[j];
	C[j]=C[j-1];
	C[j-1]=a;
      }
    }
  }
}

void SelectionSort(tr *C,int N)
{
  for(int i = 0;i<N;i++){
    int minj = i;
    for(int j = i;j<N;j++){
      if (C[j].value < C[minj].value)
        minj = j;
    }
    tr a=C[i];
    C[i]=C[minj];
    C[minj]=a;
  }
}

bool isStable(tr *in,tr *out,int N){
  int i,j,a,b;
  for (i = 0;i<N;i++){
    for (j = i+1;j<N;j++){
      for (a = 0;a<N;a++){
	for (b = a+1;b<N;b++){
	  if(in[i].value==in[j].value){
	    if(in[i].m== out[b].m &&in[i].value== out[b].value){
	      if( in[j].m == out[a].m  && in[j].value == out[a].value)
		return false;
	    }
	  }
	}
      }
    }
  }
  return true;
}

int main()
{
  int n;
  cin>>n;
  tr c[36];
  tr c2[36];
  tr c3[36];
  for(int i=0;i<n;i++){
    cin>>c[i].m>>c[i].value;
    c2[i]=c[i];
    c3[i]=c[i];
  }
  BubbleSort(c,n);
  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<c[i].m<<c[i].value;
  }
  cout<<endl;
  cout<<"Stable"<<endl;
  SelectionSort(c2,n);
  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<c2[i].m<<c2[i].value;
  }
  cout<<endl;
  if(isStable(c3,c2,n))
      cout<<"Stable"<<endl;
    else
      cout<<"Not stable"<<endl;

  return 0;
}



Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;

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

    int n,t[105],m,sum=0;
    cin>>n;
    reps(i,n){
	cin>>t[i];
	sum+=t[i];
    }
    
    cin>>m;
    int p,x;
    rep(i,m){
	cin>>p>>x;
	cout<<sum-t[p]+x<<'\n';
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int main()
{
	char s[100005];
	scanf("%s", s);
	int n = strlen(s);

	vector<pair<int,pair<int, int>>> segs;

	int it = 0;

	while(it < n) {

		int l = it;
		while(s[it] == 'R') {
			it += 1;
		}
		int m = it;
		while(s[it] == 'L') {
			it += 1;
		}
		int r = it;

		segs.push_back({l, {m - l, r - m}});
	}

	vector<int> ans(n, 0);

	for(auto& seg : segs) {

		int l_it = seg.first;
		int l = seg.second.first;
		int r = seg.second.second;

		int x = (l + 1) / 2 + r / 2;
		int y = l / 2 + (r + 1) / 2;

		ans[l_it + l - 1] = x;
		ans[l_it + l] = y;
	}

	for(int i = 0; i < n; i++) {
		printf("%d%c", ans[i], (i + 1 == n) ? '\n' : ' ');
	}

	return 0;
}


Measured memory_bytes: 1656
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    b = defaultdict(int)
    N = II()
    for i in range(N):
        b[input()] += 1
    print(len(list(b.keys())))
    

if __name__ == '__main__':
    main()

Measured memory_bytes: 110664
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a,b,c,d;
    int m=0,n=0,t=0;
    cin>>a>>b>>c>>d;
    if(abs(a-b)<=d)
        m=1;
    if(abs(b-c)<=d)
        n=1;
    if(abs(a-c)<=d)
        t=1;
    if((m==1 && n==1)||(m==1 && t==1)||(t==1 && n==1)||t==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    c = [[0 for _ in range(10)] for _ in range(10)]
    tmp = 1
    for i in range(1, n + 1):
        if i >= tmp * 10:
            tmp *= 10
        c[i // tmp][i % 10] += 1

    ans = 0
    for i in range(1, 10):
        for j in range(1, 10):
            ans += c[i][j] * c[j][i]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064