akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i

N = INT()
H = LIST()
A = LIST()

bit = BIT(N+1, max, 0)
for h, a in zip(H, A):
    # ここより手前で出現した自分より低い花から、一番いいところを取る
    mx = bit.query(h)
    # 自身の最善の値を更新
    bit.update(h, mx + a)
ans = bit.query(N)
print(ans)


Measured memory_bytes: 109012
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define fastio                        \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(NULL);
#define pb push_back
#define mp make_pair

typedef long long ll;

using namespace std;

int main()
{
    fastio;
    int n;
    cin>>n;
    int *a = new int[n];
    for (int i =0;i<n;i++) {
        cin>>a[i];

    }
    int count = 0;
    while (true) {
        bool even = false;
        for (int i=0;i<n;i++) {
            if (!(a[i]&1)) {
                even = true; count++; 
                a[i]/=2;break;
            }
        }
        if(even == false){
            cout<<count<<endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 3652
#pragma warning disable

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
// Do not use: System.Numerics;

public class Test
{
    public static void Main()
    {
        var S = Console.ReadLine();
        var T = Console.ReadLine();
        var n = Int32.Parse(Console.ReadLine());

        var SA = new int[S.Length + 1];  // Sのi-1文字目までの累計のAの文字数
        var SB = new int[S.Length + 1];
        var TA = new int[T.Length + 1];
        var TB = new int[T.Length + 1];

        int a = 0;
        int b = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == 'A')
            {
                a++;
            }
            else
            {
                b++;
            }
            SA[i + 1] = a;
            SB[i + 1] = b;
        }

        a = 0;
        b = 0;
        for (int i = 0; i < T.Length; i++)
        {
            if (T[i] == 'A')
            {
                a++;
            }
            else
            {
                b++;
            }
            TA[i + 1] = a;
            TB[i + 1] = b;
        }

        for (int i = 0; i < n; i++)
        {
            var line1 = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();

            int SACount = SA[line1[1]] - SA[line1[0] - 1];
            int SBCount = SB[line1[1]] - SB[line1[0] - 1];
            int TACount = TA[line1[3]] - TA[line1[2] - 1];
            int TBCount = TB[line1[3]] - TB[line1[2] - 1];

            int diff = (SACount - SBCount) - (TACount - TBCount);

            if (diff % 3 == 0)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}

Measured memory_bytes: 19892
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,ans = 0;
  cin>>N;
  vector <int> num1(N);
  vector <int> num2(N);
  for(int i = 0;i<N;i++){
    cin >> num1.at(i) >> num2.at(i);
    ans += num2.at(i)-num1.at(i)+1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

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

    vector<int64> ans;

    vector<int64> aa(a);
    vector<int64> bb(b);

    int64 amin = INT_MAX;
    int64 bmin = INT_MAX;
    for (int64 i=0; i<a; i++) { cin >> aa[i]; amin=min(amin,aa[i]);}
    for (int64 i=0; i<b; i++) { cin >> bb[i]; bmin=min(bmin,bb[i]);}

    ans.push_back(amin+bmin);

    for (int64 i=0; i<m; i++) {
        int64 x,y,c;
        cin >> x >> y >> c;
        ans.push_back(aa[x-1] + bb[y-1] - c);
    }

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

    cout << ans[0] << endl;
}

Measured memory_bytes: 2936
#include <iostream>
using namespace std;
const int MAXN=1e6+7;
int n,k,a[MAXN],f[MAXN][2];
int DFS(int s,int t)
{
	//cout<<"@@@ "<<s<<" "<<t<<endl;
	if(f[s][t]) return f[s][t];
	int ans=0;
	for(int i=1;i<=n;i++)
		if(s>=a[i]) ans|=!DFS(s-a[i],!t);
	return f[s][t]=ans;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(DFS(k,0)==false) cout<<"Second"<<endl;
	else cout<<"First"<<endl;
	return 0;
}

Measured memory_bytes: 9036
from collections import defaultdict

import sys
sys.setrecursionlimit(10**6)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    n=list(input())
    for s in n:
        if s=='7':
            print('Yes')
            exit()
    print('No')



if __name__ == "__main__":
    main()

Measured memory_bytes: 9352
def main():
    N = int(input())
    W_before = input()
    word_set = set()
    word_set.add(W_before)
    for i in range(N-1):
        W_after = input()
        if W_before[-1] != W_after[0]:
            print('No')
            return
        if W_after in word_set:
            print('No')
            return
        word_set.add(W_after)
        W_before = W_after
    print('Yes')

if __name__ == "__main__":
    main()


Measured memory_bytes: 9128
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    ll n;
    ll a[100010];
    ll count[100010];
    Fill(count,0);
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        count[ a[i] ]++;
    }
    ll result = 0;
    for (int i = 0; i <= 100000; i++) {
        result = max(result,count[i]+count[i+1]+count[i+2]);
    }
    std::cout << result << std::endl;
    return 0;
}


Measured memory_bytes: 1792
from sys import stdin

A = list(map(int,stdin.readline().split()))
B = list(map(int,stdin.readline().split()))
C = [x for x in range(-10,110)]
C = set(C)
B = set(B)
C = C.difference(B)
C = list(C)
X=A[0]
N=A[1]
record=200
number=1000
K=0

if N==0:
    print(X)
    K=1

for t in C:
    diff=abs(t-X)
    if diff<record:
        record=diff
        number=t
    elif diff==record:
        number=min(number,t)

if K==0:
   print(number)

Measured memory_bytes: 9236
N = int(input())
A = [0] + list(map(int,input().split())) + [0]
B = [abs(A[i] - A[i+1]) for i in range(0,N+1)]
C = [abs(A[i] - A[i+2]) for i in range(0,N)]
S = sum(B)
for i in range(N):
    print(S-B[i]-B[i+1]+C[i])

Measured memory_bytes: 16640
n,k=map(int,input().split())
m=10**9+7

k=min(k,n-1)
t,c,h=1,1,1
for i in range(1,k+1):
  p=pow(i,m-2,m)
  c=(c*(n-i+1)* p)%m
  h=(h*(n-i)  * p)%m
  t=(t+c*h)%m

print(t%m)


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

using namespace std;

typedef long long ll;

int n;
int arr[110];

int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d",&arr[i]);
    int j=0, ans = 0;
    for (i=0;i<n;i=j) {
        for (j=i;j<n&&arr[j]==arr[i];j++);
        ans += (j-i)/2;
    }
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 256
// Author : MohamedSameh
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
int n ;
int a[100000];
int main ()
{
    scanf ("%d" , &n );
    for (int i =0 ; i < n ;i++){
            int v ;
            scanf ("%d" , &v );
            a[v-1] = i ;
    }
    for (int i =0 ; i < n ;i++)printf ("%d ", a[i] + 1 );
 return 0 ;
}


Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		scan.close();
		System.out.println(((a*b)%2==0)? "Even":"Odd");

	}

}


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

