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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 103<<1;

int n,nn,val[_];

int main()
{
	n=ty(),nn=n+n;
	for(int i=1;i<=nn;i++)val[i]=ty();
	sort(val+1,val+nn+1);

	lint ans=0;
	for(int i=1;i<=nn;i+=2)ans+=min(val[i],val[i+1]);
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 256
s = [int(x) for x in input()]
##print(s)
count = len(s)-1##+の入りうるポジション数
sum = 0
for bit in range(2**count):
    hugou = [""] * count
    ##print(bin(bit))
    for i in range(count):
        if (bit >> i) & 1:
            hugou[count-1-i] = "+"
            ##print(hugou)
    calc = ""
   
    for j in range(count):
        calc += str(s[j])
        ##print(s)
        calc += str(hugou[j])
        ##print(hugou)
        ##print(calc)
    calc += str(s[-1])
    ##print(calc)
    sum += eval(calc)
print(sum)

Measured memory_bytes: 3064
(defun collector (function lst); listの各要素を数えるコレクタ 10^7くらいまで
  (if lst
      (let* ((ans '())
             (mem (cons (car lst) 1)))
        (mapcar (lambda (k)
                  (if (funcall function k (car mem))
                      (incf (cdr mem))
                      (progn (push mem ans)
                             (setf mem (cons k 1))))) (cdr lst))
        (push mem ans)
        ans)
      '()))
(let* ((n (read))
       (lst (sort (loop :repeat n :collect (read-line)) #'string>))
       (ll (collector #'string= lst))
       (mx (reduce #'max (mapcar #'cdr ll)))
       (lk (remove-if-not (lambda (k) (= mx (cdr k))) ll)))
  (loop :for k :in lk :do(format t "~A~%" (car k))))


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

ll gcd(ll a, ll b) {
    if(a < b){
        return gcd(b, a);
    }
    ll r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

ll lcm(ll a, ll b){
    return a * (b / gcd(a, b));
}

void solve(long long N, long long M, std::vector<long long> a){
    vector<ll> b(N);
    REP(i, N){ b.at(i) = a.at(i) / 2; }
    ll l = 1;
    REP(i, N){ l = lcm(l, b.at(i)); }
    REP(i, N){
        if((l / b.at(i)) % 2 == 0){
            cout << 0 << endl;
            return;
        }
    }
    ll ans = ((M / l) + 1) / 2;
    cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, M, std::move(a));
    return 0;
}


Measured memory_bytes: 1792
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = a[i]
for l in range(1, n):
    for s in range(n - l):
        dp[s][s + l] = max(a[s] - dp[s + 1][s + l], a[s + l] - dp[s][s + l - 1])
print(dp[0][n - 1])

Measured memory_bytes: 112476
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = (int)1e9 + 7;
int add(int x, int y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}

const int N = 200200;
int a[N];
int dp1[N];
int dp2[N];
int n, m;

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d", &m);
	while(m--) {
		int x;
		scanf("%d", &x);
		if (n == 0 || a[n - 1] != x)
			a[n++] = x;
	}
	dp1[1] = 1;
	for (int i = 1; i < n; i++) {
		dp1[i + 1] = add(dp1[i + 1], dp2[a[i]]);
		dp1[i + 1] = add(dp1[i + 1], dp1[i]);
		dp2[a[i - 1]] = dp1[i];
	}
	printf("%d\n", dp1[n]);

	return 0;
}


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

void solve()
{
    long long t,n,m,i,j,k=0,kk=0,x,y,z=0,mn,mx,a[10];

    cin >> n;

    z = (n*(n+1))/2;

    x = n/3;

    y = n/5;

    k = n/(15);

    for(i=1;i<=x;i++)
    {
        z-=3*i;
    }

    for(i=1;i<=y;i++)
    {
        if(i%3!=0)
        z-=5*i;
    }

    cout << z << endl;

}

int main()
{
     long long t,n,m,i,j,k=0,kk=0,x,y,z=0,mn,mx;

     //cin >> t;

     //while(t--)
     solve();

}


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

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SORTVG(v) sort(v.begin(),v.end(),greater<>())
#define SORTV(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef pair<int,int> Pii;
typedef vector<int> Vi;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}
template<class T> void AorB(T& a, string A,string B) {if(a){cout << A << ENT;}else{cout << B << ENT;}}

int atcoder(){
    ll ans=1;
    string s;
    cin>>s>>s;
    map<char,ll> mp;
    REP(i,0,s.length()){
        mp[s[i]]++;
    }
    
    for(auto x : mp){
        ans = ((x.second+1)*ans)%MOD;
    }
    ans--;
    cout<<ans<<ENT;
    return 0;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
    unsigned int a,b,c, sum;
    cin >> a >> b >> c;
    sum = a+b+c;
    if(sum >= 22) {
        cout << "bust" << endl;
    }else{
        cout << "win" << endl;
    }
    return 0;
    
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,b,c,d;
    scanf("%d",&a);
    d = a%60;
    c = (a-d)/60;
    b = c;
    c %= 60;
    b -= c;
    b /= 60;
    printf("%d:%d:%d\n",b,c,d);
    return 0;
}


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

vector<int> s[22], p(22);
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int k, a;
		cin >> k;
		for (int j = 0; j < k; j++)
			cin >> a, s[i].push_back(a);
	}
	for (int i = 0; i < m; i++)
		cin >> p[i];
	int c = 0;
	for (int i = 0; i < 1 << n; i++) {
		for (int j = 0; j < m; j++) {
			int b = p[j];
			for (int a : s[j])
				b ^= i >> a - 1;
			if (b & 1) goto pn;
		}
		c++;
	pn:;
	}
	cout << c << endl;
	return 0;
}


Measured memory_bytes: 256
'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const N = parseInt(args[0][0], 10)
	const A = args[1].map(arg => parseInt(arg, 10))
	const t1 = new Array(N)

	for (let i = 0; i < N; i++) {
		const a = A[i]
		t1[a - 1] = i + 1
	}

	console.log(t1.join(' '))
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


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

#define all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

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

  string s; cin >> s;
  if (sz(s) & 1) {
    cout << "No\n";
  } else {
    for (int i = 0; i < sz(s); i += 2) {
      if (s[i] != 'h' || s[i + 1] != 'i') {
        cout << "No\n";
        return 0;
      }
    }
    cout << "Yes\n";
  }

  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define all(v) (v).begin(),v.end()
#define fi first
#define se second
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
map<char,int> mp;
int main(){
string s;
cin>>s;
for(int i=0;i<s.size();i++)mp[s[i]]++;
int mi=min({mp['a'],mp['b'],mp['c']});
//cout<<mi<<endl;
if(mp['a']-mi>=2||mp['b']-mi>=2||mp['c']-mi>=2)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}


Measured memory_bytes: 512
S1, S2, S3, S4 = input()
Front = 10 * int(S1) + int(S2)
Back  = 10 * int(S3) + int(S4)

if 1 <= Front <= 12 and 1 <= Back <= 12:
    print('AMBIGUOUS')
elif (Front > 12 or Front == 0) and 1 <= Back <= 12:
    print('YYMM')
elif 1 <= Front <= 12 and (Back > 12 or Back == 0):
    print('MMYY')
else:
    print('NA')


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    if(a < b) swap(a, b);
    while(b > 0){
        ll tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}

ll lcm(ll a, ll b){
    return (a/(gcd(a, b)))*b;
}

int main(){
    int T;
    cin >> T;
    for(int i = 0; i < T; i++){
        ll A, B, C, D;
        cin >> A >> B >> C >> D;
        if(A < B || D < B){
            cout << "No" << endl;
        }else if(C >= B-1){
            cout << "Yes" << endl;
        }
        else{
            ll m = gcd(B, D);
            if(B-1-C >= m){
                cout << "No" << endl;                
            }else if(((C+1)%m) <= (A%m) && (A%m) <= ((B-1)%m)){
                cout << "No" << endl;
            }else{
                cout << "Yes" << endl;
            }
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vvl = vector<vl>;

const ll MAX_VAL = 1e9;
int H, W, h, w;
vvl ans;

void update(int y, int x, int val) {
    for (int i = y; i < H; i += h) {
        for (int j = x; j < W; j += w) {
            ans[i][j] = val;
        }
    }
}

void output() {
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cout << ans[i][j] << " \n"[j==W-1];
        }
    }
}

int main() {
    cin >> H >> W >> h >> w;
    ll p, m;
    p = m = (H/h) * (W/w);
    p += (H % h != 0) + (W % w != 0);
    p += (H % h != 0 and W % w != 0);

    bool ng = false;
    ng |= (h == 1 and w == 1);
    ng |= (h == 1 and W % w == 0);
    ng |= (H % h == 0 and w == 1);
    ng |= (H % h == 0 and W % w == 0);
    ng |= (p * (MAX_VAL-1) - m * MAX_VAL <= 0);
    if (ng) {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    ans.assign(H, vl(W, 0));
    update(0, 0, MAX_VAL-1);
    update(h-1, w-1, -MAX_VAL);
    output();
    return 0;
}


Measured memory_bytes: 4864
import java.util.*;

class Main{
	public static void main(String[] $){
		System.err.println();
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		int v=0;
		long r=0;
		for(int i=0;i<n;++i){
			int d=s.nextInt();
			long c=s.nextLong();
			while(true){
				//System.err.println(r+" "+v+" "+d+" "+c);
				if(d==0){
					r+=c;
					break;
				}
				if(c%2==1){
					--c;
					++r;
					if((v+=d)>9){
						v=f(v);
						++r;
					}
					if(c==0)
						break;
				}
				c/=2;
				r+=d<=4?c:c*2;
				d=f(d*2);
			}
		}
		System.out.println(r-1);
	}

	private static int f(int v){
		return v%10+v/10;
	}
}


Measured memory_bytes: 95240
def Euclid(x,y):
    if x<y:
        hoge = x
        x = y
        y = hoge
    a = x%y
    while a!=0:
        x = y
        y = a
        a = x % y
    print(y)

x,y = map(int,input().split())
Euclid(x,y)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
template<class T> inline istream& operator >> (istream & c, vector<T> & A) {rep(i, A.size()) c >> A[i];return c;}
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long k;
	cin >> k;
	ll m = k / 50;
	ll rem = k % 50;
	vector<ll> a(50);
	for (int i = 0; i < rem; ++i) {
		a[i] = 49 + m + 50 - (rem - 1);
	}
	for (int i = rem; i < 50; ++i) {
		a[i] = 49 + m - rem;
	}
	cout << 50 << endl;
	for (int i = 0; i < 50; ++i) {
		if (i) cout << ' ';
		cout << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int a[100004][2],b[100004];
void fun(int n,int m)
{
    int i,j,s,p,w;
    if(n>m)
        return;
    i=n;
    j=m;
    s=a[i][0];
    w=a[i][1];
    while(i!=j)
    {
        while((a[j][0]>s||(a[j][0]==s&&a[j][1]>=w))&&i<j)
            j--;
        while((a[i][0]<s||(a[i][0]==s&&a[i][1]<=w))&&i<j)
            i++;
        if(i<j)
        {
            p=a[i][0];
            a[i][0]=a[j][0];
            a[j][0]=p;
            p=a[i][1];
            a[i][1]=a[j][1];
            a[j][1]=p;
            p=b[i];
            b[i]=b[j];
            b[j]=p;
        }
    }
    a[n][0]=a[i][0];
    a[n][1]=a[i][1];
    a[i][0]=s;
    a[i][1]=w;
    p=b[n];
    b[n]=b[i];
    b[i]=p;
    fun(n,i-1);
    fun(i+1,m);
    return;
}
int main()
{
    int n,m,i,j,s,w,c[100004],d[100004][2];
    while(~scanf("%d %d",&n,&m))
    {
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&a[i][0],&a[i][1]);
            b[i]=i;
            d[i][0]=a[i][0];
            d[i][1]=a[i][1];
        }
        fun(1,m);
        for(i=1;i<=m;i++)
        {
            if(i==1||a[i][0]!=a[i-1][0])
                c[b[i]]=1;
            else
                c[b[i]]=c[b[i-1]]+1;
        }
        for(i=1;i<=m;i++)
            printf("%06d%06d\n",d[i][0],c[i]);
    }
    return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <set>
#include <utility>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A[3];
  cin >> A[0] >> A[1] >> A[2];
  sort(A, A+3);
  cout << A[2] - A[0] << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		while (true) {
		    
		    String[] expression = scanner.nextLine().split(" ");
		    
		    int a = Integer.parseInt(expression[0]);
		    String operation = expression[1];
		    int b = Integer.parseInt(expression[2]);
		    
		    if (operation.equals("?")) {
		        break;
		    }
		    
		    if (operation.equals("+")) {
		        System.out.println(a + b);
		    }
		    
		    if (operation.equals("-")) {
		        System.out.println(a - b);
		    }
		    
		    if (operation.equals("*")) {
		        System.out.println(a * b);
		    }
		    
		    if (operation.equals("/")) {
		        System.out.println(a / b);
		    }
		    
		}
		scanner.close();
	}
}


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

int N, K;
vector<int> g[101010];
ll mod = 1e9 + 7;
ll ret = 1;

void solve(int cur, int p, int num) {
    ret = ret * num % mod;

    num = K-1;
    if (p != -1) num--;
    for (auto e : g[cur]) {
        if (e == p) continue;
        solve(e, cur, num);
        num--;
    }
}

int main() {
    cin >> N >> K;
    rep(i, N-1) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    solve(0, -1, K);
    cout << ret << endl;
}


Measured memory_bytes: 9216
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String[] s = new String[]{
			"Rock", "Fire", "Scissors", "Snake", "Human",
			"Tree", "Wolf", "Sponge", "Paper", "Air",
			"Water", "Dragon", "Devil", "Lightning", "Gun"
		};
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			
			boolean[] f = new boolean[15];
			for(int i=0;i<n;i++){
				String t = sc.next();
				for(int j=0;j<15;j++){
					if(t.compareTo(s[j])==0){
						f[j] = true;
						break;
					}
				}
			}
			
			int win = -1;
			int cnt = 0;
			int p;
			for(int i=0;i<15;i++){
				if(f[i]){
					boolean flag = true;
					for(int j=1;j<=7;j++){
						p = i+j;
						if(p>14) p-=15;
						if(f[p]) flag = false;
					}
					if(flag==true) continue;
					for(int j=1;j<=7;j++){
						p = i-j;
						if(p<0) p+=15;
						if(f[p]) flag = true;
					}
					if(flag==false){
						win = i;
						cnt++;
					}
				}
			}
			if(cnt==1) System.out.println(s[win]); 
			else System.out.println("Draw");
		}
	}

}

Measured memory_bytes: 45680
#include<iostream>

using namespace std;

int main(){
    int N, Y;
    cin >> N;
    cin >> Y;
    bool find = false;
    int a,b,c;

    for (int i = 0; i <= N; i++){
        for (int j = 0; j <= N; j++){
            if(9000 * j + 4000 * i == Y - 1000 * N){
                find = true;
                a = j; b = i; c = N - (a + b);
            }
            if (find == true && c >= 0) break;
        }
        if (find == true && c >= 0) break;
    }

    if (find == true && c >= 0) cout << a << " "<< b << " " <<  c << endl;
    else cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
from fractions import gcd
a, b, c, d = list(map(int, input().split()))
e = c * d // gcd(c, d)
print(int(b - a + 1 - ((b // c + b // d - b // e) - ((a - 1) // c + (a - 1) // d - (a - 1) // e))))

Measured memory_bytes: 5048
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <numeric>
#include <complex>
#include <tuple>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define reps(i,n) for(int i=1;i<=int(n);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define iceil(x,y) (x+y-1)/y
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

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

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII> PP;

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

ll N;
ll T, A;
ll H;
float d;
ll ans=0;

int main()
{
	FAST;

	float mindef = LONG_MAX;

	cin >> N >> T >> A;
	rep(i,N) {
		cin >> H;
		d = T - H*0.006;
		if (mindef>=abs(d-A)) {
			ans=i+1;
			mindef = abs(d-A);
		}
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
using System;

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var sp = Console.ReadLine().Split(' ');
            var a = int.Parse(sp[0]);
            var b = int.Parse(sp[1]);
            var c = int.Parse(sp[2]);
            var k = int.Parse(sp[3]);

            int total = 0;
            if (a+b<k)
            {
                total = a - (k - a - b);
            } else
            {
                total = a >= k ? k : a;
            }
            Console.WriteLine(total);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27548
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def factorization(n):
   arr = []
   temp = n
   for i in range(2, int(-(-n**0.5//1))+1):
       if temp%i==0:
           cnt=0
           while temp%i==0:
               cnt+=1
               temp //= i
           arr.append([i, cnt])
   if temp!=1:
       arr.append([temp, 1])
   if arr==[]:
       arr.append([n, 1])
   return arr

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
    n, m = MAP()
    if m != 1:
        lis = factorization(m)
        p = 0
        for x in lis:
            p += x[1]
        #print(lis)
        #print(p)

        ans = 1
        for p, b in lis:
            ans *= cmb(b + n - 1, b)

        print(ans%mod)

    else:
        print(1)

if  __name__=='__main__':
    main()


Measured memory_bytes: 5584
import numpy as np

N, M, X = list(map(int, input().split()))

C = [0] * N
A = [[0]] * N

for i in range(N):
    tmp = list(map(int, input().split()))
    C[i] = tmp[0]
    A[i] = tmp[1:]

candidates = []

def iter(i, cost, learned):
    if(all(elm >= X for elm in learned)):
            candidates.append(cost)

    i += 1

    if(i >= N): return 0

    iter(i, cost, learned)
    iter(i, (np.array(cost) + np.array(C[i]).tolist()), (np.array(learned) + np.array(A[i])).tolist())


iter(0, C[0], A[0])
iter(0, 0, [0]*M)

if(len(candidates) == 0): print(-1)
else: print(min(candidates))

Measured memory_bytes: 27416
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, x = map(int, input().split())
    A = list(map(int, input().split()))

    A_origin = A.copy()

    if A[0] > x:
        A[0] = x

    for i in range(0, N - 1):
        if A[i] + A[i + 1] > x:
            A[i + 1] -= A[i] + A[i + 1] - x

    res = 0
    for i in range(N):
        res += abs(A_origin[i] - A[i])

    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 15612
#include<stdio.h>
int main(void)
{
	int a,b,c,i,x[10];

	scanf("%d%d%d",&a,&b,&c);
	x[0]=a*c-b;
	for(i=1;i<=10;i++){
		x[i]=x[i-1]*a-b;
		
		printf("%d\n",x[i-1]);
		}
	return 0;
}



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

typedef vector<int>  vi;
typedef set<char> setchar;
typedef set<int> sett;
typedef deque <int> dq;
typedef long long ll;
#define vec(a)  a.begin(),a.end()
#define pb     push_back
#define pf     push_front
#define mem(a,b) memset(a,b,sizeof(a));
#define inI(a)  scanf("%d",&a);
#define inL(a)  scanf("%lld",&a);
#define uff ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
//int fx[]={+0,-1,-1,-1,+0,+1,+1,+1};
//int fy[]={-1,-1,+0,+1,+1,+1,+0,-1};
int fx[]= {0,-1,0,+1};
int fy[]= {-1,0,+1,0};



int main()
{
     uff
    //freopen("input.txt","r",stdin);
    int n,k;
    cin>>n>>k;
    if(k==1)
        cout<<"0"<<endl;
    else
    {
        cout<<(n-k)<<endl;
    }



    return 0;

}







Measured memory_bytes: 256
def _mergesort_ lst
    if (len = lst.size) <= 1 then
        return lst
    end

    # pop ??????????????????????????¨????????¨?????????????????¨?????????lst ???????????????
    lst2 = lst.pop(len >> 1)

    return _merge_(_mergesort_(lst), _mergesort_(lst2))
end

def _merge_ lst1, lst2
    len1, len2 = lst1.size, lst2.size
    result = Array.new(len1 + len2)
    a, b = lst1[0], lst2[0]
    i, j, k = 0, 0, 0
    loop {
        if a <= b then
            result[i] = a
            i += 1 ; j += 1
            break unless j < len1
            a = lst1[j]
        else
            result[i] = b
            i += 1 ; k += 1
            $cnt += len1 - j
            break unless k < len2
            b = lst2[k]
        end
    }
    while j < len1 do
        result[i] = lst1[j]
        i += 1 ; j += 1
    end
    while k < len2 do
        result[i] = lst2[k]
        i += 1 ; k += 1
    end
    return result
end
n = gets.to_i
arr = gets.split.map(&:to_i)
$cnt = 0
_mergesort_ arr
p $cnt

Measured memory_bytes: 33600
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl
#define NN cout << "No" << endl
#define pint pair<int,int>
#define vi(v) rep(i,v.size())cin >> v[i]
#define vc(v) rep(i,v.size())cout << v[i] << endl
#define ni(n) cin >> n
#define nc(n) cout << n << endl
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int solve(){
  int n,m;
  cin >> n >> m;
  vector<int>cnt(n);
  ll sum = 0;
  rep(i,n){
    int tmp;
    cin >> tmp;
    cnt[i] += tmp;
    sum += tmp;
  }
  int cn = 0;
  rep(i,n){
    if(cnt[i] >= ((double)sum * (1.0 / (4.0 * m))))cn++;
  }
  if(cn >= m)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt();
        int col = sc.nextInt();
        char[][] picture = new char[row][col];
        for(int r = 0; r < row; r++) {
            String line = sc.next();
            for(int c = 0; c < col; c++) {
                picture[r][c] = line.charAt(c);
            }
        }
        for(int r = 0; r < row; r++) {
            for(int c = 0; c < col; c++) {
                if(picture[r][c] == '.') continue;
                int count = 0;
                for(int i = -1; i <= 1; i++) {
                    for(int j = -1; j <= 1; j++) {
                        if(i == 0 && j == 0 || i == -1 && j == -1 || i == 1 && j == -1 || i == -1 && j == 1 || i == 1 && j == 1) continue;
                        int nextRow = r + i;
                        int nextCol = c + j;
                        if(nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col) {
                            if(picture[nextRow][nextCol] == '#') count++;
                        }
                    }
                }
                if(count == 0) {
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <queue>

using namespace std;

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;
typedef pair<int, int> pii;

int main(){
    int n;
    cin >> n;
    vector<int> os(1e5 + 10, 0);
    vector<int> es(1e5 + 10, 0);
    vector<int> vs(n, 0);
    rep(i, n){
        int v;
        cin >> v;
        if(i % 2 == 1){
            os[v] ++;
        }else{
            es[v] ++;
        }
        vs[i] = v;
    }
    vector<pii> ops(1, {-1, -1});

    vector<pii> eps(1, {-2, -2});
    rep(i, os.size()){
        if(os[i] != 0){
            ops.push_back({os[i], i});
        }
        if(es[i] != 0){
            eps.push_back({es[i], i});
        }
    }
    sort(ops.begin(), ops.end());
    sort(eps.begin(), eps.end());
    int oIndex = ops.size() - 1;
    int eIndex = eps.size() - 1;
    int oOpt = ops[oIndex].second;
    int eOpt = eps[eIndex].second;
    int oOpt1 = ops[oIndex - 1].second;
    int eOpt1 = eps[eIndex - 1].second;
    int ans = 0;

    rep(i, vs.size()){
        if(i % 2 == 1 && vs[i] != oOpt){
            ans ++;
        }
        if(i % 2 == 0 && vs[i] != eOpt){
            ans ++;
        }
    }
    if(eOpt == oOpt){
        ans = 0;
        rep(i, vs.size()){
            if(i % 2 == 1 && vs[i] != oOpt){
                ans ++;
            }
            if(i % 2 == 0 && vs[i] != eOpt1){
                ans ++;
            }
        }
        int tmp = 0;
        rep(i, vs.size()){
            if(i % 2 == 1 && vs[i] != oOpt1){
                tmp ++;
            }
            if(i % 2 == 0 && vs[i] != eOpt){
                tmp ++;
            }
        }
        ans  = min(ans, tmp);
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2428
#include<stdio.h>
int main() {
 long long int a,b=0,c=100,i=1;
 scanf("%lld",&a);
  
  if(a==100) {
    i = 0;
 } else {
   while(1)
{
     b = c / 100;
     c += b;
     if(c >= a)
       break;
     i++;
   }
 }
  printf("%lld\n",i);
  return 0;
}

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

int main(void) {
    long n, a, b;
    cin >> n >> a >> b;
    a--, b--;

    if(a>b) swap(a,b);
    assert(a < b);

    if((a&1) == (b&1)) {
        cout << (b-a)/2 << endl;
    } else {
        long r = 1e18;
        {
            long c = n-1-b + 1;
            long aa = a+c;
            r = min(r, c+ (n-1 - aa)/2);
        }
        {
            long c = a-0 + 1;
            long bb = b-c;
            r = min(r, c+ (bb - 0)/2);
        }
        cout << r << endl;
    }
}


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

#define ln '\n'
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if(b % a == 0) {
        cout << a + b << ln;
    } else {
        cout << b - a << ln;
    }
    return 0;
}


Measured memory_bytes: 256
while True:
    value = input().split(" ")
    a = int(value[0])
    b = int(value[2])
    op = value[1]

    if op == "+":
        c = a + b
        print("{0}".format(c))
    elif op == "-":
        c = a - b
        print("{0}".format(c))
    elif op == "*":
        c = a * b
        print("{0}".format(c))
    elif op == "/":
        c = int(a / b)
        print("{0}".format(c))
    elif op == "?":
        break


Measured memory_bytes: 5596
#include<stdio.h>

int main(){
  int n,i,k,m,f;
  long long int l;

  scanf("%d",&n);
  
  int a[n];
  
  l=1;
  
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    }
  
  
  
  
  f=0;
  for(i=0;i<n;i++)
    f=f+a[i]-1;
  
  printf("%d",f);
}

Measured memory_bytes: 128
import Data.List
import Data.Bool

main = print . (`mod` (10^9 + 7)) . solve . map read . drop 1 . words =<< getContents

solve :: [Integer] -> Integer
solve as
    | oddl as && length a' == 1 && a == 0 = bool 0 r . ssolve 2 $ tail as'
    | otherwise = bool 0 r $ ssolve 1 as'
    where
        oddl = odd . length
        a = head a'
        a' = head as'
        as' = group $ sort as
        r = (2^) . bool n (n-1) $ oddl as
        n = length as'

ssolve n as = all (\(a,x) -> length a == 2 && head a == x) $ zip as [n,n+2..]


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

#define out(v) cout<<v<<"\n"
const int MOD = 1e9+7;

const int MAX = 1e6+1;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long comb(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  COMinit();
  int X, Y; cin >> X >> Y;
  int l = (2*X - Y) / 3;
  int k = (2*Y - X) / 3;
  if (k + 2 * l != X || 2 * k + l != Y)
    out(0);
  else
    out(comb(l + k, k));

  return 0;
}


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

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    int a[10][10];
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j <= 9; ++j) {
            a[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int cur = 1;
        while (i / cur > 0) {
            cur *= 10;
        }
        cur /= 10;
        a[i / cur][i % 10]++;
    }
    ll ans = 0;
    for (int i = 1; i <= 9; ++i) {
        for (int j = i; j <= 9; ++j) {
            ans += (i == j ? 1ll : 2ll) * a[i][j] * a[j][i];
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;

int lsone(int n)
{
	return (n&-n);
}

ll pow1(ll a, ll b)
{
	if (b == 0)
		return 1ll;
	else if (b == 1)
		return a;
	else
	{
		ll x = pow1(a, b/2);
		x *= x;
		x %= mod;
		if (b%2)
		{
			x *= a;
			x %= mod;
		}
		return x;
	}
}

int n, val;
double dp[310][310][310];

double solve(int x, int y, int z) {
	if (x == 0 and y == 0 and z == 0)
		return 0;
	if (dp[x][y][z] > 0)
		return dp[x][y][z];

	int zero = n - (x+y+z);

	double p_zero = double(zero)/double(n);
	double p_one = double(x)/double(n);
	double p_two = double(y)/double(n);
	double p_three = double(z)/double(n);

	double zero_inf = 1.00F / (1.00F - p_zero);

	if (x > 0)
		dp[x][y][z] += (p_one * zero_inf * zero_inf) + (p_one * zero_inf * solve(x-1, y, z));
	if (y > 0)
		dp[x][y][z] += (p_two * zero_inf * zero_inf) + (p_two * zero_inf * solve(x+1, y-1, z));
	if (z > 0)
		dp[x][y][z] += (p_three * zero_inf * zero_inf) + (p_three * zero_inf * solve(x, y+1, z-1));

	return dp[x][y][z];
}

int main()
{	
	cin>>n;
	int a[4] = {0};

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

	double ans = solve(a[1], a[2], a[3]);

	printf("%.15F\n", ans);

	return 0;
}


Measured memory_bytes: 225536
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define  LL long long
const double pi = acos(-1);
const double g = -9.8;
const int maxn = 1e5+555;
 
int main()
{
	char s[maxn];
	scanf("%s",s);
	int ll=strlen(s);
	int ans=ll/2;
	int l,r;
	while(1){
		l=ll-ans;
		r=ans+1;
		int flag=1;
		int now=s[l-1];
		for(int i=l;i<r;i++){
			if(s[i]!=now){
				flag=0;
				break;
			}
		}
		if(!flag){
			break;
		}
		ans++;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))
#define Rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define pb push_back

const int inf = 999999999;
const int mod = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main(){
	int n; cin >> n;
	int a[n], ans = 1;
	Rep(i, n){
		cin >> a[i];
	}
	sort(a, a + n);
	Rep(i, n - 1){
		if(a[i] != a[i + 1]) ans += 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

    for i in range(n):
        N[i+1] += N[i]
        if S[i:i+2] == 'AC':
            N[i+1] += 1
    for i in range(q):
        l,r = map(int,input().split())
        print(N[r-1]-N[l-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 50776
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << (a + b) * c / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = readline.split(' ').map(&:to_i)
Edges = Hash.new {|h,k| h[k]=Hash.new }

M.times do |idx|
  n1, n2, dist = readline.split(' ').map(&:to_i)
  Edges[n1-1][n2-1] = [dist, idx]
  Edges[n2-1][n1-1] = [dist, idx]
end

# flooding
minimum_distance_matrix = Array.new(N) {Array.new(N)}
N.times do |i|
  minimum_distance_matrix[i][i]=0
end
N.times do
  changed = false
  Edges.each_pair do |src, h|
    h.each_pair do |dst, edge|
      N.times do |i|
	next unless minimum_distance_matrix[i][src]

	#e = Edges[src][dst]
	current = minimum_distance_matrix[i][dst]
	next_cand = minimum_distance_matrix[i][src]+edge[0]
	if !current or current>next_cand then
	  minimum_distance_matrix[i][dst] = next_cand
	  changed = true
	end
      end
    end
  end
  break unless changed
end

# count the edges which is not shortest for adjacent node pairs
count=0
Edges.keys.sort.each do |src|
  Edges[src].keys.sort.each do |dst|
    if src<=dst then
      break
    end

    e = Edges[src][dst]
    if minimum_distance_matrix[src][dst] < e[0]
      count += 1
    end
  end
end

puts count



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

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

int main(){
  IO; int H, W; cin >> H >> W;
  vector<string> s(H);
  REP(i, H) cin >> s[i];
  mi DP(H, vi(W, 10000));
  DP[0][0] = (s[0][0] == '#');
  REP(i, H){
    REP(j, W){
      if(i) DP[i][j] = DP[i-1][j] + (s[i-1][j] == '.' && s[i][j] == '#');
      if(j) MIN(DP[i][j], DP[i][j-1] + (s[i][j-1] == '.' && s[i][j] == '#'));
    }
  }
  cout << DP[H-1][W-1] << endl;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      
      long a = sc.nextInt();
      long b = sc.nextInt();
      long c = sc.nextInt();
      long d = sc.nextInt();
      
      long product = a*c;
      
      if(a*d > product){
      	product = a*d;
      }
      if(c*b > product){
      	product = c*b;
      }
      if(b*d > product){
      	product = b*d;
      }
      
      System.out.println(product);
    }
}

Measured memory_bytes: 27064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n, 0);
    rep1(i, n) cin >> a[i];
    sort(a.begin(), a.end(), greater<ll>());
    ll ans = 0; 
    for (ll i=0; i<(n-2); i++){
        for (ll j=i+1; j<(n-1); j++){
            for (ll k=j+1; k<(n); k++){
                if (a[i]+a[j]>a[k] && a[k]+a[i]>a[j] && a[j]+a[k]>a[i]) ans++;
                else break;
            }
        }
    }
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 3620
#include <stdio.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 100
#define INF 5000000

int prim();
int n;
int c[MAX];
int M[MAX][MAX];
int d[MAX];
int p[MAX];

int main(){
  int i,j;
  int length;
  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&length);
      if(length==-1) M[i][j]=INF;
      else M[i][j]=length;
    }
  }

  printf("%d\n",prim());
  return 0;
}

int prim(){
  int u;
  int i;
  int min;
  int sum=0;
  for(i=0;i<n;i++){
    c[i]=WHITE;
    d[i]=INF;
    p[i]=-1;
  }

  d[0]=0;

  while(1){
    min=INF;
    for(i=0;i<n;i++){
      if(c[i]!=BLACK && d[i]<min){
	min=d[i];
	u=i;
      }
    }

    if(min==INF) break;

    c[u]=BLACK;

    for(i=0;i<n;i++){
      if(c[i]!=BLACK && M[u][i]!=INF){
	if(M[u][i]<d[i]){
	  d[i]=M[u][i];
	  p[i]=u;
	  c[i]=GRAY;
	}
      }
    }
  }

  for(i=0;i<n;i++){
    if(p[i]!=-1)sum+=M[i][p[i]];
  }

  return sum;
}



Measured memory_bytes: 2088
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    
    private static class Point {
        private final int i;
        private final int j;
        
        private Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int H = sc.nextInt();
        final int W = sc.nextInt();
        final int startI = sc.nextInt() - 1;
        final int startJ = sc.nextInt() - 1;
        final int endI = sc.nextInt() - 1;
        final int endJ = sc.nextInt() - 1;
        
        final int[][] field = new int[H][W];
        
        for (int i = 0; i < H; i++) {
            String s = sc.next();
            
            for (int j = 0; j < W; j++) {
                field[i][j] = s.charAt(j) == '.'
                        ? -1 // 未検証
                        : -2; //壁
            }
        }
        
        int currJump = 0;
        Queue<Point> testTarget = new ArrayDeque<>();
        testTarget.add(new Point(startI, startJ));
        
        while (true) {
            Set<Point> pointsOfCurrJump = new HashSet<>();
            
            // ジャンプ無しで到達できる位置をすべて調べ上げる
            while (!testTarget.isEmpty()) {
                Point p = testTarget.poll();
                pointsOfCurrJump.add(p);
                
                if (1 <= p.i && field[p.i - 1][p.j] == -1) {
                    field[p.i - 1][p.j] = currJump;
                    testTarget.add(new Point(p.i - 1, p.j));
                }
                if (1 <= p.j && field[p.i][p.j - 1] == -1) {
                    field[p.i][p.j - 1] = currJump;
                    testTarget.add(new Point(p.i, p.j - 1));
                }
                if (p.i <= H - 2 && field[p.i + 1][p.j] == -1) {
                    field[p.i + 1][p.j] = currJump;
                    testTarget.add(new Point(p.i + 1, p.j));
                }
                if (p.j <= W - 2 && field[p.i][p.j + 1] == -1) {
                    field[p.i][p.j + 1] = currJump;
                    testTarget.add(new Point(p.i, p.j + 1));
                }
            }
            
            // ジャンプ無しで到達できる場所を調べつくしたら、
            // そこからジャンプして到達できる位置をすべて調べ上げる
            int j = ++currJump;
            pointsOfCurrJump.forEach(p -> {
                for (int di = -2; di <= 2; di++) {
                    for (int dj = -2; dj <= 2; dj++) {
                        int ni = p.i + di;
                        int nj = p.j + dj;
                        
                        if (0 <= ni && ni < H && 0 <= nj && nj < W && field[ni][nj] == -1) {
                            field[ni][nj] = j;
                            testTarget.add(new Point(ni, nj));
                        }
                    }
                }
            });
            if (field[endI][endJ] != -1 || testTarget.isEmpty()) {
                break;
            }
        }
        System.out.println(field[endI][endJ]);
    }
}


Measured memory_bytes: 64396
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

const ll MOD = 1e9+7;

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

    ll N, M;
    cin >> N >> M;
    vector<ll> S(N), T(M);
    Rep (i, N) cin >> S[i];
    Rep (i, M) cin >> T[i];

    vector<vector<ll>> dp(N+1, vector<ll>(M+1, 0)), sdp(N+2, vector<ll>(M+2, 0));
    dp[0][0] = 1;
    Rep (i, N+1) {
        Rep (j, M+1) {
            if (i-1 >= 0 && j-1 >= 0 & S[i-1] == T[j-1]) dp[i][j] = sdp[i][j];
            sdp[i+1][j+1] = (((sdp[i+1][j] + sdp[i][j+1]) % MOD + dp[i][j]) % MOD - sdp[i][j]) % MOD;
            if (sdp[i+1][j+1] < 0) sdp[i+1][j+1] += MOD;
        }
    }

    // Rep (i, N+2) {
    //     Rep (j, M+2) {
    //         cout << sdp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    cout << sdp[N+1][M+1] << "\n";
}

Measured memory_bytes: 63104