akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
from copy import deepcopy
def main():
    n, k, *a = map(int, read().split())
    inf = float('inf')
    visible = [inf] * (n + 1)
    pat = tuple(product((0, 1) , repeat=(n - 1)))
    for pate in pat:
        a2 = deepcopy(a)
        cost = 0
        visible_cur = 1
        tall_max = a2[0]
        for i1 in range(1, n):
            tall_max = max(tall_max, a2[i1 - 1])
            visible_flag = tall_max < a2[i1]
            if pate[i1 - 1]:
                if tall_max >= a2[i1]:
                    cost += tall_max + 1 - a2[i1]
                    a2[i1] = tall_max + 1
                visible_flag = True
            visible_cur += visible_flag
        visible[visible_cur] = min(visible[visible_cur], cost)
    ans = min(visible[k:])
    print(ans)

if __name__ == '__main__':
    main()


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



int main() {
  int n;
  cin >> n;
  int rest = n%1000;
  if(rest)
  cout << 1000-rest << endl;
  else cout << 0 << endl;
  
  return 0;
}


Measured memory_bytes: 3628
while True:
    a,op,b = input().split()
    a=int(a)
    b=int(b)

    if op=='+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(int(a/b))
    elif op == '?':
        break



Measured memory_bytes: 5592
H, W= map(int, input().split())
A = [input() for i in range(H)]

v_list = []
reverse_list = [""]*W
h_list = []

# 1行全てが "." のとき削除する関数
def delete(h, input, output):
    for i in range(h):
        if "#" in input[i]:
            output.append(input[i])

# 転置する関数
def reverse(w, h, input, output):
    for i in range(w):
        for j in range(h):
            output[i] = output[i] + input[j][i]

delete(H, A, v_list)

reverse(W, len(v_list), v_list, reverse_list)

delete(W, reverse_list, h_list)

result_list = [""]*(len(h_list[0]))

reverse(len(h_list[0]), len(h_list), h_list, result_list)

for s in result_list:
    print(s)


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


class maki {
    static void Main(string[] args) {
        //int[] cin=Console.ReadLine().Split().Select(int.Parse).ToArray();
        //int n = int.Parse(Console.ReadLine());
        string s=Console.ReadLine();
        int a=0;
        int n=s.Length;
        for(int i=0;i<n;i++){
        	if(s[i]=='0'){
        		a++;
        	}
        	else{
        		a--;
        	}
        }
        Console.WriteLine(n-Math.Abs(a));
    }
}


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

int main()
{
	int n;
	cin >> n;
	vector<ll> a(n);
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}

	vector<ll> s(n);
	s[0] = a[0];
	for (int i = 1; i < n - 1; i++) s[i] = s[i - 1] + a[i];

	ll ans = INT_MAX;
	for (int i = 0; i < n - 1; i++) {
		ans = min(ans, abs(s[i] - (sum - s[i])));
	}
	cout << ans << endl;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[100000+1];
int main(){
    int n,weight;
    cin>>n>>weight;
    int w[n],v[n];
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=weight;j>=w[i];j--){
            if(j-w[i]>=0)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            else
                dp[j]=dp[j];

        }
    }


    cout<<dp[weight]<<endl;
    return 0;
}



Measured memory_bytes: 1024
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

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

int h[100010];
signed main(void)
{
	int n, a, b;
	cin >> n >> a >> b;
	REP(i, n) cin >> h[i];
	sort(h, h+n, greater<int>());
	ll high = 1000000000, low = 0;
	while(high - low > 1) {
		ll mid = (high+low)/2;
		//cout << high << " " << mid << " " << low << endl;
		ll an = mid;
		bool flag = true;
		REP(i, n) {
			ll l = 0, r = an+1;
			while(r-l > 1) {
				ll m = (r+l)/2;
				//cout << "i:" << i << " " << r << " " << m << " " << l << endl;
				if(m*a+(mid-m)*b > h[i]) r = m;
				else l = m;
			}
			ll tmp;
			if(l*a+(mid-l)*b >= h[i]) tmp = l;
			else tmp = r;
			//cout << l << " " << r << " " << tmp << " " << tmp*a+(mid-tmp)*b << endl;
			if(tmp*a+(mid-tmp)*b < h[i]) {/*cout << "f" << endl;*/ flag = false; break;}
			an -= tmp;
			if(an < 0) {flag = false; break;}
		}
		if(flag) {
			high = mid;
		} else {
			low = mid;
		}
	}
	bool flag = true;
	ll an = low;
	REP(i, n) {
		ll l = 0, r = an;
		//cout << "l" << l << " " << r << endl;
		//r回ちょうどのとき
		if((r-1)*a + (low-r+1)*b < h[i]) {
			if(r*a + (low-r)*b < h[i]) {flag = false; break;}
			an -= r;
			continue;
		}
		while(r-l > 1) {
			ll m = (r+l)/2;
			//cout << "i:" << i << " " << r << " " << m << " " << l << endl;
			if(m*a+(low-m)*b > h[i]) r = m;
			else l = m;
		}
		ll tmp;
		if(l*a+(low-l)*b >= h[i]) tmp = l;
		else tmp = r;
		//cout << tmp << " " << tmp*a+(low-tmp)*b << endl;
		if(tmp*a+(low-tmp)*b < h[i]) {/*cout << "f" << endl;*/ flag = false; break;}
		an -= tmp;
		//cout << "an" << an << endl;
		if(an < 0) {flag = false; break;}
	}
	if(flag) cout << low << endl;
	else cout << high << endl;

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int k;
    cin >> k;
    int sum;
    int mx;
    mx = max({a,b,c});
    sum = (a+b+c-mx)+mx*pow(2,k);
    cout << sum << endl;
}




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

