akhauriyash/Code-Regression huggingface dataset:
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
dis = float('inf')
ans = -1
for i in range(n):
    tmpdis = abs(t - h[i] * 0.006 - a)
    if tmpdis < dis:
        ans = i + 1
        dis = tmpdis
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
int v = 100005,e;
int c = 0;
vector<vector<int>> graph(v,vector<int>());
vector<bool> seen(v,false);
vector<int> ord(v);
vector<int> low(v);
vector<P> bridges;

void dfs(int i,int par=-1){
    seen[i] = true;
    ord[i] = low[i] = c++;

    for(int j:graph[i]){
        if(!seen[j]){
            dfs(j,i);
            low[i] = min(low[i],low[j]);
            if(ord[i] < low[j]) bridges.push_back(P(min(i,j),max(i,j)));
        }else if(j!=par){
            low[i] = min(low[i],ord[j]);
        }
    }

    return;
}

int main(){
    cin >> v >> e;
    rep(i,e){
        int s,t;
        cin >> s >> t;
        graph[s].push_back(t);
        graph[t].push_back(s);
    }
    dfs(0);
    sort(bridges.begin(),bridges.end());
    for(P p:bridges){
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}


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

int main(){
    int a,b;
    cin>>a>>b;
    --a;
    --b;
    cout<<"100 100"<<endl;
    bool m[100][100]={0};
    for(int i=0;i<100;++i){
        for(int j=0;j<100;++j){
            if(i<50){
                if(a>0 && (i%2==0 && j%2==0)){
                    --a;
                    m[i][j]=true;
                }
                else m[i][j]=false;
            }
            else{
                if(b>0 && (i%2==1 && j%2==0)){
                    --b;
                    m[i][j]=false;
                }
                else m[i][j]=true;
            }
        }
    }
    for(int i=0;i<100;++i){
        for(int j=0;j<100;++j){
            if(m[i][j])printf(".");
            else printf("#");
        }
        printf("\n");
    }
}

Measured memory_bytes: 256
a = gets.to_i
h = gets.chomp.split(" ").map(&:to_i);
r = Array.new(a)
r[0] = 0
r[1] = (h[1]-h[0]).abs

i = 2
(a - 2).times do 
  jump1 = r[i-1] + (h[i-1] - h[i]).abs
  jump2 = r[i-2] + (h[i-2] - h[i]).abs

  if jump1 < jump2
    r[i] = jump1
  else
    r[i] = jump2
  end
  i += 1
end

puts r.last


Measured memory_bytes: 9220
#include<iostream>
using namespace std;
int main()
{
    int h,m,s,x;
    cin >> x;
 
    s = x  %60;
    h = x /3600; 
    m = (x / 60) - (h*60); 

    
    cout << h<<":"<<m<<":"<<s<<endl;
    
}


Measured memory_bytes: 3100
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
  
int main(){
 int n;cin>>n;
  int ans=0;
  for(int i=0;i<n;i++)
  {
    int a;cin>>a;
    while(1)
    {
      if(a%2==0)
      {
        ans++;
        a=a/2;
      }
      else
        break;
    }
  }
  cout<<ans<<endl;
}
    
  

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

using ull_t = unsigned long long;

int main()
{
    size_t N, M;
    cin >> N >> M;

    vector<size_t> A(M, 0);
    for (auto &a : A)
        cin >> a;

    size_t sum = 0;
    for (auto a : A) sum += a;

    cout << ((sum > N) ? -1 : (int)(N - sum)) << endl;
}


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

using ll = long long ;
ll knapsack(ll* wt, ll* val, ll n, ll W){

    ll mat[2][W+1];
    memset(mat, 0, sizeof(mat));
    int i = 0;
    while (i < n)
    {
        int j = 0;
        if (i%2!=0)
        {
            while (++j <= W)
            {
                if (wt[i] <= j)
                    mat[1][j] = max(val[i] + mat[0][j-wt[i]], mat[0][j] );
                else
                    mat[1][j] = mat[0][j];
            }
        }
        else
        {
            while(++j <= W)
            {
                if (wt[i] <= j)
                    mat[0][j] = max(val[i] + mat[1][j-wt[i]], mat[1][j]);
                else
                    mat[0][j] = mat[1][j];
            }
        }
        i++;
    }
    return max(mat[0][W],mat[1][W]);
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,tot;
    cin>>n>>tot;

    ll w[n],v[n];

    for(int i=0 ; i<n ; i++)
        cin>>w[i]>>v[i];

    cout<<knapsack(w,v,n,tot);

}




Measured memory_bytes: 1792
import java.util.Scanner;

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

    int A = scanner.nextInt();
    int B = scanner.nextInt();
    int tot = 0;
    for (int i = A; i <= B; i++) {
      if (palindromic(i)) tot++;
    }
    System.out.println(tot);
  }

  private static boolean palindromic(int n) {
    char[] s = Integer.toString(n).toCharArray();
    int i = 0;
    int j = s.length - 1;
    while (i < j) {
      if (s[i] != s[j]) return false;
      i++;
      j--;
    }
    return true;
  }
}


Measured memory_bytes: 30676
o = gets.chomp.chars
e = gets.chomp.chars
password = []
i = 0
while i < e.size
  password.push(o[i])
  password.push(e[i])
  i += 1
end
if e.size < o.size
  password.push(o[o.size - 1])
end
puts password.join


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