int main()
{
	int N;
	cin >> N;
	int ans = 0;
	rep(i,N)
	{
		cin >> a[i];
		if (i % 2 == 0 && a[i] % 2 == 1) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int A = sc.nextInt();
      int B = sc.nextInt();
      if(A+B>=A-B&&A+B>=A*B){
        System.out.println(A+B);
      }else if(A-B>=A+B&&A-B>=A*B){
        System.out.println(A-B);
      }else if(A*B>=A+B&&A*B>=A-B){
        System.out.println(A*B);
      }
    }
}
      

Measured memory_bytes: 35672
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

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

int main(){
    ll N;
    ll ans =0;
    cin>>N;
    if(N>=105)ans++;
    if(N>=135)ans++;
    if(N>=189)ans++;
    if(N>=165)ans++;
    if(N>=195)ans++;
    cout<<ans;
    return 0;
}

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

using namespace std;

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

    long long int a, b, k;
    cin >> a >> b >> k;

    if (k<=a)
        a -= k;
    else if (k<=a+b) {
        b -= k-a;
        a = 0;
    }
    else {
        a = 0;
        b = 0;
    }

    cout << a << " " << b << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define OPEMAX (10000000)

struct stack{
  int index;
  double ope[OPEMAX];
} stackope;

char *getstringcopy(char *str)
{
  char *cpdata = (char*)malloc(sizeof(char)*strlen(str));
  strcpy(cpdata,str);
  return cpdata;
}

char **getformula()
{
  int i, c, ci;
  char **formula = (char**) malloc(sizeof(char*)*500);
  char el[20];

  i = 0;
  ci = 0;
  while ( -1 )
  {
    c = getchar();
    if (c == ' ' || c == '\n')
    {
        el[ci]='\0';
        formula[i] = getstringcopy(el);
        ci = 0;
        i++;
        if (c == '\n') break;
    }
    else
    {
      el[ci]= c;
      ci++;
    }
  }
  formula[i]=NULL;
  return formula;
}

int countel(char **formula)
{
  int i;
  for(i=0; formula[i] != NULL; i++);
  return i;
}
void initstackope(void)
{
  stackope.index = 0;
}

void pushope(double ope)
{
  stackope.ope[stackope.index] = ope;
  stackope.index++;
}

double popope(void)
{
  stackope.index--;
  return (stackope.ope[stackope.index]);
}


void freeformula(char **formula)
{
  for(int i=0; formula[i] != NULL; i++)
    free(formula[i]);

  free(formula);
}

double calcope(char rator, double a, double b)
{
  if (rator == '+')
    return (a + b);
  else if (rator == '-')
    return (b - a);
  else if (rator == '*')
    return (b*a);
  else if (rator == '/')
    return (b/a);

  return (a+b);
}

double calcpo(char **formula)
{
  int count = countel(formula);

  for(int i=0; i < count; i++)
  {
    if('0' <= formula[i][0] && formula[i][0] <= '9')
    {
      pushope(atof(formula[i]));
    }else{
      double a,b;
      a = popope();
      b = popope();
      a = calcope(formula[i][0], a, b);
      pushope(a);
    }
  }

  return (popope());
}

int main(void)
{
  char **formula;
  double res;
  formula = getformula();
  int count = countel(formula);
  
  printf("%d\n",(long)calcpo(formula));
  freeformula(formula);

}



Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
using namespace std;

#define sz(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define mp make_pair
typedef pair<int, int> pii;
//////////////////////////

int const N = 2e5 + 41;
int const MOD = 1e9 + 7;

void add(int &a, int b){
	a += b;
	if(a >= MOD) a -= MOD;
}

void sub(int &a, int b){
	a -= b;
	if(a < 0) a += MOD;
}

int mul(int a, int b){
	return a * 1LL * b % MOD;
}

int bp(int x, int d){
	if(!d) return 1;
	if(d&1) return mul(x, bp(x, d-1));
	int r = bp(x, d/2);
	return mul(r, r);
}

int f[N], invF[N];

int getC(int n, int k){
	if(k > n) return 0;
	int ret = f[n];
	ret = mul(ret, invF[k]);
	ret = mul(ret, invF[n-k]);
	return ret;
}