using namespace std;
using std::vector;

#define MAX_N 100

void print(vector<int>& A, int N) {
  for (int i = 0; i < N - 1; i++)
    cout << A[i] << " ";
  cout << A[N-1] << endl;
}

int bubbleSort(vector<int>& A, int N) {
  int sw = 0;
  bool flag = true;
  for (int i = 0; flag; ++i) {
    flag = false;
    for (int j = N - 1; j >= 1; j--) {
      if (A[j] < A[j-1]) {
        swap(A[j], A[j-1]);
        flag = true;
        sw++;
      }
    }
  }
  return sw;
}

int main() {

  vector<int> A;
  int N, sw;

  cin >> N;
  A.reserve(N);
  for (int i = 0; i < N; i++) {
    int v;
    cin >> v;
    A.push_back(v);
  }

  sw = bubbleSort(A, N);
  for (int i = 0; i < N; i++) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl
       << sw << endl;
  return 0;
}

Measured memory_bytes: 3096
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.Scanner;
import java.math.RoundingMode;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            BigDecimal a = new BigDecimal(in.next());
            BigDecimal b = new BigDecimal(in.next());
            BigDecimal ans = a.multiply(b);
            BigDecimal ans2 = ans.setScale(0, RoundingMode.DOWN);

            // 出力
            out.println(ans2.toPlainString());

        }

    }
}



Measured memory_bytes: 36060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
static const long long INF = 1LL<<59;
static const long long MOD = (ll)1e9+7;

#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i, n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)((v).size())
#define WHOLE(v) (v).begin(), (v).end()
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).begin(), (v).end())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define CUMSUML(src, dst) FOLDL(src, dst, [](auto a, auto b) {return a+b;})
#define CUMSUMR(src, dst) FOLDR(src, dst, [](auto a, auto b) {return a+b;})
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define SUM(v, d0) ACCUM(v, d0, [](auto a, auto b) {return a+b;})
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);v.erase(unique(v.begin(), v.end()), v.end())

template <typename T>void debug(T t) {cerr << t << endl;}
template <typename T, typename ...Args>void debug(T t, Args ...args) {cerr << t << " ";debug(args...);}
template <typename T>void out(T t) {cout << t << endl;}
template <typename T, typename ...Args>void out(T t, Args ...args) {cout << t << " ";out(args...);}

void solve() {
    vector<vll> mp;
    ll n;
    cin >> n;
    mp.resize(n, vector<ll>(26));
    REP(i, n) {
        str s;
        cin >> s;
        REP(j, s.size()) {
            mp[i][(int)(s[j] - 'a')]++;
        }
    }
    str ans;
    REP(i, 26) {
        ll mn = INF;
        REP(j, n) {
            mn = min(mn, mp[j][i]);
        }
        REP(j, mn) {
            ans.push_back((char)(i + 'a'));
        }
    }
    out(ans);
}

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


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws IOException {
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		end: {
			while (true) {
				String str = br.readLine();
				switch (str.substring(0, 2)) {

				case "in":
					// insert????????????
					int insert = Integer.parseInt((String) str.subSequence(7, str.length()));
					int key = 2000000000 - insert;
					map.put(key, insert);
					queue.add(key);
					
					break;

				case "ex":
					// extract????????????
					key = queue.poll();
					sb.append(map.get(key) + "\n");
					break;

				case "en":
					// end??\??????????????????
					break end;
				}
			}
		}
		System.out.print(sb.toString());
	}
}

Measured memory_bytes: 199020
package main

import (
  "fmt"
)

func main() {
  var n int
  s := []int{}

  fmt.Scanf("%d", &n)

  for i:=0; i<n; i++ {
    var x int
    fmt.Scanf("%d", &x)
    s = append(s, x)
  }

  count := 0
  for {
    for i:=0; i<n; i++ {
      if s[i] % 2 == 1 {
        fmt.Print(count)
        return
      }
    }

    for i:=0; i<n; i++ {
      s[i] /= 2
    }
    count++
  }

  fmt.Print(count)
}

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