int main() {
	string s;
	cin >> s;
	vector<int> a(s.size() + 1, -1);
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '<') {
			if (a[i] == -1) {
				a[i] = 0;
				a[i + 1] = 1;
			}
			else
				a[i + 1] = a[i] + 1;
		}
	}
	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == '>') {
			if (a[i + 1] == -1) {
				a[i + 1] = 0;
				a[i] = 1;
			}
			else
				a[i] = a[i + 1] + 1;
		}
	}
	for (int i = 0; i < s.size() - 1; i++)
		if (s[i] == '<' && s[i + 1] == '>')
			a[i + 1] = max(a[i], a[i + 2]) + 1;
	long long sum = 0;
	for (int i = 0; i < a.size(); i++)
		sum += a[i];
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 2820
fn d() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).expect("input error");
    let n = input.trim_right().parse::<usize>().expect("parse error");

    let mut input = String::new();
    std::io::stdin().read_line(&mut input).expect("input error");
    let arr : Vec<u32> = input.split_whitespace()
        .map(|s| s.parse::<u32>().expect("parse error") - 1)
        .collect();

    let mut map = vec![0i64; n + 1];
    for i in &arr {
        map[*i as usize] += 1;   
    }

    let total = map.iter()
        .map(|&n| n * (n - 1) / 2)
        .sum::<i64>();

    for k in 0..n {
        let v = map[arr[k as usize] as usize] as i64;
        println!("{}", total - (v * (v - 1) / 2) + ((v - 1) * (v - 2) / 2));
    }
}

fn main() {
    d();
}

Measured memory_bytes: 12796
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
using namespace std;

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

    vector<int> a(10, 0), b(100, 0), c(1000, 0);
    for (int i = 0; i < n - 2; i++) {
        int x = stoi(s.substr(i, 3));
        a[x / 100] = 1; x %= 100;
        int y = x / 10;
        for (int j = 0; j < 10; j++) {
            if (a[j]) b[10 * j + y] = 1;
        }
        x %= 10;
        for (int j = 0; j < 100; j++) {
            if (b[j]) c[10 * j + x] = 1;
        }
    }

    cout << accumulate(c.begin(), c.end(), 0) << endl;

    return 0;
}


Measured memory_bytes: 256
import math
N = int(input())

ans = [0] * N
n = int(math.sqrt(N)) 

for x in range(1, n+1):
    for y in range(1, x+1):
        for z in range(1, y+1):
            i = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if i <= N:
                if x == y == z:
                    ans[i-1] += 1
                elif x == y or y == z:
                    ans[i-1] += 3
                else:
                    ans[i-1] += 6

for j in range(N):
    print(ans[j])

Measured memory_bytes: 9112
/**
  * author : thegeniushead
**/
#include <bits/stdc++.h>
 
/*.....DEFINITIONS...... */
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define T() int tt; cin>>tt; while(tt--)
#define rep(i,start,lim) for(int i=start;i<lim;i++)
#define rep1(i,start,lim) for(int i=start; i<=lim; ++i)
#define repd(i,start,lim) for(int i=start;i>=lim;i--)
#define mp make_pair
#define pb push_back
#define lchild (2*node+1)
#define rchild (2*node+2)
#define ff first
#define ss second
#define br cout<<"\n"
#define MOD (1000000007LL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eps (1e-6)
#define sll(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define what_is(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define infll 9e18
#define inf 1e12

using namespace std;
 
/*.....TYPEDEFS ....*/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;
 
/*....USEFUL FUNCTIONS....*/
ll pwr(ll base, ll exp, ll mod=MOD){ll res=1; while(exp>0){if(exp%2){res=(res*base)%mod;}base=(base*base)%mod;exp/=2;}return res;}
ll gcd(ll a, ll b){ if(b==0)return a; else gcd(b, a%b);}
bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if (n%2==0||n%3==0)return false;for(int i=5; i*i<=n; i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
 
/*....I/O Functions...*/
inline string rs(){char x[1234567];scanf("%s", x);string s = x; return s;}
inline int ri(){int x; scanf("%d", &x);return x;}
inline long long rl(){long long x; scanf("%lld", &x); return x;}
 
/*---------Solution below this line --------*/
 
const int N = 12;

int n, res;
int a[N], b[N];

void BT(int idx){
	if(idx == -1){
		int cur = 1;
		rep(i,0,n) cur *= b[i];
		if(cur % 2 == 0)++res;
		return;
	}
	b[idx] = a[idx];
	BT(idx - 1);
	b[idx] = a[idx] - 1;
	BT(idx - 1);
	b[idx] = a[idx] + 1;
	BT(idx - 1);
}


int32_t main()
{
	FIO
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	cin >> n;
	
	rep(i,0,n) cin >> a[i], b[i] = a[i];
		
	BT(n-1);
	
	cout << res << '\n';
	
	
	
	
	return 0;
}

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

int main () {
  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;

  for(int i=0;i<gy-sy;i++) { //(0,0)を原点として、差で表す
    cout << "U";
  }
  for(int i=0;i<gx-sx;i++) {
    cout << "R";
  }
  for(int i=0;i<gy-sy;i++) {
    cout << "D";
  }
  for(int i=0;i<gx-sx;i++) {
    cout << "L";
  } //これで1往復　UUURRRRDDDLLLL(原点から左に1ずれた状態)

  cout << "L"; //左に1ズレる

  for(int i=0;i<(gy-sy)+1;i++) { //(0,1)から差+1の位置へ
    cout << "U";
  }
  for(int i=0;i<(gx-sx)+1;i++) { //目的地の上につく
    cout << "R";
  }

  cout << "DR"; //目的地に入り、右に1ずれる

  for(int i=0;i<(gy-sy)+1;i++) {
    cout << "D";
  }
  for(int i=0;i<(gx-sx)+1;i++) { //目的地の一個下に入る
    cout << "L";
  }

  cout << "U"; //とーちゃく
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T>
bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
struct edge{ll to;};
struct graph{
    ll N;
    vector<vector<edge> > G;
    vector<bool> used;

    graph(ll n): N(n), G(N), used(N,false) {}
    
    void add_edge(ll s, ll t){
        G[s].emplace_back((edge){t});
        G[t].emplace_back((edge){s}); //無向ならON
    }

    ll dfs(ll v=0){
        used[v]=true;
        ll depth=0;
        ll doudep=0;
        map<ll,ll> mp;
        ll ct=0;
        for(auto E : G[v]){ // 4,4,4,5,5
            if(!used[E.to]){
                ll what=dfs(E.to)+1;
                ++mp[what];
                ++ct;
            }
        }
        ll res=0;
        ll mpsize=ct;
        for(auto r:mp){
            maxi(res,r.first+mpsize-1);
            mpsize-=r.second;
        }
        return res;
    }
};

//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    graph g(N);
    rep(i,N-1){
        int x; cin>>x; --x;
        g.add_edge(i+1,x);
    }
    cout<< g.dfs() <<"\n";
}
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


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

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

  if ((N - 3) % 10 == 0) {
    cout << "bon" << endl;
  }
  else if ((N - 1) % 10 == 0 || (N - 8) % 10 == 0 || (N - 6) % 10 == 0 || N % 10 == 0) {
    cout << "pon" << endl;
  }
  else {
    cout << "hon" << endl;
  }
}

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

