akhauriyash/Code-Regression huggingface dataset:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  set<string> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    m.insert(s);
  }
  cout << (int)m.size() << '\n';
  return 0;
}

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

#define rep(i,n) for(ll i = 0; i < (n); i++)
#define repd(i,n) for(ll i = (n); i >= 0; i--)
#define FOR(i,t,n) for(ll i = (t); i < (n); i++)
#define FORD(i,t,n) for(ll i = (n); i >= t; i--)
#define ALL(x) x.begin(),x.end()
#define asort(x) sort(ALL(x))

int main() {
    int a;
    cin >> a;
    if(a >= 30) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
  
}

Measured memory_bytes: 3612
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdlib, std.datetime;

immutable int N = 26;
//immutable int D = 365;
int D;
long[] C;
long[][] S;

void main() {
    auto stattime = Clock.currTime();
    D = readln.chomp.to!int;
    C = readln.split.map!(to!long).array;
    S = iota(D).map!(_ => readln.split.map!(to!long).array).array;

    auto ans = new int[](D);
    auto prev = new int[](N);
    prev[] = -1;

    foreach (i; 0..D) {
        int best_idx = -1;
        long best_score = -(1L << 59);
        foreach (j; 0..N) {
            long minus = (i - prev[j]) * C[j];
            long plus = S[i][j];
            long score = minus + plus;
            if (score >= best_score) {
                best_score = score;
                best_idx = j;
            }
        }
        ans[i] = best_idx;
    }

    ans.each!(a => writeln(a + 1));
}


Measured memory_bytes: 3696
#include<stdio.h>

int main(void)
{
      long long int a, b, c, d, x ;
      scanf("%lld %lld %lld %lld", &a, &b, &c, &d) ;
      x = a*c ;
      if (a*d > x)
          x = a*d ;
      if (b*c > x)
          x = b*c ;
      if (b*d > x)
          x = b*d ;
      printf("%lld\n", x) ;
      return 0 ;
}

Measured memory_bytes: 1704
import bisect
from itertools import accumulate

n, m, k = map(int, input().split())
A = list(accumulate([0]+list(map(int, input().split()))))
B = list(accumulate([0]+list(map(int, input().split()))))
ans = 0
for i, a in enumerate(A):
    if a > k:
        break
    j = bisect.bisect_right(B, k-a)-1
    temp = i+j
    ans = max(ans, temp)
