akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvl vector<vector<ll>>
#define v(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

//-I/usr/local/include
#include <boost/multiprecision/cpp_dec_float.hpp>
namespace mp = boost::multiprecision;
typedef mp::number<mp::cpp_dec_float<1000, std::int64_t>> fl_1000;
typedef mp::cpp_dec_float_100 fl;
/*
  mp::sqrt(x)

*/

int main(int argc, char const *argv[]) {
  fl_1000 a, b, c;std::cin >> a >> b >> c;
  bool f = mp::sqrt(a)+mp::sqrt(b)<mp::sqrt(c);
  std::cout << (f?"Yes":"No") << '\n';
  return 0;
}


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

int main()
{
	double a, b, C, t ,PI;
	double S, c, L, h;
	cin >> a >> b >> t;

	PI = acos(-1);
	C = t*PI / 180;

	S = a*b*sin(C)/2;
	c = sqrt(a*a + b*b - 2*a*b*cos(C));
	L = a + b + c;
	h = 2 * S / a;

	printf("%lf\n%lf\n%lf\n", S, L, h);

	return 0;
}

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

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

main() {
  int H, W; cin >> H >> W;
  vector<string> S(H + 2, string(W + 2, '.'));
  for (int i = 1; i < H + 1; i++) {
    string str; cin >> str;
    S[i].replace(1, H, str);
  }

  for (int i = 1; i < H + 1; i++) {
    for (int j = 1; j < W + 1; j++) {
      if (S[i][j] == '#') {
        cout << '#';
      } else {
        int cnt = 0;
        for (int k = 0; k < 8; k++) if (S[i + dy[k]][j + dx[k]] == '#') cnt++;
        cout << cnt;
      }
      if (j == W) cout << endl;
    }
  }
}


Measured memory_bytes: 256
int main(void){int a[100000],n,s[100001]={0},f[100001]={0},i,j,ans=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);f[a[i]]=1;}
for(i=0;i<100000;i++)ans+=f[i+1];
printf("%d\n",ans-((n-ans)%2?1:0));
return 0;}

Measured memory_bytes: 896
(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
      (cons (subseq str 0 pos)
            (split x (subseq str (+ pos size))))
      (list str))))