void solve(){
	f[0] = invF[0] = 1;
	rep(i, 1, N){
		f[i] = mul(f[i-1], i);
		invF[i] = bp(f[i], MOD-2);
	}
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	int ans = getC(h - 1 + w - 1, h - 1);
	int wb = 0;
	int r = h - a + 1;
	rep(i, 1, b+1){
		int wc = getC(r - 1 + i - 1, i - 1);
		sub(wc, wb);
		add(wb, wc);
		wc = mul(wc, getC(h - r + w - i, w - i));
		sub(ans, wc);
	}

	cout << ans << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();


	return 0;
}

Measured memory_bytes: 1792
n,m = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(n)]
from itertools import *
res = 0
for a in product([-1, 1], [-1, 1], [-1, 1]):
  res = max(res, sum(sorted((sum(i*j for i,j in zip(a,t)) for t in x),reverse=True)[:m]))
print(res)

Measured memory_bytes: 3284
input = input()
s_input = input.split()
x = int(s_input[0])
a = int(s_input[1])
b = int(s_input[2])

kigenchouka = b - a

if kigenchouka > x:
    print("dangerous")
else:
    if kigenchouka <= 0:
        print("delicious")
    else:
        print("safe")


Measured memory_bytes: 9076
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = sum(a)
for i in range(n):
    a[i] = a[i] - b[i]
    if a[i] < 0:
        a[i+1]=a[i+1]+a[i]
        if a[i+1] < 0:
            a[i+1] = 0
        a[i] = 0

print(ans-sum(a))

Measured memory_bytes: 19116
// -*- coding:utf-8-unix -*-

use proconio::input;

// n^p mod m (繰り返し二乗法)
fn repeat_square(n: u64, p: u64, m: u64) -> u64 {
    if p == 0 {
        1
    } else if p == 1 {
        n % m
    } else if p % 2 == 0 {
        repeat_square(n, p / 2, m).pow(2) % m
    } else {
        (n * repeat_square(n, p - 1, m)) % m
    }
}

// m が素数であること
fn ncr_mod(n: u64, r: u64, m: u64) -> u64 {
    let mut denominator = n;
    let mut numerator = 1;
    for i in 1..r {
        denominator = (denominator * (n - i)) % m;
        numerator = (numerator * (i + 1)) % m;
    }
    (denominator * repeat_square(numerator, m - 2, m)) % m
}

fn main() {
    input! {
        n: u64,
        a: u64,
        b: u64,
    }

    let divisor = 10_u64.pow(9) + 7;
    let mut ans: u64 = repeat_square(2, n, divisor) - 1;

    ans = (ans + divisor - ncr_mod(n, a, divisor)) % divisor;
    ans = (ans + divisor - ncr_mod(n, b, divisor)) % divisor;

    println!("{}", ans);
}


Measured memory_bytes: 2160
n, m = map(int,input().split())
h = list(map(int,input().split()))

rem_list = []

for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] <= h[b-1]:
        rem_list.append(a-1)
    if h[b-1] <= h[a-1]:
        rem_list.append(b-1)

print(n-len(set(rem_list)))


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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int A, P;
	cin>>A>>P;
	cout<<(3*A+P)/2<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n,k,q;
  cin >> n >> k >> q;
  vector<ll> p(n);
  //for(int i = 0;i < n;i++)p[i] = 0;
  //cout << p[0] << endl;
  for(int i = 0;i < q;i++){
    ll in;
    cin >> in;
    in--;
    p[in]++;
  }
  for(int i = 0;i < n;i++){
    if(q - k < p[i])cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 4056
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
int main() {
	int n, l;
	scanf("%d %d", &n, &l);
	int app[n];
	int flav[n];
	int tot_flav=0;
	for(int i=0; i<n; i++)
	{
	    app[i]=i+1;
	    flav[i]=l+app[i]-1;
	    tot_flav+=flav[i];
	}
    int pos_flav[n];
    for(int i=0; i<n; i++)
    {
        pos_flav[i]=tot_flav-flav[i];
    }
    int diff[n];
    int min=1000;
    int p;
    for(int i=0; i<n; i++)
    {
        diff[i]=abs(tot_flav-pos_flav[i]);
        if(diff[i]<min)
        {
            p=i;
            min=diff[i];
        }
    }
    printf("%d", pos_flav[p]);
	return 0;
}

Measured memory_bytes: 128
// Package main provides
//
// File:  b.go
// Author: ymiyamoto
//
// Created on Sat Jan  5 15:33:40 2019
//
package main

import (
	"fmt"
	"sort"
)

func min(slice ...int) int {
	sort.Ints(slice)
	return slice[0]
}

func main() {
	var N int
	fmt.Scan(&N)

	arr := make([]int, N)
	for i := 0; i < N; i++ {
		var a int
		fmt.Scan(&a)

		count := 0
		for a%2 == 0 {
			a /= 2
			count++
		}
		arr[i] = count
	}
	fmt.Println(min(arr...))
}


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

int main() {
  int A;
  cin>>A;
  int B;
  cin>>B;
  int a=0;
  
  while(A<B+1){
    if (A/10000==A%10&&A/1000-A/10000*10==(A%100-A%10)/10)
      a++;
    A++;}
  cout<<a<<endl;
  
    
}

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

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int ans = (N - 1 + K - 2) / (K - 1);
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	private static final long x = (long) Math.pow(10, 18);

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int c = (int)s.charAt(0);

		if ((int)'a' <= c && c <= (int)'z') {
			System.out.println("a");
		} else {
			System.out.println("A");
		}

		sc.close();
	}

}


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

