akhauriyash/Code-Regression huggingface dataset:
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        x: i32,
        a: i32,
        b: i32,
    }
    println!("{}",
        if (x-a).abs() < (x-b).abs() { "A" } else { "B" }
    );
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる
typedef complex<double> P;


struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
  L(){;}
};

struct C {
  P c;double r;
  C(const P &c,double r):c(c),r(r){}
  C(){;}
};

namespace std{//演算子の定義
  bool operator < (const P& a,const P& b) {
    return real(a)!= real(b) ? real(a) < real(b) : imag(a) < imag(b);
    //return imag(a) != imag(b) ? imag(a) < imag(b) : real(a) < real(b)
  }
  bool operator == (const P& a,const P& b) {
    return a.real()==b.real() && a.imag()==b.imag();
  }
}


double dot(P a,P b) {
  return real(conj(a)*b);
}

double cross(P a,P b) {
  return imag(conj(a)*b);
}

P projection(const L &l, const P &p) { //pの直線l上の射影の点
  double t=dot(p-l[0],l[0]-l[1])/norm(l[0]-l[1]);
  return l[0]+t*(l[0]-l[1]);
}

bool intersectSP(const L &s, const P &p) { //直線と点の交差判定
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // 三角不等式
}

double distancePP(const P &p, const P &q){ //2点間の距離
  return hypot(p.real()-q.real(), p.imag()-q.imag());
}

double distanceSP(const L &s, const P &p) {//直線と点との距離
  const P r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s[0] - p), abs(s[1] - p));
}

P inP(){
  double x,y;
//  scanf("%lf,%lf", &x, &y);
  cin >> x >> y;
  P p(x,y);
  return p;
}

L inL(){
  P p1 = inP();
  P p2 = inP();
  L l(p1,p2);
  return l;
}

C inC(){
  P p = inP();
  double r;
  cin >> r;
  C c(p,r);
  return c;
}

bool intersectCS(const C &c, const L &l){//円と線分の交差判定
    double close = distanceSP(l,c.c);
    double far = max(distancePP(l[0],c.c),distancePP(l[1],c.c));
    if(close <= c.r && far >= c.r)return true; //重なっていても良い
    //完全に交差している場合のみだと、イコールを外す
    return false;
}

signed main(void) {
    int n;
    while(cin >> n,n){
        vector<C> c(n);
        rep(i,n)c[i] = inC();
        int m;
        cin >> m;
        rep(_,m){
            L l = inL();
            bool ans = false;
            rep(i,n)if(intersectCS(c[i],l))ans = true;
            if(ans){
                cout << "Safe" << endl;
            }else{
                cout << "Danger" << endl;
            }
        }
    }
}



Measured memory_bytes: 3188
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll Power[20];
ll dfs(ll l , ll r , ll d) {
    if(l >= r) {
        if(d == 0) return l == r ? 10 : 1;
        return 0;
    }
    if(d % 10 == 0) {
        if(l != 1) return 10 * dfs(l + 1 , r - 1 , d / 10);
        return 9 * dfs(l + 1 , r - 1 , d / 10);
    }
    ll differ = d % 10 - 10;
    ll next = d - differ + differ * Power[r - l];
    if(l == 1) return (9 + differ) * dfs(l + 1 , r - 1 , abs(next) / 10);
    return (10 + differ) * dfs(l + 1 , r - 1 , abs(next) / 10);
}
int main() {
    ll d;
    cin >> d;
    Power[0] = 1;
    for(int i = 1 ; i <= 18 ; i++) {
        Power[i] = Power[i - 1] * 10;
    }
    ll ans = 0;
    for(int i = 2 ; i <= 18 ; i++) {
        ans += dfs(1 , i , d);
    }
    cout << ans << endl;
    return 0;
}

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

const int MOD = 100000;

int main() {
    int N, M, S;
    while(cin >> N >> M >> S, N | M | S) {
        vector<vector<int>> dp(N * N + 1, vector<int>(S + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= M; ++i) for(int j = N * N; j >= 1; --j) for(int k = i; k <= S; ++k)
            dp[j][k] = (dp[j][k] + dp[j - 1][k - i]) % MOD;
        cout << dp[N * N][S] << endl;
    }
}

Measured memory_bytes: 1784
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int frower[6][2] = {{2,380},{3,550},{5,850},{10,1520},{12,1870},{15,2244}};
  int dp[51] = {0};
  for(int i=1; i<51; i++){dp[i] = 100000;}
  for(int i=0; i<51; i++){
    for(int j=0; j<7; j++){
      if(frower[j][0]<=i){
	dp[i] = min(dp[i],dp[i-frower[j][0]]+frower[j][1]);
      }
    }
  }
  int n;
  while(cin>>n,n){
    cout <<dp[n/100]<<endl;
  }
  return 0;
}

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