#define ll long long
#define ull unsigned long long 

int main(){
    string s;
    cin >> s;
    int n = s.length();

    ll ans=0, b=0;
    for(int i=0; i<n; ++i){
        if(s[i] == 'B')
            b++;
        else
            ans += b;
    }

    cout << ans;
}

Measured memory_bytes: 3716
import bisect

N,H=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]

AB.sort()
MAX=AB[N-1][0]

AB.sort(key=lambda x:x[1])

for i in range(N):
    if AB[i][1]>MAX:
        break

THRSUM=[AB[N-1][1]]
for j in range(N-2,i-1,-1):
    THRSUM.append(AB[j][1]+THRSUM[-1])

if H>THRSUM[-1]:
    ANS=0
    H-=THRSUM[-1]
    ANS+=len(THRSUM)

    print(ANS+-(-H//MAX))

else:
    print(bisect.bisect_left(THRSUM,H)+1)


Measured memory_bytes: 31948
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string t, h;
    int tp = 0, hp = 0;
    for(int i = 0; i < n; i++) {
        cin >> t >> h;
        if (t > h)
            tp += 3;
        else if (t == h) {
            tp += 1;
            hp += 1;
        }
        else
            hp += 3;
    }
    cout << tp << " " << hp << '\n';
  
    return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1e9+7;
using namespace std;

int N;
string s;
ll f[3030][3030];

void solve(){
	f[1][1] = 1;
	for(int i = 2;i<=N;i++){
		if(s[i-1] == '<'){
			for(int j = 1;j<=i;j++){
				f[i][j] = f[i][j-1] + f[i-1][j-1]; f[i][j] %= mod;
			}
		}else{
			for(int j = i;j>=1;j--){
				f[i][j] = f[i][j+1] + f[i-1][j]; f[i][j] %= mod;
			}
		}
	}
	ll ans = 0;
	for(int i = 1;i<=N;i++) ans = (ans + f[N][i]) %mod;
	cout<<ans<<'\n';
}

int main(){
    // debug;
    ios;

    cin>>N;
    cin>>s; 
    s = '#' + s;
    solve();
    
    return 0;
}


Measured memory_bytes: 70400
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=2e5+5;
int a[1000];
int main()
{
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);

    ll ans=0,sum=inf;
    for(int i=a[0];i<=a[n-1];i++)
    {
        for(int j=0;j<n;j++)
            ans=ans+(a[j]-i)*(a[j]-i);
        sum=min(ans,sum);
        ans=0;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100 + 50;
const int mod = 1e9+7;
int n, W, w[maxn], v[maxn];
ll dp[105][100050];
int main(){
    cin >> n >> W;
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];    
    memset(dp, 127, sizeof(dp));
    for(int i = 0; i <= n; i++) dp[i][0] = 0;
    for(int  i = 1; i <= n; i++)
        for(int j = 1; j <= 100000; j++){
            dp[i][j] = dp[i-1][j];
            if(j >= v[i])
                dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }

//    cout << dp[1][30];
    for(int i = 100000; i >= 1; i--){
        if(dp[n][i] <= W){
            cout << i << endl;
            break;
        }
    }
            

    return 0;
}

Measured memory_bytes: 82304
#include <iostream>
#include <string>

using namespace std;

int main(){
    string S; cin >> S;

    int N = S.length();

    if(S[0] == S[N-1]){
        if((N-3)%2==1){
            cout << "First" << endl;
        }else{
            cout << "Second" << endl;
        }
    }else if(S[0] != S[N-1]){
        if((N-2)%2==1){
            cout << "First" << endl;
        }else{
            cout << "Second" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PI 3.1415926535897932384626433832795
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long MOD = 998244353;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
string toString(long long x)
{
stringstream ss;
ss << x;
string str = ss.str();
return str;
}
long long fastpow(long long x,long long k)
{
    if(!k)
        return 1;
    if(k & 1)
        return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
    long long ans = fastpow(x,k/2);
    ans %= MOD;
    ans *= ans;
    ans %= MOD;
    return ans;
}
long long sumF(long long x)
{
    int s = 0;
    while(x)
        s += x%10,x /= 10;
    return s;
}
int main()
{
    IO;
    int x,y,z,k;
    cin >> x >> y >> z >> k;
    vector<long long> a(x),b(y),c(z);
    for(int i = 0;i < x;i++)
        cin >> a[i];
    for(int i = 0;i < y;i++)
        cin >> b[i];
    for(int i = 0;i < z;i++)
        cin >> c[i];
    vector<long long> ab;
    for(int i = 0;i < x;i++)
    {
        for(int j = 0;j < y;j++)
            ab.push_back(a[i] + b[j]);
    }
    sort(ab.begin(),ab.end(),greater<long long>());
    sort(c.begin(),c.end(),greater<long long>());
    vector<long long> ans;
    for(int i = 0;i <= 3000 && i < ab.size();i++)
    {
        for(int j = 0;j <= 3000 && j < c.size();j++)
            ans.push_back(ab[i] + c[j]);
    }
    sort(ans.begin(),ans.end(),greater<long long>());
    stack<long long> ff;
    for(int i = 0;i < k;i++)
        cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 43240
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
  ll m,d,cnt=0,a,b;
  cin >> m >> d;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=d;j++){
      if(j>=10){
        b=j%10;
        a=j/10;
        if(a>=2&&b>=2&&a*b==i) cnt++;
      }
    }
  }
  cout << cnt << endl;
}


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

int main(){
  int i,j,k,n,ice[1002][1002],a,b;
  char x[2000],y[2000];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",x);
    scanf("%s",y);
    a=strlen(x);
    b=strlen(y);
    for(j=0;j<=a;j++){
      ice[j][0]=0;
    }
    for(k=1;k<=b;k++){
      ice[0][k]=0;
    }

    for(j=1;j<=a;j++){
      for(k=1;k<=b;k++){
	if(x[j-1]==y[k-1]){
	  ice[j][k]=ice[j-1][k-1]+1;
	}
	else if(ice[j][k-1]<ice[j-1][k]){
	  ice[j][k]=ice[j-1][k];
	}
	else {
	  ice[j][k]=ice[j][k-1];
	}
      }
    }
    printf("%d\n",ice[a][b]);
  }

  return 0;
}



Measured memory_bytes: 5660
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

typedef long long LL;
typedef unsigned int UI;

#define rSort(a) 		sort(a.rbegin(),a.rend())
#define Sort(a) 		sort(a.begin(),a.end())
#define Reverse(a) 		reverse(a.begin(),a.end())
#define Sum(a)  		accumulate(a.begin(), a.end(), 0)
#define REP(i, n) 		for(UI i = 0;i < n;i++)
#define REPR(i, n) 		for(UI i = n;i >= 0;i--)
#define FOR(i, m, n) 	for(UI i = m;i < n;i++)
#define pb(i) 			push_back(i)
#define SWAP(x,y) 		((x!=y)&&(x^=y,y^=x,x^=y))

#define MOD  			(LL)1e9 + 7;
#define INF  			(LL)1 << 62;

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

	cin.tie(0);
	ios::sync_with_stdio(false);

	LL A, B, ans;
	int ret = 0;

	cin >> A >> B;

	for (ans = 0; ans < 1e9; ans++) {
		if (llabs(A - ans) == llabs(B - ans)) {
			ret = 1;
			break;
		}
	}

	if (ret) {
		cout << ans << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}

	return 0;
}

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

int main() {
  int n; cin>>n;
  vector<int> w(n);
  for(auto &e: w) cin>>e;
  int total = accumulate(w.begin(),w.end(),0);
  int ans = total,presum = 0;
  for(int i=0;i<n;i++) {
      presum += w[i];
      ans = min(ans,abs(total-2*presum));
      if (total-2*presum < 0) break;
  }
  cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
 long long int n,a[1000000],i;
 cin>>n;
 for(i=0;i<n;i++){
    cin>>a[i];
 }
 long long int max=a[0],ans=0;
 for(i=1;i<n;i++){
    if(max<a[i])max=a[i];
    else ans=ans+max-a[i];
 }
 cout<<ans;
return 0;
}


Measured memory_bytes: 5172
N, M = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return -1, -1

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

        return x, y

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


bridge = [(map(int, input().split())) for _ in range(M)][::-1]

unionfind = UnionFind(N)
total = N * (N - 1) // 2
ans = [total]
roots = set()
size = [1] * (N + 1)
not_fuben = 0
for a, b in bridge[:-1]:
    x, y = unionfind.union(a - 1, b - 1)
    if x != -1:
        not_fuben += size[y] * size[x]
        size[x] += size[y]
    ans.append(total - not_fuben)
for a in ans[::-1]:
    print(a)

Measured memory_bytes: 116184
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	data = [0]
	if n > 0: data += map(int,raw_input().split())
	if m > 0: data += map(int,raw_input().split())
	data = sorted(data)
	print max(data[i+1]-data[i] for i in range(n+m))

Measured memory_bytes: 5336
#include<iostream>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		if(a==0&&b==0)
			break;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				cout<<'#';
			}
			cout<<endl;
		}
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <cmath>
#include <cstring>
#define EPS 1e-9
#define INF 1e10