int main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    ll a[x], b[y], c[z];
    for (int i = 0; i < x; i++) cin >> a[i];
    for (int i = 0; i < y; i++) cin >> b[i];
    for (int i = 0; i < z; i++) cin >> c[i];
    priority_queue<ll> que, ans;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            que.push(a[i] + b[j]);
        }
    }
    sort(c, c + z, greater<ll>());
    for (int i = 0; i < k && !que.empty(); i++) {
        ll t = que.top(); que.pop();
        for (int j = 0; j < min(k, z); j++) {
            ans.push(t + c[j]);
        }
    }
    for (int i = 0; i < k; i++) {
        cout << ans.top() << endl;
        ans.pop();
    }
}

Measured memory_bytes: 44084
import java.util.*;

class Main
{

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

        int A = scan.nextInt();
        int B = scan.nextInt();
        int X = scan.nextInt();
        int n;
        int o;
        int t;
        int g;
        int z;
        int y;


        n = X / 1000;
	
        if (X % 1000 == 0) {
            o = A * n;
        } else {
            o = A * (n + 1);
        }


        t = X / 500;

        if (X % 500 == 0) {
            g = B * t;

        } else {
            g = B * (t + 1);         
        }


        int mini = 99999999;
        int nedan;

        for (int i = 0; i < 1000; i++) {
            if (X >= i * 1000) {
                z = X - (i * 1000);

                y = z / 500;
                if (z % 500 == 0) {
                    nedan = i * A + y * B;
                }else{
                    nedan = i * A + (y + 1) * B;
                }
                if (mini >= nedan) {
                    mini = nedan;
                }
            }
        }
        if (0 < g && o < mini) {
            System.out.println(o);

        } else if (g < o && g < mini) {

            System.out.println(g);

        } else if (mini <= o && mini <= g) {
            System.out.println(mini);
            
        }
    }
}



Measured memory_bytes: 26364
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
#define LLINF 2000000000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
#define int long long

signed main(){
  int n,k;
  cin >> n >> k;
  int h[n];
  LOOP(i,n){
    cin >> h[i];
  }
  sort(h,h+n);
  int ans = 0;
  LOOP(i,n-k){
    ans += h[i];
  }cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define rep(i, a, b) for(int i = a; i < b; ++i)

const int N = 5e5;

int n, a[N];
map <int, int> c;

main() {
	cin >> n;
	rep(i, 1, n + 1) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = n; i >= 1; --i) {
		ans += c[a[i] + i];
		c[i - a[i]]++;
	}
	cout << ans << '\n';
}

Measured memory_bytes: 27748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll ans=INF;
	for(ll i=1;i<=sqrt(n);i++){
		if(n%i==0){
			ans=min(ans,n/i+i-2);
		}
	}
	cout <<ans;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Here your code !
    int n,i,j;
    int a[200000];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    if(n%2 == 0){
        for(i=n-1;i>0;i-=2){
            printf("%d ",a[i]);
        }
        for(j=0;j<n;j+=2){
            printf("%d ",a[j]);
        }
    }
    else {
        for(i=n-1;i>=0;i-=2){
            printf("%d ",a[i]);
        }
        for(j=1;j<n;j+=2){
            printf("%d ",a[j]);
        }
        
    }
    printf("\n");
    
    
    return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <math.h>
#include <string>
#include <iomanip>
using namespace std;

int main(void)
{
	int n, x[100], y[100], i;
	double d1 = 0, d2, d3, di = 0, sum2 = 0, sum3 = 0;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> x[i];
	}

	for (i = 0; i < n; i++) {
		cin >> y[i];
	}

	for (i = 0; i < n; i++) {
		d1 += (double)fabs(x[i] - y[i]);
		sum2 += pow(fabs(x[i] - y[i]), 2);
		sum3 += pow(fabs(x[i] - y[i]), 3);
		if (di < fabs(x[i] - y[i])) {
			di = (double)fabs(x[i] - y[i]);
		}
	}

	d2 = pow(sum2, (double)(1) / (double)(2));
	d3 = pow(sum3, (double)(1) / (double)(3));

	cout << setprecision(10) << d1 << endl;
	cout << setprecision(10) << d2 << endl;
	cout << setprecision(10) << d3 << endl;
	cout << setprecision(10) << di << endl;
}