int main() {
  string sa, sb, sc;
  cin >> sa >> sb >> sc;

  char turn = 'a';
  int alen = sa.length();
  int ai = 0;
  int blen = sb.length();
  int bi = 0;
  int clen = sc.length();
  int ci = 0;
  while (true) {
    if (turn == 'a') {
      if (ai == alen) {
        cout << "A" << endl;
        break;
      }
      turn = sa[ai];
      ai++;
    } else if (turn == 'b') {
      if (bi == blen) {
        cout << "B" << endl;
        break;
      }
      turn = sb[bi];
      bi++;
    } else if (turn == 'c') {
      if (ci == clen) {
        cout << "C" << endl;
        break;
      }
      turn = sc[ci];
      ci++;
    }
  }
  return 0;
}

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

int main() {
  string S;
  cin >> S;
  string S2;
  copy(S.begin(), S.end(), back_inserter(S2));
  int L = S.size();
  reverse(S2.begin(), S2.end());
//  cout << S << endl;
//  cout << S2 << endl;
  if (S != S2) {
    cout << "No" << endl;
    return 0;
  }

  S2 = S.substr(0, L/2);
  string S3;
  copy(S2.begin(), S2.end(), back_inserter(S3));
  reverse(begin(S3), end(S3));
//  cout << S2 << endl;
//  cout << S3 << endl;
  if (S2 != S3) {
    cout << "No" << endl;
    return 0;
  }

  S2 = S.substr((L+3)/2 - 1, L - 1);
  string S4;
  copy(S2.begin(), S2.end(), back_inserter(S4));
  reverse(S4.begin(), S4.end());
//  cout << S2 << endl;
//  cout << S4 << endl;
  if (S2 == S4) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef long double ld;
#define endl "\n"
const int MAX= 100005 ;
const long long mod = 1e9+7;
int n;
vector<int> adj[MAX+1];
int dp[MAX+1][2];
void dfs(int node,int parent)
{   
    dp[node][0]=1;
    dp[node][1]=1;
    for(auto child: adj[node])
    {
        if(child != parent)
        {   
            //cout<<child<<" "<<parent<<" "<<node<<endl;
            dfs(child,node);
            dp[node][0] *= (dp[child][0]+ dp[child][1]);  
            dp[node][1] *= dp[child][0];
            dp[node][0]%=mod;
            dp[node][1]%=mod;
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int i,j,x,y;
    cin>>n;
    for(i=0;i<(n-1);i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    memset(dp,0,sizeof(dp));
    dfs(1,-1);
    cout<<(dp[1][0]+dp[1][1])%mod<<endl;
   /* for(i=1;i<=n;i++)
    {
        cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
    }*/
}

Measured memory_bytes: 14208
n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]
p = [k for i in range(n)]
def judge(x):
    if p[x] - q <= 0:
        return 'No'
    else:
        return 'Yes'
for i in range(q):
    p[a[i] - 1] += 1
b = [judge(i) for i in range(n)]
print('\n'.join(b))

Measured memory_bytes: 11692
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
#define MAX 1005
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
ull A[MAX], B[MAX];

int main() {
  int n,i;
  ull h,w;
  cin >> n >> h >> w;
  for(i=0;i<n;i++) {
    cin >> A[i] >> B[i];
  }
  int count=0;
  for(i=0;i<n;i++) {
    if((A[i]>=h&&B[i]>=w) ) {
      count++;
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        string[] cin = Console.ReadLine().Split();
        int n = int.Parse(cin[0]);
        int m = int.Parse(cin[1]);

        var list = new List<KeyValuePair<long, int>>();
        for (int i = 0; i < n; i++)
        {
            cin = Console.ReadLine().Split();
            list.Add(new KeyValuePair<long, int>(long.Parse(cin[0]), int.Parse(cin[1])));
        }

        var c = new Comparison<KeyValuePair<long, int>>(Compare);
        list.Sort(c);

        long ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += Math.Min(m, list[i].Value) * list[i].Key;
            m -= Math.Min(m, list[i].Value);
            if (m == 0) break;
        }

        Console.WriteLine(ans);
    }

    static int Compare(KeyValuePair<long, int> a, KeyValuePair<long, int> b)
    {
        if (a.Key > b.Key) return 1;
        else if (a.Key < b.Key) return -1;
        else return 0;
    }
}

Measured memory_bytes: 19144
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=n-1;i > m;i--)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl;
#define Vecpr vector<pair<lli,lli>>
#define mod 1000000007;
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli A,B,N,M;
  cin >> N;
  vector<int>DP(N,INF),Ct(N,0);
  rep(i,0,N)cin >> Ct[i];
  DP[0]=0;
  rep(i,0,N){
    chmin(DP[i+2],DP[i]+abs(Ct[i]-Ct[i+2]));
    chmin(DP[i+1],DP[i]+abs(Ct[i]-Ct[i+1]));
  }
  Out(DP[N-1]);
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  ll n, ans = 0;
  cin >> n;
  string s[n];
  ll ra = 0, lb = 0, ba = 0;
  rep(i, n) {
    cin >> s[i];
    rep(j, s[i].size() - 2) if (s[i][j] == 'A' && s[i][j + 1] == 'B') ans++;
    if (s[i][0] == 'B' && s[i][s[i].size() - 1] == 'A')
      ba++;
    else if (s[i][0] == 'B')
      lb++;
    else if (s[i][s[i].size() - 1] == 'A')
      ra++;
  }
  // cout << ba << " " << lb << " " << ra << " " << ans << endl;
  // ll mx = max(lb, ra);
  // ll mn = min(lb, ra);
  // ans = ans + mn + min(mx - mn, ba) + max(ba - (mx - mn), 0ll) / 2;
  if (ba == 0)
    ans += min(lb, ra);
  else {
    if (lb + ra > 0)
      ans += ba + min(lb, ra);
    else
      ans += ba - 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long{} long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll N = 1e6;
const ll inf = 1e9;
const double pi = acos(-1);
ll fact[N];
ll power(ll a, ll n){
   if(a == 1)return 1;
   if(n == 0)return 1;
   if(n == 1)return a%MOD;
   ll p = power(a,n/2);
   p*=p;
   p%=MOD;
   if(n & 1){
      p*=a;
      p%=MOD;
   }
   return p;
}
void precalculate_fact(){
   fact[0] = 1;
   loop(i,1,N){
      fact[i] = (fact[i-1] * i)%MOD;
   }
}
ll ncr(ll n, ll r){
   if(n > r)return 0;
   ll ans = fact[n];
   ans*=power(fact[r],MOD-2);
   ans%=MOD;
   ans*=power(fact[n-r],MOD-2);
   return ans%MOD;
}
int main(){
 	string a;
  cin >> a;
  V<char> ans;
  for(char i : a){
  	if(i == 'B'){
    	if(ans.size())ans.pop_back();
    }else{
    	ans.pb(i);
    }
  }
  for(char i: ans)cout << i;
  return 0;
}

Measured memory_bytes: 256
/*
???????????´??°a, b, c?????????????????????????????? a < b < c????????¶????????????????????°"Yes"??????
???????????????????????°"No"???????????????????????°?????????????????????????????????
*/

#include <iostream>

int main() {
	int num1, num2, num3;
	std::cin >> num1 >> num2 >> num3;

	if (num1 < num2 && num2 < num3 && num1 < num3) {
		std::cout << "Yes" << std::endl;
	}
	else
	{
		std::cout << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 3088
'use strict'

function main(input) {
  input = input.split('\n') //.map(v => ~~v)
  const n = ~~input[0]
  const L = input[1].split(' ').map(v => ~~v)
  L.sort((a, b) => b - a)

  const L0 = L.shift()
  const Lsum = L.reduce((a, b) => a + b)

  let ans = (L0 < Lsum) ? 'Yes' : 'No'
  console.log(ans)


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


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

typedef long long ll;

const int N = 3e5+1;
ll bp = 998244353, fact[N];

void init(){
	fact[0] = 1;
	for(ll i = 1; i < N; i++)
		fact[i] = (fact[i-1] * i) % bp;
}

ll fexp(ll b, ll p){
	if(p <= 0)
		return 1;
	ll ans = 1;
	while(p){
		if(p%2)
			ans = (ans*b)%bp;
		p >>= 1;
		b = (b*b)%bp;
	}
	return ans;
}

ll ncr(ll n, ll r){
	return (fact[n] * ((fexp(fact[r], bp-2)*fexp(fact[n-r], bp-2))%bp) )%bp;
}

int main(){
	init();
	ll n, a, b, k;
	cin >> n >> a >> b >> k;
	ll ans = 0;
	for(ll i = 0; i <= n && a*i <= k; i++)
		if((k - a*i)%b == 0 && (k - a*i)/b <= n)
			ans = (ans + (ncr(n,i)*ncr(n, (k-a*i)/b))%bp) %bp;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int A,B,C,n;
int l[9];
int dfs(int id,int a,int b,int c)
{
	int r1,r2,r3,r4;
	if(id==n)
	{
		if(a==0||b==0||c==0)
			return 8001;
		return abs(a-A)+abs(b-B)+abs(c-C);
	}
	r1=dfs(id+1,a+l[id+1],b,c)+10;
	r2=dfs(id+1,a,b+l[id+1],c)+10;
	r3=dfs(id+1,a,b,c+l[id+1])+10;
	r4=dfs(id+1,a,b,c);
	return min(r1,min(r2,min(r3,r4)));
}
int main()
{
	int i;
	scanf("%d %d %d %d",&n,&A,&B,&C);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&l[i]);
	}
	printf("%d",dfs(0,0,0,0)-30);
	return 0;
}

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

using namespace std;

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

    int flg = 0;    
    int cnt=0;
    int l = S.size();
    S.erase(l-1);
    l = S.size();
    while(l >= 2 || flg == 0){
        int l = S.size();
        if(l % 2 == 1){
            S.erase(l-1);
            l -= 1;
        }
        string T;
        int half = l/2;
        cnt = 0;
        for(int i=half; i<l; i++) T += S[i];
        for(int i=0; i<half; i++){
            ++cnt;
            if(S[i] != T[i]) break;
            if( i == half-1 && S[i] == T[i]){
                flg = 1;
                break;
            }
        }
        if(flg == 1) break;
        S.erase(l-1);
        l -= 1;
    }

    cout << cnt*2 << endl;

    return 0;
}

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

using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (int)n; i++)

int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll c = a+b;
  ll ans = a * (n/c);
  ans += min(n%c, a);
  cout << ans << endl;
}


Measured memory_bytes: 3604
X, N = map(int, input().split())

if N > 0:
    p = set(map(int, input().split()))
else:
    print(X)
    exit()

if X not in p:
    print(X)
    exit()

i = 0

while True:
    if X-i not in p:
        print(X-i)
        exit()
    elif X+i not in p:
        print(X+i)
        exit()
    i += 1



Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define bitsz(x) int(__builtin_popcount(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
#define mod 1000000007
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};


using Graph = vector<vector<int>>;

int ans = 0;
int tmp = 0;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    tmp++;
    seen[v] = true;
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v); // 再帰的に探索
    }
}
 