signed main(){
  int A,B,X;
  cin>>A>>B>>X;
  string ans="NO";
  for(int i=0;i<=B;i++){
    if(A+i==X)ans="YES";
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
 
int main() {
	ll n, a,b;
	cin>>n>>a>>b;
	ll num_ab = n / (a+b);
	ll rem = n- num_ab * (a+b);
	ll ans = num_ab*a;
	if (rem >= a) ans += a;
	else ans += rem;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3540
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<int> b;
	vector<int> c;
	vector<int> a;
	a.resize(n);
	b.resize(n);
	c.resize(n);

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

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

	for (int i = 0; i < n - 1; ++i)
	{
		cin >> c[i];
	}

	int total = 0;
	int prev = -1000;

	for (int i = 0; i < n; ++i)
	{
		int j = a[i];
		total += b[j];
		if (j == prev + 1)
		{
			total += c[prev];
		}
		prev = j;
	}

	cout << total << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<pair<ll,ll> > vii;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<ll,pair<ll,ll> > iii;
#define PI 3.141592653589793
#define mod (ll)(1000*1000*1000+7)
//# define N 300005
template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, ll m){T ans=1; while(b>0){ if(b%2==1) ans=((ans%m)*(a%m))%m; b/=2; a=((a%m)*(a%m))%m; } return ans%m; }
# define INF (ll)1e18
# define LG 20  
typedef pair<ll,pair<ll,ll> > pii;
# define INF1 (ll)1e9+2
# define maxn 200005
# define offset 1000005

/*************************************************
struct Coupon {
    ll l;
    ll r;
    ll id;

    Coupon(ll l, ll r, ll id): l(l), r(r), id(id) {} // Initialization

    bool operator<(const Coupon& c) { // Sorting
        return l < c.l;    
    }
};

**************************************************/
ll cf[maxn];
ll a[maxn];

int main()
{
  IOS;
  int n;
  cin >> n;
  for(int i=1;i<=n;i++)
   {
      cin >> a[i];
      cf[i]=cf[i-1]+a[i];
   }

  int x1=1;
  int x3=3;
  ll ans=INF;
  for(int i=2;i<n;i++)
  {
    while(x1<n-3 && abs(cf[x1]-(cf[i]-cf[x1]))>abs((cf[x1+1]-(cf[i]-cf[x1+1])))) x1++;
    while(x3<n-1 && abs((cf[x3]-cf[i])-(cf[n]-cf[x3]))>abs((cf[x3+1]-cf[i])-(cf[n]-cf[x3+1]))) x3++;
    ll d1=cf[x1];
    ll d2=cf[i]-cf[x1];
    ll d3=cf[x3]-cf[i];
    ll d4=cf[n]-cf[x3];
    //trace4(d1,d2,d3,d4);
    //trace4(x1,i,x3,n);
    ans=min(ans,max(d1,Max(d2,d3,d4))-min(d1,Min(d2,d3,d4)));
  }
  cout << ans;
}

Measured memory_bytes: 3328
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format, std.datetime;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long R, G, B, N;
    scan(R, G, B, N);
    long ans;
    foreach (r; 0 .. N / R + 1)
    {
        foreach (g; 0 .. (N - r * R) / G + 1)
        {
            if ((N - r * R - g * G) % B == 0)
            {
                // writefln("%s %s %s", r, g, (N - r * R - g * G) / B);
                ans++;
            }
        }
    }
    writeln(ans);
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main
{
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int a = s.nextInt();
		int b = s.nextInt();
		int area = area(a,b);
		int lenght = length(a,b);
		System.out.println(area + " " + lenght);
	}

	//??¢???????±???????????????????
	public static int area(int a, int b){
		int ans;
		ans = a * b;
		return ans;
	}
	//??¨?????????????±???????????????????
	public static int length(int a, int b){
		int ans = 0;
		ans += a;
		ans += a;
		ans += b;
		ans += b;
		return ans;
	}
}

Measured memory_bytes: 26092
v, e, r = map(int, input().split()) # 頂点数v,辺数e,始点rを入力

g = [[] for i in range(v)] # グラフ

for i in range(e):
 s, t, d = map(int, input().split())
 g[s].append([t,d]) # sからtへの辺とその重みd


cost = ['INF' for i in range(v)] # 出力結果を初期化
cost[r] = 0

import heapq
h = []

u = r # 新しく確定した頂点

for count in range(v-1):

 for adj in g[u]:
  if cost[ adj[0] ] != 'INF':
   continue

  new_cost = cost[u] + adj[1]
  heapq.heappush(h, (new_cost, adj[0]))
  
  
 while 1:
  if len(h) == 0:
   break

  minc = heapq.heappop(h)
  if cost[ minc[1] ] == 'INF':
   cost[ minc[1] ] = minc[0]
   u = minc[1]
   break


for i in range(v):
 print(cost[i])


Measured memory_bytes: 104124
cases = int(input())

ac_count = 0
wa_count = 0
tle_count = 0
re_count = 0

arr = []
for i in range(cases):
    x = input()
    if x == "AC":
        ac_count += 1
    elif x == "WA":
        wa_count += 1
    elif x == "TLE":
        tle_count += 1
    elif x == "RE":
        re_count += 1

print("AC x {0}".format(ac_count))
print("WA x {0}".format(wa_count))
print("TLE x {0}".format(tle_count))
print("RE x {0}".format(re_count))

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

int main(){
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int temp = 0;
    int ans = 0;
    for (int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            for (int p = 0; p <= C; p++){
                temp = 500 * i + 100 * j + 50 * p;
                if(temp == X){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

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


int main () {
  int n ;
  cin >> n;
  cout << n*n*n << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
typedef vector<tint> vtint;
typedef vector<vint> vvint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//↑templete
signed main(){

    int K;
    cin>>K;
    int A, B;
    cin>>A>>B;

    for(int i=A;i<=B;i++){
        if(i%K==0){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;

    return 0;
}


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

void solve(long long N, long long K, vector<long long> a){
	vector<long long> b(N + 1), c(N + 1);

	for (int i = 0; i < N; ++i ) {
		b[i + 1] = b[i] + a[i];
		c[i + 1] = c[i] + max(a[i], 0LL);
	}

	long long res = 0;
	for(int i = 0; i + K <= N; ++i) {
		res = max(res, c[i] + max(b[i + K] - b[i], 0LL) + c[N] - c[i + K]);
	}
	cout << res << endl;
}

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



Measured memory_bytes: 3328
#include<stdio.h>
int main(void)
{
	int a[101],s,i,d;
	scanf("%d",&s);
	for(i=1;i<=s;i++){
		scanf("%d",&a[i]);
	}
	d=1;
	for(i=s;i>=1;i--){
		d++;
		printf("%d",a[i]);
		if(d<=s){
			printf(" ");
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1028
import sys
from heapq import heappush, heappop
#input = sys.stdin.readline

def main():
    s=list(input())
    n=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(n)]
    if s[0]=='?':
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[0])]=1
    for i in range(1,n):
        for j in range(13):
            if s[i]=='?':
                for k in range(10):
                    x=(j*10+k)%13
                    dp[i][x]+=dp[i-1][j]
                    dp[i][x]%=mod
            else:
                x=(j*10+int(s[i]))%13
                dp[i][x]+=dp[i-1][j]
                dp[i][x]%=mod
    print(dp[n-1][5])

if __name__ == '__main__':
    main()

Measured memory_bytes: 64888
#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <utility>
#include <string>
#include <vector>
#include <limits>
#include <queue>
#include <cmath>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

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

    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        int x = 0;
        cin >> x;
        v[i] = x - (i + 1);
    }

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

    ll out = 0;
    int b = v[n / 2];

    for(int x: v)
        out += abs(x - b);

    cout << out << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> c(m);
    rep(i, m){
        cin >> c[i];
    }
    SORT(c);
    int dp[25][50050]; //dp[i][j] i番目まででj円払うのに必要な枚数
    rep(i, m){
        dp[i][0] = 0;
    }
    rep(i, m){
        rep(j, n+1){
            if(i == 0){
                dp[i][j] = j;
            }else if(j >= c[i]){
                dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]] + 1);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[m-1][n] << endl;
    return 0;
}


Measured memory_bytes: 7064
#include<iostream>
#include<string.h>

int main(){
  std::string s;
  std::cin >> s;
  
  int n = s.size();
  long long dp[n + 1][13];
  for(int i = 0; i <= n; i++) for(int j = 0; j < 13; j++) dp[i][j] = 0;
  
  dp[0][0] = 1;
  
  for(int i = 0; i < n; i++){
    int t = s[i] == '?' ? -1 : s[i] - '0';
    
    for(int r = 0; r < 10; r++){
      if(t != -1 && t != r) continue;
      for(int b = 0; b < 13; b++){
        dp[i + 1][(b * 10 + r) % 13] += dp[i][b];
      }
    }
    for(int j = 0; j < 13; j++){
      dp[i + 1][j] %= 1000000007;
    }
  }
  
  std::cout << dp[n][5] << std::endl;
  
  return 0;
}

Measured memory_bytes: 10624
import itertools

n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

Psort = sorted(P)
Pp = list(itertools.permutations(Psort))

a = Pp.index(P)
b = Pp.index(Q)

print(abs(a-b))

Measured memory_bytes: 13684
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int result = 0;
		int N = sc.nextInt();
		String[] s = new String[N];
		for(int i = 0; i < N; i++) {
			s[i] = sc.next();
		}

		int M = sc.nextInt();
		String[] t = new String[M];
		for(int i = 0; i < M; i++) {
			t[i] = sc.next();
		}

		for(int i = 0; i < N; i++) {
			int count = 1;
			for(int j = 0; j < N; j++) {
				if(i != j) {
					if(s[i].equals(s[j])) {
						count++;
					}
				}
			}
			for(int j = 0; j < M; j++) {
				if(s[i].equals(t[j])) {
					count--;
				}
			}
			result = Math.max(result, count);
		}

		System.out.println(result);
	}
}


Measured memory_bytes: 22996
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define debug(x) cout<<#x<<"="<<x<<endl;
#define chk() cout<<C((n-j+1)*(k-1)+(n-i)-1,k-2)<<endl;
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^'0');
	return x*f;
}
const int maxn=2010;
const int mod=1e9+7;
int ifac[maxn*maxn],fac[maxn*maxn],inv[maxn*maxn];
int f[maxn][maxn];
inline int C(int n,int m){
	if(m==0)return 1;
	if(n<m)return 0;
	return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
int n,k;
inline void init(){
	n=read(),k=read();
	if(n==0 || k==0)printf("0"),exit(0);
	if(k==1)puts("1"),exit(0);
	inv[0]=inv[1]=1;
	for(register int i=2;i<=maxn*maxn;++i)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	fac[0]=fac[1]=1;
	for(register int i=2;i<=maxn*maxn;++i)
		fac[i]=1ll*fac[i-1]*i%mod;
	ifac[0]=ifac[1]=1;
	for(register int i=1;i<=maxn*maxn;++i)
		ifac[i]=1ll*ifac[i-1]*inv[i]%mod;

//	for(register int i=1;i<=n;++i)for(register int j=1;j<=i;++j)cout<<f[i][j]<<endl;
}
inline void solve(){
	f[1][0]=1;
	//这里为什么不是n
	//出现一个白球不应该是随便放一个都可以吗
	for(register int i=0;i<=n;++i)
		for(register int j=0;j<=i;++j){
			if(i)(f[i][j]+=f[i-1][j])%=mod;
			if(j)(f[i][j]+=1ll*C((n-j+1)*(k-1)+(n-i)-1,k-2)*f[i][j-1]%mod)%=mod;
		}
	//                              ^
 	//                              |
	//                       求解释这一坨
	cout<<1ll*f[n][n]*fac[n]%mod;
	//为啥这里要乘fac[n];
}
int main(){
	init();
	solve();
	return 0;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

#define SIZE 100005

// 素数判定 (エラトステネスのふるい)
bool isPrime[SIZE];
void initIsPrime() {
    for(int i=0;i<SIZE;i++){
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i=2;i*i<=SIZE;i++){
        if(isPrime[i]){
            for(int j=i*i;j<=SIZE;j+=i){
                isPrime[j] = false;
            }
        }
    }
}

int sum[100001];

int main() {
    std::ios::sync_with_stdio(false);
    initIsPrime();
    sum[1] = 0;
    for(int i=1;i<=100000;i++){
        sum[i+1] = sum[i] + (isPrime[i] && isPrime[(i+1)/2]);
    }
    int q;cin >> q;
    for(int i=0;i<q;i++){
        int l, r;cin >> l >> r;r++;
        cout << sum[r]-sum[l] << endl;
    }
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
    int a,b,c,d=0;
    int x[20]; int s=1;
     cin>>a>>b; if(a<=0&&b>=0)
      cout<<"Zero"<<endl;
      if(a>0&&b>0)
        cout<<"Positive"<<endl;
      if(a<0&&b<0)
        { for(int i=a;i<=b;i++)
         {
             if(i<=b) d++;
             }
      if(d%2==0) cout<<"Positive"<<endl;
      else cout<<"Negative"<<endl;
      }
       return 0;
}









Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define pb push_back
//#define mp make_pair
#define eps 1e-9
#define pp pair < pair<ll,ll> , ll> 
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define foll(i,j,k) for(ll i=j;i<=k;i++)
#define clr(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vll vector<ll>
#define sz(a) a.size()
#define len(a) a.length()
#define all(a) a.begin(),a.end()
#define io_file freopen("Contest/input_file.in", "r", stdin); freopen("Contest/output_file.in", "w", stdout)

const ll INF = 1e18 + 5;
const int MAXN = 2e5+5;
using namespace std;
ll power(ll x, ll y)
{
  ll res = 1;
  while(y>0)
  {
    if(y&1)
       {
         res = (res*x)%mod;
        }
     x = (x*x)%mod;
     y = y>>1;
  }
    return res;
}
std::vector<ll> divi[1000004];

void divisor(int n)
{
   for(ll i=1;i<=n;i++)
   {
     for(ll j=i;j<=n;j+=i)
     {
       divi[j].pb(i);
     }
   }
}

ll a[200004];
ll b[200004];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
	ll n;
	cin>>n;
	ll ans = 1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans = max(ans,b[a[i]-1]+1);
		b[a[i]] = b[a[i]-1] + 1;
	}
	cout<<n-ans<<endl;


    
   	return 0;


}

Measured memory_bytes: 26880
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};
constexpr int MAX_N = 100001;

int n;
ll fact[MAX_N], rfact[MAX_N];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

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

    init(n);

    vector<ll> p(n, fact[n-1]);
    p[0] = 0;
    for(int i=1;i<n;++i) {
        p[i] = p[i-1] + (fact[n-1] * modpow(i, MOD-2)) % MOD;
    }
    
    ll ans = 0LL;
    for(int i=1;i<n;++i) {
        ans += ((a[i+1]-a[i]) * p[i]) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

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

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  const int sqrtN = 512;

  int n;
  cin >> n;
  vint a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];

  int bucket_sz = (n+sqrtN-1)/sqrtN;
  vint bucketFlagA(bucket_sz, 0);
  vint bucketFlagB(bucket_sz, 0);
  vint bucketMinA(bucket_sz, inf);
  vint bucketMinB(bucket_sz, inf);

  rep(i, n) chmin(bucketMinA[i/sqrtN], a[i]);
  rep(i, n) chmin(bucketMinB[i/sqrtN], b[i]);

  auto push = [&](int k) {
    assert(bucketFlagA[k]+bucketFlagB[k] < 2);
    //if(!bucketFlagA[k]) return;
    if(bucketFlagA[k]) {
      reps(i, k*sqrtN, min(n, (k+1)*sqrtN)) a[i] = b[i];
      bucketMinA[k] = bucketMinB[k];
      bucketFlagA[k] = 0;
    } else if(bucketFlagB[k]) {
      reps(i, k*sqrtN, min(n, (k+1)*sqrtN)) b[i] = a[i];
      bucketMinB[k] = bucketMinA[k];
      bucketFlagB[k] = 0;
    }
  };
  auto setA = [&](int y, int z) {
    int k = y/sqrtN;
    push(k);
    a[y] = z;
    bucketMinA[k] = inf;
    reps(i, k*sqrtN, min(n, (k+1)*sqrtN)) chmin(bucketMinA[k], a[i]);
  };
  auto setB = [&](int y, int z) {
    int k = y/sqrtN;
    push(k);
    b[y] = z;
    bucketMinB[k] = inf;
    reps(i, k*sqrtN, min(n, (k+1)*sqrtN)) chmin(bucketMinB[k], b[i]);
  };
  auto getA = [&](int y, int z) {
    int res = inf;
    rep(i, bucket_sz) {
      int l = i*sqrtN, r = (i+1)*sqrtN;
      if(r <= y || z <= l) continue;
      if(y <= l && r <= z) {
	if(bucketFlagA[i]) chmin(res, bucketMinB[i]);
	else chmin(res, bucketMinA[i]);
      } else {
	push(i);
	reps(j, max(l, y), min(r, z)) chmin(res, a[j]);
      }
    }
    return res;
  };
  auto getB = [&](int y, int z) {
    int res = inf;
    rep(i, bucket_sz) {
      int l = i*sqrtN, r = (i+1)*sqrtN;
      if(r <= y || z <= l) continue;
      if(y <= l && r <= z) {
	if(bucketFlagB[i]) chmin(res, bucketMinA[i]);
	else chmin(res, bucketMinB[i]);
      } else {
	push(i);
	reps(j, max(l, y), min(r, z)) chmin(res, b[j]);
      }
    }
    return res;
  };
  auto copyA = [&]() {
    rep(i, bucket_sz) {
      if(!bucketFlagB[i]) bucketFlagA[i] = 1;
    }
  };
  auto copyB = [&]() {
    rep(i, bucket_sz) {
      if(!bucketFlagA[i]) bucketFlagB[i] = 1;
    }
  };
  int q;
  cin >> q;
  while(q--) {
    int x, y, z;
    cin >> x >> y >> z;
    if(x == 1) setA(y-1, z);
    else if(x == 2) setB(y-1, z);
    else if(x == 3) cout << getA(y-1, z) << endl;
    else if(x == 4) cout << getB(y-1, z) << endl;
    else if(x == 5) copyA();
    else if(x == 6) copyB();
  }

  return 0;
}



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