Measured memory_bytes: 3460
#include<cstdio>
#include<cstring>
#define N 505
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x<y?y:x;}
int A[N],B[N][N],C[N][N],D[N][N],E[N][N],F[N][N],X,a[N][N],b[N][N],d[N],e[N],f[N][N],g[N],h,i,j,k,o,p,q[N],t;char c[N][N],s[N][N];long long x;
inline int get(int x,int y,int z){return f[x][y]<=z?z=min(z,min(d[x],d[y])),A[z]-B[z][x+1]-C[z][y-1]+D[x+1][y-1]:0;}
inline void solve(int m,int n)
{
    for(i=1;i<=m;i++)a[i][0]=a[i][n+1]=n+1,b[i][0]=b[i][n+1]=E[i][n+1]=0,E[i][0]=m+1;
    for(j=1;j<=n;j++)a[0][j]=a[m+1][j]=n+1,b[0][j]=b[m+1][j]=E[m+1][j]=0,E[0][j]=m+1;
    for(i=0;i<=n;i++)memset(D[i+1],0,n+1<<2),memset(F[i]+1,0x3f,n+1<<2);
    for(h=m+2>>1,memset(A+h-1,0,m-h+2<<2),i=h-1;i<=m;i++)memset(B[i]+1,0,n+1<<2),memset(C[i],0,n+1<<2);
    for(j=1;j<=n;j++)!c[h][j]?a[h][j]=n+1,b[h][j]=0:a[h][b[h][j]=j]=min(a[h][j-1],j);
    for(i=h+1;i<=m;i++)for(j=1;j<=n;j++)c[i][j]?a[i][j]=min(a[i-1][j],a[i][j-1]),b[i][j]=max(b[i-1][j],b[i][j-1]):(a[i][j]=n+1,b[i][j]=0);
    for(i=m;i>=h;i--)for(j=n;j;j--)E[i][j]=c[i][j]?max(max(E[i+1][j],E[i][j+1]),i):0;
    for(memcpy(d+1,E[h]+1,n<<2),i=1;i<=h;i++)for(j=1;j<=n;j++)E[i][j]=c[i][j]?min(min(E[i-1][j],E[i][j-1]),i):m+1;
    for(memcpy(e+1,E[h]+1,n<<2),i=m;h<=i;i--)for(j=1;j<=n;j++)if(a[i][j]<=b[i][j])A[i]+=c[i][j],B[i][a[i][j]]+=c[i][j],C[i][b[i][j]]+=c[i][j],D[a[i][j]][b[i][j]]+=c[i][j],F[a[i][j]][b[i][j]]=i;
    for(i=h;i<=m;i++)for(j=1;j<=n;j++)C[i][j]+=C[i-1][j]+C[i][j-1]-C[i-1][j-1];
    for(i=h;i<=m;A[i]+=A[i-1],i++)for(j=n;j;j--)B[i][j]+=B[i-1][j]+B[i][j+1]-B[i-1][j+1];
    for(i=n;i;i--)for(j=1;j<=n;j++)D[i][j]+=D[i+1][j]+D[i][j-1]-D[i+1][j-1];
    for(i=1;i<=n;i++)for(j=n;j;j--)F[i][j]=min(min(F[i-1][j],F[i][j+1]),F[i][j]);
    for(i=1;i<=n;i++)for(j=i;j<=n;j++)f[i][j]=F[i][j]<=min(d[i],d[j])?F[i][j]:m+1;
    for(j=n;j;j--)!c[h][j]?a[h][j]=n+1,b[h][j]=0:b[h][a[h][j]=j]=max(b[h][j+1],j);
    for(i=h;--i;)for(j=n;j;j--)c[i][j]?a[i][j]=min(a[i+1][j],a[i][j+1]),b[i][j]=max(b[i+1][j],b[i][j+1]):(a[i][j]=n+1,b[i][j]=0);
    for(i=1;i<h;i++)for(j=1,k=t=1,X=o=p=0;j<=n;j++)if(a[i][j]<=b[i][j])
    {
        while(k<=b[i][j])
        if(e[k]<=i)
        {
            for(q[p]=0;o<p&&d[q[p]]<d[k];p--)X-=g[q[p-1]],X+=g[q[p-1]]-=get(q[p-1],k,min(d[q[p-1]],d[k]))-get(q[p-1],k,min(d[q[p]],d[k]));
            X+=g[q[++p]=k]=get(k,k,m),p++,k++;
        }
        else k++;
        while(t<a[i][j])e[t]<=i?X-=g[t]:0,t++;
        while(o<p&&q[o]<a[i][j])o++;
        x+=X*c[i][j];
    }
}
void dfs(int l,int r,int L,int R)
{
    if(l==r&&L==R)return;
    else if(r-l<R-L)
    {
        for(i=0;i<=R-L;i++)for(j=0;j<=r-l;j++)c[i+1][j+1]=s[j+l][i+L];
        solve(R-L+1,r-l+1),dfs(l,r,L,L+R-1>>1),dfs(l,r,L+R+1>>1,R);
    }
    else
    {
        for(i=0;i<=r-l;i++)memcpy(c[i+1]+1,s[i+l]+L,R-L+1<<2);
        solve(r-l+1,R-L+1),dfs(l,l+r-1>>1,L,R),dfs(l+r+1>>1,r,L,R);
    }
}
int n;
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)for(scanf("%s",s[i]+1),j=1;j<=n;j++)s[i][j]=s[i][j]=='#'?0:s[i][j]^48;
    dfs(1,n,1,n),printf("%lld\n",x);
    return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
static const int MAX = 200000;

int main() {
    int R[MAX], n;
    cin >> n;
    for (int i=0; i<n; i++) cin >> R[i];
    int maxv = -2000000000;
    int minv = R[0];

    for (int i=1; i<n; i++) {
        maxv = max(maxv, R[i]-minv);
        minv = min(minv, R[i]);
    }

    cout << maxv << endl;
    return 0;
}


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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> p;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  vector<ll> v(n+1);
  for (ll i = 1; i <= n; i++) {
    cin >> v[i];
  }
  vector<int> b(n+1);

  for (int i = n; i >= 1; i--) {
    int sum = 0;
    for (int j = i+i; j <= n; j += i) {
      sum ^= b[j];
    }
    // cout << sum << endl;
    b[i] = sum^v[i];
  }
  vector<int> res;
  for (int i = 1; i <= n; i++) {
    if(b[i]) res.push_back(i);
  }
  // print(b);

  cout << res.size() << endl;
  for(auto a : res){
    cout << a << ' ';
  }
  cout << endl;

}