int main() {
    int n,m; cin >> n >> m;
    Graph G(n);
    int u,v;
    rep(i,m) {
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int count = 0;
    seen.assign(n, false);
    for (int v = 0; v < n; ++v) {
        tmp = 0;
        if (seen[v]) continue; // v が探索済みだったらスルー
        dfs(G, v); // v が未探索なら v を始点とした DFS を行う
        chmax(ans,tmp);
    }
    cout << ans << endl;
}


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

int main(){
	int N;
	cin >> N;
	vector<int> p(N);
	for(int i=0; i<N; ++i){
		cin >> p[i];
	}
	int m = *max_element(p.begin(),p.end());

	int sum = accumulate(p.begin(), p.end(), 0);

	cout << sum - m/2 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7, N = 100;
int dp[N][4][4];
inline void add(int &x, int add){
    x += add;
    if(x >= MOD)
        x -= MOD;
}
int main(){
    int n;
    string hint1,hint2;
    cin >> n >> hint1 >> hint2;
    dp[0][0][0] = 1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= 3; ++j)
            for(int k = 0; k <= 3; ++k)
                for(int l = 1; l <= 3; ++l)
                    for(int m = 1; m <= 3; ++m)
                        if(j != l && k != m)
                            if(l == m && hint1[i] == hint2[i]){
                                add(dp[i+1][l][m],dp[i][j][k]);
                            }
                            else if(l != m && hint1[i] != hint2[i]){
                                add(dp[i+2][l][m],dp[i][j][k]);
                            }
    int ans = 0;
    for(int i = 0; i < 4; ++i)
        for(int j = 0; j < 4; ++j)
            add(ans,dp[n][i][j]);
    cout << ans << '\n';
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const ll INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){
    int N;
    cin >> N;
    vector<ll> a(N), b(N);
    REP(i,N){cin >> a[i]; b[i] = a[i];}
    vector<ll> s(N);
    s[0] = a[0];
    
    ll ans = 0;
    if(a[0] <= 0){
        ans = -a[0]+1;
        s[0] = 1;
    }
    
    REP(i,N-1){
        if((s[i]+a[i+1])*s[i]>=0){
            ans += abs(s[i]+a[i+1])+1;
            a[i+1] += -(s[i]+a[i+1]);
            if(s[i] > 0) a[i+1]--;
            else a[i+1]++;
        }
        s[i+1] = s[i]+a[i+1];
    }

    ll ans1 = 0;
    s[0] = b[0];
    
    if(a[0] >= 0){
        ans1 = b[0]+1;
        s[0] = -1;
    }

    REP(i,N-1){
        if((s[i]+b[i+1])*s[i]>=0){
            ans1 += abs(s[i]+b[i+1])+1;
            b[i+1] += -(s[i]+b[i+1]);
            if(s[i] > 0) b[i+1]--;
            else b[i+1]++;
        }
        s[i+1] = s[i]+b[i+1];
    }
    cout << min(ans, ans1) << endl;
    return 0;
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef double ld;
 
template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=20;
map<pii,ll> f[N][N];
ll ans=1e18;
int a[N],n;

void cmin(ll &x,ll y){
	if(y<x)x=y;
}

ll solve(int l,int r,int x,int y){
	if(l+1==r)return 0;
	if(l+2==r)return (ll)a[l+1]*(x+y);
	if(f[l][r].count(mp(x,y)))
		return f[l][r][mp(x,y)];
	ll res=1e18;
	rep(k,l+1,r-1)
		cmin(res,solve(l,k,x,x+y)+solve(k,r,x+y,y)+(ll)a[k]*(x+y));
	f[l][r][mp(x,y)]=res;
	return res;
}

int main(){
	read(n);
	rep(i,1,n)read(a[i]);
	cout<<a[1]+a[n]+solve(1,n,1,1)<<endl;
	return 0;
}

Measured memory_bytes: 8704
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

#define fst first
#define snd second

typedef long long llint;
typedef pair<int, int> pii;

const int B = 27397, MOD = 1e9 + 7;
const int B1 = 33941, MOD1 = 1e9 + 9;

const int MAXN = 1e5+10;

int m, n;
int fact[MAXN];

int add(int a, int b) {
  a += b;
  while (a < 0) a += MOD;
  return a % MOD;
}

int mul(int a, int b) {
  return (llint) a*b % MOD;
}

void init() {
  fact[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    fact[i] = mul(i, fact[i - 1]);
}

int main(void) {
  init();
  scanf("%d%d", &m, &n);
  if (n > m) swap(m, n);

  if (abs(n - m) > 1) {
    printf("0\n");
    return 0;
  }

  if (m == n) {
    printf("%d\n", mul(2, mul(fact[m], fact[n])));
  } else {
    printf("%d\n", mul(fact[m], fact[n]));
  }
  return 0;
}



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

using namespace std;

int main(void){
	int n,i,s,b,w,ans;
	while(true){
		scanf("%d",&n);
		if(n==0){break;}
		ans = 0;
		b = -1;
		w = 1001;
		for(i=0; i<n; i++){
			 cin >> s;
			 b = max(s,b);
			 w = min(s,w);
			 ans += s;
		}
		ans -= b;
		ans -= w;
		cout << (ans/(n-2)) << endl;
	}
	return 0;
}

Measured memory_bytes: 3112
#include <iostream>
using namespace std;
int main(void){
    int k;
    cin >> k;
    int line[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << line[k-1] << endl;
}


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

int main(){
	long long a, b, x;
	cin >> a >> b >> x;
	if(a % x != 0){
		a += (x - a % x);
	}
	if(b % x != 0){
		b -= b % x;
	}
	// cout << a << " " << b << endl;
	cout << max(0LL, b / x - a / x + 1) << endl;
	return 0;
}

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

int main(){
  int a,b;

  scanf("%d %d",&a,&b);
  // hairetu syokika sitai
  std::vector<int> v(b);
  for(int i =0;i<b;i++){
    std::cin >> v[i];
  }

  int sum = std::accumulate(v.begin(),v.end(),0);

  // printf("%d %d\n",a,b);  

  int nokori = a - sum;
  if (nokori < 0){
    printf("-1");
  }
  else{
    printf("%d",nokori);
  }

  return 0;
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
// #define mp make_pair
//#define endl '\n'

int main() {
  int n;
  cin >> n;
  vi a(n + 1);
  rep1 (i, n) {
    cin >> a[i];
  }

  vi b(n + 1);
  vi sum(n + 1);
  vii yaku(n + 1);

  rep1 (i, n) {
    for (int j = 1; j * i <= n; j++) {
      yaku[i * j].push_back(i);
    }
  }

  rrep1 (i, n) {
    if (a[i] != sum[i] % 2) {
      b[i] = 1;
      rep (j, yaku[i].size()) {
        sum[yaku[i][j]]++;
      }
    }
  }

  int m = 0;
  rep1 (i, n) {
    m += b[i];
  }
  cout << m << endl;
  rep1 (i, n) {
    if (b[i]) {
      cout << i << " ";
    }
  }
  cout << endl;
}


Measured memory_bytes: 24576
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int a,b;
	cin>>a>>b;
	cout<<1LL*(a-1)*(b-1);
    return 0;
}


Measured memory_bytes: 256
import bisect
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_T = [0]
B_T = [0]
c = 0
for i in range(N):
    c += A[i]
    A_T.append(c)
c = 0
for i in range(M):
    c += B[i]
    B_T.append(c)

ans = 0
for i in range(N+1):
    if K - A_T[i] >= 0:
        k = bisect.bisect_right(B_T, K-A_T[i])
        ans = max(ans, k+i-1)
print(ans)

Measured memory_bytes: 126892
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#include <numeric>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[8]={ 0, 1, 0,-1, 1, 1,-1,-1}; // x軸方向への変位
ll dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1}; // y軸方向への変位

int main(void) {
    ll x;
    cin >> x;
    vector<p> a, b;
    a.push_back(p(0,0)); b.push_back(p(0,0));
    for(ll i = 1; i <= 100000; i++){
        ll c = (ll)(pow(i, 5));
        a.push_back(p(i, c)); a.push_back(p(-i, -c));
        b.push_back(p(-i, -c)); b.push_back(p(i, c));
      //  cout << c << endl;
        if(pow(i+1, 5)>1e+18) break;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    bool check = false;
   // cout << a.size() << " " << b.size() << endl;
    for(ll i = 0; i < a.size(); i++){
      //  cout << a[i].second << endl;
        for(ll j = 0; j < b.size(); j++){
            if(a[i].second-b[j].second==x){
                cout << a[i].first << " " << b[j].first << endl;
                check = true;
                break;
            }
        }
        if(check==true) break;
    }
    //cout << a.size() << endl;
    return 0;
}


Measured memory_bytes: 4412
import itertools
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

X = []
Y = []
Z = []
for _ in range(N):
    x, y, z = map(int, input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)

X = np.array(X)
Y = np.array(Y)
Z = np.array(Z)

ans = 0
for xsign, ysign, zsign in itertools.product([1, -1], repeat=3):
    indexes = np.argsort(X * xsign + Y * ysign + Z * zsign)[::-1][:M]
    ans = max(ans, abs(sum(X[indexes])) + abs(sum(Y[indexes])) + abs(sum(Z[indexes])))

print(ans)


Measured memory_bytes: 12512
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    if (n % 2 == 0)
    {
        for (int i = n - 1; i >= 0; i -= 2)
            cout << a[i] << " ";
        for (int i = 0; i < n; i += 2)
            cout << a[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = n - 1; i >= 0; i -= 2)
            cout << a[i] << " ";
        for (int i = 1; i < n; i += 2)
            cout << a[i] << " ";
        cout << endl;
    }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using P = pair<int,int>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}




int main()
{
    int N,K;
    string S;
    cin >> N >> K >> S;

    int ans = 0;
    rep(i,N){
        if(i == 0 && S[i] == 'R' && S[i + 1] == 'R') ans++;
        else if(i == N - 1 && S[i] == 'L' && S[i - 1] == 'L') ans++;
        else{
            if(S[i] == 'R' && S[i + 1] == 'R') ans++;
            else if(S[i] == 'L' && S[i - 1] == 'L') ans++;
        }
    }
    ans += K*2;
    if(ans > N - 1) ans = N - 1;

    cout << ans << endl;

    return 0;
}
//Ctrl+Shift+Bでコンパイルと実行を行ってデバッグすること

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

int main() {
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	a *= 100; b *= 100;


	pair<int, int> ans;
	ans.first = a, ans.second = 0;
	for (int wa = 0; wa < 39; wa++) {
		for (int wb = 0; wb < 39; wb++) {
			int water = wa * a + wb * b;
			if (water >= f) break;
			
			int sugar = 0;
			for (int sc = 0; sc < 1509; sc++) {
				for (int sd = 0; sd < 1509; sd++) {
					if (sc * c + sd * d > f - water) break;
					if ((sc * c + sd * d) * 100 > e * water) break;
					sugar = max(sugar, sc * c + sd * d);
				}
			}

			if (ans.second * (water + sugar) < sugar * ans.first) {
				ans.first = water + sugar; ans.second = sugar;
			}
		}
	}

	cout << ans.first << " " << ans.second << endl;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();
        if(k*500>=x){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

using namespace std;
typedef long long ll;

int main(){
  int a,b,k;
  cin >> a >> b;
  if((a+b)%2==0) {
    cout << (a+b)/2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define MOD 1000000007

int main()
{

    set<ll> s;
    ll n;
    cin >> n;
    while(n--)
    {

        ll x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size();
}


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

using namespace std;

const int N = 100000;

int vr[N];
int dp[N];
vector<int> a;
vector<int> topo;
vector<int> vec[N];
int main()
{
    int n,m,u,v;
    cin>>n>>m;
    for(int i=0 ; i<m; i++)
    {
        cin>>u>>v;
        v--;
        u--;
        vec[u].push_back(v);
        vr[v]++;
    }
    for (int i=0; i<n; i++)
    {
        if(vr[i]==0)
        {
            a.push_back(i);
        }
    }
    while( a.size() )
    {
        int x = a.back();
        a.pop_back();
        topo.push_back(x);
        for(int y:vec[x])
        {
            dp[y]=max(dp[y],dp[x]+1);
            vr[y]--;
            if(vr[y]==0)
            {
                a.push_back(y);
            }
        }
    }
    int mx=0;
    for(int i=0; i<N; i++)
    {
        mx=max(mx,dp[i]);
    }
cout<<mx;
}


Measured memory_bytes: 7164
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head


const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
const int N = 1e3+10;
int n,m,d[N][N],vis[N][N];
char s[N][N];
queue<pii> q;

int main() {
	scanf("%d%d", &n, &m);
	REP(i,1,n) { 
		scanf("%s",s[i]+1);
		REP(j,1,m) if (s[i][j]=='#') { 
			vis[i][j] = 1;
			q.push(pii(i,j));
		}
	}
	int ans = 0;
	while (q.size()) {
		pii u(q.front()); q.pop();
		ans = d[u.x][u.y];
		REP(k,0,3) {
			int x=u.x+dx[k],y=u.y+dy[k];
			if (1<=x&&x<=n&&1<=y&&y<=m&&!vis[x][y]) {
				q.push(pii(x,y));
				vis[x][y] = 1;
				d[x][y] = d[u.x][u.y]+1;
			}
		}
	}
	printf("%d\n", ans);
}









Measured memory_bytes: 14608
#include <stdio.h>
int main(){
    int i, j, d, k;
    int n, m, l;
    int A[100][100];
    int B[100][100];
    long C[100][100];
    
    scanf("%d%d%d",&n, &m, &l);
    
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            scanf("%d", &d);
            A[i][j] = d;
        }
    }    

    for(i = 0; i < m; i++){
        for(j = 0; j < l; j++){
            scanf("%d", &d);
            B[i][j] = d;
        }
    }
    
    for(i = 0;i < n; i++){
        for(j = 0; j < l; j++){
            for(k = 0; k < m; k ++){
                C[i][j] += (A[i][k]*B[k][j]);
            }
        }
    }

   for(i = 0;i < n; i++){
        for(j = 0; j < l; j++){
            printf("%ld", C[i][j]);
            if(j < (l-1)){
                printf(" ");
            }else{
                printf("\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 760
import java.util.*;
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int AA =0;
    int BB =0;

    int A = sc.nextInt();
    int B = sc.nextInt();

    int  max = Math.max(A,B);

    for(int k = 0 ;k<max;k++){
        AA = Math.abs(A-k);
        BB = Math.abs(B-k);

        if(AA==BB){
          System.out.println(k);
          System.exit(0);
        }
    }
    System.out.println("IMPOSSIBLE");
  }
}

Measured memory_bytes: 23124
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 998244353
N,M,K = map(int,input().split())

max = N + M + K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)


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

int main() {
  int N, K, a;
  cin >> N >> K;
  a = 1;

  for (int i = 0; i < N; i++) {
    if (a * 2 <= a + K) {
      a *= 2;
    }
    else {
      a += K;
    }
  }

  cout << a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define eps 1e-9
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

string s;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	for(int i = 1; i < s.size(); i++){
		if(s[i-1] == s[i]){
			cout << i << " " << i+1 << endl;
			return 0;
		}
	}
	for(int i = 0; i+2 < s.size(); i++){
		string t = s.substr(i, 3);
		sort(t.begin(), t.end());
		if(t[0] == t[1] || t[1] == t[2]){
			cout << i+1 << " " << i+3 << endl;
			return 0;
		}
	}
	cout << -1 << " " << -1 << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
string s;
int n, dp[305][305][305];
int go(int l, int r, int k) {
	if (dp[l][r][k] != -1) return dp[l][r][k];
	if (l == r) {
		return dp[l][r][k] = 1;
	}
	if (l + 1 == r) {
		if (s[l] == s[r] || k) {
			return dp[l][r][k] = 2;
		} else {
			return dp[l][r][k] = 1;
		}
	}
	dp[l][r][k] = max(go(l + 1, r, k), go(l, r - 1, k));
	if (s[l] == s[r]) {
		dp[l][r][k] = max(dp[l][r][k], go(l + 1, r - 1, k) + 2);
	} else if (k) {
		dp[l][r][k] = max(dp[l][r][k], go(l + 1, r - 1, k - 1) + 2);
	}
	return dp[l][r][k];
}
int main() {
	int k;
	cin >> s >> k;
	n = s.size();
	memset(dp, -1, sizeof(dp));
	cout << go(0, n - 1, k) << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N, M, K; cin >> N >> M >> K;

	bool ok = false;
	REP(i,N+1){
		REP(j,M+1){
			if((j*N + i*M - 2*i*j) == K) ok = true;
		}
	}

	if(ok) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;

}


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

#define mod 1000000007
using ll = long long;

int main(){

  int n,k;
  cin >> n >> k;

  if(n==k){
    ll ans = 1;
    ll num;
    for(int i=0;i<n;i++){
      cin >> num;
      ans=ans*num%mod;
    }
    cout << (ans+mod)%mod;
    return 0;
  }

  priority_queue<ll> pos;
  priority_queue<ll> neg;
  ll num;
  for(int i=0;i<n;i++){
    cin >> num;
    if(num>=0){
      pos.push(num);
    }else{
      neg.push(-num);
    }
  }


  if(k%2==1 && pos.empty()){
    ll ans=1;
    ll num;
    for(int i=0;i<n;i++){
      num=-neg.top();
      neg.pop();
      if(i>=n-k){
        num=num%mod;
        ans=ans*num%mod;
      }
    }
    cout << (ans+mod)%mod << endl;
    return 0;
  }


  ll ans=1;
  ll posnum=1;
  ll negnum=1;
  ll count=0;
  priority_queue<ll> que;
  if(k%2==1){
    ans=pos.top()%mod;
    pos.pop();
    count++;
  }

  while(pos.size()>=2){
    posnum=pos.top();
    pos.pop();
    posnum=posnum*pos.top();
    pos.pop();
    que.push(posnum);
  }

  while(neg.size()>=2){
    negnum=neg.top();
    neg.pop();
    negnum=negnum*neg.top();
    neg.pop();
    que.push(negnum);
  }

  ll s;
  while(1){
    if(count==k){
      cout << (ans+mod)%mod << endl;
      return 0;
    }
    s=que.top()%mod;
    que.pop();
    ans=ans*s%mod;
    count+=2;
  }

}


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

int main(){
    int n,p;
    int sum = 0;
    int max = 0;
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> p;
        if(p>max){
            max = p;
        }
        sum += p;
    }
    sum -= max/2;

    cout << sum <<endl; 
}

Measured memory_bytes: 256
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			long n = sc.nextLong();
			long a = sc.nextLong();
			long b = sc.nextLong();
			
			
			if(a>b||(n==1&&a!=b)) {
				System.out.println(0);
				return;
			}
			if(a==b) {
				System.out.println(1);
				return;
			}
			
			System.out.println((n-2)*(b-a)+1);
			
	    }
				
	}


Measured memory_bytes: 23892
#include<bits/stdc++.h>
#define PI 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
using namespace std;
const int inf=0x3f3f3f3f;
const long long inf2=(1<<62)-1;
const double eps=1e-6;
int dist(int x,int y,int x2,int y2){
	return (abs)(x-x2)*(y-y2);
}
int main(){
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	int x=x2-x1,y=y2-y1;
	cout<<x1+x-y<<" "<<y1+y+x<<" "<<x1-y<<" "<<y1+x<<endl;
	return 0;
}


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

using ll = long long int;

ll lcm(ll a,ll b){
    if(b == 0) return a;
    return lcm(b,a%b);
}

int arr[100010] = {};

int main(void){
    
    int n,k;
    cin >> n >> k;
    
    bool f = false;
    
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        if(k <= arr[i]) f = true;
    }
    
    int res = arr[0];
    for(int i = 1; i < n; i++){
        res = lcm(res,arr[i]);
    }
    
    if(k%res == 0 && f ){
        cout << "POSSIBLE" << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
    
    
    
    
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 50000;
const int INF = 1e8;
const int M = 20;

int dp[M+1][N+1];
unsigned int cnt;
vector<int> v;

int rec(int m,int n){
    if(dp[m][n] != -1){
        return dp[m][n];
    }

    if(!n){
        return 0;
    }

    if(!m){
        return INF;
    }

    if(v[m-1] > n){
        return dp[m][n] = rec(m-1,n);
    }else{
        return dp[m][n] = min(rec(m-1,n),rec(m,n-v[m-1])+1);
    }
}

/*int main(){
    int n,m;
    cin >> n >> m;

    v.resize(m);

    for(auto &t: v){
        cin >> t;
    }

    for(int i=0;i<=M;i++){
        for(int j=0;j<=N;j++){
            dp[i][j]=(j==0?0:INF);
        }
    }

    for(int i=0; i<m; i++){
        for(int j=0; j<=n; j++){
            if(j < v[i]){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = min(dp[i][j],dp[i+1][j-v[i]]+1);
            }
        }
    }

    cout << dp[m][n] << endl;
}*/

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

    v.resize(m);
    for(auto &t: v){
        cin >> t;
    }

    memset(dp,-1,sizeof(dp));

    cout << rec(m,n) << endl;
}

Measured memory_bytes: 5416