using namespace std;

struct P{
	double x,y;
};
struct L{
	P p1,p2;
};
struct STAR{
	P p[5];
	L l[5];
};

STAR star[102];
double dp[102][102];

void setStar(STAR *star, int x, int y, int a, int r){
	int i;
	for(i=0;i<5;i++){
		star->p[i].x = x+r*cos((double)M_PI*(a+90+i*72)/180);
		star->p[i].y = y+r*sin((double)M_PI*(a+90+i*72)/180);
	}
	star->l[0].p1 = star->p[0];star->l[0].p2 = star->p[2];
	star->l[1].p1 = star->p[0];star->l[1].p2 = star->p[3];
	star->l[2].p1 = star->p[1];star->l[2].p2 = star->p[3];
	star->l[3].p1 = star->p[1];star->l[3].p2 = star->p[4];
	star->l[4].p1 = star->p[2];star->l[4].p2 = star->p[4];
}

int isIntersect(L l1, L l2){
if (((l1.p1.x - l1.p2.x) * (l2.p1.y - l1.p1.y) + (l1.p1.y - l1.p2.y) * (l1.p1.x - l2.p1.x)) * 
        ((l1.p1.x - l1.p2.x) * (l2.p2.y - l1.p1.y) + (l1.p1.y - l1.p2.y) * (l1.p1.x - l2.p2.x)) < 0){
        if (((l2.p1.x - l2.p2.x) * (l1.p1.y - l2.p1.y) + (l2.p1.y - l2.p2.y) * (l2.p1.x - l1.p1.x)) * 
            ((l2.p1.x - l2.p2.x) * (l1.p2.y - l2.p1.y) + (l2.p1.y - l2.p2.y) * (l2.p1.x - l1.p2.x)) < 0	){
            return 1;
        }
    }
    return 0;
}