Measured memory_bytes: 3832
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)




using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll Nmax=1e9;


// B貪欲法で決定する．
int main(){
  int d;
  cin>>d;
  vector<int> c(26);
  vector<vector<int>> s(d,vector<int>(26));
  vector<int> last(26);
  vector<int>c_inv(26); // iを選んだ際の1日での下がり幅

  ll c_tot=0;
  rep(i,26){
    cin>> c[i];
    c_tot+=c[i];
    last[i]=-1;
  }
  rep(i,26){
    c_inv[i]=c_tot-c[i];
  }

  rep(i,d){//i日目
    int maxs=0;
    int jm=0;

    rep(j,26){
      cin>>s[i][j];
      ll casej=s[i][j]-c_inv[j];

      if(casej>maxs){
        maxs=s[i][j]-c_inv[j];
        jm=j;
      }
    }
    cout<<jm+1<<endl;

  }











}


Measured memory_bytes: 3696
import java.util.*;

public class Main {

    static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
    static int mod = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long K = sc.nextLong();
        long[] A = new long[(int) N];
        long[] teleported = new long[(int) N];

        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
            teleported[i] = -1;
        }

        long currentPoint = 1;
        teleported[0] = 0;
        long warpCount = 0;
        long loop;
        long restOfLoop =0;
        for(long i=0;i<Math.min(N,K);i++){
            warpCount++;
            currentPoint = A[(int) (currentPoint-1)];

            if(teleported[(int) (currentPoint-1)] == -1){
                teleported[(int) (currentPoint-1)] = warpCount;
            } else {
                loop = warpCount - teleported[(int) (currentPoint-1)];
                restOfLoop = (K - teleported[(int) (currentPoint-1)]) % loop;
                break;
            }
        }

        for(long i=0;i<restOfLoop;i++){
            currentPoint = A[(int) (currentPoint-1)];
        }

        System.out.println(currentPoint);

    }

}









Measured memory_bytes: 62724
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18) + 1;
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
string s,t;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s>>t;
    sort(ALL(s));
    sort(ALL(t),greater<char>());
    if(s<t){
        yes;
    }
    else no;
}


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

using namespace std;
int a, b, c, x, y;
int main(){
    cin >> a >> b >> c >> x >> y;
    if(a + b > c * 2){
        int kol = min(x, y);
        x -= kol;
        y -= kol;
        if(x && a > c * 2){
            kol += x;
            x = 0;
        }
        if(y && b > c * 2){
            kol += y;
            y = 0;
        }
        cout << (kol * 2) * 1ll * c + a * 1ll * x + b * 1ll * y;
    }
    else{
        cout << a * 1ll * x + y * 1ll * b;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
typedef unsigned short ushort;
typedef vector <int> vi;

class blanch{
	public:
		bool visited;
		int distance;
		ushort from;
		ushort to;
};
typedef vector <blanch> vb;
typedef vector <vb> vvb;

int make_graph(vvb &graph, vb &nodes){

	int n=nodes.size();
	for (ushort i=0; i<n; i++){
		nodes[i].visited = false;
		nodes[i].distance = INT_MAX;
	}

	for (ushort i=0; i<n; i++){
		int i2, n2;
		cin>>i2;
		cin>>n2;

		blanch tmp;
		tmp.visited = false;
		tmp.from = i2;

		for (ushort j=0; j<n2; j++){
			cin>>tmp.to;
			cin>>tmp.distance;
			graph[i2].push_back(tmp);
		}
	}
	return 0;
}

int Shortest_Path(vvb &graph, vb &nodes){

	int p1=0;
	nodes[p1].distance = 0;

	int p2;
	while (p1 != -1){
		nodes[p1].visited=true;
		for (ushort i = 0; i < graph[p1].size(); i++){
			blanch tmp = graph[p1][i];
			p2=tmp.to;
			if (!nodes[p2].visited){
				int tmp2 = tmp.distance + nodes[p1].distance;
				if (tmp2 < nodes[p2].distance){
					tmp.distance = tmp2;
					nodes[p2] = tmp;
				}
			}
		}

		p1 = -1;
		int tmp = INT_MAX;
		for (ushort i=0; i<graph.size(); i++){
			if (!nodes[i].visited && nodes[i].distance<tmp){
				p1 = i;
				tmp = nodes[i].distance;
			}
		}
	}
	return 0;
}

int resultout(vb &nodes){
	for (ushort i=0; i<nodes.size(); i++){
		cout<<i<<" "<<nodes[i].distance<<endl;
	}
	return 0;
}

int main(void){

	int n;
	cin>>n;
	vvb G(n, vb());
	vb nodes(n);

	make_graph(G, nodes);

	Shortest_Path(G, nodes);

	resultout(nodes);
	G.clear();
	nodes.clear();

	return 0;
} 

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

ULL gcd(ULL a, ULL b) { return b ? gcd(b, a % b) : a; }

int main() {
	ULL W, H, C; cin >> W >> H >> C;
	ULL G = gcd(W, H);
	W /= G; H /= G;
	cout << (W * H * C) << endl;
	return 0;
}



Measured memory_bytes: 3088
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>

typedef unsigned long long ULONG;
typedef long long LONG;
using namespace std;

#define PI 3.1415926535897932384626433
#define _DBG_

#define BIG 10000000000 //10

#define LAST 10000000 //10^7


LONG D;
vector<LONG> cost(26);
//vector<vector<ULONG>> sati(D + 1, vector<ULONG>(27));
vector<vector<LONG>> sati;
vector<LONG> answer;
vector<int> lastDate(26, -1);
LONG satVal = 0;


LONG calcSabunScore(int eventType, LONG date) {

	LONG sabun = sati[date][eventType];
	// costsum
	LONG costSum = 0;
	for (int i = 0; i < 26; i++) {
		if (i != eventType) {
			costSum += cost[i] * (date - lastDate[i]);
		}
	}

	sabun -= costSum;
	

	return sabun;

}


int main(void) {
	// for B

	cin >> D;

	vector<LONG> tmpans(D);
	answer = tmpans;


	for (int i = 0; i < 26; i++) {
		cin >> cost[i];
	}



	for (int d = 0; d < D; d++) {
		vector<LONG> tmpsati(26);
		for (int i = 0; i < 26; i++) {
			cin >> tmpsati[i];
		}
		sati.push_back(tmpsati);
	}
	// finish data input


	// answerを決める
	for (int d = 0; d < D; d++) {
		cin >> answer[d];
		answer[d] -= 1;
	}





	// calc score
	for (int d = 0; d < D; d++) {
		LONG sabun = calcSabunScore(answer[d], d);

		satVal += sabun;

		lastDate[answer[d]] = d;

		cout << satVal << endl;

	}



	return 0;
}

Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    vector<vector<int>> ans(h, vector<int>(w));
    int now = 0;
    rep(i,h) rep(j, w){
        if (a[now] == 0) now++;
        ans[i][j] = now+1;
        a[now]--;
    }
    rep(i,h){
        if (i % 2 != 0) reverse(all(ans[i]));
    }

    rep(i,h){
        rep(j,w){
            printf("%d%c", ans[i][j], j == w-1 ? '\n' : ' ');
        }
    }
    return 0;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)


int main(void){
  int a,b;
  int cnt=1,i=0;
  cin>>a>>b;
  if(b==1)i=0;
  else{
    while(cnt<b){
      cnt=cnt+(a-1);
      i++;
    }
  }
  cout<<i<<endl;


return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iomanip>
#include <ctime>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s1 = "AC", s2 = "WA", s3 = "TLE", s4 = "RE";
    int n, k1 = 0, k2 = 0, k3 = 0, k4 = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == s1) {
            k1++;
            continue;
        }
        if (s == s2) {
            k2++;
            continue;
        }
        if (s == s3) {
            k3++;
            continue;
        }
        if (s == s4)
            k4++;
    }
    cout << s1 << " x " << k1 << endl;
    cout << s2 << " x " << k2 << endl;
    cout << s3 << " x " << k3 << endl;
    cout << s4 << " x " << k4 << endl;

    return 0;
}