using namespace std;
using ll = long long;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((int)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back

int main()
{
    string S;
    cin >> S;
    
    if(S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) _PR("Bad");
    else _PR("Good");

    return 0;
}

/*



*/

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

string s[52];

int main(void){
  int h, w;
  cin >> h >> w;
  for(int j=0;j<=w+1;j++) s[0] += '.';
  for(int i=1;i<=h;i++){
    cin >> s[i];
    s[i] = '.' + s[i] + '.';
  }
  s[h+1] = s[0];
  
  for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
    if (s[i][j]=='.'){
      int cnt = 0;
      for(int k=-1;k<2;k++)for(int l=-1;l<2;l++){
        if (s[i+k][j+l]=='#') cnt++;
      }
      s[i][j] = '0' + cnt;
    }    
  }
  
  for(int i=1;i<=h;i++) cout << s[i].substr(1, w) << endl;
  return 0;  
}  

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

int main(){
  int n;

  while( cin>>n && n ){
    int sum=0;

    if( n>1 ) sum=1;
    int a,b;
    for( int i=2;i<n;i++ ){
      if( n%i==0 ){
	a=i;
	b=n/i;
	if( a<b )	  sum+=b;
	else if( a>b )	  break;
	sum += a;
      }
    }
    //    cout << n << " " << sum << "\t";

    if( sum==n )
      cout << "perfect number" << endl;
    else if( sum<n )
      cout << "deficient number" << endl;
    else
      cout << "abundant number" << endl;

  }
  return 0;
}