print(ans)

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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define REPC(var, start, end) for(int var = start; var <= (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
    string a, b, c;
    cin >> a >> b >> c;

    cout << a[0] << b[0] << c[0] << endl;

	return 0;
}

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

using namespace std;

const int N = 2e5 + 2;
int n, v[N];
long long s;
int main() {
	//freopen("oj.in", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int x;
		scanf("%d", &x);
		v[i] = x;
		s += x;
	}

	long long mn = 1e14, currs = 0;
	for (int i = 1; i < n; ++i) {
		 currs += v[i];
		 s -= v[i];
		 mn = min(mn, abs(s - currs));
	}
	printf("%lld", mn);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
	using namespace std;
	#define IOS ios::sync_with_stdio(false), cin.tie(0)
	#define REP(i, n) for (int i = 0; i < n; i++)
	#define FOR(i, a, b) for (int i = a; i < b; i++)
	#define ALL(x) (x).begin(), (x).end()
	#define dump(x) cout << (x) << endl
	#define LMAX 9223372036854775807LL
	#define LMIN -9223372036854775807LL

	using ll = long long;
	template<typename T>
	using vec = vector<T>;
	using P = pair<ll, ll>;

	template <typename A, size_t N, typename T>
	void Fill(A (&array)[N], const T &val){
		fill((T *)array, (T *)(array + N), val);
	}
	
	const ll INF = 1e16;
	const ll MOD = 1e9 + 7;

	//int dx[4] = {1,0,-1,0};
	//int dy[4] = {0,1,0,-1};
	//ll pas[51][52];

	signed main(){
		IOS;
		ll n, w;
		cin >> n >> w;
		ll 	w1, v1;
		cin >> w1 >> v1;
		vec<ll> a[4];
		a[0].push_back(v1);
		REP(i, n - 1){
			ll wi, vi;
			cin >> wi >> vi;
			a[wi - w1].push_back(vi);
		}
		vec<ll> s[4];
		REP(i, 4){
			int x = a[i].size();
			sort(ALL(a[i]),greater<ll>());
			s[i].push_back(0);
			for(int j = 0;j < x;j++){
				s[i].push_back(s[i][j] + a[i][j]);
			}
		}
		ll ans = 0;
		for(int i = 0;i < s[0].size();i++){
			for(int j = 0;j < s[1].size();j++){
				for(int k = 0;k < s[2].size();k++){
					for(int l = 0;l < s[3].size();l++){
						ll size = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l;
						if(size > w)continue;
						ans = max(ans,s[0][i] + s[1][j] + s[2][k] + s[3][l]);
					}
				}
			}
		}
		dump(ans);
	}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <limits>
#include <iomanip>
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> a(n, 0);
    for( int i = 0 ; i < n ; i++ ) cin >> a[i];

    bool allow = true;
    for( int i = 0 ; i < n ; i++ ){
        if( a[i]%2 == 0){
            if( a[i]%3 != 0 && a[i]%5 != 0 ) allow = false;
        }
    }

    if( allow ) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(i,s,e) for(ll i=s;i<e;i++ )
typedef pair<ll,ll> P;
const ll mod = 1000000007;
const ll INF = 100000000000009;
ll i;

int main(){
    ll A,B,T;
    cin>>A>>B>>T;
    cout<<B*(T/A)<<endl;
}



Measured memory_bytes: 256
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
X, Y = map(int, input().split())
if X > Y:
    X, Y = Y, X
dist = X + Y
if dist % 3 != 0:
    print(0)
    quit()
n = int((2 * X - Y) / 3)
m = int((2 * Y - X) / 3)
if n < 0 or m < 0:
    print(0)
    quit()
mod = 10 ** 9 + 7
fac, ifac = make_tables(mod, n + m)
ans = cmb(n + m, m, mod, fac, ifac)
print(ans)

Measured memory_bytes: 82360
n, k, q = gets.chomp.split.map(&:to_i)

answer_of_a_n = Array.new(n, 0)

q.times do |n|
    ai =  gets.chomp.to_i
    answer_of_a_n[ai - 1] += 1
end

answer_of_a_n.each do |an|
    puts k - q + an > 0 ? 'Yes' : 'No'
end


Measured memory_bytes: 5116
n=int(input())
a=[]
m,m2=-1,-1
  
for i in range(n):
  b=int(input())
  a.append(b)
  m2=max(m2,min(m,b))
  m=max(m,b)

if m==m2:
  for i in range(n):
    print(m)
else:
  l=[m]*n
  l[a.index(m)]=m2
  for i in range(n):
    print(l[i])

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

int N;
int x[10], y[10];

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

void solve() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> x[i] >> y[i];
    double ans = 0.0;
    for(int i = 1; i <= N; i++) {
        for(int j = i + 1; j <= N; j++) ans += dist(i, j) * 2 / N;
    }
    cout << fixed << setprecision(10) << ans << endl;
    return;
}

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


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

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    
    long long n;
    cin >> n;

    int m = sqrt(n);
    long long res = 1; // n
    for (int i = 2; i <= m; i++) {
        long long num = n;
        if (num % i == 0) {
            while (num % i == 0) {
                num /= i;   
            }
            if (num % i == 1) {
                res++;
                //cout << i << " " << num << endl;
            }
        }
    }

    n--;
    int s = sqrt(n);
    for (int i = 1; i <= s; i++) {
        if (n % i == 0) {
            res += 2;
            if (n / i == i) {
                res--;
            }
            //cout << i << " " << n / i << endl;
        }
    }
    res--; // i = 1
    cout << res;

    return 0;
}

Measured memory_bytes: 256
import math
a,b,h,m = map(int,input().split())

theta_m = 6*m
theta_h = 30*h+m/2
theta = abs(theta_h-theta_m)
r = math.radians(theta)
ans = math.sqrt(a**2+b**2-2*a*b*math.cos(r))
print(ans)