Measured memory_bytes: 3652
N = int(input())
L = list(map(int, input().split()))

L.sort()

def bsearch(array, value):
  left = 0
  right = len(array)
  while left + 1 < right:
    idx = int(left + (right - left) / 2)
    if array[idx] < value:
      left = idx
    else:
      right = idx
  return left

sum = 0
ai = 0
while ai < len(L) - 2:
  bi = ai + 1
  while bi < len(L) - 1:
    a = L[ai]
    b = L[bi]
    i = bsearch(L, a + b)
    sum += (i - bi)

    bi += 1
  ai += 1

print(sum)

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


int main(){
  
  int N, L, i, pos, Sum = 0, Min = 300;
  cin >> N >> L;
  
  for(i = 0; i < N; i++){
    
    Sum += L + i;
    if (L + i < 0){
      Min = min(- L - i, Min);
      pos = -1;
    }else{
      Min = min(L + i, Min);
      pos = 1;
    }
  }
  
  cout << Sum - pos * Min << endl;
  return 0;
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;

int a[100005];

int main() {
	int n, m, v, p;
	scanf("%d%d%d%d", &n, &m, &v, &p);
	for (int i=0 ; i<n ; i++) {
		scanf("%d", a+i);
	}
	sort(a, a+n);
	reverse(a, a+n);
	int pos = 0;
	int jump = 1<<18;
	while (jump/=2) {
		int x = pos + jump;
		if (x>=n) continue;
		int br = a[x] + m;
		ll cnt = 0;
		bool ok = true;
		int num = 0;
		for (int i=n-1 ; i>=0 ; i--) {
			if (i == x) continue;
			if (num<n-p) {
				if (br<a[i]) {
					ok = false;
					continue;
				}
				cnt += min(br-a[i], m);
			} else {
				cnt += m;
			}
			num++;
		}
		//cout <<"x = "<<x<<"    ok = "<<ok<<"      cnt = "<<cnt<<endl;
		if (!ok) continue;
		if (cnt >= (ll)m*(v-1)) {
			pos = x;
		}
	}
	printf("%d\n", pos+1);
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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

  ll M , N ;
  cin >> N >> M ; 

  ll x, y;
  cin >> x >> y ; 

  rep(i,N){
    ll inp;
    cin >> inp;

    x = max(x, inp);
  }
  rep(i,M){
    ll inp;
    cin >> inp;

    y = min(y, inp);
  }

  if(x < y) cout << "No War" << endl;
  else cout << "War" << endl;
  
  
  return 0;
}


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

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

int main()
{
    int n;
    cin >> n;
    vector<int> fib(n + 1, 1);
    rep(i, n - 1)
    {
        fib[i + 2] = fib[i] + fib[i + 1];
    }

    cout << fib[n] << endl;

    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;

const int MAX = 1000010;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


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

    COMinit();

    int N;
    cin>>N;
    int A[N];
    int s=1;
    map<int,int> m;
    rep(i,N) {
        cin>>A[i];
        int x=A[i];
        for(int j=2;j*j<=A[i];j++){
            int c=0;
            while(x%j==0){
                x/=j;
                c++;
            }
            if(c>m[j]){
                rep(k,c-m[j]){
                    s*=j;
                    s%=MOD;

                }
                m[j]=c;
            }
        }
        if(m[x]==0){
            s*=x;
            s%=MOD;
            m[x]=1;
        }
        
    }
    int ans=0;
    rep(i,N){
        ans+=s*inv[A[i]];
        ans%=MOD;
    }
    cout << ans << endl;

    



}


Measured memory_bytes: 24448
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <unordered_map>
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int diff = a - b;
    if(diff >= c) cout << 0 << endl;
    else{
        cout << c-diff << endl;
    }
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <sstream> 
#include <cctype>
#include <stack>
#include <queue>
#include <cstring>
#include <map>
#include <list>
#include <cassert>
#include <climits>

using namespace std;

int main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;

    if (n >= k) {
        cout << (k * x) + ((n - k) * y);

    }
    else {
        cout << (n * x);
    }
    
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;


//void warshall_floyd(int n){
//    for(int k=0;k<n;k++){
//        for(int i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//            }
//        }
//    }
//}
//ll calc_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        ++res;
//        N /= 10;
//    }
//    return res;
//}
//ll sum_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        res += N % 10;
//        N /= 10;
//    }
//    return res;
//}


int main(){
    int n; cin >> n;
    int a[n]; cin >> a[0];
    int ans = 0;
    for(int i = 1;i < n;i++){
        cin >> a[i];
        if(a[i] == a[i-1]){
            ans++;
            a[i] = 0;
        }
    }
    cout << ans;
}



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

using namespace std;

/*
  二部グラフの最大マッチングを計算する
  最初にグラフを作成して登録するが
  最初にグラフをクリアするためにclearGraphを呼び出す必要があることに注意する
 */
class BiMatching{
private:
  static const int MAX_V = 10000;
  static const int INF = 100000000;
  // グラフのリスト表現
  vector<int> G[MAX_V];
  // dfsですでに調べたかどうかのフラグ
  bool used[MAX_V];
public:
  // マッチングのペア
  int match[MAX_V];
  void clearGraph(){
    for(int i=0;i<MAX_V;i++)
      G[i].clear();
  }
  // uとvを結ぶ辺をグラフに追加
  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }
  // 増加パスをdfsで探す
  bool dfs(int v){
    used[v] = true;
    for(int i = 0; i < (int)G[v].size(); i++){
      int u = G[v][i],w = match[u];
      if(w < 0 || !used[w] && dfs(w)){
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  // 二部グラフの最大マッチングを求める
  int bipartite_matching(int V){
    int res = 0;
    memset(match,-1,sizeof(match));
    for(int v = 0; v < V; v++){
      if(match[v] < 0){
        memset(used,0,sizeof(used));
        if(dfs(v)){
          res++;
        }
      }
    }
    return res;
  }
};
class UnionFindTree{
private:
  // indexの数の親ノード(ある集合の親を見つけたいときはここを直接参照せず、findを使う)
  vector<int> par;
  // indexを根とする木のランク
  vector<int> rank;
  // 集合のサイズ
  vector<int> cnts;
  // 木の最大値
  int treeSize;
public:
  UnionFindTree(int initTreeSize = 1000){
    // 引数で与えられた値を最大格納数とするUnionFindTreeの作成
    treeSize = initTreeSize;
    init(initTreeSize);
  }
  void init(int sz){
    par.clear(),rank.clear(),cnts.clear();
    treeSize=sz;
    for(int i = 0; i < sz; i++){
      par.push_back(i);
      rank.push_back(0);
      cnts.push_back(1);
    }
  }
  // 与えられた数が格納されている木のルートを探索
  int find(int x){  
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
  }
  // 和集合をとる。ただしここでは各集合の親の付け替えは起こらない
  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      par[x] = y;
      cnts[y]+=cnts[x];
    }
    else{
      par[y] = x;
      cnts[x]+=cnts[y];
      if(rank[y] == rank[x])rank[x]++;
    }
  }
  // xの属する集合のサイズ
  int getCnt(int x){
    return cnts[find(x)];
  }
  bool same(int x,int y){
    return find(x) == find(y);
  }
    
};
BiMatching bm;
UnionFindTree uft(101);
int N;
int W[101],H[101];
int main(){

  cin>>N;
  for(int i=0;i<N;i++)cin>>W[i]>>H[i];
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(i==j)continue;
      // jがiの上に乗るか
      if((W[i]>W[j]&&H[i]>H[j])
         ||(W[i]>H[j]&&H[i]>W[j])){
        bm.add_edge(i,j+N);
        //cout<<i<<" "<<j<<endl;
      }
    }
  }
  bm.bipartite_matching(2*N);
  set<int> st;
  for(int i=0;i<N;i++){
    if(bm.match[i]!=-1){
      uft.unite(i,bm.match[i]-N);
    }
  }
  for(int i=0;i<N;i++){
    st.insert(uft.find(i));
  }
  cout<<st.size()<<endl;
  
  return 0;
}


Measured memory_bytes: 1556
from collections import deque
k=int(input())
d=deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
  x=d.popleft()
  if x%10!=0:
    d.append(10*x+x%10-1)
  d.append(10*x+x%10)
  if x%10!=9:
    d.append(10*x+x%10+1)
print(x)

Measured memory_bytes: 11908