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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e5 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);


int n , m;

int a[20][20];
int c[20];

void solve(int testCase){

    int x;
    scanf("%d %d %d" , &n , &m , &x);

    for(int i = 0 ; i < n ; i ++) {
            scanf("%d" , &c[i]);

            for(int j = 0 ; j < m ; j ++) {
                    scanf("%d" , &a[i][j]);
            }
    }

    int ans = INT_MAX;


    for(int mask = 0 ; mask < (1 << n) ; mask ++) {

            int cost = 0;
            bool ok = 1;

            vector < int > total(m + 1 , 0);

            for(int i = 0 ; i < n ; i ++) {
                    if(mask & (1 << i)) {

                            cost += c[i];
                            for(int j = 0 ; j < m ; j ++) {
                                    total[j] += a[i][j];
                            }

                    }

            }
                    for(int j = 0 ; j < m ; j ++) {
                            if(total[j] < x) {
                                    ok = 0;
                            }
                    }

            if(ok) {
                    ans = min(ans , cost);
            }
    }



    printf("%d\n" , ans == INT_MAX ? -1 : ans);


}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
#define endl "\n" 
#define pi acos(-1)
#define ll long long 
using namespace std;
void solve();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int q=1;//cin>>q;
    while(q--){
        solve();
    }
    return 0;
}
void solve(){
  int d,t,s;cin>>d>>t>>s;
  int p;
  if(d%s==0)
    p=d/s;
  else
    p=d/s+1;
  if(p<=t)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
} 

Measured memory_bytes: 3640
#include <iostream>
#include <math.h>

#include <stdlib.h>

using namespace std;

int bs(int a[], int l, int r, int m){
	int mid = l+(r-l)/2 ;
	if (r>=l)
	{
		if (a[mid]==m)
		{
			return mid+1;
		}
		if (a[mid]>m)
		{
			return bs(a, l, mid-1, m);
		}
		if (a[mid]<m)
		{
			return bs(a, mid+1, r, m);
		}
	}
	return l;
}

int ncr(int n, int r){
	int ans = 1;
	if (r==0)
	{
		return 1;
	}
	if (r==1)
	{
		return n;
	}
	for (int i = 0; i < r; ++i)
	{
		ans *= n-i;
		ans /= (i+1);
	}
	return ans;
}

void swap(int* gg, int* b){
	int temp;
	temp = *gg;
	*gg = *b;
	*b = temp;
}

int partition(int arr[], int low, int high){
	int pivot = arr[high];
	int f = (low-1);
	for (int j=low; j<high; j++)
	{
		/* code */
		if(arr[j]<=pivot){
			f++;
			swap(&arr[f], &arr[j]);
		}
	}
	swap(&arr[f+1], &arr[high]);
	return (f+1);
}

void quickSort(int arr[], int low, int high){
	if(low<high){
		int pi = partition(arr,low,high);
		quickSort(arr, low, pi-1);
		quickSort(arr, pi+1, high);
	}
	return;
}

int main(){

	
	int r;
	cin>>r;
	if (r<2800)
	{
		if (r<1200)
		{
			cout<<"ABC"<<endl;
		}
		else{
			cout<<"ARC"<<endl;
		}
	}
	else{
		cout<<"AGC"<<endl;
	}
	return 0;
}








Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int box, num1, num2, i;
  while(scanf("%d%d",&num1,&num2),num1+num2) {
    if( num1 < num2 ) {
      box = num1;
      num1 = num2;
      num2 = box;
    }
    for(i = 0; num2; i++ ) {
      box = num1 % num2;
      num1 = num2;
      num2 = box;
    }
    printf("%d %d\n",num1, i);
  }
  return 0 ;
}

Measured memory_bytes: 600
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] ABK = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            List<int> divisorA = new List<int>();
            List<int> divisorB = new List<int>();
            List<int> result = new List<int>();
            //Aの約数すべて
            for (int j = 1; j < ABK[0]+1; j++)
            {
                if (ABK[0] % j == 0)
                {
                    divisorA.Add(j);
                }
            }
            //Bの約数すべて
            for (int z = 1; z < ABK[1]+1; z++)
            {
                if (ABK[1] % z == 0)
                {
                    divisorB.Add(z);
                }
            }
            //共通約数求め
            for (int p = 0; p < divisorB.Count; p++)
            {
                if (divisorA.Contains(divisorB[p]))
                {
                    result.Add(divisorB[p]);
                }
            }
            result.Sort();
            result.Reverse();
            Console.WriteLine(result[ABK[2]-1]);
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();


Measured memory_bytes: 13280
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;

string n;