Measured memory_bytes: 9480
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

    int N;
    int[] a;

    public void solve() {
        N = nextInt();
        a = new int[N];
        for(int i = 0;i < N;i++){
            a[i] = nextInt();
        }

        int[] b = new int[100000 + 1];
        for(int i = 0;i < N;i++){
            b[a[i]]++;
        }

        int ans = 0;
        for(int i = 0;i <= 100000;i++){

            int sum = b[i];
            if(i + 1 <= 100000) {
                sum += b[i+1];
            }

            if(i - 1 >= 0) {
                sum += b[i-1];
            }

            ans = Math.max(ans,sum);
        }

        out.println(ans);

    }

    public static void main(String[] args) {
        out.flush();
        new Main().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[2048];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 35072
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double D;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
 
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d %d",&x,&y)
#define rl(x) scanf("%lld",&x)
#define rl2(x,y) scanf("%lld %lld",&x,&y)
#define wd(x) printf("%d" ,x)
#define wd2(x,y) printf("%d %d",x,y)
#define wl(x) printf("%lld",x)
#define wl2(x,y) printf("%lld %lld",x,y)
#define PC(x) putchar(x)
#define GC() getchar()
#define NL printf("\n")
#define SP printf(" ")
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fr(i,s,e) for(int i=s;i<e;i++)
#define frl(i,s,e) for(ll i=s;i<e;i++)
#define frr(i,s,e) for(int i=s-1;i>=e;i--)
#define frv(i,a) for(int i = 0;i<(int)a.size();i++)
#define frvr(i,a) for(int i = a.size()-1;i>=0;i--)
#define tr(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end();i++)

#define mod 1000000007
#define maxn 100009
#define maxr 100009
// ll powd(ll n,ll md)
// {
// 	ll ans=1,pr=1;
// 	while(n)
// 	{
// 		if(n%2==1)
// 		{
// 			ans=pr*n
// 		}
// 		pr*=
// 	}
// }
int main(){
	//sstd::ios::sync_with_stdio(false); cin.tie(NULL);
	ll up[100001],down[100001];
	ll n;rl(n);
	map<string,ll> mp;
	fr(i,0,n)
	{
		string str;
		cin>>str;
		sort(ALL(str));
		mp[str]+=1;
	}
	ll sum=0;
	for(auto i: mp)
	{
		//scout<<i.F<<" "<<i.S<<endl;
		ll k=i.S;
		if(k>1)
			sum+=(k*(k-1))/2;
	}
	wl(sum);
	NL;
	return 0;
}

Measured memory_bytes: 11136
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  double tmp, gap = 1e3; int H, N, T, A, index;cin>>N>>T>>A;
  for(int i=0;i<N;i++){cin>>H;tmp = abs(A-(T-H*0.006));if(tmp<gap){gap=tmp;index=i;}}
  cout<<index+1<<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")


Measured memory_bytes: 107240
import java.util.*;


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

        StringBuilder sb = new StringBuilder();
        sb.append(line);
        if (line.charAt(line.length() - 1) == 's') {
            sb.append("es");
        } else {
            sb.append("s");
        }

        System.out.println(sb.toString());
    }
}

Measured memory_bytes: 35612
// practice with kaiboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	void main() {
		long k = sc.nextLong();
		int n = 50;
		int r = (int) (k % n);
		println(n);
		for (int i = 0; i < r; i++)
			print(n - 1 + 1 + k / n + " ");
		for (int i = r; i < n; i++)
			print(n - 1 - r + k / n + " ");
		println();
	}
}


Measured memory_bytes: 39084
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <utility>
typedef long long lint;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
#define INF 1e18