Measured memory_bytes: 852
#include <stdio.h>
int main(void) {
	int i,max=0,c1[20],c2[20],c3[20];
	for(i=0;i<20;i++){
		int ret=scanf("%d %d %d",&c1[i],&c2[i],&c3[i]);
		if(ret==EOF) break;
		if(i>max) max=i;
	}
	int c4[20];
	for(i=0;i<=max;i++){
		c4[i]=c1[i]+c2[i];
	}
	int c5[20],k=0;
	double c6[20];
	for(i=0;i<=max;i++){
		for(c5[i]=1;c5[i]<=10;c5[i]++){
			if(c5[i]!=c1[i]&&c5[i]!=c2[i]&&c5[i]!=c3[i]){
				if(c4[i]+c5[i]<=20){
					k++;
				}
			}
		}
		c6[i]=(double)k/7.0;
		if(c6[i]>=0.5)
			puts("YES");
		else
			puts("NO");
		k=0;
	}
	return 0;
}


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

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

	int digit = n%10;

	if(digit==2 || digit==4 || digit==5 || digit==7 || digit==9)
		cout<<"hon";
	else if(digit==0 || digit==1 || digit==6 || digit==8)
		cout<<"pon";
	else
		cout<<"bon";

	return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int a,b,c,d;
	cin>>a>>b>>c>>d;
	 long long int ar[4];
	long long int p=(a*c);
	ar[0]=p;
	
	 long long int q=(a*d);
	ar[1]=q;
	
	long long int r=(b*c);
	ar[2]=r;
	long long int s=(b*d);
	ar[3]=s;
	sort(ar,ar+4);
	cout<<ar[3];
	}
				
			
				
			

		


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