double lpdistance(L l, P p){
    double dx = (l.p2.x - l.p1.x), dy = (l.p2.y - l.p1.y);
    double a = dx * dx + dy *dy, b = dx * (l.p1.x - p.x) + dy * (l.p1.y - p.y);
    double t = -b / a;
    if(t < 0) t = 0;
    if(t > 1) t = 1;
    double tx = l.p1.x + dx * t, ty = l.p1.y + dy * t;
    return sqrt((p.x - tx) * (p.x - tx) + (p.y - ty) * (p.y - ty));
}

double lldistance(L l1, L l2){
	if(isIntersect(l1, l2)) return 0;
	double     minl= lpdistance(l1, l2.p1);
	minl = min(minl, lpdistance(l1, l2.p2));
	minl = min(minl, lpdistance(l2, l1.p1));
	minl = min(minl, lpdistance(l2, l1.p2));
	return minl;
}

double ssdistance(STAR s1, STAR s2){
	double minl = INF;
	int i,j;
	for(i=0;i<5;i++)
	for(j=0;j<5;j++){
		minl = min(minl, lldistance(s1.l[i], s2.l[j]));
	}
	return minl;
}

main(){
	int n,m,l,i,j,k,x,y,a,r;
	while(cin>>n>>m>>l,n){
		memset(dp, 0, sizeof(dp));
		for(i=1;i<=n;i++){
			cin>>x>>y>>a>>r;
			setStar(star+i,x,y,a,r);
		}
		for(i=1;i<n;i++){
			dp[i][i]=0;
			for(j=i+1;j<=n;j++){
				dp[i][j]=dp[j][i]=ssdistance(star[i], star[j]);
			}
		}
		
		for(k=1;k<=n;k++){
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
		}
		printf("%.20lf\n", dp[m][l]);
	}
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;

int main(){
	int n; cin >> n; vector<int> v(n);
	for(auto &i : v) scanf("%d",&i);
	sort(all(v));
  n /= 2;
	printf("%d\n", v[n] - v[n-1]);
}


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

int main(){
int N;
  cin>>N;
  int sum=0, M=0;
  for(int i=0; i<N; i++){
    int p;
   cin>>p;
   sum+=p;
   M=max(M, p);}
  
  int ans=sum-(M/2);
  
  cout<<ans<<endl; 
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
int main() {
    fastio ;
    ll a, b, c, d;
    cin>>a>>b>>c>>d;
    ll f1 = a*c;
    ll f2 = a*d;
    ll f3 = b*c;
    ll f4 = b*d;
    f1 = max(f1, f2);
    f1 = max(f1, f3);
    f1 = max(f1, f4);
    cout<< f1 <<endl;
}


Measured memory_bytes: 3616
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef unsigned long long ul;
int a[5000], b[5000];
bool used[5000];
int n;
vector<int> u[5000];
void init() {
	rep(i, n) {
		Rep(j, i, n) {
			u[i].push_back(a[j]);
		}
	    sort(u[i].begin(), u[i].end());
	}
}
vector<P> v;
int calc(int id) {
	int c = 0; int le = u[id].size()-1;
	per(i, v.size()) {
		if (used[v[i].second])continue;
		while (le>=0 && u[id][le]>=v[i].first) {
			le--;
		}
		if (le<0)break;
		c++; le--;
	}
	return c;
}

int main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n) {
		cin >> b[i];
		v.push_back({ b[i],i });
	}
	sort(v.begin(), v.end());
	init();
	vector<int> ans;
	rep(i, n) {
		int c = calc(i);
		int b = lower_bound(v.begin(), v.end(), P{ a[i] + 1,-1 }) - v.begin();
		int le = b; int ri = v.size();
		while (ri - le > 1) {
			int mid = (ri + le) >> 1;
			used[v[mid].second] = true;
			int z = calc(i + 1);
			used[v[mid].second] = false;
			if (a[i] < v[mid].first)z++;
			if (z == c) {
				le = mid;
			}
			else {
				ri = mid;
			}
		}
		if (le < v.size()) {
			used[v[le].second] = true;
			int cz = calc(i + 1);
			if (cz + 1 == c) {
				ans.push_back(v[le].first);
				v.erase(v.begin() + le);
				continue;
			}
		    used[v[le].second] = false;
		}
		ri = b; le = 0;
		while (ri - le > 1) {
			int mid = (ri + le) >> 1;
			used[v[mid].second] = true;
			int z = calc(i + 1);
			used[v[mid].second] = false;
			if (a[i] < v[mid].first)z++;
			if (z == c) {
				le = mid;
			}
			else {
				ri = mid;
			}
		}
		used[v[le].second] = true;
		ans.push_back(v[le].first);
		v.erase(v.begin() + le);
	}
	rep(i, n) {
		if (i > 0)cout << " ";
		cout << ans[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 64644
# AGC014B - Unplanned Queries
from collections import Counter


def main():
    *A, = map(int, open(0).read().split())
    T = Counter(A[2:]).values()
    flg = all(i % 2 == 0 for i in T)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

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

using namespace std;

int main(){
	int N;
	while(cin >> N){
		int base = 0;
		vector<int> res;
		if(N == 3){
			res.push_back(2);
			res.push_back(5);
			res.push_back(63);
			N = 0;
		}
		if(N == 4){
			res.push_back(2);
			res.push_back(3);
			res.push_back(4);
			res.push_back(9);
			N = 0;
		}
		if(5 <= N && N <= 6){
			res.push_back(2);
			res.push_back(3);
			res.push_back(4);
			res.push_back(6);
			res.push_back(9);
			if(N == 6) res.push_back(12);
			N = 0;
		}
		while(N > 0){
			int p = min(8, N);
			int arr[] = {3, 9, 8, 10, 2, 4, 6, 12};
			int start = 8 - (p+1)/2 * 2;
			for(int i=0;i<p;i++) res.push_back(base + arr[i + start]);
			base += 12;
			N -= p;
		}
		cout << res[0];
		for(int i=1;i<res.size();i++) cout << " " << res[i];
		cout << endl;
	}
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
using namespace std;
int main(){
  char S[3];
  for(int i=0;i<3;i++){
    cin>>S[i];
  }
  if(S[0]==S[1] && S[1]==S[2] && S[0]==S[2])cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
}


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

using ll = long long;
using ull = unsigned long long;

using namespace std;

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

    ll X,Y,Z;

    cin >> X >>Y>>Z;

    cout<<Z<<' '<<X<<' '<<Y<<'\n';

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int n;
  cin>>n;
  long long a;
  map<long long,int> mp;
  REP(i,n){
    cin>>a;
    mp[a]++;
  }
  
  int ans=0;
  for(auto p:mp){
    if(p.second%2==0){
      continue;
    }else{
      ans++;
    }
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    string target = "AKIHABARA";
    string s;
    cin >> s;
    int n = target.length();
    int p = 0;
    bool ok = true;
    for(int i = 0; i<n; i++){
        if(p<s.length() && s[p]==target[i]){
            p++;
            continue;
        }
        else if(target[i]=='A'){
            continue;
        }
        else{
            ok = false;
            break;
        }
    }
    ok &= p==s.length();
    cout << (ok?"YES":"NO") << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int H, W, N;
	cin >> H >> W >> N;
	
	int mx = max(H, W);
	int ans = (N + mx - 1) / mx;
	cout << ans << endl;
	
	return 0;
}


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


int main() {
  long N;
  cin>>N;
  long ans=0;
  for(int i=1;i<sqrt(N);i++){
    long M=N-i;
    if(M%i==0&&i<M/i) ans+=M/i;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define F first
#define S second

#define ALL(x)      (x).begin(), (x).end()
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#ifndef ONLINE_JUDGE
#define DBG(x)      cout << __LINE__ << " says: " << #x << " = " << (x) << endl
#else
#define DBG(x)
#endif

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 80+7;

int main()
{
    optimizeIO();

    int tc = 1 ;

    while(tc--)
    {
        int n;
        cin>>n;

        vector<LL>v(n+10);

        for(int i=1; i<=n; i++)
            cin>>v[i];

        v[n+1] = INT_MIN;

        int p1 = -1, p2 = 1;
        LL cur  = 1000;

        while(1)
        {
            if(p1>=n || p2>=n)
                break;

            bool hoise = false;

            for(int i=p2+1; i<=n; i++)
                if(v[i]>v[i-1])
                {
                    p1 = i-1;
                    hoise = true;
                    break;
                }

            if(!hoise)
                break;

            for(int i=p1+1; i<=n+1; i++)
                if(v[i]<v[i-1])
                {
                    p2 = i-1;
                    break;
                }

            LL buy = cur/v[p1];

            LL gain = (v[p2]-v[p1]) * buy;

            cur += gain;

            DBG(p1);
            DBG(p2);
            DBG(cur);

        }

        cout<<cur<<endl;



    }

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<string>
#include<iomanip>
#include<numeric>
using namespace std;

long long  mod = 1000000007;

long max(long x, long y) {
	return x > y ? x : y;
}

long min(long x, long y) {
	return x < y ? x : y;
}

long factorial(long n) {
	if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

long long  fel(long long  n,long long  f) {

		if (f == 1) {
			return n % mod;
		}
		else if (f % 2 == 0) {
			return (fel(n,f / 2) * fel(n,f / 2)) % mod;
		}
		else {
			return ((n  * fel(n,f / 2) %mod) * fel(n,f / 2))% mod;
		}
	

}


int main()
{
	long long n,m;
	cin >> n;
	cin >> m;
	
	vector<long long> a(n),b(50),c(n);
	for (long long i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 50; i++) {
		b[i] = 0;
	}

	sort(a.begin(), a.end());
	
	int ma;
	for (long long i = 0; i < n; i++) {
		c[i] = log2(a[i]);
		b[c[i]]++;
		ma = c[i];
	}

	int fl = ma;
	long long sum = 0;
	
	while (sum <= m) {
		if (fl > 0) {
			b[fl - 1] = b[fl] + b[fl - 1];
			sum = sum + b[fl];
		}
		else {
			break;
		}
		fl--;
	}

	if (b[fl]+sum<= m) {
		cout << "0";
	}
	else{
		for (long long i = 0; i < n; i++) {
			if(c[i]>=fl+1){
				a[i]=a[i]/pow(2,c[i]-(fl+1));
			}
		}
		sort(a.begin(), a.end(), greater<>());

		for (long long i = 0; i < m - (sum-b[fl+1]); i++) {
			a[i] = a[i] / 2;
		}
		sum = 0;
		for (long long i = 0; i < n; i++) {
			sum = sum + a[i];
		}
		cout << sum;
	}

	

	/*vector<vector<double>> a(2, vector<double>(n));
	vector<int> b(n);
	*/

	/*long long kai;
	kai = 1;
	for (long long i = 1; i <= nm; i++) {
		kai = (kai * i) % mod;
	}*/


	//cout << fel(kai,mod-2);

	//vector<long long> sei(nm), gyaku(nm);

}


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

int main(void){
	int n;
	int t[10];

	while(cin>>n,n){
		memset(t,0,sizeof(t));
		for(int i=0;i<n;i++){
			int x;
			cin>>x;
			if(x/10 < 6){
				t[x/10]++;
			}
			else{
				t[6]++;
			}
		}

		for(int i=0;i<7;i++){
			cout<<t[i]<<endl;
		}
	}

	return 0;
}

Measured memory_bytes: 864
/*
     Author: Wasi Ur Rahman
     RMSTU,Rangamati,Chittagong,Bangladesh
*/
#include <bits/stdc++.h>
using namespace std;
#define  gcd(a,b) __gcd(a,b)
#define  lcm(a,b) (a*b)/gcd(a,b)
#define  PI acos(-1.0)
#define  sqr(x) ((x)*(x))
#define  min3(a,b,c) min(a,min(b,c))
#define  min4(a,b,c,d) min(d,min(a,min(b,c)))
#define  max4(a,b,c,d) max(d,max(a,max(b,c)))
typedef   pair<int, int> ii;
typedef   std::vector<ii> vii;
#define   vi   std::vector<int>
#define   vll  std::vector<ll>
#define   all(n) n.begin(),n.end()
#define  mpsi std::map<string, int>
#define  pb             push_back
#define  ll             long long int
#define  ln             printf("\n");
#define  fast           ios::sync_with_stdio(false);cin.tie(0)
#define  max3(a,b,c)    max(a,max(b,c))
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define dec(x,y)        fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
#define  mod           1e9 + 7;
bool prm[1000001];
void sieve()
{
    prm[0] = prm[1] = 1;
    for(ll i = 4 ; i <= 1000000 ; i += 2)
        prm[i] = 1 ;
    for(ll i = 3 ; i * i <= 1000000 ; i += 2)
    {
        if(!prm[i])
        {
            for(ll j = i * i ; j <= 1000000 ; j+= i + i)
                prm[j] = 1 ;
        }
    }
}
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
        return x;

    // Staring from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result <= x)
    {
        i++;
        result = i * i;
    }
    return i - 1;
}
int main()
{
    fast;
    int N;
    cin>>N;
    vector<int>v(N);
    for(int i=0; i<N; ++i)
    {
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    int answer=v[v.size()/2]-v[v.size()/2-1];
    cout<<answer<<endl;
    return 0;
}


Measured memory_bytes: 640
import math
def comb(n, k):
    if n < 0 or k < 0 or n < k: return 0
    return math.factorial(n) // math.factorial(n-k) // math.factorial(k)



n,k = map(int, input().split())
MOD = 10 ** 9 + 7

all = 0

for i in range(k):
    add = comb(k, i) * ((k-i) ** n) % MOD
    if i & 1: all = (all - add + MOD) % MOD
    else: all = (all + add) % MOD

print(all)


Measured memory_bytes: 5668
import sys
from math import sqrt
from collections import Counter, defaultdict

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    s = input()

    l = list(s)
    if l[2] == l[3] and l[4] == l[5]:
        print("Yes")
    else:
        print("No")
    pass


if __name__ == "__main__":
    main()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n;
  string s;
  cin >>n>>s;
  ll w=0,e=0;
 for(ll i=0;i<n;i++){
   if(s[i]=='#') w++;
   else e++;
 }
 ll cnt,ww=0,ee=0;
 if(s[0]=='#') ee+=e,cnt=ee;
 else ee+=(e-1),cnt=ee;
 ll ans=ww+ee;
 for(ll i=0;i<n-1;i++){
   if(s[i]=='#') {
     ww++;
     if(s[i+1]=='.') ee--;
   }
   else{
     if(s[i+1]=='.') ee--;
   }
   cnt=ww+ee;
   ans=min(ans,cnt);
 }
 cout <<ans<<endl;
}


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

int main() {
  int N;
  int d[110];
  cin>>N;
  for (int i=0;i<N;++i) cin>>d[i];
  
  int num[110]={0};
  for (int i=0;i<N;++i){
    ++num[d[i]];
  }
  
  int res=0;
  for (int i=1;i<=100;++i) {
    if(num[i]>0) {
      ++res;
    }
  }
  cout<<res<<endl;
}

Measured memory_bytes: 256
data class Ball(val c: Char, val v: Int)

const val INF = Int.MAX_VALUE / 4

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val balls = Array( 2 * n, {
    val (cString, vString) = readLine()!!.split(" ")
    val c = cString[0]
    val v = vString.toInt()
    Ball(c, v)
  })
      .toMutableList()

  val whiteValueToIndex = IntArray(n + 1, { -1 })
  val blackValueToIndex = IntArray(n + 1, { -1 })
  for (i in 0 until 2 * n) {
    if (balls[i].c == 'W') {
      whiteValueToIndex[balls[i].v] = i
    } else {
      blackValueToIndex[balls[i].v] = i
    }
  }

  val whiteLeft = Array(2 * n, { BooleanArray(n + 1) })
  val blackLeft = Array(2 * n, { BooleanArray(n + 1) })
  val countWhiteLE = Array(2 * n, { IntArray(n + 1) })
  val countBlackLE = Array(2 * n, { IntArray(n + 1) })
  for (i in 0 until 2 * n) {
    if (balls[i].c == 'W') {
      for (j in i + 1 until 2 * n) {
        whiteLeft[j][balls[i].v] = true
      }
    } else {
      for (j in i + 1 until 2 * n) {
        blackLeft[j][balls[i].v] = true
      }
    }
  }
  for (i in 0 until 2 * n) {
    for (k in 1..n) {
      countWhiteLE[i][k] = countWhiteLE[i][k - 1] + if (whiteLeft[i][k]) 1 else 0
      countBlackLE[i][k] = countBlackLE[i][k - 1] + if (blackLeft[i][k]) 1 else 0
    }
  }

  val dp = Array(n + 1, { IntArray(n + 1, { INF }) })
  dp[0][0] = 0

  for (w in 0..n) {
    for (b in 0..n) {
      // w White and b Black are used now.

      // w + 1 White
      if (w < n) {
        val index = whiteValueToIndex[w + 1]
        // val index = balls.indexOfFirst { it.c == 'W' && it.v == w + 1 }
        val cost = index - countWhiteLE[index][w] - countBlackLE[index][b]
        dp[w + 1][b] = Math.min(dp[w + 1][b], dp[w][b] + cost)
      }

      // b + 1 Black
      if (b < n) {
        val index = blackValueToIndex[b + 1]
        // val index = balls.indexOfFirst { it.c == 'B' && it.v == b + 1 }
        val cost = index - countWhiteLE[index][w] - countBlackLE[index][b]
        dp[w][b + 1] = Math.min(dp[w][b + 1], dp[w][b] + cost)
      }
    }
  }
  println(dp[n][n])
}


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

using namespace std;

#define ll long long

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

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

	int t = 1, i = 1;
	//cin >> t;
	while(t--) {
		//cout << "Case #" << i << ": ";
		solve();
		//i++;
	}
	return 0;
}



Measured memory_bytes: 3600
/*
Author: QAQAutomaton
Lang: C++
Code: B.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cp;
typedef pair<int,int> pii;
int inf;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T,class T2>int chkmin(T &a,T2 b){return a>b?a=b,1:0;}
template<class T,class T2>int chkmax(T &a,T2 b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T,class T2>T mmin(T a,T2 b){return a<b?a:b;}
template<class T,class T2>T mmax(T a,T2 b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
struct __INIT__{
	__INIT__(){
		memset(&inf,0x3f,sizeof(inf));
	}
}__INIT___;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template<typename A>
	inline bool read (A &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
		return 1;
	}
	inline bool read (char &x) {
		while((x=gc())==' '||x=='\n' || x=='\r');
		return x!=EOF;
	}
	inline bool read(char *x){
		while((*x=gc())=='\n' || *x==' '||*x=='\r');
		if(*x==EOF)return 0;
		while(!(*x=='\n'||*x==' '||*x=='\r'||*x==EOF))*(++x)=gc();
		*x=0;
		return 1;
	}
	template<typename A,typename ...B>
	inline bool read(A &x,B &...y){
		return read(x)&&read(y...);
	}
	template<typename A>
	inline bool write (A x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
		return 0;
	}
	inline bool write (char x) {
		putc(x);
		return 0;
	}
	inline bool write(const char *x){
		while(*x){putc(*x);++x;}
		return 0;
	}
	inline bool write(char *x){
		while(*x){putc(*x);++x;}
		return 0;
	}
	template<typename A,typename ...B>
	inline bool write(A x,B ...y){
		return write(x)||write(y...);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
char s[200005];
signed main(){
#ifdef QAQAutoMaton 
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
	read(s);	
	int n=strlen(s);
	for(int i=0;i<n;++i)putc(s[i]=='P'?'P':'D');
	putc('\n');
	return 0;
}



Measured memory_bytes: 4224
#include<bits/stdc++.h>
#pragma GCC optimize("02")
#define ll long long
#define _inline __inline__ __attribute__((always_inline))
using namespace std;
struct ios{
    inline char gc(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> _inline ios & operator >> (_Tp &x){
        static char ch,sgn; ch=gc(),sgn=0;
        for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
        for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
        sgn&&(x=-x); return *this;
    }
}inc;
string s;
int main(){
	cin>>s;
	for(int i=0;i<s.size();i+=2) putchar(s[i]);
	puts("");
	return 0;
}

Measured memory_bytes: 512