akhauriyash/Code-Regression huggingface dataset:
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Measured memory_bytes: 79196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll s,w;
	cin>>s>>w;
	if(w>=s){
		cout << "unsafe";
	}
	else{
		cout << "safe";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3644
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;
const MOD: usize = 1e9 as usize + 7;

fn main() {
    input!{
      n: usize,
      k: usize,
    }
    let root = (n as f64).sqrt() as usize;
    let mut nums = vec![];
    {
        let mut i = 1;
        while i <= n {
            if i <= root {
                nums.push(1);
                i += 1;
            } else {
                let lower = i;
                let upper = n / (n/lower);
                nums.push(upper - lower + 1);
                i = upper + 1;
            }
        }
    }
    let nn = nums.len();
    let mut dp = vec![vec![0; nn]; k];

    for i in 0..nn {
        dp[0][i] = nums[i];
    }
    for i in 0..k-1 {
        let mut acm = vec![0; nn+1];
        for j in 0..nn {
            acm[j+1] = acm[j] + dp[i][j];
            acm[j+1] %= MOD;
        }
        for j in 0..nn {
            dp[i+1][j] = acm[nn-j] * nums[j] % MOD;
        }
    }
    let mut ans = 0;
    for i in 0..nn {
        ans += dp[k-1][i];
        ans %= MOD;
    }
    println!("{}", ans);
}


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

const int N = (int) 2e6 + 10 ;
const int inf = (int) 2e9 ;

int main() {
//    freopen("in.txt" , "r" , stdin ) ;
    long long a , b , c ; cin >> a >> b >> c ;
    long long answer = 0 , mn ;
    if( c == 0 ) {
        answer = b ;
    } else {
        answer = 1 , c -= 1 ;
        mn = min(c , a) ;
        answer += mn , c -= mn , a -= mn ;

        mn = min(c , b) ;
        answer += mn + mn , c -= mn , b -= mn ;

        answer += b ;
    }
    cout << answer << endl ;
    return 0 ;
}


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

int main()
{
  int a,b;
  cin >> a >> b;
  if(a * 500 >= b){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

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

int main()
{
  string s;
  cin>>s;
  ll n=s.length();
  cout<<s;
  if(s[n-1]=='s')
    cout<<"es";
  else
    cout<<'s';
  
  
  
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

// 

public class ABC117_B // ←Class名変更！！
{
    public static void Main()
    {
        var n = Ri();
        var l = Ria();

        var total = 0;
        var max = 0;
        foreach (var item in l)
        {
            total += item;
            if (max < item)
            {
                max = item;
            }
        }

        if (max < total - max)
        {
            WriteLine($"Yes");

        }
        else
        {
            WriteLine($"No");
        }
    } // Main

    public static string Rs() { return ReadLine(); }
    public static char Rc() { var c = ReadLine(); return c[0]; }    //最初の1文字だけ返す
    public static int Ri() { return int.Parse(ReadLine()); }
    public static long Rl() { return long.Parse(ReadLine()); }
    public static char[] Rca() { return ReadLine().ToCharArray(); }
    public static int[] Ria() { return Array.ConvertAll(ReadLine().Split(' '), int.Parse); }
    public static long[] Rla() { return Array.ConvertAll(ReadLine().Split(' '), long.Parse); }
} // Class


Measured memory_bytes: 11220
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  // sort, 二分探索, etc
#include <iomanip>  // setprecision (浮動小数点の出力の誤差)
#include <map>
#include <queue>
#include <set>
#include <stack>

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=a,i##_len=(b);i<i##_len;++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define cauto const auto&
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

using namespace std;
using ui = unsigned int;
using ll = long long;
using ull = unsigned long long;

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

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll comb(int n, int r) {
    vector<vector<ll> > v(n+1, vector<ll>(r+1, 0));
    for(int i=0;i<n+1;i++) {v[i][0]=1; if(i < r+1)v[i][i]=1; }
    for(int i=1;i<n+1;i++) {for(int j=1;j<min(i,r+1);j++) {v[i][j]=v[i-1][j-1]+v[i-1][j];}}
    return v[n][r];
}

// CHAR_MAX  = 127
// INT_MAX   = 2.1e+09 (2147483647)
// LONG_MAX  = 9.2e+18 (9223372036854775807)
// LLONG_MAX = 9.2e+18 (9223372036854775807)


int main() {
    ll n, k;
    cin >> n >> k;

    ll r = n % k;

    cout << min(r, abs(k - r)) << '\n';

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(long long i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;
const ll INF = 1E+18;
const ll MAX_S = 2505;

struct state {
    ll v;
    ll s;
    ll t;
    state(ll v, ll s, ll t): v(v), s(s), t(t) {}
    bool operator<(const state& a) const {
        return t > a.t;
    }
};

struct Edge {
    ll to;
    ll a, b;
    Edge(ll to, ll a, ll b): to(to), a(a), b(b) {}
};

vector<Edge> g[55];
ll dp[55][MAX_S+5];

int main(){
    ll n, m, s;
    cin >> n >> m >> s;
    
    rep(i, m) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
    }
    vector<ll> c(n);
    vector<ll> d(n);

    rep(i, n) {
        cin >> c[i] >> d[i];
    } 

    rep(i, n) rep(j, MAX_S) {
        dp[i][j] = INF;
    }
    

    s = min(s, MAX_S);
    dp[0][s] = 0;
    priority_queue<state> q;
    q.push(state(0, s, 0));

    auto addque = [&] (ll v, ll s, ll t) {
        if (s<0) return;
        if (dp[v][s]<=t) return;
        dp[v][s] = t;
        q.push(state(v, s, t));
    };

    while (!q.empty()) {
        state now = q.top();
        q.pop();
        ll nv = now.v;
        ll ns = now.s;
        ll nt = now.t;
        if (dp[nv][ns]!=nt) continue;
        for (Edge e: g[nv]) {
            addque(e.to, ns-e.a, nt+e.b);
        }
        addque(nv, min(ns+c[nv], MAX_S), nt+d[nv]);
    }

    for (ll i=1; i<n; i++) {
        ll ans = INF;
        rep(j, MAX_S) {
            ans = min(ans, dp[i][j]);
        }
        cout << ans << endl;
    }
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 7224
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;



int main()
{
	ll a,b,c ;
	cin >>a>>b>>c ;
	if (4 * a * b < (c - a - b) * (c - a - b)&&c-a-b>0)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

int main(){
    string s;
    cin >> s;
    int size = s.size();
    vector<int> vec(0);
    for (int i = 0; i < size; i++) {
        int input = 0;
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            input = 1;
        }
        vec.push_back(input);
    }
    for (int i = 1; i < size; i++) {
        if (vec[i] == 0) {
            continue;
        }
        vec[i] += vec[i-1];
    }
    sort(vec.begin(), vec.end());
    cout << vec[size - 1] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	VE a(n); rep(i, n)cin >> a[i];
	int ans = 0;
	while (true) {
		bool ok = true;
		rep(i, n) {
			if (a[i] != 0) {
				ok = false;
			}
		}
      
		if (ok)break;
		int cnt = 0;
		rep(i, n) {
			if (a[i] == 0) {
				if (cnt) {
					ans++;
					cnt = 0;
				}
			}
			else {
				a[i]--;
				cnt++;
			}
		}
      if (cnt) {
					ans++;
					cnt = 0;
				}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    int n,su=0; cin>>n;
    vector<int> ar(n);
    for(int i=0;i<n;i++) cin>>ar[i];
    sort(ar.begin(),ar.end());
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            for(int k=j+1;k<n;k++)
            {
                if((ar[i]+ar[j])>ar[k])
                {
                    su++;
                }
            }
    cout<<su;
    return 0;
}


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

int main(){
  int n,k;
  cin >> n >> k;
  double prob=0.0;

  for (int i=1;i<=n;i++){
    int j = i,kazu=0;
    while (true){
      if (j >= k) break;
      kazu++;
      j = j*2;
    }
    double prob2 = (1.0/n);
    for (int i =0;i<kazu;i++) prob2 *= 0.5;
    prob += prob2;
  }
  cout << setprecision(12) << prob;
}

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

int main(){
    string s;
    cin >> s;
    int x=0;
    rep(i,4){
        if(s[i]=='+'){
            x++;
        }else if(s[i]=='-'){
            x--;
        }
    }
    cout << x << endl;
}


Measured memory_bytes: 3576
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
const long long LINF=1e18;
signed main(void)
{
  int N,zero=0;
  long long x;
  x=scanf("%d",&N);
  long long A[N];
  rep(i,N){x=scanf("%lld",&A[i]);if(A[i]==0)zero=1;}
  if(zero)x=0;
  rep(i,N)
  {
    if(A[i]==0){x=0;break;}
    else if(LINF/A[i]<x){x=-1;break;}
    else x*=A[i];
  }
  return printf("%lld",x),0;
}

Measured memory_bytes: 2484
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long int n;
  cin >> n;
  long int a = sqrt(n);
  long int p, q;
  for(long int i = a; i > 0; i--){
    if(n%i == 0){
      p = i;
      q = n/i;
      break;
    }
  }
  cout << p+q-2 << endl;
}

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

class Main{
    public static void main(String args[])throws IOException{
      try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
        StringBuilder sb = new StringBuilder();
        String[] input = br.readLine().split(" ");

        sb.append(input[1]);
        sb.append(input[0]);

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

Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//UnionFind
//全て添字で扱うこと
struct union_find {
  vll parent;
  vll size;

  void init(ll n) {
    for (ll i = 0; i < n; i++) parent.push_back(i);
    for (ll i = 0; i < n; i++) size.push_back(1);
    return;
  }

  ll root(ll n) {
    if (parent[n] == n) return n;
    return parent[n] = root(parent[n]);
  }

  void unite(ll a, ll b) {
    ll ra = root(a), rb = root(b);
    parent[rb] = ra;
    size[ra] += size[rb];
    return;
  }

  bool is_united(ll a, ll b) {
    return (root(a) == root(b));
  }
};

int main() {
  ll n, m;
  cin >> n >> m;

  vll a(m), b(m);
  for (ll i = 0; i < m; i++) cin >> a[i] >> b[i];

  struct union_find uf;
  uf.init(n);

  ll unconv = n * (n - 1) / 2;
  vll ans(1, unconv);

  for (ll i = m - 1; i > 0; i--) {
    ll x = uf.root(a[i] - 1), y = uf.root(b[i] - 1);
    if (!uf.is_united(x, y)) {
      unconv -= uf.size[x] * uf.size[y];
      uf.unite(x, y);
    }
    ans.push_back(unconv);
  }

  for (ll i = 0; i < m; i++) cout << ans[m - 1 - i] << endl;
}

Measured memory_bytes: 5364
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(), (x).end()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end());
// map<int,int> mp;

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

}

Measured memory_bytes: 256
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int mod = 1e+9 + 7;

//マクロ
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main()
{
  int n, m;
  cin >> n >> m;
  priority_queue<int> q;
  rep(i, n)
  {
    int a;
    cin >> a;
    q.push(a);
  }
  rep(i, m)
  {
    int a = q.top();
    q.pop();
    q.push(a / 2);
  }
  ll ans = 0;
  rep(i, n)
  {
    ans += q.top();
    q.pop();
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 892
class Amidakuji
   def initialize(w)
	  @array = []
	  (1..w).each {|each| @array.push(each)}
   end

   def replace(x,y)
	  #?????????x????????¨y???????????\???????????????x,y???Array?????????
	  tempo = @array[y]
	  @array[y] = @array[x]
	  @array[x] = tempo
   end

   def puts_array
	  @array.each do |i|
		 puts i.to_s
	  end
   end
end

verti = gets.to_i
a = Amidakuji.new(verti)
hori = gets.to_i
hori.times do
   ex = gets.split(',').map(&:to_i)
   a.replace(ex[0]-1, ex[1]-1)
end
a.puts_array

Measured memory_bytes: 6108
import sys
R = lambda:map(int,raw_input().split())

while 1:
    try:
        cntJ = 0
        cntI = 0
        s = raw_input()
        for i in xrange(len(s)-2):
            neko = "".join([s[i], s[i+1], s[i+2]])
            #print neko
            if neko == 'JOI': cntJ += 1
            elif neko == 'IOI': cntI += 1
        print cntJ
        print cntI
    except EOFError:
        break

Measured memory_bytes: 4228
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a+b>=k){
        if(a>=k){
            cout<<k<<endl;
        }
        else cout<<a<<endl;
    }
    else{
        cout<<a-(k-(a+b))<<endl;
    }
    return 0;   
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int> pq;
	int n, k, m , x=0, a=0, b=0;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> m;
		pq.push(m);
	}
	for(int i=1;i<=(n+2)/2;i++){
		if(pq.empty()){
			break;
		}
		a=a+pq.top();
		pq.pop();
		if(pq.empty()){
			break;
		}
		b=b+pq.top();
		pq.pop();
		if(pq.empty()){
			break;
		}
	}
	printf("%d",abs(a-b));
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<vector<bool> > vvb;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define yn(f) (f?"yes":"no")
#define YN(f) (f?"YES":"NO")
#define Yn(f) (f?"Yes":"No")
#define mod 1000000007
#define intmax 2147483647
#define intmin -2147483648
#define longmax 9223372036854775807
#define longmin -9223372036854775808
int main() {
	int N;
	cin >> N;
	vvi A(N,vi(N,intmax));
	vi color(N,0);
	vi mincost(N,intmax);
	for (int i = 0; i < N; i++)
	{
		int u,k;
		cin >> u>>k;
		A[i].push_back(u);
		for (int j = 0; j < k; j++)
		{
			int v, w;
			cin >> v >> w;
			A[u][v] = w;
		}
	}
	color[0] = 127;
	mincost[0] = 0;
	while (true) {
		int minIndex = -1;
		for (int i = 0; i < N; i++)
		{
			if (color[i]==127&&(minIndex==-1||mincost[i]<mincost[minIndex]))minIndex = i;
		}
		if (minIndex==-1) break;
		color[minIndex] = 255;
		for (int i = 0; i < N; i++)
		{
			if (color[i]!=255&&A[minIndex][i]<intmax) {
				mincost[i] = min(mincost[i],mincost[minIndex]+ A[minIndex][i]);
				color[i] = 127;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << i << " " << mincost[i] << endl;
	}
};



Measured memory_bytes: 3144
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <list>
#include <bitset>

using namespace std;

// #define DEBUG

int main()
{
#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif
    int q, op, p, x;
    deque<int> a;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> op >> p;
        if (op == 0 && p == 0)
        {
            cin >> x;
            a.push_front(x);
        }
        else if (op == 0 && p == 1)
        {
            cin >> x;
            a.push_back(x);
        }
        else if (op == 1)
        {
            cout << a[p] << endl;
        }
        else if (op == 2 && p == 0)
        {
            a.pop_front();
        }
        else if (op == 2 && p == 1)
        {
            a.pop_back();
        }
    }
    return 0;
}


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

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

ll const MOD = 1e+9 + 7;

int main()
{
    int H, W;
    cin >> H >> W;
    string field[H];
    for (int h = 0; h < H; h++)
    {
        cin >> field[h];
    }

    ll dp[H + 10][W + 10];
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = 1;
    for (int y = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++)
        {
            for (int k = 0; k < 2; k++)
            {
                int ny = y + dy[k];
                int nx = x + dx[k];
                if (ny < H && nx < W && field[ny][nx] == '.')
                {
                    dp[ny][nx] = (dp[ny][nx] + dp[y][x]) % MOD;
                }
            }
        }
    }

    cout << dp[H - 1][W - 1] << endl;
    return 0;
}

Measured memory_bytes: 9216
import itertools

if True:
    n, m, q = map(int, input().split())
    aa = [0] * q
    bb = [0] * q
    cc = [0] * q
    dd = [0] * q
    for i in range(q):
        a, b, c, d = map(int, input().split())
        aa[i] = a - 1
        bb[i] = b - 1
        cc[i] = c
        dd[i] = d

ans = 0
ma = None
for a in itertools.combinations_with_replacement(list(range(1, m + 1)), n):
    x = 0
    for i in range(q):
        if a[bb[i]] - a[aa[i]] == cc[i]:
            x += dd[i]
    if x > ans:
        ma = a
    ans = max(ans, x)
print(ans)


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

int main(void){
    char s[4];
    scanf("%s",s);
    if(strcmp(s,"abc")==0 || strcmp(s,"acb")==0 || strcmp(s,"bac")==0 || strcmp(s,"bca")==0 || strcmp(s,"cab")==0 || strcmp(s,"cba")==0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define N 100

int main(){

  int i,j,l,n,v,num[N],c=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&num[i]);
  }

  for(i=0;i<n;i++){
    l=i;
    for(j=i;j<n;j++){
      if(num[j]<num[l])l=j;
    }
    if(i!=l){
      v=num[i];
      num[i]=num[l];
      num[l]=v;
      c++;
    }
  }
  for(i=0;i<n-1;i++){
    printf("%d ",num[i]);
  }
  printf("%d\n%d\n",num[n-1],c);
  return 0;
}



Measured memory_bytes: 2140
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<sstream>
#include<algorithm>
#include<stack>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define mst(a,b) memset(a,b,sizeof(a))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define dbg(a) cout<<"* "<< #a <<" : "<<a<<endl
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls x<<1
#define rs x<<1|1
#define lowbit(x) x&(-x)
#define ac cout<<ans<<endl
//#define DEBUG 0
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-6;
const ull hashp=1e7+19;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=2e5+100;
ll a[maxn];
ll p[maxn];
ll check(ll x){
	for(int i=60;~i;i--){
		if(p[i]>0&&(x&(1LL<<i)))x^=p[i];
	}
	return x;
}
void add(ll x){
	x=check(x);
	if(!x)return ;
	for(int i=60;~i;i--){
		if(x&(1LL<<i)){
			p[i]=x;
			return ;
		}
	}
}
ll getmax(){
	ll ret=0;
	for(int i=60;~i;i--){
		if((ret^p[i])>ret)ret^=p[i];
	}
	return ret;
}
void solve()
{
	int n;scd(n);
	ll ans=0;
	rep1(i,n){
		scanf("%lld",&a[i]);
		ans^=a[i];
	}
	rep1(i,n){
		a[i]&=(~ans);
		add(a[i]);
	}
	ans+=2*getmax();
	ac;
}
int main(){
    //IOS;
    //freopen("D://data.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n, m, i, I, a[100][100], b[100], c[100] = {0};
	scanf("%d%d", &n, &m);
	for(i = 0 ; i < n ; i++)
	{
		I = 0;
		while(scanf("%d", &a[i][I]))
		{
			char x = getchar();
			if(x == '\n')
			{
				break;
			}
			I++;
		}
	}
	
	for(i = 0 ; i < m ; i++)
	{
		scanf("%d", &b[i]);
	}
	
	for(i = 0 ; i < n ; i++)
	{
		for(I = 0 ; I < m ; I++)
		{
			c[i] += (a[i][I]*b[I]);
		}
	}
	for(i = 0 ; i < n ; i++)
	{
		printf("%d\n", c[i]);
	}
	return 0;
}



Measured memory_bytes: 2128
S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
#        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
#        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

Measured memory_bytes: 8820
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll n;cin>>n;
    map<string,ll>m;
    ll ma=0;
    rep(i,n){
        string s;cin>>s;
        m[s]++;
        ma=max(ma,m[s]);
    }
    for(auto e:m){
        if(e.second==ma)cout<<e.first<<endl;
    }
}

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

struct Main {
  map<string, vector<string> > m;
  set<string> num, vis;

  int rec(const string &s) {
    vis.insert(s);
    if(!m.count(s)) return 1;
    int res = 0;
    for(int i = 0; i < m[s].size(); ++i) {
      if(vis.count(m[s][i])) continue;
      res += rec(m[s][i]);
    }
    return res;
  }

  Main() {
    int n; cin >> n;
    if(n == 0) exit(0);
    string first;
    for(int i = 0; i < n; ++i) {
      string s; cin >> s;
      replace(s.begin(), s.end(), ':', ' ');
      replace(s.begin(), s.end(), ',', ' ');
      replace(s.begin(), s.end(), '.', ' ');
      stringstream ss(s);
      string group;
      ss >> group;
      if(first.empty()) first = group;
      string name;
      while(ss >> name) {
        m[group].push_back(name);
      }
    }
    cout << rec(first) << endl;
  }
};

int main() {
  while(delete new Main(), 1);
  return 0;
}

Measured memory_bytes: 1392
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int main(int argc, const char * argv[]) {
  	int N,X;
    cin >> N >> X;
  	int i;
  ll total;
  int L;
  for(i=0;i<N;i++){
    cin >> L;
    total += L;
    if(total>X) break;
  }
  cout << i+1;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<cmath>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)
int L;
int main() {
	scanf("%d", &L);
	printf("%f", pow((double)L / 3, 3));
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        n: usize,
    }

    println!("{}", n * (n - 1) / 2);
}


Measured memory_bytes: 2156
#include <stdio.h>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

int main() {
    int c[3][3];
    scanf("%d %d %d", &c[0][0], &c[0][1], &c[0][2]);
    scanf("%d %d %d", &c[1][0], &c[1][1], &c[1][2]);
    scanf("%d %d %d", &c[2][0], &c[2][1], &c[2][2]);

    int a12[3], a13[3], a23[3];
    REP(0, i, 3) {
        a12[i] = c[0][i] - c[1][i];
        a13[i] = c[0][i] - c[2][i];
        a23[i] = c[1][i] - c[2][i];
    }

    int b12[3], b13[3], b23[3];
    REP(0, i, 3) {
        b12[i] = c[i][0] - c[i][1];
        b13[i] = c[i][0] - c[i][2];
        b23[i] = c[i][1] - c[i][2];
    }

    // REP(0, i, 3) {
    //     printf("a12[%d]: %d\n", i, a12[i]);
    //     printf("a13[%d]: %d\n", i, a13[i]);
    //     printf("a23[%d]: %d\n", i, a23[i]);
    //     printf("b12[%d]: %d\n", i, b12[i]);
    //     printf("b13[%d]: %d\n", i, b13[i]);
    //     printf("b23[%d]: %d\n", i, b23[i]);
    // }

    if (a12[0] == a12[1] && a12[1] == a12[2] &&
        a13[0] == a13[1] && a13[1] == a13[2] &&
        a23[0] == a23[1] && a23[1] == a23[2] &&
        b12[0] == b12[1] && b12[1] == b12[2] &&
        b13[0] == b13[1] && b13[1] == b13[2] &&
        b23[0] == b23[1] && b23[1] == b23[2]) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <limits>
#include <iterator>
#include <cmath>
#include <numeric>
#include <stack>
#include <queue>
#include <cassert>
#include <forward_list>
#include <chrono>
#include <deque>
#include <list>
#include <random>
#include <cstdio>
#include <sstream>

using namespace std;

//最大公約数
template<class T>
inline T GCD(T m, T n)
{
	T temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

//最小公倍数
template<class T>
inline T LCM(T m, T n)
{
	return m * n / GCD(m, n);
}



int main()
{
	int n, q; string s;
	cin >> n >> q >> s;
	vector<int> index;
	
	int margin = 0;
	while (true)
	{
		if (margin >= n - 1) { break; }

		if (s[margin] == 'A')
		{
			if (s[margin + 1] == 'C')
			{
				index.emplace_back(margin);
			}
		}
		margin++;
	}

	for (int i = 0; i < q; i++)
	{
		int first, last; cin >> first >> last;
		int num = 0;

		for (auto it : index)
		{
			if (first - 1 <= it && it + 1 <= last-1)
			{
				num++;
			}
		}

		cout << num << endl;
	}

	return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[1 << 18], B[1 << 18], indeg[1 << 18], outdeg[1 << 18], incnt[1 << 18], outcnt[1 << 18];
int col[1 << 18], col2[1 << 18], cnts, cntv;
bool used[1 << 18];
vector<int> X[1 << 17], Y[1 << 17], Z[1 << 17], E[1 << 17], G;

void dfs1(int pos) {
	if (used[pos] == true) return;
	used[pos] = true;
	for (int i = 0; i < X[pos].size(); i++) dfs1(X[pos][i]);
	G.push_back(pos);
}

void dfs2(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts;
	for (int i = 0; i < Y[pos].size(); i++) dfs2(Y[pos][i]);
}

void dfs3(int pos) {
	if (col2[pos] >= 1) return;
	col2[pos] = cntv; E[cntv].push_back(pos);
	for (int i = 0; i < Z[pos].size(); i++) dfs3(Z[pos][i]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
	}

	// 強連結成分分解をする
	for (int i = 0; i < N; i++) {
		if (used[i] == true) continue;
		dfs1(i);
	}
	for (int i = G.size() - 1; i >= 0; i--) {
		if (col[G[i]] >= 1) continue;
		cnts++; dfs2(G[i]);
	}

	// 入次数・出次数を求め、グラフを作る
	for (int i = 0; i < M; i++) {
		int p1 = col[A[i]], p2 = col[B[i]]; if (p1 == p2) continue;
		Z[p1].push_back(p2);
		Z[p2].push_back(p1);
		indeg[p1]++; outdeg[p2]++;
	}

	// 連結成分を求める
	for (int i = 1; i <= cnts; i++) {
		if (col2[i] >= 1) continue;
		cntv++; dfs3(i);
	}

	if (cntv == 1) {
		// 連結成分ごとの結果を求める
		for (int i = 1; i <= cntv; i++) {
			if (E[i].size() == 1) continue;
			for (int j = 0; j < E[i].size(); j++) {
				if (indeg[E[i][j]] == 0) incnt[i]++;
				if (outdeg[E[i][j]] == 0) outcnt[i]++;
			}
		}

		// 最後に答えを求める
		int c1 = 0, c2 = 0;
		for (int i = 1; i <= cntv; i++) {
			c1 += incnt[i];
			c2 += outcnt[i];
		}
		cout << max(c1, c2) << endl;
	}
	else {
		// 連結成分ごとの結果を求める
		for (int i = 1; i <= cntv; i++) {
			for (int j = 0; j < E[i].size(); j++) {
				if (indeg[E[i][j]] == 0) incnt[i]++;
				if (outdeg[E[i][j]] == 0) outcnt[i]++;
			}
		}

		// 最後に答えを求める
		int c1 = 0, c2 = 0;
		for (int i = 1; i <= cntv; i++) {
			c1 += incnt[i];
			c2 += outcnt[i];
		}
		if (c1 == 1 && c2 == 1) cout << "0" << endl;
		else cout << max(c1, c2) << endl;
	}
	return 0;
}


Measured memory_bytes: 19708
import sys
import heapq
def Dj(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    vis = [-1 for i in range(n)]
    li = [(0,s)]
    dist[s]=0
    heapq.heapify(li)
    while len(li):
        d,u = heapq.heappop(li)
        if vis[u]==1:
            continue
        vis[u]=1
        for v in G[u]:
            if dist[v[1]]>dist[u] + v[0]:
                dist[v[1]] = dist[u] + v[0]
                heapq.heappush(li,(dist[u] + v[0],v[1]))
    return dist
                
    
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    S = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[2],line[1]))
    for k in Dj(G,S):
        if k ==float("inf"):print("INF")
        else:print(k)
main()

    
    



Measured memory_bytes: 93372
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    if(s.equals("SUN")){
      System.out.println(7);
    }else if(s.equals("MON")){
      System.out.println(6);
      }else if(s.equals("TUE")){
      System.out.println(5);
      }else if(s.equals("WED")){
      System.out.println(4);
      }else if(s.equals("THU")){
      System.out.println(3);
      }else if(s.equals("FRI")){
      System.out.println(2);
      }else if(s.equals("SAT")){
      System.out.println(1);
    }
      
  }
  

  
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 1 << 17;
const ll INF = ((1 << 30) - 1) * 2 + 1;
ll n,dat[2 * MAX_N - 1];

void init(int n_)
{
	n = 1;
	while(n < n_) n *= 2;
	rep(i,2 * n - 1)
	{
		dat[i] = INF;
	}
}

void update(int k, int a)
{
	k += n - 1;
	dat[k] = a;
	while(k > 0)
	{
		k = (k - 1) / 2;
		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}

ll query(int a, int b, int k, int l, int r)
{
	if (r <= a || b <= l) return INF;
	if (a <= l && r <= b) return dat[k];
	else
	{
		ll vl = query(a, b, k*2+1, l, (l+r)/2);
		ll vr = query(a, b, k*2+2, (l+r)/2, r);
		return min(vl,vr);
	}
}

int main()
{
	int N,q;
	cin >> N >> q;
	init(N);
	rep(i,q)
	{
		int c,x,y;
		cin >> c >> x >> y;
		if (c == 0)
		{
			update(x,y);
		}
		else
		{
			cout << query(x,y+1,0,0,n) << endl;
		}
	}
	return 0;
}


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

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define RREP(i, N) for (int i =(int)N-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
typedef pair<int,string> Pis;

bool pairCompare_S(const Pis& firstElof, const Pis& secondElof)
{
    return firstElof.second < secondElof.second;
}
bool pairCompare_I(const Pis& firstElof, const Pis& secondElof)
{
    return firstElof.first > secondElof.first;
}
int main(){
  int k,x;
  cin>>k>>x;
  if(k*500>=x){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int mod=(1e9)+7;
int t, n, m, k, a[300010], q, l, s;
int dp[2010];

int32_t main(){
INIT
cin>>s;
dp[0]=1;
for(int s1=3; s1<=s; s1++){
    for(int s2=3; s2<=s1; s2++){
            dp[s1]=(dp[s1]+dp[s1-s2])%mod;
    }
}
cout<<dp[s];

return 0;
}





Measured memory_bytes: 3604
from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

print(*A)
for i in range(1,N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(*A)


Measured memory_bytes: 5980
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int a,b,t;
  cin>>a>>b>>t;
  cout<<b*(t/a)<<endl;
}





Measured memory_bytes: 256
import java.util.Scanner;

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

        int N = scanner.nextInt();

        double acc = 0;

        for(int i=0; i<N; i++){
            double x = scanner.nextDouble();
            String s = scanner.next();

            if(s.equals("BTC")){
                x *= 380000.0;
            }

            acc += x;
        }

        System.out.println(acc);

    }
}


Measured memory_bytes: 22868
import static java.lang.System.in;
import static java.lang.System.out;

import java.io.*;
import java.util.*;

public class Main {
	static final double EPS = 1e-10;
	static final double INF = 1L << 31;
	static final double PI = Math.PI;

	public static Scanner sc = new Scanner(in);
	StringBuilder sb = new StringBuilder();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public void run() throws IOException {
		String input;
		String[] inputArray;
		input = br.readLine();
		inputArray = input.split(" ");

		int n = Integer.valueOf(inputArray[0]);
		int A = Integer.valueOf(inputArray[1]);
		int B = Integer.valueOf(inputArray[2]);
		int a=0, b=0;
		input = br.readLine();
		for (int i=0; i<n; i++){
			switch (input.charAt(i)){
				case 'a': {
					if (a+b<A+B){
						a++;
						sb.append("Yes\n");
					} else{
						sb.append("No\n");
					}
					break;
				}
				case 'b': {
					if (a+b<A+B && b<B){
						b++;
						sb.append("Yes\n");
					} else{
						sb.append("No\n");
					}
					break;
				}
				case 'c': {
					sb.append("No\n");
					break;
				}
			}
				
		}
		ln(sb);
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	public static void ln(Object obj) {
		out.print(obj);
	}
}


Measured memory_bytes: 16396
#include <iostream>

using namespace std;

const int limit = 50;

int N, M;
int a[limit], b[limit];

bool G[limit][limit];
bool visited[limit];


void dfs(int v){
    visited[v] = true;
    for(int v2 = 0; v2 < N; v2++){
        if(G[v][v2] == false){
            continue;
        }else if(visited[v2] == true){
            continue;
        }else{
            dfs(v2);
        }
    }
}


int main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]][b[i]] = true; G[b[i]][a[i]] = true;
    }

    int ans = 0;
    bool bridge = false;
    for(int i = 0; i < M; i++){
        G[a[i]][b[i]] = false; G[b[i]][a[i]] = false;
        for(int j = 0; j < N; j++){
            visited[j] = false;
        }

        dfs(0);

        bridge = false;
        for(int j = 0; j < N; j++){
            if(visited[j] == false){
                bridge = true;
            }
        }
        if(bridge == true){
            ans++;
        }

        G[a[i]][b[i]] = true; G[b[i]][a[i]] = true;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FOR(i, i0, n) for(int i = (i0); i < (n); i ++)
#define COUT(val) cout << (val) << "\n";
using namespace std;
using ll = long long int;

int main(void){
    string s, t;
    cin >> s >> t;
    
    int ns = s.size(), nt = t.size();
    vector<vector<int>> dp(ns+1, vector<int>(nt+1, -1));
    FOR(i, 0, ns+1) dp[i][0] = 0;
    FOR(j, 0, nt+1) dp[0][j] = 0;
    
    FOR(i, 1, ns+1) FOR(j, 1, nt+1){
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if(s[i-1] == t[j-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
    }
    
    string ans = "";
    while(dp[ns][nt] > 0){
        while(dp[ns][nt] == dp[ns-1][nt]) ns --;
        while(dp[ns][nt] == dp[ns][nt-1]) nt --;
        ans.push_back(s[ns-1]);
        ns --;
        nt --;
    }
    reverse(ans.begin(), ans.end());
    COUT(ans);
}

Measured memory_bytes: 35584
lst = map(int, input().split())
lst = sorted(lst)
a, b, c = lst

if (b - a) % 2 == 0:
    ret = (b - a)//2 + (c - b)
else:
    ret = 1 + (b + 1 - a)//2 + (c - b)
print(ret)

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

int main(){
    long long h,w,x,y;
    int midpoint = 0;
    cin >> w >> h >> x >> y;
    if((h % 2) == 0 && (w % 2) == 0 && (w / 2) == x && (h / 2) == y)midpoint = 1;
    printf("%.8lf %d\n",h * w / 2.0,midpoint);

}

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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

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

    int A, B;
    cin >> A >> B;
    if(A % 2 == 0 || B % 2 == 0) cout << "No";
    else cout << "Yes";
    cout << "\n";
    return 0;
}

Measured memory_bytes: 256