int N;
signed main()
{
	cin >> N;

	vector<int> A(N);
	rep(i, N) cin >> A[i];

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

	int left = N;
	int mm = A[0];

	int ans = INF;

	while (A.size() > 1)
	{
		sort(A.begin(), A.end());
		mm = A[0];
		for (int i = 1; i < A.size(); i++)
		{
			A[i] %= mm;
		}

		vector<int>::iterator it = A.begin();
		while (it != A.end())
		{
			if (*it == 0)
			{
				it = A.erase(it);
			}
			else
				++it;
		}

		for (auto a : A)
		{
			if (a != 0)
				ans = min(ans, a);
		}
	}

	cout << ans << endl;

	return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL a,v,b,w,t;

int main()
{
	cin>>a>>v>>b>>w>>t;
	if(t*(v-w)>=abs(a-b)) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 3652
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;

struct Edge{int to,from,cost;};

template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define mp make_pair
#define PUTLINE cout<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

double g[110][110];
double dp[110][110];

int main() {
	int n,m;
	for(;;){
		cin>>n>>m;
		if(n==0&&m==0)break;
		rep(y,n)rep(x,n)cin>>g[y][x];
		rep(y,m)rep(x,n)dp[y][x]=0;
		rep(i,n)dp[0][i]=1;
		repn(i,1,m-1)rep(j,n)rep(k,n)chmax(dp[i][j],dp[i-1][k]*g[k][j]);
		double res=0;
		rep(i,n)chmax(res,dp[m-1][i]);
		Int r=(res+0.005)*100;
		printf("%lld.%02lld\n",r/100,r%100);
	}
	return 0;
}

Measured memory_bytes: 1148
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int X,Y;

bool stoi(string A,string B){
  if(B.size()&&B[0]=='0')return false;
  X=0;
  for(int i=0;i<A.size();i++)X=X*10+A[i]-'0';
  Y=0;
  for(int i=0;i<B.size();i++)Y=Y*10+B[i]-'0';
  return true;
}

set<P> ans;

void check(){
  if((X+Y)%2)return;
  if(Y-X<0||(Y-X)%2)return;
  ans.insert(P(X,Y));
}

int main(){
  string s;
  cin>>s;
  if(stoi("",s))check();
  for(int i=0;i<s.size()-1;i++)
    if(stoi(s.substr(0,i+1),s.substr(i+1,s.size()-i-1)))check();
  if(stoi(s,""))check();
  cout<<ans.size()<<endl;
  return 0;
}

Measured memory_bytes: 3208
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long long ll;



int main() {
	int n;
	scanf("%d", &n);
	vector<int> in(n);
	for(int & x : in) {
		scanf("%d", &x);
		--x;
	}
	vector<int> len(n, INT_MIN);
	for(int x : in) {
		len[x] = 1;
		if(x) len[x] = max(len[x], len[x-1] + 1);
	}
	int best = 0;
	for(int x : len) best = max(best, x);
	printf("%d\n", n - best);
}


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

int main() {
    string s; cin >> s;
    string t("YAKI");
    rep(i, min(s.size(),t.size())) {
        if (s.at(i) != t.at(i)) {
            puts("No");
            return 0;
        }
    }
    if (s.size() < t.size()) {
        puts("No");
    }
    else {
        puts("Yes");
    }

    return 0;
}

Measured memory_bytes: 256
def main():
    N, M, C = map(int, input().split())
    B = [int(a) for a in input().split()] 
    A = [[int(a) for a in input().split()] for m in range(N)]
    count = 0
    for i in range(N):
        s = 0
        for j in range(M):
            s += B[j]*A[i][j]
        if s + C > 0:
            count += 1
    print(count)
main()

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

int main()
{
  int n;
  cin >> n;
  int ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      for(int k = 1; k <= n; k++){
        ans += gcd(i, gcd(j, k));
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3540
package main

import (
	"fmt"
	"strings"
)

func Solve(s string) int {
	var a int
	b := strings.Count(s, ".")
	n := b
	for i := 0; i < len(s); i++ {
		if s[i] == '#' {
			a++
		} else {
			b--
		}
		if c := a + b; c < n {
			n = c
		}
	}
	return n
}

func main() {
	var n int
	fmt.Scanf("%d", &n)
	var s string
	fmt.Scanf("%s", &s)
	result := Solve(s)
	fmt.Println(result)
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> a(N+1);
    for(int i=1; i<=N; i++) {
        cin >> a.at(i);
    }
    vector<int> b(N+1);
    for(int i=N; i; i--) {
        b.at(i) = a.at(i);
        for(int j=2; i*j<=N; j++) {
            if(b.at(i*j) == 1) {
                b.at(i) = 1 - b.at(i);
            }
        }
    }
    int M = accumulate(b.begin(), b.end(), 0);
    cout << M << endl;
    for(int i=1; i<=N; i++) {
        if(b.at(i) == 1) {
            cout << i << " " << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI (acos(-1))
#define ct cout<<
#define cn cin>>
#define spc <<" "<<
#define nl puts("")
#define _fl(x) puts("FLAG " #x);
#define  _(x)  cout<< #x <<" is "<< x <<endl;
#define fs first
#define sc second
#define pb push_back
#define all(v)  (v).begin(), (v).end()
#define _109 (1000000000)
#define _0(arr) memset(arr,0,sizeof ( arr ) )
#define _1(arr) memset(arr,-1,sizeof ( arr ) )
#define _ninp(n,arr) for(int i=0; i<n;i++)cin>>arr[i];
#define _nout(n,arr) for(int i=0; i<n;i++)cout<<arr[i]<<" \n"[i==n-1];
double _eps=1e-6;
long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ull g=1000000000000000;

int main() {

    double l;
    cn l;

    

    printf("%.10f\n",(l*l*l/27));







    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;cin>>n;
    int cnt = 0;
    for(int i=0;i<n;i++)
    {
    	ll x;cin>>x;
    	while(x%2==0)
    	{
    		cnt++;x/=2;
    	}
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <limits.h>
#include <utility>
#include <stack>

using namespace std;

#define fs first
#define sc second

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> T;

int main(){
    ll N;
    cin >> N;
    ll a[101000];
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }

    ll bMax = 1;
    ll res = a[0] - 1;
    for(int i = 1; i < N; i++){
        if(bMax + 1 >= a[i]){
            bMax = max(bMax, a[i]);
            continue;
        }
        int x = (a[i] - 1) / (bMax + 1);
        res += x;
    }
    cout << res << endl;


    return 0;
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int a,b,c,d;cin>>a>>b>>c>>d;
  int l=a+b;
  int r=c+d;
  if(l>r){
    cout<<"Left"<<endl;
  }else if(l==r){
    cout<<"Balanced"<<endl;

  }else{
    cout<<"Right"<<endl;

  }

  return 0;
}


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

const int MOD = 1000000007;

int64_t dp[110][110000];
int64_t dp_sum[110][110000];
int a[110];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dp[0][0] = 1;
    for (int j = 0; j <= k; j++) dp_sum[0][j] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = dp_sum[i-1][j];
            if (j-a[i]-1 >= 0) dp[i][j] -= dp_sum[i-1][j-a[i]-1];
            if (j-1 >= 0) dp_sum[i][j] = dp_sum[i][j-1] + dp[i][j];
            else dp_sum[i][j] = dp[i][j];
            dp[i][j] %= MOD;
            dp_sum[i][j] %= MOD;
        }
    }
    if (dp[n][k] < 0) dp[n][k] += MOD;
    cout << dp[n][k] << endl;
}

Measured memory_bytes: 176256
n=int(input())
a=list(map(int,input().split()))
dp=[0]*n 
for i in range(1,n):
    if i==1:
        dp[i]=abs(a[i]-a[i-1]) 
    else:
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))
print(dp[n-1])        

Measured memory_bytes: 13980
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	int a[n], b[n], c[n-1];
	for( int i = 0; i < n; ++i ){
		cin >> a[i];
		a[i] -= 1;
	}
	for( int i = 0; i < n; ++i ) cin >> b[i];
	for( int i = 0; i < n-1; ++i ) cin >> c[i];
	int score = 0;
	for( int i = 0; i < n; ++i ) score += b[a[i]];
	for( int i = 1; i < n; ++i ){
		if( a[i]-a[i-1] == 1 ) score += c[a[i-1]];
	}
	cout << score << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    if(s=="RRR") cout<<3;
    else if(s=="RRS"||s=="SRR") cout<<2;
    else if(s=="SSS") cout<<0;
    else cout<<1;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int> m;
    int sum=0;
    int i=1;
    while(sum<n)
    {
        sum+=i;
        m[i]++;
        i++;
    }
    int rem=sum-n;
    m.erase(rem);
    for(auto it:m)
    cout<<it.first<<endl;
}

Measured memory_bytes: 3820
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


int main(){
    int N;
    cin>>N;
    // vector<ll> a;
    ll a_;
    ll m=9223372036854775807, s=0;
    int n=0;
    rep(i, N){
        cin>>a_;
        if(a_<0){
            ++n;
        }
        m = min(m, abs(a_));
        s+=abs(a_);
        // a.push_back(a_);

    }
    if(n%2==1){
        s-=m*2;
    }
    cout<<s<<endl;

    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mp(x,y)     make_pair(x,y) 
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,a,n)   for(ll i=a;i<n;i++)
#define frr(i,a,n)  for(ll i=n-1;i>=a;i--)


const ll N   =  500005;
const ll mod = 1e9 + 7;

using namespace std;


void solve()
{
// string s;
  ll n,m,k,x=0,y=0,c=0,q,ans=0;
  cin>>n;
  ll a[n];
  for (ll i = 0; i < n; ++i)
  {
  cin>>a[i];
  }
  ll arr[n],b[n];
  arr[0] = a[0];
  b[n-1] = a[n-1];
  for (int i = 1; i < n; ++i)
  {
    arr[i] = __gcd(arr[i-1],a[i]);
    b[n-i-1] = __gcd(b[n-i],a[n-i-1]);
  }
  ans = max(arr[n-2],b[1]);
  for (int i = 1; i < n-1; ++i)
  {
    x = __gcd(arr[i-1],b[i+1]);
    ans = max(x,ans);
  }

  

  cout<<ans<<" ";
}

signed main(){
  
      ios_base::sync_with_stdio(false);   
      cin.tie(NULL);
      ll T=1;
      //cin>>T;
      while(T--)
      {
      solve();
      }
      return 0;
    }


Measured memory_bytes: 2560
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
if A.count(0) > 0:
    print(0)
else:
    ans = A[0]
    flag = 0
    for i in range(1,N):
        ans *= A[i]
        if ans > 10**18:
            flag += 1
            print(-1)
            break
    if flag == 0:
        print(ans)

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

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	B += A;
	C += D;
	if(B>C)cout << "Left" << endl;
	if(B<C)cout << "Right" << endl;
	if(B==C)cout << "Balanced" << endl;
	return 0;
}

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

int main(){
  int X;
  cin>>X;
  int N=1000000;
  vector<int> A(N);
  A.at(0)=1;
  for(int i=2; i<=N/2; i++){
    for(int j=2; i*j<=N; j++){
      if(A.at(i*j-1)==0){
        A.at(i*j-1)=1;
      }
    }
  }
  for(int i=0; i<N; i++){
    if(A.at(i)==0&&i+1>=X){
      cout<<i+1<<endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 7212
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

class UnionFind {
    vector<int> par;
    int n;

public:
    UnionFind(int n) : par(n, -1) {}

    int find(int x) {
        if (par[x] < 0) return x;
        return par[x] = find(par[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

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

    int n, m;
    cin >> n >> m;

    UnionFind uf(100005);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;

        if (!uf.same(x, y)) {
            uf.unite(x, y);
            n--;
        }
    }

    cout << n << "\n";
    return 0;
}

Measured memory_bytes: 1272
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main(){
    cin>>N>>K;
    vec a(N);
    rep(i,N){
        cin>>a[i];
        K -= a[i];
    }
    sort(a.begin(), a.end());
    cout<<N + (K / a[0])<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vec vector
typedef long long ll;
typedef pair<ll,pair<ll,ll>> P;
//const ll big=998244353;
const ll big=1000000007LL;
const ll INF=1e18;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
    if(x>y)return x;
    else return y;
}
ll min(ll x,ll y){
    if(x<y)return x;
    else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}

struct edge{
    ll to,cost;
};



struct graph{
    vector<vector<edge>> g;
    vector<ll> d;

    graph(ll n) : g(n),d(n,INF){}

    void addedge(const ll s,const ll t,const ll cost){
        edge e;
        e.to=t;
        e.cost=cost;
        g[s].emplace_back(e);
    }
    //E+VlogV
    void dijkstra(ll s,set<pair<int,int>> &al){//sからstartのdijkstra
        rep(i,d.size())d[i]=INF;
        d[s]=0;
        priority_queue<P,vector<P>,greater<P>> que;
        que.push(P(0,{s,-1}));
        while(!que.empty()){
            P pa=que.top();que.pop();
            ll k=pa.second.first;
            if(d[k]<pa.first)continue;
            if(pa.second.second==-1)goto skip;
            if(pa.second.second < pa.second.first)swap(pa.second.second , pa.second.first);
            al.insert({pa.second.first,pa.second.second});
            skip:;
            for(auto e:g[k]){
                if(d[e.to]>d[k]+e.cost){
                    d[e.to]=d[k]+e.cost;
                    que.push(P(d[e.to],{e.to,k}));//secondには頂点情報が入っている
                }
            }
        }
    }
};


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/
    
    set<pair<int,int>> al;
    int n,m;cin >> n >> m ;
    graph g(n);
    rep(i,m){
        int a,b,c;cin >> a >> b >> c;
        g.addedge(a-1,b-1,c);
        g.addedge(b-1,a-1,c);
    }
    rep(i,n){
        g.dijkstra(i,al);
    }
    cout << m-(int)al.size() << endl;
}

Measured memory_bytes: 3700
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define v vector
#define ALL(x) x.begin(),x.end()
#define rALL(x) x.rbegin(),x.rend()
#define endl '\n'
#define F first
#define S second
#define DEBUG

template<typename T> void DBG(const char* name, T&& H) {
	cerr << name << " = " << H << ')' << endl;
}

template<typename T, typename... Args> void DBG(const char* names, T&& H, Args&&... args) {
	const char* NEXT = strchr(names+1, ',');
	cerr.write(names, NEXT-names) << " = " << H << " |";
	DBG(NEXT+1, args...);
}

#ifdef DEBUG
	#define dbg(...) cerr << __FUNCTION__ << ' ' <<__LINE__ << " : (", DBG(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
#endif

using ll = long long;
using ld = long double;

const long long mod = 998244353;
const long double PI = acos(-1.0);
const long long INF = 1e18;
const int maxN = 2e5+1;

void Solve() {
	long long N, D;
	cin >> N >> D;
	vector<pair<long long, long long>> pts(N);
	for(int i = 0; i < N; i ++) {
		cin >> pts[i].first >> pts[i].second;
	}
	int count = 0;
	for(int i = 0; i < N; i ++) {
		long long dist = pts[i].first*pts[i].first + pts[i].second*pts[i].second;
		if(dist <= D*D) count ++;
	}
	cout << count << endl;
}

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

	int tt = 1;
	while(tt --) {
		Solve();
	}
	
	return 0;
}

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

class Program
{
    void Run()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int a = sc.NextInt();
        int b = sc.NextInt();
        Console.WriteLine(Math.Min(b, a * n));
    }

    static void Main(string[] args)
    {
        new Program().Run();
    }

    static long Gcd(long a, long b)

    {
        if (a < b) return Gcd(b, a);
        if (b == 0) return a;
        return Gcd(b, a % b);
    }

    static long Lcm(long a, long b)
    {
        long d = Gcd(a, b);
        return a / d * b;
    }
}

class Scanner
{
    int index = -1;
    string[] buf;

    public Scanner()
    {
    }

    public int NextInt()
    {
        CheckNext();
        return int.Parse(buf[index++]);
    }

    public long NextLong()
    {
        CheckNext();
        return long.Parse(buf[index++]);
    }

    public double NextDouble()
    {
        CheckNext();
        return double.Parse(buf[index++]);
    }

    public string NextString()
    {
        CheckNext();
        return buf[index++];
    }

    private void CheckNext()
    {
        if (index >= 0 && index < buf.Length) return;

        buf = Console.ReadLine().Split(' ');
        index = 0;
    }
}


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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, Q;
    cin >> n >> Q;
    string s;
    cin >> s;
    ll cnt[n + 1] = {};
    for(int i = 1; i < n; i++) {
        if(s[i - 1] == 'A' && s[i] == 'C') {
            cnt[i]++;
        }
    }
    for(int i = 0; i <= n; i++) {
        cnt[i + 1] += cnt[i];
    }
    for(int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << cnt[r] - cnt[l - 1] - (r < n && s[r - 1] == 'A' && s[r] == 'C') << endl;
    }
}

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


int main(){
 int n;
 cin>>n;
 vector<int> a(n);
 int f2=0;

 for(int i=0;i<n;i++){
    cin>>a[i];
 }
 vector<int> arr(maxn,0);
for(auto x: a){
    arr[x]+=1;
    f2=__gcd(f2,x);
}
int f1=1;
 //sort(a.begin(),a.end());
 for(int i=2;i<maxn;i++){
        int ct=0;
    for(int j=i;j<maxn;j+=i){
           ct+=arr[j];
    }
    f1=f1&(ct<=1);
 }

 if(f1==1){
    cout<<"pairwise coprime"<<endl;
 }
 else if(f2==1){
    cout<<"setwise coprime"<<endl;
 }
 else{
    cout<<"not coprime"<<endl;
 }

}


Measured memory_bytes: 11156
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<28);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int a[18][2],dp[1<<18][18],b[18];

int main(void){
	int n,i,j,mask,k,t,ans=-INF;
	fill(dp[0],dp[1<<18],-INF);
	cin >> n; b[n] = (1<<n);
	for(i=0; i<n; ++i){
		cin >> a[i][0];
		b[i] = (1<<i);
	}
	for(i=0; i<n; ++i){
		cin >> a[i][1];
		dp[b[i]][i] = 0;
	}
	for(mask=1; mask<b[n]; ++mask){
		k = __builtin_popcount(mask);
		for(i=0; i<n; ++i){
			if(!(mask&b[i])){
				continue;
			}
			t = a[i][abs(i-k+1)%2];
			for(j=0; j<n; ++j){
				if(mask&b[j]){
					continue;
				}
				if(t>a[j][abs(j-k)%2]){
					continue;
				}
				dp[mask+b[j]][j] = max(dp[mask+b[j]][j],dp[mask][i]+__builtin_popcount(mask&(b[j]-1)));
			}
		}
	}
	for(i=0; i<n; ++i){
		ans = max(ans,dp[b[n]-1][i]);
	}
	cout << ((ans<0)?(-1):(n*(n-1)/2-ans)) << endl;
	return 0;
}


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

int main(){
  int n,m,c;
  scanf("%d%d%d",&n,&m,&c);
  
  ll sum = 0;
  vector< vector<pll> > g(n);
  for(int i=0;i<m;i++){
    int a,b,d;
    scanf("%d%d%d",&a,&b,&d);
    a--; b--;
    g[a].push_back(pll(d,b));
    g[b].push_back(pll(d,a));
    sum += d;
  }

  vector<ll> d(n,1e18); d[0] = 0;
  priority_queue< pll, vector<pll>, greater<pll> > q; 
  q.push(pll(0,0));

  while(q.size()){
    pll p = q.top(); q.pop();
    ll c = p.first, v = p.second;
    for(pll e : g[v]){
      ll nc = c + e.first, u = e.second;
      if(d[u] > nc){
	d[u] = nc;
	q.push(pll(nc,u));
      }
    }
  }

  vector<pll> ord(n);
  for(int i=0;i<n;i++)ord[i] = pll(d[i],i);
  sort(ord.begin(),ord.end());

  vector<int> used(n,0);
  ll res = 1e18;
  for(int i=0;i<n;i++){
    int v = ord[i].second;
    for(pll e : g[v]){
      if(used[e.second])sum -= e.first;
    }
    res = min(res, sum + ord[i].first*c);
    used[v] = 1;
  }
  printf("%lld\n",res);
}

Measured memory_bytes: 17152
import java.io.*;
import java.util.*;

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        String s = in.next();
        int k = in.nextInt();

        out.println(check(s, 0, k));
    }

    private static int check(String s, int current, int remain) {
        if (current == s.length()) {
            return remain == 0 ? 1 : 0;
        }

        if (remain == 0) {
            return 1;
        }

        int d = s.charAt(current) - '0';
        int ret = 0;
        for (int i = 0; i < d; i++) {
            if (i == 0) {
                ret += combination(s.length() - current - 1, remain) * power(9, remain);
            } else {
                ret += combination(s.length() - current - 1, remain - 1) * power(9, remain - 1);
            }
        }
        ret += check(s, current + 1, d == 0 ? remain : remain - 1);
        return ret;
    }

    private static int combination(int n, int r) {
        int ret = 1;
        for (int i = 0; i < r; i++) {
            ret *= (n - i);
        }
        for (int i = 1; i <= r; i++) {
            ret /= i;
        }
        return ret;
    }

    private static int power(int n, int pow) {
        int ret = 1;
        for (int i = 0; i < pow; i++) {
            ret *= n;
        }
        return ret;
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 23124
#pragma optimize("Ofast")
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
int len[2005];
char s[2005][10005];
bitset<10005> can[2005];
pair<int,int> dp[10005][2005];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		scanf("%s",s[i]);
		len[i]=strlen(s[i]);
	}
	for(int i=0;i<n;i++){
		can[i].reset();
	}
	can[n]=1;
	for(int i=n-1;i>=0;i--){
		can[i]=can[i+1]|(can[i+1]<<len[i]);
	}
	int cnt=0,ii=0;
	for(int i=0;i<n;i++){
		if(can[i+1][k-len[i]]) dp[0][cnt++]=make_pair(i,0);
	}
	string res;
	for(int i=1;i<=k;i++){
		char mi='z';
		int cnt2=0;
		for(int j=0;j<cnt;j++){
			mi=min(s[dp[i-1][j].first][dp[i-1][j].second],mi);
		}
		res+=mi;
		int miid=1e9;
		for(int j=0;j<cnt;j++){
			int fi=dp[i-1][j].first,se=dp[i-1][j].second;
			if(s[fi][se]==mi){
				if(se+1==len[fi]) miid=min(miid,fi);
				else{
					dp[i][cnt2++]=make_pair(fi,se+1);
				}
			}
		}
		for(int j=miid+1;j<n;j++){
			if(k-len[j]-i>=0&&can[j+1][k-len[j]-i]) dp[i][cnt2++]=make_pair(j,0);
		}
		cnt=cnt2;
	}
	cout<<res;
}