int main() {
int N;
  cin>>N;
  vector<int>t(100010), x(100010), y(100010);
  for(int i=1; i<=N; i++){
   cin>>t[i]>>x[i]>>y[i]; }
  
  bool  flag=true;
  for(int i=0; i<N; i++){
   x[0]=0, y[0]=0, t[0]=0; 
    int T=t[i+1]-t[i];
    int d=abs(x[i+1]-x[i])+abs(y[i+1]-y[i]); 
    if(!(d<=T && T%2==d%2)){flag=false;} 
  }
  
  if(flag){cout<<"Yes";}
  else{cout<<"No";}
}


Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;


typedef pair<ll,ll> P;

bool ps1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool ps2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool ps3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool ps4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}

int main()
{

	ll q,h,s,d;
	cin>>q>>h>>s>>d;
	ll n;
	cin>>n;
	map<ll,ll>map;
	map[-2]=q;
	map[-1]=h;
	map[0]=s;
	map[1]=d;
	vector<pair<ll,ll>>cospa;
	cospa.pb(make_pair(8*q,-2));
	cospa.pb(make_pair(4*h,-1));
	cospa.pb(make_pair(2*s,0));
	cospa.pb(make_pair(d,1));
	sort(all(cospa),ps1);
	int j=0;
	if(n>=cospa[0].S){

	}else{
		j++;
	}

	ll num=n/pow(2,cospa[j].S);//本数
    //cout<<num<<endl;
	ll cost =num*map[cospa[j].S];
	//cout<<cost<<endl;
	long dis=n-num*pow(2,cospa[j].S);//lの差
	//cout<<dis<<endl;
	
	if(cospa[j].S==1&&dis>0){
		cost+=min(q*4,min(2*h,s))*dis;
	}
	cout<<cost<<endl;

}

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