int main()
{
	cin>>n;
	for(int i=0;i<n.length();i++)
	{
		if(n[i]=='7')
		{
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}

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

if N <=1000:
    print(1000-N)

elif N <=2000:
    print(2000-N)

elif N <=3000:
    print(3000-N)

elif N <=4000:
    print(4000-N)

elif N <=5000:
    print(5000-N)

elif N <=6000:
    print(6000-N)

elif N <=7000:
    print(7000-N)

elif N <=8000:
    print(8000-N)

elif N <=9000:
    print(9000-N)

elif N <=10000:
    print(10000-N)
    


Measured memory_bytes: 9100
//03
#include<iostream>

using namespace std;

int main(){
  for(int x,y;cin>>x>>y,x|y;){
    int g[17][16]={};
    for(int i=1;i<=y;i++){
      for(int j=1;j<=x;j++){
	cin>>g[i][j];
      }
    }
    int a[17][16]={};
    for(int i=1;i<=x;i++){
      a[1][i]=g[1][i]==0;
    }
    for(int i=1;i<=y-1;i++){
      for(int j=1;j<=x;j++){
	if(g[i][j]==0){
	  for(int k=-1;k<=1;k++){
	    if(1<=j+k&&j+k<=x){
	      if(g[i+1][j+k]==0){
		a[i+1][j+k]+=a[i][j];
	      }else if(k==0&&g[i+1][j]==2){
		a[i+1][j]+=a[i][j];
	      }
	    }
	  }
	}else if(g[i][j]==2){
	  if(g[i+2][j]!=1){
	    a[i+2][j]+=a[i][j];
	  }
	}
      }
    }
    int ans=0;
    for(int i=1;i<=x;i++){
      ans+=a[y][i]+a[y+1][i];
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
h,w = map(int,input().split())
buf = '#' * (w+2)
lst = [buf]
for i in range(h):
    s = '#' + input() + '#'
    lst.append(s)
lst.append(buf)

def check(x,y):
    if (lst[x-1][y]=='#') or (lst[x+1][y]=='#') or (lst[x][y+1]=='#') or (lst[x][y-1]=='#'):
        return True
    else:
        return False

for i in range(1,h+1):
    for j in range(1,w+1):
        if (lst[i][j] == '#'):
            flg = check(i,j)
            if not flg:
                print('No')
                exit()
print('Yes')

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

using namespace std;

#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int> > vvi;
typedef pair<ll, ll>   pairl;
typedef vector<ll>     vl;
typedef vector<ll>     vll;
typedef vector<vector<ll> > vvl;
const   int            infi = numeric_limits<int>::max();
const   ll             infl = numeric_limits<ll>::max();
const   double         eps = 0;
const   int            ms  = 0;



int main()
{
    ios::sync_with_stdio(false);//endl->"\n"
    cin.tie(0);
    

    int N;
    cin >> N;
    vl A(N);
    rep(i, N)cin >> A[i];
    if (A[0] != 0){
        cout << -1 << "\n";
        return 0;
    }
    ll ans = 0;
    for(int i=1; i < N; i++){
        if(A[i]-A[i-1] >1){
            cout << -1 << "\n";
            return 0;
        }
        if(A[i] == 0)continue;
        if(A[i] == 1){
            ans++;

        }
        else if(A[i] - A[i-1] == 1){
            ans+=1;        

        }
        else {
            ans+= A[i];
            
        }
        //debug(ans)
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define mx 38461538461538
typedef long long int ll;
int main(){
    ll n,m;
    cin>>n;
    vector<char>v;
    deque<char>duck;
    v.push_back('z');
    v.push_back('a');
    for(int i=1;i<26;i++){
        v.push_back('a'+i);
    }
    while(n!=0){
       if(n%26==0){
        duck.push_front(v[n%26]);
        n=(n/26)-1;
       }
       else{
        duck.push_front(v[n%26]);
        n=n/26;
       }
    }
    for(int i=0;i<duck.size();i++)cout<<duck[i];
    cout<<endl;
    duck.clear();
    return 0;
}


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

int main(void) {
    vector<int> height;
    vector<int> width;
    int n = 0;
    while (true) {
        int h, w;
        cin >> h >> w;
        if (h == 0 && w == 0) {
            break;
        }
        height.push_back(h);
        width.push_back(w);
        n++;
    }
    for (int i = 0; i < n; i++) {
        for (int y = 0; y < height.at(i); y++) {
            for (int x = 0; x < width.at(i); x++) {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i,n) for(int i=n; i>=0; i--)
#define FOR(i,m,n) for(int i=m; i<(n); i++)
#define ALL(v) v.begin(),v.end()
#define INF 2e9
using namespace std;
typedef long long ll;
 
 
int main()
{
    int N;
    cin >> N;
    vector<string> W(N);
    REP(i, N) cin >> W[i];

    int b = 0;
    for (int i = 1; i < N; i++)
    {
        if(W[i-1].substr(W[i-1].length()-1, 1) == W[i].substr(0, 1)){
            b += 1;
        }
    }
    
    sort(ALL(W));
    int a = 0;
    for (int i = 1; i < N; i++)
    {
        if(W[i] != W[i-1]){
            a += 1;
        }
    }
    
    if(b == N-1 && a == N-1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 256
import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 998244353, BASE: int = 37):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: search_max = False の場合、answer <= x であればcheck_func(x) = true となるような関数
#             search_max = True  の場合、x <= answer であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 10 ** 18 + 3
    # BASEはMOD未満で1でない奇数とする
    BASE = random.randint(2, MOD // 2 - 1) * 2 + 1
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            # 自分より開始点がL以上前の文字列のハッシュを検索対象に追加
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            # ハッシュが衝突したら、範囲を重ねず同じ文字列となる文字列が存在することになる
            if v in hashes:
                return True
        return False

    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 4264
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;


int main()
{
	int n;
	cin >> n;
	iv v;
	
	REP(i,n)
	{
		int tmp;cin >> tmp;tmp--;
		v.PB(tmp);
	}
	
	int ans = 0,now = 0;
	
	while(ans < 100100)
	{
		ans++;
		now = v[now];
		if(now == 1)
		{
			cout << ans << endl;
			return 0;
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}

Measured memory_bytes: 892
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) {return *(char*)a - *(char*)b;}
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)


int main(void)
{
	char s[100000][11];
	int n;
	scanf("%d", &n);
	int i;
	for (i = 0; i < n; i++) {
		scanf("%s", s[i]);
		qsort(s[i], 10, sizeof(char), cmp_char);
	}
	qsort(s, n, sizeof(char) * 11, strcmp);
	long long int prev, ana;
	prev = ana = 0;
	for (i = 0; i < n - 1; i++)
	{
		if(strcmp(s[i], s[i + 1]) == 0)
			ana += ++prev;
		else
			prev = 0;
	}
	printf("%lld\n", ana);
	return 0;
}

Measured memory_bytes: 2428
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		while (str != null) {
			String[] strA = str.split("");
			str = br.readLine();
			String[] strB = str.split("");
			int lengthA = strA.length;
			int lengthB = strB.length;
			int maxn = 0;
			for (int i = 0; i < lengthA; i++) {
				int n = 0;
				int p = 0;
				while (p < lengthA && i + p < lengthB) {
					if (strA[p].equals(strB[i + p])) {
						n++;
						if (maxn < n)
							maxn = n;
					} else {
						n = 0;
					}
					p++;
				}
			}
			for (int i = 0; i < lengthB; i++) {
				int n = 0;
				int p = 0;
				while (p < lengthB && i + p < lengthA) {
					if (strB[p].equals(strA[i + p])) {
						n++;
						if (maxn < n)
							maxn = n;
					} else {
						n = 0;
					}
					p++;
				}
			}
			System.out.println(maxn);
			str = br.readLine();
		}
	}
}

Measured memory_bytes: 30104
n, x, y = map(int, input().split())
x, y = x-1, y-1

ans = [0] * n
for i in range(n):
    for j in range(i+1, n):
        ind = min(j-i, abs(x-i)+abs(y-j)+1)
        ans[ind] += 1

for k in range(1, n):
    print(ans[k])

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

#define ll long long
#define endl "\n"
ll INF = 1e9 + 7;

int main(){
	string a, b, ans = ""; cin>>a>>b;
	map<pair<int, int>, string> m;
	vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
	m[{0, 0}] = "";
	for(uint i = 1; i <= a.length(); i++){
		for(uint j = 1; j<= b.length(); j++){
			//string c = "";
			if(a[i-1] == b[j-1]){
				dp[i][j] = 1+dp[i-1][j-1];
				//c += m[{i-1, j-1}] + a[i-1];
				//m[{i, j}] = c;
			}else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
				//if(dp[i][j] == dp[i][j-1]){
					//c += m[{i, j-1}];
				//}else{
					//c += m[{i-1, j}];
				//}
				//m[{i, j}] = c;
			}
			//if(i > 2 && j > 2){
				//m.erase({i-2, j-2});
				//m.erase({i-2, j-1});
				//m.erase({i-1, j-2});
			//}
		}
	}
	int i = a.length(), j = b.length();
	while(i>0 && j>0){
		if(i == 1 || j == 1){
			if(a[i-1] == b[j-1]){
				ans += a[i-1];
				i--; j--;
			}else if(i > 1){
				i--;
			}else if(j > 1){
				j--;
			}else{
				break;
			}
		}else if(dp[i][j] == dp[i][j-1]){
			j--;
		}else if(dp[i][j] == dp[i-1][j]){
			i--;
		}else if(dp[i][j] == 1 + dp[i-1][j-1]){
			ans += a[i-1];
			i--; j--;
		}
	}
	reverse(ans.begin(), ans.end());
	//cout<<m[{a.length(), b.length()}]<<endl;
	cout<<ans<<endl;
}


Measured memory_bytes: 35584
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
  int a, b, cnt = 0;

  cin >> a >> b;

  for(int i = a; i <= b; i++){
    string suu = to_string(i);
    
    if(suu[0] == suu[4] && suu[1] == suu[3])
      cnt++;
  }
  cout << cnt <<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef int64_t Int;
const double pi = M_PI;

int main()
{
    int n;

    cin >> n;

    for (Int i = 1; i <= n; i++)
    {
        int x = i;
        bool flag = true;

        if (x % 3 == 0)
        {
            cout << ' ' << i;
            flag = false;
        }

        while (flag && x)
        {
            if (x % 10 == 3)
            {
                cout << ' ' << i;
                break;
            }
            x /= 10;
        }
    }
    cout << endl;
}


Measured memory_bytes: 3116
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::min;
const int MAXN=400010;
const int INF=2e9;
struct Edge {
	int u,v,w;
	friend bool operator<(Edge a,Edge b) {
		return a.w<b.w;
	}
}ed[MAXN];
int cnt=0;
inline void join(int x,int y,int z) {
	ed[++cnt].u=x;
	ed[cnt].v=y;
	ed[cnt].w=z;
	return;
}
int f[MAXN];
inline void init(int n) {
	for(int i=0;i<=n;++i) {
		f[i]=i;
	}
}
int find(int x) {
	return x==f[x]?x:(f[x]=find(f[x]));
}
int best[MAXN];
int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=0;i<=n;++i) {
		best[i]=INF;
	}
	int x,y,z;
	for(int i=1;i<=q;++i) {
		scanf("%d%d%d",&x,&y,&z);
		join(x,y,z);
		best[x]=min(best[x],z+1);
		best[y]=min(best[y],z+2);
	}	
	for(int i=0;i<n*2;++i) {
		best[(i+1)%n]=min(best[(i+1)%n],best[i%n]+2); //n*2防止更新了n-1到0 
	}
	for(int i=0;i<n;++i) {
		if(best[i]!=INF) join(i,(i+1)%n,best[i]);
	}
	init(n);
	sort(ed+1,ed+1+cnt);
	long long ans=0;
	for(int i=1;i<=cnt;++i) {
		int a=find(ed[i].u),b=find(ed[i].v);
		if(a!=b) {
			ans+=ed[i].w;
			f[a]=b;
		}
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 10368
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);

int main() {
	int a;
	cin >> a;

	cout << a + a * a + a * a*a << endl;
	return 0;
}

Measured memory_bytes: 3624
process.stdin.resume();
process.stdin.setEncoding('utf8');
var input = '';
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function() {
    var lines = input.split('\n');
    for (var i = 0; i < lines.length; i++) {
        var args = lines[i].split(' ').map(Number);
        if (args[0] == 0 && args[1] == 0) {
            break;
        }
        var result = args.sort(function(a, b) {
            return a - b;
        });
        console.log(result.join(' '));
    }
});

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

ans = []

for i in range(1,N+1):
    n = i
    if i%3 == 0:
        ans.append(i)

    while n > 0:

        if n % 10 == 3:
            ans.append(i)

        n = n//10


print(" "+" ".join([str(i) for i in set(ans)]))


Measured memory_bytes: 6620
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int sum_keta(int n){
    int sum=0;
    while(n>0){
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int main() {
    int n;
    cin>>n;
    int minimam=1000000;
    if(n%10==0) cout<<"10"<<endl;
    else{
        
    for(int a=1;a<=n;a++){
        int b=n-a;
        int s=sum_keta(a)+sum_keta(b);
        minimam=min(minimam,s);
    }
    cout<<minimam<<endl;
    }
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct LazySegmentTree {
    int n;
    vector<ll> node, lazy;

    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while (n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 1e10);

        for (int i=0; i<sz; ++i) node[i+n-1] = v[i];
        for (int i=n-2; i>=0; --i) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    LazySegmentTree(int Sz) {
        int sz = Sz;
        n = 1; while (n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 1e10);

        for (int i=0; i<sz; ++i) node[i+n-1] = 1e10;
        for (int i=n-2; i>=0; --i) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    void eval(int k, int l, int r) {
        if (lazy[k] != 0) {
            node[k] = min(node[k], lazy[k]);

            if (r - l > 1) {
                lazy[2*k+1] = min(lazy[2*k+1], lazy[k]);
                lazy[2*k+2] = min(lazy[2*k+2], lazy[k]);
            }

            lazy[k] = 1e10;
        }
    }

    // RMQ
    void update(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;

        eval(k, l, r);

        if (b <= l or r <= a) return;
        if (a <= l and r <= b) {
            lazy[k] = min(lazy[k], x);
            eval(k, l, r);
        }
        else {
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    ll getmin(int a, int b, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;
        if (b <= l or r <= a) return 1e10;
        eval(k, l, r);
        if (a <= l and r <= b) return node[k];
        ll vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

ll S[201010], T[201010], X[201010], D[201010];

int main() {
    int N, Q;
    cin >> N >> Q;
    rep(i, N) cin >> S[i] >> T[i] >> X[i];
    rep(i, Q) cin >> D[i];

    set<ll> pos;
    rep(i, N) pos.insert(S[i]-X[i]);
    rep(i, N) pos.insert(T[i]-X[i]);
    rep(i, Q) { pos.insert(D[i]); pos.insert(D[i]+1); }
    int L = pos.size(), id = 0;
    map<int, int> mp; vector<int> mpr(L);
    for (int p : pos) {
        mpr[id] = p;
        mp[p] = id++;
    }

    rep(i, N) S[i] = mp[S[i]-X[i]];
    rep(i, N) T[i] = mp[T[i]-X[i]];
    rep(i, Q) D[i] = mp[D[i]];

    LazySegmentTree st(L);
    rep(i, N) {
        st.update(S[i], T[i], X[i]);
    }
    rep(i, Q) {
        ll ans = st.getmin(D[i], D[i]+1);
        if (ans == 1e10) ans = -1;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 118400
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

ll n,m;
vector<P> v[55];
P a[22];
ll u[55];
ll dfs(ll x,ll k) {
  if(x==a[k].S) return 1;
  u[x]=1;
  ll ff=0;
  rep(i,v[x].size()) {
    ll y=v[x][i].F;
    if(u[y]) continue;
    ll f=dfs(y,k);
    if(f) v[x][i].S|=1<<k;
    ff|=f;
  }
  return ff;
}

ll dp[55][1<<20];

void Main() {
  cin >> n;
  rep(i,n-1) {
    ll x,y;
    cin >> x >> y;
    x--,y--;
    v[x].pb(P(y,0));
    v[y].pb(P(x,0));
  }
  cin >> m;
  rep(i,m) {
    cin >> a[i].F >> a[i].S;
    a[i].F--,a[i].S--;
    mem(u);
    dfs(a[i].F,i);
    swap(a[i].F,a[i].S);
    mem(u);
    dfs(a[i].F,i);
  }
  dp[0][0]=1;
  vector<ll> g;
  rep(i,n) {
    rep(j,v[i].size()) {
      if(i<v[i][j].F) g.pb(v[i][j].S);
    }
  }
  rep(i,g.size()) {
    rep(t,1<<m) {
      dp[i+1][t|g[i]]+=dp[i][t];
      dp[i+1][t]+=dp[i][t];
    }
  }
  pr(dp[g.size()][(1<<m)-1]);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);
    int a, b; cin >> a >> b;
    cout << (a - b + 1) << endl;
}

Measured memory_bytes: 256
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

a,b = I()
ans = a*b
if ans % 2== 0:
    print("Even")
else:
    print("Odd")


Measured memory_bytes: 9872
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int r,g,b;
    cin >> r >> g >> b;
    int n = r*100+g*10+b;
    YES(n%4 == 0);
}

Measured memory_bytes: 256
H,W = map(int,input().split())
S = []
res = [[0 for i in range(W)]for i in range(H)]

for i in range(H):
    s = list(input())
    S.append(s)

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            res[i][j] = '#'
            for x,y in [[j-1,i-1],[j,i-1],[j+1,i-1],[j-1,i],[j+1,i],[j-1,i+1],[j,i+1],[j+1,i+1]]:
                if 0 <= x and 0 <= y and x <= W-1 and y <= H-1:
                    if res[y][x] != '#':
                        res[y][x] += 1
for i in range(H):
    for j in range(W):
        res[i][j] = str(res[i][j])
for i in range(H):
    print("".join(res[i]))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;

int main() {
  ll N,x;
  cin >> N >> x;
  vector<ll> a(N);
  rep(i,N){
    cin >> a[i];
  }
  vector<ll> b(N);
  b = a;
  if(a[0] >x) a[0] = x;
  
  rep(i,N-1){
    if(a[i]+a[i+1] > x){
      a[i+1] = x-a[i];
    }
  }
  ll c = 0;
  rep(i,N){
    c += b[i]-a[i];
  }
  cout << c << endl;
}

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

int n,f[200009],cnt[200009];

int main()
{
	cin >> n;
	for(int i = 2,fa;i<=n;i++)cin >> fa,cnt[fa]++;
	for(int i = 1;i<=n;i++)cout << cnt[i] << endl;
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)

ll lcs( const vector<ll>& s, const vector<ll>& t )
{
	// dp[i][j] : sのi番目とtのj番目までの共通部分列個数
	vector< vector<ll> > dp( s.size()+1, vector<ll>( t.size()+1, 0 ) );
	dp[0][0] = 1;
	REP(i,s.size()+1) dp[i][0]=1;
	REP(j,t.size()+1) dp[0][j]=1;
	REP( i, s.size() ) REP( j, t.size() )
	{
		dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j];
		dp[i+1][j+1] = ( dp[i+1][j+1] + cMOD ) % cMOD;
		if( s[i] == t[j] )
		{
			dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j];
			dp[i+1][j+1] = dp[i+1][j+1]%cMOD;
		}
	}
	return dp[s.size()][t.size()];
}

int main()
{
	ll n,m; cin>>n>>m;
	vector<ll> s(n,0),t(m,0);
	REP(i,n)cin>>s[i];
	REP(j,m)cin>>t[j];

	cout << lcs(s,t) << endl;
	return 0;
}

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

void code()
{
    ll n;
    cin>>n;
    ll A[n];
    for(ll i=0;i<n;i++)
    {
        cin>>A[i];
    }
    ll s=1000;
    for(ll i=0;i<n-1;i++)
    {
        ll j=0;
        if(A[i]<A[i+1])j=s/A[i];
        s+=(A[i+1]-A[i])*j;        
    }
    cout<<s<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    // cin>>t;
    while(t--)
    {
        code();
    }
}

Measured memory_bytes: 3664
N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-(i+1))
C=sorted(B)
ans=0
bns=0
if N%2==1:
  a=C[(N-1)//2]
  for i in range(N):
    ans+=abs(A[i]-(a+i+1))
  print(ans)
else:
  a=C[N//2]
  b=C[N//2-1]
  for i in range(N):
    ans+=abs(A[i]-(a+i+1))
    bns+=abs(A[i]-(b+i+1))
  print(min(ans,bns))

Measured memory_bytes: 26020
#include<stdio.h>

int main(void){
    int K, N, distance = 0, max_num = 0;
    scanf("%d %d",&K, &N);
    int A[N], difference[N];
    for(int i = 0; i < N; i++){
        scanf("%d",&A[i]);
    }
    for(int i = 1; i < N; i++){
        difference[i-1] = A[i] - A[i-1];
    }
    difference[N-1] = (K - A[N-1]) + A[0];

    for(int i = 1; i < N; i++){
        if(difference[i] > difference[max_num]){
            max_num = i;
        }
    }
    for(int i = 0; i < N; i++){
        distance += difference[i];
    }
    distance -= difference[max_num];
    printf("%d\n",distance);
    return 0;
}

Measured memory_bytes: 1664
/***
	chauhan176's code

	Nothing Happens , It's True
***/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define ld long double
#define fi first
#define se second
#define mod 1000000007
#define maxn 300005
#define all(v) v.begin(),v.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define go_t int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;

typedef pair<int,int>pi;
const ll inf = 1e10;//0x3f3f3f3f3f3f3f3fll;//4x10e18
const int maxx = 10000000;
#define PI 3.14159265
ll power(ll x,ll y,ll p)
{
    ll res = 1;
    x = x % p;

    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
    fastio;
    ll x,y;
    cin>>x>>y;
    if((x+y)%3!=0)
    {
        cout<<0<<endl;
        return 0;
    }
    ll ti = (x+y)/3;
    pi one = {2*ti , ti};
    ll dif = y-ti;
    if(dif<0 || ti<0 || dif > ti)
    {
        cout<<0<<endl;
        return 0;
    }
    //trace4(ti,one.fi,one.se,dif);
    ll ans = 1;
    for(int i=ti;i>1;i--)
    {
        ans = ans*i;
        ans%=mod;
    }
    ll den = 1;
    for(int i=2;i<=dif;i++)
    {
        den = den*power(i,mod-2,mod);
        den = den%mod;
    }
    for(int i=2;i<=(ti-dif);i++)
    {
        den = den*power(i,mod-2,mod);
        den = den%mod;
    }
    //cout<<den<<endl;
    ans = (ans*den)%mod;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
using namespace std;

const int INF=12345678;
int n;
vector<int> nei[100005];
int dist[2][100005],used[100005];
queue<int> q;

void BFS(int x){
	int sign=0;
	if(x==1) sign=0;
	else sign=1;
	for(int i=1;i<=n;i++){
		used[i]=0;
		dist[sign][i]=INF;
	}
	used[x]=1;
	dist[sign][x]=0;
	q.push(x);
	while(!q.empty()){
		int now=q.front();
		used[now]=1;
		q.pop();
		for(int i=0;i<nei[now].size();i++){
			if(used[nei[now][i]]) continue;
			dist[sign][nei[now][i]]=dist[sign][now]+1;
			q.push(nei[now][i]);
		}
	}
}

int main(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	BFS(1);
	BFS(n);
	int tot1=0,totn=0;
	for(int i=1;i<=n;i++){
		//cout<<dist[0][i]<<" "<<dist[1][i]<<endl;
		if(dist[0][i]<=dist[1][i]) tot1++; else totn++;
	}
	if(tot1>totn) puts("Fennec");
	else puts("Snuke");
	return 0;
}

Measured memory_bytes: 7040
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string n;
	cin >> n;
	for(int i=0; i<n.size(); ++i){
		if( n[i] == '9' )	n[i] = '1';
		else if( n[i] == '1' )	n[i] = '9';
		cout << n[i];
	}
	cout << endl;	 
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
 long long N, T;
 cin >> N >> T;
 long long t[N+1];
 for(int i=0; i<N; ++i)
   cin >> t[i];
  
 long long sum = 0;
  
 for(int i=0; i<N-1; ++i) {
   if(t[i+1]-t[i]<T) sum += t[i+1]-t[i];
   else sum += T;
 }
  
 cout << sum + T << endl;
  
 return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
    #define loop(i,a,b) for(int i=a;i<b;i++)
    #define loopb(i,a,b) for(int i=a;i>=b;i--)
    #define loopm(i,a,b,step) for(int i=a;i<b;i+=step)
    #define loopbm(i,a,b,step) for(int i=a;i>=b;i-=step)
    #define pb(a) push_back(a)
    #define mp(a,b) make_pair(a,b)
    #define init(arr,val) memset(arr,val,sizeof(arr))
    #define INF 1000000007
    #define MOD 1000000007
    #define BINF 1000000000000000001
    #define int long long int
    #define double long double
     
    using namespace std;
 
	vector<int>costs;

int dp[100005];
	
int go(int N)
{
	if(N==0) return 0;
	
	else if(dp[N]>=0) return dp[N];
	
	else
	{
		int ans=INT_MAX;
		loop(i,0,costs.size())
		{
			if(costs[i]>N) break;
			else
			{
				ans=min(ans,go(N-costs[i])+1);
			}
		}
		
		dp[N]=ans;
		return ans;
	}
}
  
    
     
    #undef int
    int main()
    {
    #define int long long int
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
       // freopen("input.txt","r",stdin);
        
        int t=1;
        //cin>>t;
        while(t--)
        {
        	int N;
        	cin>>N;
        	costs.push_back(1);
        	int fxp=6;
        	
        	while(fxp<=N)
        	{
        		costs.push_back(fxp);
        		fxp*=6;	
        	}
        	costs.pb(fxp);
        	
        	fxp=9;
        	while(fxp<=N)
        	{
        		costs.push_back(fxp);
        		fxp*=9;
        	}
        	costs.pb(fxp);
        	sort(costs.begin(),costs.end());
        	
        	loop(i,0,N+1) dp[i]=-1;
        	
        	int ans=go(N);
        	cout<<ans;
        	
        }
             
            
        
        return 0;
    } 

Measured memory_bytes: 4224
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
bool visited[100005];
const int max_N=1e5+10;
string s;
int main(void)
{
  cin >> s;
  for (int i = 0; i < int(s.size()-1); i++)
  {
    if(s[i]==s[i+1])
    {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <sstream>
#include <iterator>
#include <sstream>
#include <iomanip>
#include <istream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main()
{
   int n, m;
   cin >> n >> m;
   if(n > 8 || m > 8) cout << ":(";
   else cout << "Yay!";
   
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
alist = [] # yen
blist = [] # 本数
n.times do |i|
  alist[i], blist[i] = gets.split.map(&:to_i)
end

ans = 0
[*0...n].sort_by{|i| alist[i]}.each do |i|
  a = alist[i]
  b = blist[i]

  if m <= b # 残りの本数が少ない場合
    ans += m * a
    break
  else
    ans += a * b
    m -= b
  end
end

p ans

Measured memory_bytes: 8176
n = int(input())

a = [int(x) for x in input().split()]

b = [0] * 9
for i in range(n):
    if a[i] // 400 < 8:
        b[a[i] // 400] += 1
    else:
        b[8] += 1

minsum = 0
maxsum = 0

for i in range(8):
    if b[i] > 0:
        minsum += 1

maxsum = minsum
maxsum += b[8]

if minsum == 0:
    minsum = 1

print("{} {}".format(minsum, maxsum))


Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int cnt_a=0,cnt_w=0,cnt_t=0,cnt_r=0;
  for(int i=0;i<n;i++){
    string s;
    cin >> s;
    if(s=="AC"){
      cnt_a++;
    }
    if(s=="WA"){
      cnt_w++;
    }
    if(s=="TLE"){
      cnt_t++;
    }
    if(s=="RE"){
      cnt_r++;
    }
  }
  cout << "AC x " << cnt_a << endl;
  cout << "WA x " << cnt_w << endl;
  cout << "TLE x " << cnt_t << endl;
  cout << "RE x " << cnt_r << endl;
}
  


Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
   int n;
   cin>>n;
   vector<int> v(n),c(n);
   for(auto &it:v)cin>>it;
   for(auto &it:c)cin>>it;
   int a,b;
   a=0,b=0;
   for(int i=0;i<n;i++){
	    if(v[i]>c[i]){
		   a+=v[i];
		   b+=c[i];	
		} 
	  }
	  cout<<a-b<<endl;
}
int32_t main(){
  IOS;
  solve();
  //debug();
 #ifdef LOCAL_DEFINE
 cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
 #endif	
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;
typedef vector<bool> vb;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sq(x) ((x)*(x))
#define fo(i,n) for(int i=0;i<n;i++)
#define fp(i,k,n) for(int i=k;i<n;i++)
#define Fo(i,n) for(int i=1;i<=n;i++)
#define all(x) x.begin(),x.end()
#define deb(x) cout<<#x<<"="<<x<<"\n"
#define deb2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<"\n"
#define fi first
#define se second
const double pi = 3.14159265358979323846;
#define uni(c) (c).resize(unique(all(c))-(c).begin())
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
//pair <int, int> w[4] = {mp(-1, 0), mp(0, -1), mp(1, 0), mp(0, 1)};   // for matrix movement:
void cp()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
void solve()
{
	ll x, n; cin >> x >> n;
	vi a, b;
	ll flag = 0;
	ll cur = x - 1, cur1 = x;
	fo(i, n)
	{
		ll p; cin >> p;
		if (p == x)
			flag = 1;
		if (p >= x)
			a.pb(p);
		else
			b.pb(p);
	}
	sort(all(a));
	sort(all(b), [](ll d, ll f)
	{
		return d > f;
	});
	ll i = 0, j = 0;
	if (flag == 1) {
		i++;
		cur1++;
	}
	while (i < a.size() or j < b.size())
	{
		if (j < b.size() and b[j] != cur)
		{
			cout << cur;
			return;
		}
		else
		{
			if (j < b.size())
				cur--;
		}
		if (i < a.size() and a[i] != cur1)
		{
			cout << cur1;
			return;
		}
		else {
			if (i < a.size())
				cur1++;
		}
		i++;
		j++;
	}
	if (abs(cur1 - x) >= abs(cur - x))
		cout << cur;
	else
		cout << cur1;




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


	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define nl cout<<"\n"
#define fr(n) for(int i = 0; i<n; i++)
#define frr(j, n) for(int i = j; i<n; i++)
#define Mem(x) memset(x, 0, sizeof(x))
using namespace std;
typedef long long int lli;

int main(){
    lli d, t, s;
    cin>>d>>t>>s;
    if(s*t>=d)cout<<"Yes";
    else cout<<"No";
    return 0;
}

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

n = int(input())
ans = 0

for i in range(1,n+1):
  if len(make_divisors(i)) == 8 and i%2 == 1:
    ans += 1

print(ans)

Measured memory_bytes: 38640
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 10

n = int(input())
h = [0] + list(map(int, input().split()))
dp = [INF] + [INF] * n
dp[1] = 0

def chmin(dp_table, index, value):
    if dp_table[index] > value:
        dp_table[index] = value

for i in range(2, n+1):
    chmin(dp, i, dp[i-1] + abs(h[i] - h[i-1]))
    chmin(dp, i, dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n])


Measured memory_bytes: 52116