Measured memory_bytes: 178688
#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = sum([int(i) for i in input().split()]) 
    c = [int(i) for i in input().split()]
    for i in range(len(a)-1):
        if a[i] + 1 == a[i+1]:
            ans += c[a[i]-1]  
    print(ans)
main()




Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn]={0};
int main(){
	int h,n,count=0;
	cin>>h>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		count+=a[i];
	}
	if(count<h)cout<<"No";
	else cout<<"Yes";
	return 0;
}

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

void solve(int n);

int main(){
	while(1){
		int n;
		cin >> n;
		if(n==0) break;
		solve(n);
		cout << endl;
	}
}


void solve(int n){
	if(n == 0) return;
	solve(n/8);
	int a = n % 8;
	cout << (a==4?5:(a>4?a+2:a));
}

Measured memory_bytes: 1160
// https://atcoder.jp/contests/abc144/tasks/abc144_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)
#define rad2deg(a) ((a) / M_PI * 180.0) /* rad を deg に換算するマクロ関数 */
#define deg2rad(a) ((a) / 180.0 * M_PI) /* deg を rad に換算するマクロ関数 */

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    double a, b, c, ans = 0;
    cin >> a >> b >> c;
    double x = 2 * c / (a * a) - b;
    if (x >= 0) {
        ans = atan2((b - x), a);
    } else {
        x = 2 * c / (a * b);
        ans = atan2(b, x);
    }
    printf("%.10f\n", rad2deg(ans));

    return 0;
}


Measured memory_bytes: 256