(setq *n* (read))
(setq *ps* (mapcar #'parse-integer (split " " (read-line))))

(defun count-transposition (l i)
  (if (equal l nil)
    0
    (if (equal (car l) i)
      (count-transposition (cdr l) (1+ i))
      (1+ (count-transposition (cdr l) (1+ i))))))

(format t "~a~%"
 (if (<= (count-transposition *ps* 1) 2)
   "YES"
   "NO"))

Measured memory_bytes: 7008
/*
author : shah_entrance
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string str;
    cin>>str;
    if(str.length()==2)
        cout<<str<<endl;
    else
    {
        reverse(str.begin(),str.end());
        cout<<str<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();
        int n = s.length;
        long[][] dp = new long[n+1][13];
        int[] mod = {1,10,9,12,3,4};
        int div = 1000000007;
        dp[0][0] = 1;
        int digit ;
        for(int i=0;i<n;i++){
            if(s[n-1-i]=='?'){
                for(int j=0;j<=9;j++){
                    digit = j*mod[i%6]%13;
                    for(int k=0;k<13;k++){
                        dp[i+1][k] += dp[i][(k-digit+13)%13];
                        dp[i+1][k]%=div;
                    }
                }
            }else{
                digit = (s[n-1-i]-'0')*mod[i%6]%13;
                for(int j=0;j<13;j++){
                    dp[i+1][j] += dp[i][(j-digit+13)%13];
                    dp[i+1][j]%=div;
                }
            }
        }
        System.out.println(dp[n][5]);
    }
}

Measured memory_bytes: 38968
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()

import bisect as bi
ans=0
for i in range(n):
    q=B[i]
    oka= bi.bisect_left(A,q)
    okb= n- bi.bisect_right(C,q)
    ans+=oka*okb
print(ans)

Measured memory_bytes: 29552
#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long

int calnim(int x,int y)
{
  int tmp,tmp1,tmp2;
  tmp=x;
  while (tmp%y!=0)
  {
    tmp1=(tmp/y+1);
    tmp2=tmp%y;
    tmp2%=tmp1;
    if (tmp2==0) return tmp/y;
    tmp-=tmp%y;
    tmp+=tmp2;
    tmp-=tmp1;
  }
  return tmp/y;
}

int main()
{
  int ans,x,y,n,i;
  scanf("%d",&n);
  ans=0;
  for (i=0;i<n;i++)
  {
    scanf("%d%d",&x,&y);
    ans^=calnim(x,y);
  }
  if (ans==0) printf("Aoki\n");
  else printf("Takahashi\n");
  return 0;
}

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

int main() {
  int N;
  cin>>N;
  vector<long long> A(N),B(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  B.at(0)=A.at(0);
  for(int i=1;i<N;i++){
    B.at(i)=B.at(i-1)+A.at(i);
  }
  long long all=B.at(N-1);
  long long ans=2100000000LL;
  for(int i=0;i<N-1;i++){
    ans=min(ans,abs(all-B.at(i)*2LL));
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 6364
#include <bits/stdc++.h>
using namespace std;
#define print(x) cout << (x) << endl;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, A;
    cin >> X >> A;
    if (X < A) {
        print(0);
    }
    else {
        print(10);
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
const ll longinf=1ll<<60;
const int inf=(1<<30)-1;

int main(){
    int n;
    cin>>n;
    int p[n];
    rep0(i,n) cin>>p[i];
    int cnt=0;
    rep0(i,n){
        if(p[i]!=i+1){
            cnt++;
        }
    }
    if(cnt<=2){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256
//TYPE
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>

using namespace std;
typedef long long ll;
#define cls(x) memset(x,0,sizeof(x))


const int INF = 0x3f3f3f3f;
const int SZ = 100;

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  map<char,int> cnt;
  for(auto ch : s) {
    cnt[ch]++;
  }
  if(cnt['R'] > cnt['B']) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x[100000],y[100000]={0};
int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            y[1]+=x[i];
        }
        else
        {
            y[1]-=x[i];
        }
    }
    for(int i=2;i<=n;i++)
    {
        y[i]=2*x[i-1]-y[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        cout<<y[i]<<" ";
    }
    return 0;
}


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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            final int n = Integer.parseInt(br.readLine());
            if (n == 0) { break; }
            
            Map<String, Long> data = new HashMap<>();
            Map<String, Long> out = new HashMap<>();
            for (int i=1; i <= n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String e = st.nextToken();
                Long p = Long.parseLong(st.nextToken());
                Long q = Long.parseLong(st.nextToken());
                Long total = data.getOrDefault(e, 0L) + p * q;
                data.put(e, total);
                if (total >= 1_000_000L) {
                    if (out.putIfAbsent(e, total) == null) {
                        System.out.println(e);
                    }
                }
            }
            if (out.size() == 0) {
                System.out.println("NA");
            }
        }
    }
}

Measured memory_bytes: 25876
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<ll> _size; // 属する連結成分の大きさ

    UnionFind(ll N) : par(N), _size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) {
            par[i] = i;
            _size[i] = 1;
        }
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        _size[ry] += _size[rx];
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }

    ll size(ll x){
        ll rx = root(x);
        return _size[rx];
    }
};

int main() {

    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll> f(N, 0), b(N, 0);
    UnionFind U = UnionFind(N);
    ll k, l;
    REP(i, M){
        cin >> k >> l;
        k--;
        l--;
        f[k]++;
        f[l]++;
        U.unite(k, l);
    }
    REP(i, K){
        cin >> k >> l;
        k--;
        l--;
        if (U.same(k, l)){
            b[k]++;
            b[l]++;
        }
        
    }
    REP(i, N){
        ll tmp = U.size(i) - f[i] - b[i] - 1;
        cout << tmp << " ";
    }
    cout << endl;

    return 0;
}



Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main() {
	int N, Y;
	cin >> N >> Y;
	int T = Y / 1000;
	int x = -1, y = -1, z = -1;

	if (T<N) cout << x << " " << y << " " << z;
	else {
		for (int i = 0;i <= (T - N) / 9;i++) {
			int X, Y, Z;
			X = i;
			Y = (T - N - 9 * X) / 4;
			Z = N - X - Y;
				if ((T - N - 9 * X) % 4 == 0 && Z >= 0) {
					x = X;
					y = Y;
					z = Z;
					i = (T - N) / 9 + 1;
				}
		}
		cout << x << " " << y << " " << z;
	}

}

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

int main() {
  int H,W;
  cin >> H >> W;
  
  for(int i = 0;i < W+2; i++) {
    cout << "#";
  }
  
  cout << endl;
  
  vector<string> a(H * W);
  
  for (int i = 0; i < H * W;i++) {
    cin >> a.at(i);
  }
  
  for (int i = 0; i < H; i++) {
    cout << "#" + a.at(i) + "#" << endl;
  }
  
  for(int i = 0;i < W+2; i++) {
    cout << "#";
  }
  
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m; cin>>n>>m;
    vll a(n);
    rep(i,n) cin>>a[i];
    rep(i,n) a[i]/=2;
    ll G=1;
    rep(i,n){
        G = a[i]*G/__gcd(G, a[i]);
    }
    bool ng=false;
    rep(i,n){
        if ((G/a[i])%2==0){
            ng = true;
            break;
        }
    }
    if (ng){
        cout<<"0\n";
    }else{
        cout<<m/G-m/(G*2)<<endl;
    }

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
using namespace std;
const int N = 1e5+5;
void fast(){std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
ll n,ans;
int main()
{
	fast();
	cin>>n;
	if(n%2==1)ans=0;
	else
	{
		n/=2;
		while(n)
		{
			ans+=n/5;
			n/=5;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <iomanip>


int max1 = -1e9;

using namespace std;

int main(int argc, const char * argv[]) {

    std::ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cin.tie(NULL);
	int n;
	cin >> n;
	long long soma = 0 ;
	vector<int> lista(10e5 + 10);
	for(int i =0;i<n;i++){
		int aux;
		cin >> aux;
		lista[aux] += 1;
		soma += aux;
	}

	int q;
	cin >> q;
	
	for(int i=0;i<q;i++){
		int aux,aux1;
		cin >> aux >> aux1;
		int tmp;
		int val1;
		int val2;
		val1 = aux * lista[aux];
		val2 = aux1 * lista[aux];
		int val = val2 - val1;
		soma += val;
		tmp = lista[aux];
		lista[aux] = 0;
		lista[aux1] += tmp;
		
		cout << soma << endl;
	}

	return 0;
}



Measured memory_bytes: 7156
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m = LI()

graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)  # 有向グラフなら消す

seed = [False] * n
seed[0] = True

def dfs(v,seed):
    if all(seed):
        return 1
    ans = 0
    for i in graph[v]:
        if seed[i]:
            continue
        seed[i] = True
        ans += dfs(i,seed)
        seed[i] = False
    return ans
print(dfs(0,seed))

Measured memory_bytes: 9156
#include <iostream>
#include <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
vector<int> lazy;
vector<int> ary;
int n;
int right(int k){
  return 2*k+2;
}
int left(int k){
  return 2*k+1;
}
int parent(int k){
  return (k-1)/2;
}
void eval(int k){
  if(lazy[k]==INT_MAX)return;
  if(k<n-1){
    lazy[left(k)]=lazy[right(k)]=lazy[k];
  }
  ary[k]=lazy[k];
  lazy[k]=INT_MAX;
}

void update(int a,int b,int k,int x,int l,int r){
  eval(k);
  if(r<=a||b<=l)return;
  if(a<=l&&r<=b){
    lazy[k]=x;
    eval(k);
  }
  else{
    update(a,b,left(k),x,l,(l+r)/2);
    update(a,b,right(k),x,(l+r)/2,r);
    ary[k] = min(ary[left(k)],ary[right(k)]);
  }
}

int query(int a,int b,int k,int l,int r){
  int res;
  eval(k);
  if(r<=a || b<=l){
    res = INT_MAX;
  }
  else if(a<=l && r<=b)res = ary[k];
  else res = min(query(a,b,left(k),l,(l+r)/2),query(a,b,right(k),(l+r)/2,r));
  return res;
}
void findmin(int a,int b){
    cout<<query(a,b+1,0,0,n)<<endl;
}
int main(){
  int m,q,com,s,t,x,i=0;
  cin>>n>>q;
  while(n>pow(2,i))i++;
  n = pow(2,i);
  m = n*2-1;
  lazy.resize(m+1);
  ary.resize(m+1);
  for(int i=0;i<=m;i++){
    lazy[i] = INT_MAX;
    ary[i] = INT_MAX;
  }
  for(int i=0;i<q;i++){
    cin>>com>>s>>t;
    if(!com){
      cin>>x;
      update(s,t+1,0,x,0,n);
    }
    else
      findmin(s,t);
  }
  return 0;
}



Measured memory_bytes: 5168
import java.util.Scanner;

public class Main {
    private static final int INITIAL_VALUE = Integer.MAX_VALUE / 2;

    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int[][] table = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            final String s = scanner.next();
            for (int j = 1; j <= n; j++) {
                final int value = s.charAt(j - 1) - '0';
                table[i][j] = value == 0 ? INITIAL_VALUE : 1;
            }
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        table[i][j] = 0;
                    }
                    if (table[i][j] < INITIAL_VALUE && table[i][k] + table[k][j] < INITIAL_VALUE
                            && table[i][j] % 2 != (table[i][k] + table[k][j]) % 2) {
                        System.out.println(-1);
                        return;
                    }
                    table[i][j] = Math.min(table[i][j], table[i][k] + table[k][j]);
                }
            }
        }

        int max = 0;
        for (final int[] array : table) {
            for (final int value : array) {
                max = Math.max(max, value + 1);
            }
        }

        System.out.println(max);
    }
}


Measured memory_bytes: 25368
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+1;
const int M = 1e9+7;
vector<vector<int>> g(N);

ll dfs(int x, int p, int k){
    int num;
    if(p == -1) num = k-1;
    else num = k-2;

    if((int)g[x].size()>k) return 0;
    else {
        ll res = 1;
        for(auto to:g[x]){
            if(to==p)  continue;
            res*=num%M;
            res%=M;
            num--;
        }
    

    for(auto to: g[x]){
        if( to==p) continue;
        res *= dfs(to,x,k);
        res%=M;
    }
    return res;
    }
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i = 0; i < n-1; i++){
        int a,b;
        cin>>a>>b;
        --a,--b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ll ans = k*dfs(0,-1,k);
    cout<<ans%M;
}


Measured memory_bytes: 11520
class M
  attr_accessor :a, :i, :a_a_i, :a_s_i
  def initialize(a, i)
    @a = a.to_i
    @i = i
    @a_a_i = @a + i
    @a_s_i = @a - i
  end
end

N = $stdin.gets.to_i
A = []
AsIMap = {}
$stdin.gets.split.each.with_index(1) do |a, i|
  m = M.new(a, i)
  A.push(m)
  if m.a_s_i < 0
    list = AsIMap[-m.a_s_i] ||= []
    list.push(m)
  end
end
count = 0
A.each do |m|
  list = AsIMap[m.a_a_i] or next
  count += list.length
end
puts count


Measured memory_bytes: 53892
#include <iostream>

using namespace std;

const int kMaxN = 100;


void insertionSort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;

        for (int k = 0; k < n; k++) {
            cout << a[k];

            if (k < n - 1) {
                cout << " ";
            }
        }

        cout << endl;
    }
}


int main() {
    int n;
    int A[kMaxN];

    cin >> n;

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

        if (i < n - 1) {
            cout << " ";
        }
    }
    
    cout << endl;
    
    insertionSort(A, n);
}




Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N=0,M=0;
  cin >> N >> M;
  vector<ll>A(M);
  vector<ll>B(M);
  rep(i,M){
    cin >> A[i];
    cin >> B[i];
  }
  sort(B.begin(), B.end()); //小さい順
  sort(A.begin(), A.end()); //小さい順
  reverse(A.begin(), A.end());
  if(B[0] >= A[0]){
    cout << B[0]-A[0]+1;
  }
  else{
    cout << "0";
  }
}

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

using namespace std;

int main(){
  int n, p[200009], q[200009];
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> p[i];
    q[p[i]]=i;
  }
  int cur=q[1];
  int cnt=1;
  int mx=1;
  for(int i=2;i<=n;i++){
    if(q[i]<cur){
      cnt=0;
    }
    cnt++;
    cur=q[i];
    mx = max(mx, cnt);
  }
  cout << n - mx << endl;
}




Measured memory_bytes: 1792
N = int(input())
A = list(map(int,input().split()))
flag = 1
count = 0
while flag:
    flag = 0
    for j in range(1,N):
        if A[N-j] < A[N-j-1]:
            dummy = A[N-j]
            A[N-j] = A[N-j-1]
            A[N-j-1] = dummy
            flag = 1
            count += 1
for i in range(N-1):
    print(A[i],end=" ")
print(f"{A[N-1]}\n{count}")


Measured memory_bytes: 5620
//Author: Kudo_kun
//AtCoder_132
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize "-O3"
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
typedef int64_t ll;
typedef long double ld;

const int N = (1e5 + 5);
const long MOD = (1e9 + 9);
const long INF = (1e18 + 18);
int n, cnt = 0;
map<char, int> mp;
vector<int> g;


int main()
{
	FastIO;
	cin >> n;
	for(int i = 0, u; i < n; i++)
		cin >> u, g.push_back(u);
	for(int i = 1; i < (n-1); i++)
	{
		int p[3];
		p[0] = g[i-1];
		p[1] = g[i];
		p[2] = g[i+1];
		sort(p, p+3);
		if(p[1] == g[i])
			cnt++;
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int n,i,yak[101]={0},j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		int icp=i;
		for(j=1;j<=icp;j++){
			if(icp%j==0&&j!=1){
				yak[j]++;
				icp=icp/j;
				j=1;
			}
		}
	}
	//for(i=1;i<=100;i++)printf("%d,",yak[i]);
	int thr=0,fv=0,thfv=0,tf=0,ft=0,sf=0;
	for(i=0;i<=100;i++){
		//if(yak[i]>=2)thr++;
		if(yak[i]<=23&&yak[i]>=4)fv++;
		if(yak[i]>=2&&yak[i]<=3)thfv++;
		if(yak[i]>=24)tf++;
		if(yak[i]>=14)ft++;
		if(yak[i]>=74)sf++;
		
	}
	int ans=0;
	if(thfv>0)ans+=thfv*(tf+fv-1)*(tf+fv)/2;
	if(tf+fv>=3)ans+=(tf+fv)*(tf+fv-1)*(tf+fv-2)/2;
	if(tf>0)ans+=tf*(fv+thfv+tf-1);
	if(ft>0)ans+=ft*(tf+fv-1);
	ans+=sf;
	printf("%d\n",ans>0?ans:0);
	return 0;
}


Measured memory_bytes: 128
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Set;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * 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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            Set<Integer> first = new HashSet<>(Arrays.asList(1, 3, 5, 7, 8, 10, 12));
            Set<Integer> second = new HashSet<>(Arrays.asList(4, 6, 9, 11));
            Set<Integer> third = new HashSet<>(Arrays.asList(2));
            int x = in.nextInt(), y = in.nextInt();
            List<Set<Integer>> list = Arrays.asList(first, second, third);
            for (int i = 0; i < 3; ++i) {
                if (list.get(i).contains(x) && !list.get(i).contains(y)) {
                    out.println("No");
                    return;
                } else if (list.get(i).contains(y) && !list.get(i).contains(x)) {
                    out.println("No");
                    return;
                }
            }
            out.println("Yes");
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}



Measured memory_bytes: 20948
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const int TIME_MAX = 100100;

int main() {
    int N, C;
    scanf("%d%d", &N, &C);
    vector<vector<int>> time(TIME_MAX, vector<int> (C, 0));
    for (int i = 0; i < N; i++) {
        int s, t, c;
        scanf("%d%d%d", &s, &t, &c);
        time[s][c-1]++; time[t][c-1]--;
    }
    
    vector<pair<int, int>> tv;
    for (int c = 0; c < C; c++) {
        int s;
        for (int i = 0; i < TIME_MAX; i++) if (time[i][c] != 0) {
            if (time[i][c] == 1) s = i;
            if (time[i][c] == -1) { tv.emplace_back(s, i); }
        }
    }
    
    sort(tv.begin(), tv.end());
    
    int ans = 0, M = tv.size();
    vector<bool> use(M, false);
    for (int tmp = 0; tmp < C; tmp++) {
        int now = 0;
        bool fin = true;
        for (int i = 0; i < M; i++) if (!use[i]) {
            if (fin) fin = false;
            int s, t; tie(s, t) = tv[i];
            if (s <= now) continue;
            use[i] = true;
            now = t;
        }
        if (fin) break;
        ans++;
    }
    
    cout << ans << endl;
    return 0;
}


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

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

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
using namespace std;
int n,t;
int mx;
int ans;
int mxx;
int a[100010];
int main()
{
	scanf("%d%d",&n,&t);
	t/=2;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
	}
	for(int i=n;i>=1;i--)
	{
		mxx=max(mxx,a[i]);
		if(mxx-a[i]>mx)
		{
			mx=mxx-a[i];
			ans=1;
		}
		else if(mxx-a[i]==mx)ans++;
	}
	printf("%d",ans);
	return 0;
}

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

int obs[10005];
int dp[10005][16];
int mask[5]={0, 3, 6, 12, 15};
int cnt[5] ={0, 1, 1, 1,  2};
int main() {
  int h, n;
  cin >> h >> n;
  fill(obs, obs+10005, 0);
  for(int i=0; i<n; i++){
    int x, y;
    cin >> x >> y;
    obs[y]=obs[y] | (1<<x);
  }
  obs[h]=15;
  fill(dp[h], dp[h]+16, 0);
  for(int i=h-1; i>=0; i--){
    for(int j=0; j<16; j++){
      dp[i][j]=0;
      for(int k=0; k<5; k++){
        if((mask[k]&j)|(mask[k]&obs[i+1])) continue;
        dp[i][j]=max(dp[i][j], 
             cnt[k]+dp[i+1][obs[i+1]|mask[k]]);
      }
    }
  }
  cout << dp[0][obs[0]] << endl;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18L + 5;
int main() {
	int n,w;
	cin>>n>>w;
    vector<int>wt(n), val(n);
    int sum_val=0;
    for(int i=0;i<n;i++){
        cin>>wt[i]>>val[i];
        sum_val+=val[i];
    }
    vector<long long>dp(sum_val+1,INF);
    dp[0]=0;
    //dp[i] have min weight for value i
    for(int i=0;i<n;i++){
        for(int j=sum_val;j>=val[i];j--){
            dp[j] = min(dp[j-val[i]]+wt[i],dp[j]);
        }
    }
    long long ans=0;
    for(int i=0;i<=sum_val;i++){
        if(dp[i]<=w){
            ans = max(ans,(long long) i);
        }
    }
    cout<<ans;
	return 0;
}

Measured memory_bytes: 4040
#include <stdio.h>
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
  int n, i, j, ans = 0;
  scanf("%d", &n);
  int a[n][n];
  char f[n];
  rep(i, n) rep(j, n) scanf("%d", &a[i][j]);
  rep(i, n) f[i] = 0;
  f[0] = 1;
  rep(i, n - 1) {
    int min = 10000, minx, miny;
    rep(j, n) {
      rep(k, n) {
        if(f[j] && !f[k] && a[j][k] >= 0 && a[j][k] < min) min = a[j][k], minx = j, miny = k;
      }
    }
    ans += min;
    f[miny] = 1;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2760
#![allow(unused_imports)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

fn main() {
    let n = read!(usize);
    let sp: Vec<(String, usize)> = read![String, usize; n];

    let mut sp: Vec<(usize, String, usize)> = sp
        .into_iter()
        .enumerate()
        .map(|(i, x)| (i, x.0, x.1))
        .collect();

    sp.sort_by(|x, y| {
        if x.1 != y.1 {
            x.1.cmp(&y.1)
        } else {
            y.2.cmp(&x.2)
        }
    });

    for a in &sp {
        println!("{}", a.0 + 1);
    }
}


Measured memory_bytes: 4352
import Data.Array.IO
import Control.Monad

main = do
  [n,k] <- map read . words <$> getLine :: IO [Int]
  as <- (newListArray (0,n-1) =<< (map read . words <$> getLine :: IO [Int])):: IO (IOArray Int Int)
  let ixs = [0..n-1]
  flip mapM_ (zip ixs $ drop (k) ixs) $ \(i,j) -> do
      x <- readArray as i
      y <- readArray as j
      putStrLn $ if y > x then "Yes" else "No"


Measured memory_bytes: 202388
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;


int N;

bool check(const vector<pair<ld, ld>>&cs, const ld amid) {
	map<ld, int>mp;
	for (auto c : cs) {
		ld r = c.second;
		ld x = c.first;
		if (r < amid)continue;
		else if (r > amid) {
			ld dis = sqrt(r*r - amid*amid);
			mp[x - dis]++;
			mp[x + dis]--;
		}
	}
	ld pre = -1;
	int num = 0;
	ld len = 0;
	bool preok = false;
	for (auto m : mp) {
		num += m.second;
		if (num) {
			if (!preok) {
				pre = m.first;
			}
			len = max(len, m.first - pre);
			preok = true;
			
			
		}
		else {
			if (num < 0)assert(false);
			if (preok) {
				len = max(len, m.first - pre);
				pre = -1;
			}
			preok = false;
		}
	}
	return amid*2 < len;
}
int main() { 
	while (1) {
		cin >> N;
		if (!N)break;
		vector<pair<ld, ld>>cs;
		for (int i = 0; i < N; ++i) {
			int x, r; cin >> x >> r;
			cs.push_back(make_pair(x, r));
		}
		cs.insert(cs.begin(), make_pair(cs.begin()->first - cs.begin()->second, 1e-18));
		cs.push_back(make_pair(cs.back().first + cs.back().second, 1e-18));
		ld amin = 0;
		ld amax = 3e6;
		int atime = 50;
		while (atime--) {
			ld amid = (amin + amax) / 2;
			if (check(cs, amid)) {
				amin = amid;

			}
			else {
				amax = amid;
			}
		}
		cout << setprecision(22) << fixed << amin*2 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 12436
x, y = map(int, input().split(" "))

amount = 0
if x == 1 and y == 1:
    amount += 400000
if x == 2:
    amount += 200000
elif x == 3:
    amount += 100000
elif x == 1:
    amount += 300000
if y == 2:
    amount += 200000
elif y == 3:
    amount += 100000
elif y == 1:
    amount += 300000

print(amount)

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

template <class T>
inline bool chmax(T& a, T b)
{
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T& a, T b)
{
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

// input
int N;
long long h[100010];

// DP table
long long dp[100010];

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> h[i];

    // 初期化(最小化問題なのでinfに初期化)
    for (int i = 0; i < N; ++i)
        dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // loop
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1)
            chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // answer
    cout << dp[N - 1] << endl;
}


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

int main(){
int E,Y;
cin>>E>>Y;
if(E == 0)
{
if(1868 <= Y && Y <= 1911) cout<<"M"<<Y - 1867<<endl;
else if(1912 <= Y && Y <= 1925) cout<<"T"<<Y - 1911<<endl;
else if(1926 <= Y && Y <= 1988) cout<<"S"<<Y - 1925<<endl;
else if(1989 <= Y && Y <= 2016) cout<<"H"<<Y - 1988<<endl;
}
else if(E == 1) cout<<1867 + Y<<endl;
else if(E == 2) cout<<1911 + Y<<endl;
else if(E == 3) cout<<1925 + Y<<endl;
else if(E == 4) cout<<1988 + Y<<endl;
}


Measured memory_bytes: 3096
S = input()
T = input()

s_list = list(S)
ns = len(s_list)

t_list = list(T)
nt = len(t_list)

max_match = 0
for i in range(ns-nt+1):
    match = 0
    for j in range(nt):
        if t_list[j] == s_list[j+i]:
            match += 1
    if match > max_match:
        max_match = match

ans = nt - max_match

print(ans)

Measured memory_bytes: 9072
n, loads = map(int,input().split(" "))
packages = []
for i in range(n):
    packages.append(int(input()))

def ifOK(p):
    j = 0
    sum = 0
    count = 0
    while j < n:
        if sum + packages[j] > p:
            count += 1
            sum = packages[j]
        else:
            sum += packages[j]
        j += 1
    if count <= loads-1:
        return True

left = max(packages)
right = sum(packages)

while True:
    mid = (left + right)//2
    if mid == max(packages):
        print(mid)
        break
    elif mid == sum(packages)-1:
        print(sum(packages))
        break
    if ifOK(mid):
        if not ifOK(mid-1):
            print(mid)
            break
        right = mid
    else:
        left = mid



Measured memory_bytes: 9552
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Salary for a Plumber
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int n = parseInt(line);
			if (n == 0) break;

			long max = 0;
			long len = 0;
			int[] joint = new int[n - 1];

			StringTokenizer st;

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				len += parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n - 1; i++) {
				joint[i] = parseInt(st.nextToken());
				len += joint[i];
			}
			Arrays.sort(joint);

			max = len;
			for (int i = 0; i < n - 1; i++) {
				len -= joint[i];
				max = Math.max(max, len * (i + 2));
			}
			System.out.println(max);
		}
	}
}

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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n,a,b; cin>>n>>a>>b;
	cout << ((a+b)%2 ? "Borys" : "Alice") << endl;
	return 0;
}


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

vector<char> num;
int a, b, d, k;
int DP[200][12][2];

int call(int pos, int cnt, int f){
    if(cnt > k) return 0;
    if(pos == num.size()){
        if(cnt == k) return 1;
        return 0;
    }

    if(DP[pos][cnt][f] != -1) return DP[pos][cnt][f];
    int res = 0;

    int LMT;

    if(f == 0){
       
        LMT = num[pos] - '0';
    } else {
        LMT = 9;
    }

    for(int dgt = 0; dgt<=LMT; dgt++){
        int nf = f;
        int ncnt = cnt;
        if(f == 0 && dgt < LMT) nf = 1; 
        if(dgt != d) ncnt++;
        if(ncnt <= k) res += call(pos+1, ncnt, nf);
    }

    return DP[pos][cnt][f] = res;
}

int solve(string b){
    num.clear();
    for(auto x : b){
      num.push_back(x);
    }
    memset(DP, -1, sizeof(DP));
    int res = call(0, 0, 0);
    return res;
}

int main () {
    string b; cin >> b;
    cin >> k;
    d = 0;
    int res = solve(b) ;
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

def main():
    n = int(input())
    la = list(map(int, input().split()))
    lai = [(a, i) for i, a in enumerate(la)]
    lai = sorted(lai)
    li1 = [str(i + 1) for a, i in lai]
    print(" ".join(li1))

if __name__ == "__main__":
    main()


Measured memory_bytes: 25320
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int[] nums = new int[n];
      	for (int i = 0; i < n; i++) {
        	nums[i] = sc.nextInt();
        }
    	
      	int res = 0;
      	
    	for (int i = 1; i < nums.length - 1; i++) {
        	if (((nums[i-1] < nums[i]) && (nums[i] < nums[i+1])) || ((nums[i-1] > nums[i]) && (nums[i] > nums[i+1])))
        		res++;
        }
      	
      	System.out.println(res);
    }
}

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

ll h[100100];
vector<pll> g[100100];
bool vis[100100];

ll solve(void){
  ll n,m,x,a,b,l;
  scanf("%lld%lld%lld",&n,&m,&x);
  for(int i=0;i<n;i++)scanf("%lld",&h[i]);

  for(int i=0;i<m;i++){
    scanf("%lld%lld%lld",&a,&b,&l);
    a--; b--;
    g[a].push_back(pll(l,b));
    g[b].push_back(pll(l,a));
  }

  priority_queue<tri> q;
  q.push(tri(pll(x,0),0));

  while(q.size()){
    tri p = q.top(); q.pop();
    ll hight = p.first.first, cost = -p.first.second, tree = p.second;

    if(vis[tree])continue;
    vis[tree] = 1;

    if(tree == n-1)return cost + h[n-1]-hight;

    for(pll e : g[tree]){
      ll nxt = e.second, t = e.first, nxtc = cost, nxth = hight;
      if(h[tree]<t)continue;

      if(hight<t){
	nxtc += 2*t-hight;
	nxth = 0;
      }else if(h[nxt]<hight-t){
	nxtc += hight-h[nxt];
	nxth = h[nxt];
      }else{
	nxtc += t;
	nxth -= t;
      }
      q.push(tri(pll(nxth,-nxtc),nxt));
    }
  }
  return -1;
}

int main(){
  printf("%lld\n",solve());
}

Measured memory_bytes: 34056
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000005
#define MOD 1000000007
#define N 100005
#define M 27000
#define LOG 1000000
#define KOK 650
#define EPS 0.000000001
using namespace std;

int n,v,w,wi;
int dp[2][100005];

int main() {

	//freopen("input.txt","r",stdin);	

	scanf("%d %d",&n,&w);

	for(int i=0;i<=n*1000;i++) dp[1][i]=dp[0][i]=inf;

	dp[0][0]=0;

	for(int i=1;i<=n;i++) {

		scanf("%d %d",&wi,&v);

		for(int j=0;j<=(i-1)*1000;j++) {

			umin(dp[1][j+v],dp[0][j]+wi);
			umin(dp[1][j],dp[0][j]);

		}

		for(int j=0;j<=i*1000;j++) {

			dp[0][j]=dp[1][j];
			dp[1][j]=inf;

		}

	}

	for(int i=n*1000;i>=0;i--) {

		if(dp[0][i]<=w) {

			printf("%d",i);

			return 0;

		}

	}

}


Measured memory_bytes: 1024
#![allow(unused_imports)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(dead_code)]
#![allow(unused_variables)]

use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::cmp::{max, min};
use std::mem::swap;
use std::io::prelude::*; // input()

fn input<T>() -> T
    where T: std::str::FromStr {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}
static INF: usize = 1_000_000;

fn main() {
    let n = input::<usize>();
    let m = input::<usize>();
    let abc = (0..m)
        .map(|_| (input::<usize>()-1,input::<usize>()-1,input::<usize>()))
        .collect::<Vec<_>>();

    let mut d = vec![vec![INF; 100]; 100];
    for i in 0..n {
        d[i][i] = 0;
    }
    for &(a, b, c) in &abc {
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    let mut ans = m;

    for &(a, b, c) in &abc {
        let shortest = || {
            for j in 0..n {
                if d[j][a] + c == d[j][b]  {
                   return true;
                }
            }
            false
        };
        if shortest() {
            ans-=1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    B = sorted(A)
    m1 = B.pop()
    m2 = B.pop()
    for i in range(N):
        if A[i] == m1:
            print(m2)
        else:
            print(m1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 70232
#include<bits/stdc++.h>
#define LIM 1+2+4+8+16+32+64+128
#define int long long 
using namespace std;
typedef struct{
  int per;
  int ko;
  int kyoda;
  int konoko;
}TRE;
int ace(int a,int b){
  int ss=0;
  for(int i=b;i<=a;i++){
    ss+=i;
  }
  return(ss);
}
typedef pair<int,int>P;
signed  main(){
  int t,n;
  int rat[5]={0,6000,4000,3000,2000};
  for(int i=0;i<4;i++){
    cin>>t>>n;
    cout<<rat[t]*n<<endl;
  }
  
  return(0);
}



Measured memory_bytes: 3104
#include <bits/stdc++.h> 
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;
using P = std::pair<int, int>;

int main(int argc, char *argv[])
{
    int A, B, K;
    std::cin >> A >> B >> K;

    std::vector<int> ans;

    for (int i = 1; i <= 100; i++) {
        if (A % i == 0 && B % i == 0) {
            ans.push_back(i);
        }
    }

    std::cout << ans[ans.size() - K] << std::endl;
    return 0;
}


Measured memory_bytes: 256
// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll mod = 1000000007;
const ll INF = 1e18;
const ll MAX = 100001;
//
//
void solve(){
    ll n;
    cin>>n;
    ll present = 100, ans = 0;
    while(present < n){
        present += present/100;
        ++ans;
    }
    cout<<ans;
}
int main(){ 
        hs;
        ll t;
        t=1;
        // cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}

Measured memory_bytes: 3556
import numpy as np

N = int(input())
order = np.zeros(N,dtype=np.int)
SP = []
for i in range(N):
  tmp = list(input().split())
  SP.append(tmp)

for i in range(N):
  idx = 0
  for j in range(N):
    if i != j and SP[i][0] > SP[j][0]:
      idx += 1
    elif i != j and SP[i][0] == SP[j][0] and int(SP[i][1]) < int(SP[j][1]):
      idx += 1
  order[idx] = i+1
for i in range(N):
  print(order[i])
  

Measured memory_bytes: 27048
#include<bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;

struct P3{
  double x,y,z,r;
  P3(double x=0, double y=0, double z=0):x(x),y(y),z(z){}
  P3 operator + (const P3 a) const{ return P3(x+a.x, y+a.y, z+a.z); }
  P3 operator - (const P3 a) const{ return P3(x-a.x, y-a.y, z-a.z); }
  P3 operator * (const double c) const{ return P3(x*c, y*c, z*c); }
  P3 operator / (const double c) const{ return P3(x/c, y/c, z/c); }
};

double dot(P3 a, P3 b){ return a.x*b.x + a.y*b.y + a.z*b.z; }

double abs(P3 p){
  return sqrt( dot(p,p) );
}

int N;
P3 s, t;
P3 c[105];

void solve(){
  
  P3 lastpoint;
  
  while(1){
    
    double mind = (1e9);
    int idx=-1;
    P3 point;
    
    for(int i=0;i<N;i++){
      
      double COS = dot(c[i]-s, t-s) / (abs(c[i]-s) * abs(t-s));
      
      if(COS<0) continue;
      if(abs(c[i]-s) <= c[i].r + EPS) continue;
      
      double A = abs(c[i]-s);
      double B = A * COS;
      
      P3 b = t-s;
      
      b = b / abs(b) * B + s;
      
      if(abs(b-c[i]) > c[i].r) continue;
      if(dot(t-s,b-s) < 0) continue;
      
      double Z = c[i].r, Y = abs(c[i]-b);
      double X = sqrt(Z*Z-Y*Y);
      
      P3 p = s-b;
      
      p = p / abs(p) * X + b;
      
      if(mind > abs(p-s)){
	mind = abs(p-s);
	idx = i;
	point = p;
      }
      
    }
    
    if(idx == -1) break;
    
    double COS = dot(s-c[idx], point-c[idx]) / (abs(s-c[idx]) * abs(point-c[idx]));
    
    double A = abs(s-c[idx]);
    double B = A * COS;
    
    P3 b = point-c[idx];

    b = b / abs(b) * B + c[idx];
    
    t = (b - s) * 2 + s;
    
    s = point;
    
    lastpoint = point;
  }
  
  printf("%.4f %.4f %.4f\n", lastpoint.x, lastpoint.y, lastpoint.z);
}

int main(){

  while(1){
  
    cin>>N;
    
    if(!N) break;
    
    s.x=0, s.y=0, s.z=0;
    
    cin>>t.x>>t.y>>t.z;
  
    for(int i=0;i<N;i++) cin>>c[i].x>>c[i].y>>c[i].z>>c[i].r;
    
    solve();

  }
  
  return 0;
}

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

#define MAXN 100005
#define MAXH 405
#define INF 1000000000
#define MOD 1000000007
int indeg[MAXH],outdeg[MAXH];
bool vis[MAXH];
vector<int> G[MAXH];

void add_edge(int u,int v)
{
    outdeg[u]++;indeg[v]++;
    G[u].push_back(v);G[v].push_back(u);
}

bool dfs(int v)
{
    bool f=indeg[v]!=outdeg[v];
    vis[v]=true;
    for(auto to:G[v])
	{
		if(!vis[to]) 
			f|=dfs(to);
	}
    return f;
}

int main()
{
	int N,H;
	int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
    scanf("%d%d",&N,&H);
    for(int i=1;i<=N;i++) 
    {
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
        int l,r;
		l= ( c[i]==0 ? a[i] : -c[i] );
        r= ( d[i]==0 ? -b[i] : d[i] );
        add_edge(l+H,r+H);
    }

    bool flag=true;
    for(int i=0;flag && i<=H;i++) 
	{
		if(outdeg[i]>indeg[i]) 
			flag=false;
	}
    for(int i=H+1;flag && i<=2*H;i++)
	{
		if(indeg[i]>outdeg[i]) 
	 		flag=false;
	}

    memset(vis,false,sizeof(vis));
    for(int i=0;flag && i<=2*H;i++)
	{
		if((indeg[i]||outdeg[i])&&!vis[i]) 
			flag &=dfs(i);
	}

    if(flag) 
	{
		printf("YES\n"); 
	}
	else
	{ 
		printf("NO\n");
	}
    return 0;
}


Measured memory_bytes: 3328