const int infty = 1<<29;
using namespace std;

int minimumCost(string need,
		map<string,int> &matval,
		map<string,vector<string> > &wrought)
{
  int ret = matval[need];
  
  int S = 1<<wrought[need].size();
  for(int i = 1; i < S; ++i){
    int cost = 0;
    for(int j = 0; j < wrought[need].size(); ++j){
      if( i & (1<<j) ){
	cost += minimumCost( wrought[need][j], matval, wrought );
      }else{
	cost += matval[ wrought[need][j] ];
      }
    }
    ret = min( ret, cost );
  }

  return ret;
}

int main()
{
  while(true){
    int n;
    cin >> n;
    map<string,int> material;
    map<string,vector<string> > wrought;

    if(n==0)break;
    for(int i = 0; i < n; ++i){
      string s;
      int val;
      cin >> s >> val;
      material[s]=val;
    }
    int m;
    cin >> m;
    for(int i = 0; i < m; ++i){
      string s;
      cin >> s;
      int num;
      cin >> num;
      for(int j = 0; j < num; ++j){
	string mat;
	cin >> mat;
	wrought[s].push_back(mat);
      }
    }
    string needed;
    cin >> needed;

    cout << minimumCost( needed, material, wrought ) << endl;
    
  }
  return 0;

}

Measured memory_bytes: 948
from operator import itemgetter
from functools import reduce
n, k = list(map(int, input().split()))
a = []
for i, v in enumerate(input().split(), 1):
    a.append([int(v) - 1, i])
a.sort(reverse=True)
ans = list(map(itemgetter(1), a))
last = ans[-1]
for _ in range(k):
    for item in a:
        if item[1] == last:
            continue
        item[0] -= 1
        ans.append(item[1])
    a.sort(reverse=True)
    last = ans[-1]

ok = reduce(lambda x, y: x and y[0] >= 0, a, True)
if ok:
    print(len(ans))
    print(*ans)
else:
    print(-1)

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

#define                  read           freopen("in.txt", "r", stdin);
#define                  ll             long long
#define                  MOD            1000000007

using namespace std;

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
inline bool isLeapYear(ll year) { return (year%400==0) || (year%4==0 && year%100!=0); }
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
inline string tstring(ll a) {stringstream ss; ss << a; string str = ss.str(); return str; }
inline int Find(char str[], char c) {char * pch; pch=strchr(str,c); return (pch-str); }
inline ll mod(ll a, ll m){ if(a<0) return m-(abs(a)%m); else if(a<m) return a; else return (a%m); }

map <char, int> mp;

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

	int n, ans=1;
	string s;

	cin >> n >> s;

	for(int i = 0; i < s.size(); i++) mp[s[i]]++;

	for(int i = 97; i <= 122; i++)
	{
		ans = modMul(mp[i]+1, ans);
	}

	cout << ans-1 << endl;


	return 0;
}

Measured memory_bytes: 512
n = int(input())
a =list(map(int, input().split()))
q = int(input())
b = [0]*q
c = [0]*q
for i in range(q):
    b[i],c[i]=map(int, input().split())

at = [0]*(10**5+100)
sum = 0

for i in a:
    at[i]= at[i]+1
    sum = sum+i


for  i in range(q):
    m= at[b[i]]
    at[b[i]]=0
    at[c[i]]=at[c[i]]+m

    sum = sum + (c[i]-b[i])*m
    print(sum)

Measured memory_bytes: 84612
#include <stdio.h>
int main(){
    int m,r,n,s,d,f,g,h,j,k,l,i,c=0;
    scanf("%d%d", &n,&r);
    for(i=n;i<=r;i++) {
        m = i % 10;
        s = i / 10;
        d = s % 10;
        f = s / 10;
        g = f % 10;
        h = f / 10;
        j = h % 10;
        k = h / 10;
        l = k % 10;
        if (l == m && d == j) {
            c++;}}
            printf("%d\n",c);


    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
//#define int long long int
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define MAX 1e15+1
#define pi  pair<int,int>
const int N=1e3+10;

const int M = ((int)1e9 + 7);

string s;





signed main(){
   fast;
   int n;
   cin>>n;
   cin>>s;
  
   if(n%2!=0){
   	cout<<"No";
   	return 0;
   }
   n/=2;
   for(int i=0;i<n;i++){
   		if(s[i]!=s[i+n]){
   			//cout<<s[i]<<s[i+n];
   			cout<<"No";
   			return 0;
   		}
   }
   cout<<"Yes";
  
   //solve();//length,
  	
   
   
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#2234
#import numpy as np

def main():
	n=II()
	A=LI()


	ans=1
	mod=10**9+7
	li=[3]+[0]*(n+1)

	for i in A:
		ans*=li[i]-li[i+1]
		ans%=mod
		li[i+1]+=1

	print(ans)


if __name__ == "__main__":
	main()

Measured memory_bytes: 12488
import numpy as np
n,m,c = map(int,input().split())
b = np.array([int(i) for i in input().split()])
a = np.array([[int(i) for i in input().split()]for j in range(n)])
count = 0
for i in a:
  if (i*b).sum()+c >0:
    count+=1
print(count)


Measured memory_bytes: 12448
import bisect

n,k = map(int, input().split())
x = list(map(int, input().split()))
j = bisect.bisect_right(x,0)
if x[-1] > 0:
    j += 1
ans = float("INF")
for i in range(max(j-1-k,0), max(min(j,n-k+1),0)):
    key = x[i+k-1]-x[i]
    ans = min(ans, min(abs(x[i])+key, abs(x[i+k-1])+key))
print(ans)

Measured memory_bytes: 14480
#include <iostream>
using namespace std;
int main(){
    long long n,m;
    cin >> n >> m;
    if (n>=2 && m>=2){
        cout << (m-2)*(n-2) << endl;
    }else if (n==1 && m==1){
        cout << 1 << endl;
    }else{
        cout << max(m,n)-2 << endl;
    }
}

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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

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; }


bool my_cp(pair<int, int> a, pair<int, int> b){
  return (double)b.first / (double)(b.second+1) < (double)a.first / (double)(a.second+1);
}

ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}

int N;

void dfs(string s, char m, int N){

  if(s.length() == N){
    cout << s << endl;
  }else{
    for(char c = 'a'; c <= m; c++){
      dfs(s + c, ((c == m)? (m + 1) : m), N);
    }
  }
}


int gcd(int a, int b){
  int resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}





// substr(start, len)

int main(){


  int K;

  cin >> K;
  int sum = 0;
  rep(i, 1, K+1){
    rep(j, 1, K+1){
      rep(k, 1, K+1){
        int gcd1 = gcd(i, j);
        sum += gcd(gcd1, k);
      }
    }
  }

  cout << sum << endl;

  // cout << setprecision(8) << ans << endl;  // For double
// CHECK if it's possible to overflow!!
}

Measured memory_bytes: 3636
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    String S = sc.next();
    int R =0;
    int B =0;
    for(int i=0;i<S.length();i++){
      if(S.substring(i,i+1).equals("0")){
        R++;
      }else{
        B++;
      }
    }
    System.out.println(Math.min(R,B)*2);

  }
    


}


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

int main(){
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%k==0){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
}

Measured memory_bytes: 3604
N = int(input())
h = list(map(int, input().split()))

ans = 0
for i in range(max(h)):
  cnt = 0
  for j in range(N):
    h[j] = h[j] - 1
    if h[j] >= 0 and (j == 0 or h[j - 1] < 0):
      cnt += 1
  ans += cnt
print(ans)

Measured memory_bytes: 3064