akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

long long inf=1000000007;

int main(){
	long long h,w,k;
	cin>>h>>w>>k;
	vector<string> cake(h);
	vector<vector<long long>> grid(h,vector<long long>(w,0));

	for(int i=0;i<h;i++){
		cin>>cake.at(i);
	}

	vector<pair<long long,long long>> tate;
	long long pre=0;
	bool yet=true;

	for(int i=0;i<h;i++){
		bool flag=false;
		for(auto a:cake.at(i)){
			if(a=='#'){
				flag=true;
				break;
			}
		}

		if(flag){
			if(yet){
				yet=false;
				continue;
			}else{
				tate.push_back(make_pair(pre,i-1));
				pre=i;
			}
		}
	}
	tate.push_back(make_pair(pre,h-1));

	long long num=0;

	for(auto y:tate){
		yet=true;
		num++;
		for(int j=0;j<w;j++){
			bool flag=false;
			for(int i=y.first;i<=y.second;i++){
				if(cake.at(i).at(j)=='#'){
					flag=true;
					continue;
				}
			}

			if(flag){
				if(yet){
					yet=false;
				}else{
					num++;
				}
			}

			for(int i=y.first;i<=y.second;i++){
				grid.at(i).at(j)=num;
			}
		}
	}

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<grid.at(i).at(j);
			if(j<w-1) cout<<" ";
			else cout<<endl;
		}
	}

	return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

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

	int cnt = count(S.begin(), S.end(), 'o');
	cout << 700 + 100 * cnt << endl;

	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>){
    val N = nextInt()
    val S = next()
    var c = '?'
    var ans = 0
    S.forEach {
        if (it != c) {
            ans++
            c = it
        }
    }
    println(ans)
}
fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta

Measured memory_bytes: 34488
# define _CRT_SECURE_NO_WARNINGS 1
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <map>
# include <stack>
using namespace std;
//# define M_PI 3.141592
# define INF ((int)(1<<30))
# define FOR(i,n) for(int i=0;i<(int)n;i++)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define toRad 2.0*M_PI/360.0
# define inin(x) int x;cin>>x;
# define all(x) x.begin(),x.end()
# define debug(x) cout<<#x<<" :"<<x<<endl;
# define rep(i,n) for(int i=0;i<(int)n;i++)
# define EPS 1e-12
# define CHECK(i,a) FOR(i,a.size())cout<<#a<<"["<<i<<"] : "<<a[i]<<endl; 
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int dx[4] = { 0,-1,1,0 }, dy[4] = { 1,0,0,-1 };

vector< pair<pii, string> > a;
int main()
{
	int n, q;
	while (cin >> n >> q&&n)
	{
		a.clear();
		FOR(i, n)
		{
			string s;
			int x, y;
			cin >> s >> x >> y;
			a.push_back(make_pair(pii(y - x, y), s));
		}
		FOR(i, q)
		{
			int x; cin >> x;
			bool ok = false;
			FOR(j, n)
			{
				if (a[j].first.first + 1 <= x&&x <= a[j].first.second)
				{
					cout << a[j].second << " " << x - a[j].first.first << endl;
					ok = true;
					break;
				}
			}
			if (!ok)
			{
				cout << "Unknown" << endl;
			}
		}
	}

}

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

using namespace std;

int n,x[210000],i,center[2];
vector<int> v;

int main(void){
    cin >> n;

    for (i=0 ; i<n ; i++) {
        cin >>  x[i];
        v.push_back(x[i]);
    }
    sort(v.begin(), v.end());

    center[0] = v[n/2-1];
    center[1] = v[n/2];

    for (i=0 ; i<n ; i++) {
        if (x[i] < center[1] ) cout << center[1] << "\n";
        else cout << center[0] << "\n";
    }
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  vector<int> ans(2);
  
  for(int i;i < N;i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin() ,vec.end());
  reverse(vec.begin() ,vec.end());
  
  for(int i;i < N;i++){
    ans.at(i % 2) += vec.at(i);
  }
  
  cout << ans.at(0) - ans.at(1) << endl;
}

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

constexpr bool isPrime(int n){
    if (n<2) return false;
    if (n==2) return true;
    if (n%2==0) return false;
    for (int i=3;i<=sqrt(n);i+=2) if (n%i==0) return false;
    return true;
}

int main(){
    int nb; cin>>nb;
    std::vector<int> lines; lines.resize(nb);
    for(auto& a:lines) cin>>a;
    
    int counter=0;
    for(auto& a:lines) if(isPrime(a)) counter++; 
    cout<<counter<<endl;
}

Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mx INT_MAX
#define mn INT_MIN
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define itr set<int> :: iterator
const int N = 1e5+10;

ll dp[100001][3];
int n;

ll solve(vector<int> h[], int pos, int i){

   if(i==n)
     return 0;
   
   if(dp[i][pos]!= -1)
      return dp[i][pos];

   if(pos == 0){
      ll r = h[i][1] + solve(h, 1, i+1);
      ll l = h[i][2] + solve(h, 2, i+1);
      dp[i][pos] = max(r,l);
      return max(r, l);
   }

   if(pos == 1){
      ll r = h[i][0] + solve(h, 0, i+1);
      ll l = h[i][2] + solve(h, 2, i+1);
      dp[i][pos] = max(r,l);
      return max(r,l);
   }

   if(pos == 2){
      ll r = h[i][0] + solve(h, 0, i+1);
      ll l = h[i][1] + solve(h, 1, i+1);
      dp[i][pos] = max(r,l);
      return max(r, l);
   }

   return 0;
}

int main(){
    // ******* START HERE ******
    
    cin>>n;
 
    vector<int> h[n];
    for(int i=0; i<n; i++){
      for(int j=0; j<3; j++){
       int x;
       cin>>x;
       h[i].pb(x);
     } 
    }
    
    memset(dp, -1, sizeof(dp));
    ll f = h[0][0] + solve(h, 0, 1);
    ll s = h[0][1] + solve(h, 1, 1);
    ll t = h[0][2] + solve(h, 2, 1);
    ll res = max(f, max(s, t));
     
    cout<<res<<endl;
    // ***** END HERE ***** 
    return 0;
}

Measured memory_bytes: 17620
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long X,K,D,max_per,answer;
  cin >> X>>K>>D;
  if(X<=0){
    X=X*(-1);//負の数
  }
    max_per=X/D;//ぎりぎりまで割っていく
    if(max_per>=K){
      cout<<X-(K*D);
    }else{
      if((K-max_per)%2==0){
        cout<<X-(max_per*D);
      }else {
        answer=abs(X-((max_per+1)*D));
        cout<<answer;
    }
  }
}

Measured memory_bytes: 3524
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define FOR(i, r, n) for (int i=(int)(r); i<=(int)(n); i++)
#define all(v) v.begin(), v.end()
#define INF 2147483647
#define INF64 9223372036854775807
#define MOD 1000000007

int main(){

    int n; cin>>n;
    vector<int> a(n);
    rep(i, n) cin>>a[i];

    vector<int> on(32);
    rep(i, n){
        bitset<31> s(a[i]);
        rep(j, 31){
            if(s.test(j)) on[j]++;
        }
    }

    vector<bool> change(32, false);
    rep(i, 31){
        if(on[i]%2==1) change[i]=true;
    }

    rep(i, n){
        bitset<31> s(a[i]);
        int ans=0;
        int x=1;
        rep(j, 31){
            if(change[j]) s.flip(j);
            if(s.test(j)) ans+=x;
            x*=2;
        }

        cout<< ans << endl;
        
    }

}

Measured memory_bytes: 4048
A = int(input())
B = int(input())
C = int(input())
X = int(input())
result = 0
for a in range(0, A + 1):
    for b in range(0, B + 1):
        for c in range(0, C + 1):
            if 500 * a + 100 * b + 50 * c == X:
                result += 1
print(result)

Measured memory_bytes: 9192
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count = 0
for i, b in enumerate(B):
    if b <= A[i]:
        count += b
    else:
        count += A[i]
        buf = b - A[i]
        if A[i+1] >= buf:
            count += buf
            A[i+1] -= buf
        else:
            count += A[i+1]
            A[i+1] = 0

print(count)

Measured memory_bytes: 81892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e5+1)
void yesno(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
ll power(ll x, ll n, ll m){if(n==0)return 1;ll u=power(x,n/2,m);u=(u*u)%m;if(n%2)u=(u*x)%m;return u;}



int main (){
fastio;

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

ll arr[n];
int i;
for(i=0;i<n;i++)
    cin>>arr[i];
sort(arr,arr+n);

ll ans=0;
for(i=0;i<k;i++)
    ans+=arr[i];

    cout<<ans;


}


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

bool cmp(int a,int b){
        return a>b;
}


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

    //Insert code
    
  
	
	ll n,x;
	cin>>n;
	ll a[1000005];
	cin>>x;
	int res = x;
	for(int i=1; i<n; i++){
		int xx; cin>>xx;
		res = __gcd(res,xx);
	}
	cout << res;

    
    //End code


    cerr << "\nTime elapsed: " << 1000*clock() / CLOCKS_PER_SEC << "ms\n";
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define vpi vector<pair<int,int> > 
#define vpll vector<pair<lli,lli> >
#define vvpi vector < vector<pair<int,int> > > 
#define vvpll  vector < vector<pair<lli,lli> > >
#define vvi vector<vector<int> >
#define vvll vector<vector<lli> >
#define maxn 1000001
#define mod 1000000007
#define inf 10000000000000000


int main()
{
    fastio;
    lli x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    lli num=x/d;
    if(num>=k)
    cout<<x-k*d<<"\n";
    else
    {
        lli rem=x%d;
        lli bal=k-num;
        if(bal%2==0)
        cout<<rem<<"\n";
        else
        cout<<d-rem<<"\n";
    }
    
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using llong = long long;
int main()
{
    llong a, b;
    string tmp;
    cin >> a >> tmp;
    b = (tmp[0] - '0') * 100 + (tmp[2] - '0') * 10 + (tmp[3] - '0');
    cout << a * b / 100 << endl;
}

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

using namespace std;

int main () {
  int k;
  cin >> k;
  cin.ignore ();
  string s;
  getline (cin, s);
  if (s.size () > k) {
    string ans = s.substr (0, k);
    cout << ans << "...\n";
  } else {
    cout << s << '\n';
  }
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,k,f[100100],a[101];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int main()
{
	n=read();k=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,k)
		rep(j,1,n)
			if (i>=a[j]) f[i]|=(f[i-a[j]]^1);
	if (f[k]) puts("First");
	else puts("Second");
	return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll LINF = 1001002003004005006LL;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n; cin >> n;
    vector<ll> ans(n+1);

    for (int i=1; i<=n; ++i) {
        int tmp = i;
        while (tmp <= n) {
            ans[tmp] += tmp;
            tmp += i;
        }
    }
    ll res = 0;
    for (int i=1; i<=n; ++i) res += ans[i];
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 81376
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int t; cin >> t; cin.ignore(); while(t--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}
 
int main(){
    fast();
 
/* you get what you work for not what you wish for */
    
    inp(n);
    if(n&1){
        cout << 0 << endl;
        return 0;
    }
    else{
        ll x = n/2;
        ll ans = 0;
        while(x){
            ans = ans + x/5;
            x/=5;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
    #include<vector>
    #include<math.h>
    #include<bits/stdc++.h>
    #include<sstream>
     
    using namespace std;
     
    int main()
    {
        long long a, b, c, count = 0;

        cin >> a >> b >> c;

        if(a == b && b == c && a == c)
        {
            if(a%2 == 0)
                cout << -1;
            else
            {
                cout << 0;
            }
            
        }
        
        else
        {
            while(a%2==0 && b%2==0 && c%2==0)
            {
                long long d,e,f;

                d = a;
                e = b;
                f = c;

                a = e/2 + f/2;
                b = d/2 + f/2;
                c = d/2 + e/2;

                count++; 
            }

            cout << count;
        }
    
    } 

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

int main(void)
{
	int n, d;
	cin >> n >> d;
	int x[n][d];
	int cnt;
	rep(i, n) rep(j, d) cin >> x[i][j];

	cnt = 0;
	rep(i, n - 1) For(j, i + 1, n)
	{
		int sum = 0;
		rep(k, d)
		{
			sum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
		}
		bool ok = false;
		rep(k, sum + 1)
		{
			if (k * k == sum)
				ok = true;
		}
		if (ok) cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T>bool chmin(T&a,const T b){if(a>b){a=b;return true;}else return false;}
template<class T>bool chmax(T&a,const T b){if(a<b){a=b;return true;}else return false;}
const ll INF=1LL<<60;
ll dp[100010];
ll h[100010];
int main(){
  ll N,K;
  cin>>N>>K;
  for(ll i=0;i<N;i++)cin>>h[i];
  for(ll i=0;i<N;i++)dp[i]=INF;
  dp[0]=0;
  for(ll i=0;i<N;i++){
    for(ll j=1;j<=K;j++){
      chmin(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
    }
  }
  cout<<dp[N-1]<<endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

int N, M, C;
int B[32];
int A[32][32];

int main(void) {
	int i, j;
	int koziruri = 0;
	if (scanf("%d%d%d", &N, &M, &C) != 3) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d", &B[i]) != 1) return 1;
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (scanf("%d", &A[i][j]) != 1) return 1;
		}
	}
	for (i = 0; i < N; i++) {
		int koziharu = C;
		for (j = 0; j < M; j++) {
			koziharu += A[i][j] * B[j];
		}
		koziruri += koziharu > 0;
	}
	printf("%d\n", koziruri);
	return 0;
}


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

int main() {
  int n,k,a,b;
  cin>>n>>k;
  a=k;b=k+n-1;
  if(a*b<=0) cout<<(a+b)*n/2<<endl;
  else{
    if(a*a<b*b)
      cout<<(a+b)*n/2-a<<endl;
    else
      cout<<(a+b)*n/2-b<<endl;
  }
      
      
  
}

Measured memory_bytes: 256
w = gets.to_i
n = gets.to_i

n_list = []
n.times.each do
  st = gets.split(/,/)
  n_list << [st[0].to_i, st[1].to_i]
end

answers = []
1.upto(w).each do |i|
  current_w = i
  n_list.each do |n_line|
    if current_w == n_line[0]
      current_w = n_line[1]
    elsif current_w == n_line[1]
      current_w = n_line[0]
    end
  end
  answers[current_w - 1] = i
end
puts answers

Measured memory_bytes: 6112
import scala.io.StdIn

object Main{
  def main(args: Array[String]){
    val n = StdIn.readLine().split(" ").map(_.toInt)
    var arr = Array.ofDim[Int](n(0) + 1, n(1) + 1)

    for(in <- 1 to n(0)){
      val line = StdIn.readLine().split(" ").map(_.toInt)

      for(in2 <- 1 to n(1)){
        arr(in - 1)(in2 - 1) = line(in2 - 1)
        arr(n(0))(in2 - 1) += line(in2 - 1)
      }
      arr(in - 1)(n(1)) = line.sum
      arr(n(0))(n(1)) += line.sum
    }

    for(in <- 1 to n(0)+1){
      for(in2 <- 1 to n(1)+1){
        print(arr(in - 1)(in2 - 1))
        if(in2 != n(1)+1){
          print(" ")
        }
      }
      println
    }
  }
}

Measured memory_bytes: 52064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ma[114514];
ll h[114514];
int main(){
	ll n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		ma[a]=max(ma[a],h[b]);
		ma[b]=max(ma[b],h[a]);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(ma[i]<h[i])ans++;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 5200
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
  while(1){
    int n,m,a;
    cin>>n;
    cin>>m;
    cin>>a;
    if(n == 0 && m == 0 && a == 0){
      break;
    }

    int ans = a;

    vector<pair<int,pair<int,int>>> w;
    pair<int,int> l;
    pair<int,pair<int,int>> v;

    for(int i = 0;i < m;++i){
      int h,p,q;
      cin>>h;
      cin>>p;
      cin>>q;

      l.first = p;
      l.second = q;

      v.first = h;
      v.second = l;

      w.push_back(v);
    }

    sort(w.begin(),w.end());
    reverse(w.begin(),w.end());

    for(pair<int,pair<int,int>> e : w){
      pair<int,int> sec;
      sec = e.second;

      int c,b;
      c = sec.first;
      b = sec.second;

      if(ans == c){
        ans = b;
      }
      else if(ans == b){
        ans = c;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 3120
# encoding:utf-8
import copy
import numpy as np
import random

a,b = map(int,input().split())
# 1digit

# F(0,n)を求める
def F(n):
    if n==0:
        tmp_ans = 0
    else:
        true_count = (n+1)//2
        if (n+1)%2==0:
            if true_count%2==0:
                tmp_ans = 0
            else:
                tmp_ans = 1
        else:
            if true_count%2==0:
                tmp_ans = n
            else:
                if n%2==0:
                    tmp_ans = n+1
                else:
                    tmp_ans = n-1

    return tmp_ans

max_digit = 0
num = b
while num > 0:
    max_digit += 1
    num = num//2

a_digits= []
b_digits = []
digits = []

A = F(a-1)
B = F(b)
# print(A,B)
for i in range(max_digit):
    a_digits.append(A%2)
    b_digits.append(B%2)
    A = A//2
    B = B//2

for i in range(max_digit):
    if (a_digits[i] == 1 and b_digits[i] == 1) or (a_digits[i] == 0 and b_digits[i]==0):
        digits.append(0)
    else:
        digits.append(1)

ans = 0
for i in range(max_digit):
    ans += digits[i]*2**i

print(ans)

'''
if a == b:
    print(a)
    exit()

def xor_0(a,b):
    if((b-a+1)//2)%2 == 0:
        if (b-a+1)%2==0:
            digit = 0
        else:
            if a%2==0:
                # 0 xor 0
                digit = 1
            else:
                # 1 xor 1
                digit = 1
    else:
        if (b-a+1)%2==0:
            digit = 1
        else:
            if a%2==0:
                # 0 xor 0
                digit = 1
            else:
                # 0 xor 1
                digit = 0

    return digit

max_digit = 0
num = b
while num > 0:
    max_digit += 1
    num = num//2

def digit_xor(a,b,i):
    if i == 0:
        return xor_0(a,b)
    else:
        count = 0
        posi_a = a%(2**(i+1))
        if posi_a>2**i:
            count += 2**i-a+1
        elif posi_a==0:
            pass
        else:
            count += 2**i

        posi_b = b%(2**(i+1))
        if posi_b > 2**i:
            count += 2**i
        else:
            count += posi_b

    if count%2==0:
        return 0
    else:
        return 1


digits = []
for i in range(max_digit):
    digits.append(digit_xor(a,b,i))

ans = 0
print(digits)
for i in range(len(digits)):
    ans += digits[i]*2**i

print(ans)
'''


Measured memory_bytes: 13780
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let k=read::<i32>();
    let s=read::<i32>();
    let mut c=0;
    for i in 0..k+1{
        for j in 0..k+1{
            if 0<=s-i-j&&s-i-j<=k{c+=1}
        }
    }
    println!("{}",c)
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b){
        int h=a+b;
        int i=1;
        while(true){
            if(h<10)
                break;
            h/=10;
            i++;
        }
        cout<<i<<endl;
    }
    return 0;
}
 

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

int main(void){
    string s,t; cin >> s >> t;
    int cnt=0;
    for(int i=0;i<3;i++){
        if(s[i]==t[i]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
N, X = map(int, input().split())
m = [int(input()) for i in range(N)]

X -= sum(m)
count = len(m)
min_m = min(m)
m.remove(min_m)

while X > min_m or m != []:
    tmp = X // min_m
    count += tmp
    X -= min_m * tmp
    min_m = min(m)
    m.remove(min_m)
print(count)

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

int main(){
  int n;
  while(1){
    cin >> n;
    if(n == 0) break;

    int ja,ma,en;
    for(int i = 0;i < n;i++){
      cin >> ma >> en >> ja;
      if(ja == 100 || ma == 100 || en == 100){
        cout << 'A' << endl;
      }else if((ma + en)/2 >= 90){
        cout << 'A' << endl;
      }else{
        double ave;
        ave = (ja + ma + en)/3.0;
        if(ave >= 80){
          cout << 'A' << endl;
        }else if(ave >= 70 || (ave >= 50 && (ma >= 80 || en >= 80))){
          cout << 'B' << endl;
        }else{
          cout << 'C' << endl;
        }
      }
    }
  }

  return 0;
}




Measured memory_bytes: 3012
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <complex>
#include <cstdio>
using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


int N,M;
vector<string> cand;
map<string, vector<int> > dic;
map<string,int> id;

int check(vector<string> lan){
	UnionFind uf(N+M);
	for( auto item : lan ){
		int u = id[item];
		
		for( auto v : dic[item] )
			uf.unionSet(u+M,v);
	}

	for(int i = 0 ; i < M ; i++)
		if( !uf.findSet(0,i) ) return false;
	return true;
}
int good = 6;
vector<string> answer;
vector<string> now;
int cur;
int dfs(int x){
	if( good <= cur ) return 0;
	if( check(now) ){
		answer = now;
		good = cur;
		return 0;
	}
	if( N <= x ) return 0;
	dfs(x+1);
	
	cur++;
	now.push_back(cand[x]);
	dfs(x+1);
	now.pop_back();
	cur--;
	
}
int main(){
	int fst = 0;
	while(cin >> N >> M && N){
		if(fst++)cout << endl;
		cand.clear();
		dic.clear();
		for(int i = 0 ; i < N ; i++){
			string t;
			cin >> t;
			cand.push_back(t);
		}
		for(int k = 0 ; k < M ; k++){
			int t;
			cin >> t;
			for(int j = 0 ; j < t ; j++){
				string s;
				cin >> s;
				dic[s].push_back(k);
			}
		}
		int k = 0;
		for( auto x : dic){
			id[x.first] = k++;
		}
		good = 6;
		cur = 0;
		dfs(0);
		if( good >= 6 ){
			cout << "Impossible" << endl;
		}else{
			cout << good << endl;
			for(int i = 0 ; i < answer.size() ; i++){
				cout << answer[i] << endl;
			}
		}
	}
}

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

int NumFlips(int start, int goal);

int main()
{
    int N, K;

    cin >> N >> K;
    double n = static_cast<double>(N), k = static_cast<double>(K);

    double p = 0;
    int flips = 0;

    for (int i = 1; i <= N; i++)
    {
        if (i >= K)
        {
            p += 1.0/n;
        }
        else
        {
            flips = NumFlips(i, K);
            p += (1.0/(pow(2.0, flips))) * (1.0/n);
        }

    }
    
    cout << fixed << setprecision(12) << p << endl;

}

int NumFlips(int start, int goal)
{
    int count = 0;
    while (start < goal)
    {
        count++;
        start *= 2;
    }

    return count;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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;
}

int main()
{
  ll a, b, c;
  cin >> a >> b >> c;
  ll d = a + b - c;
  // if (d >= 0)
  // {
  //   cout << "No" << endl;
  // }
  // else
  // {
  //   if (pow(d, 2) - 4 * a * b > 0)
  //   {
  //     cout << "Yes" << endl;
  //   }
  //   else
  //   {
  //     cout << "No" << endl;
  //   }
  // }
  if(d < 0 && d * d - 4 * a *b > 0) {
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;

//素数判定
inline bool IsPrime(int p) {
	if (p == 1) return false;
	for (int i = 2; i <= sqrt(p); i++) {
		if (p%i == 0) return false;
	}
	return true;
}

//10進数の自然数の桁数を返す
inline int GetDigit(int num) {
	return (int)log10(num) + 1;
}

//各位の和を返す
int GetDigitsSum(int num) {
	int N = 0;
	while (num > 0) {
		N += num % 10;
		num /= 10;
	}
	return N;
}



//異なるn個からr個の整数を取り出す組合せの数を求める
int combination(int n, int r) {
	if (r == 0 || n == r) {
		return 1;
	}
	else if (r == 1) {
		return n;
	}
	else {
		return combination(n - 1, r - 1) + combination(n - 1, r);
	}

}

int main() {
	int N;
	int K;
	cin >> N >> K;
	int h[100010];

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

	sort(h, h + N);
	int min = 2000000000;

	for (int i = 0; i < N-K+1; i++)
	{
		int tmp = h[i + K - 1] - h[i];
		if (tmp < min) {
			min = tmp;
		}
	}

	cout << min << endl;

	return 0;
}


Measured memory_bytes: 640
s=input()

s=s[:len(s)-1]
l=len(s)
if l%2==0:
  for i in range(0,l+1,2):
    x=s[:l-i]
    if x[:len(x)//2] == x[len(x)//2:]:
      print(len(x))
      exit()
else:
  s=s[:len(s)-1]
  l=len(s)
  for i in range(0,l+1,2):
    x=s[:l-i]
    if x[:len(x)//2] == x[len(x)//2:]:
      print(len(x))
      exit()


Measured memory_bytes: 8988
/*
 * atcoder/abc139/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

ll N;
void solve() {
  cin >> N;
  N--;
  cout << (N * (N + 1) / 2) << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
N = int(input())
c_AC = 0
c_WA = 0
c_TLE = 0
c_RE = 0
for _ in range(N):
    X = input()
    if X == "AC":
        c_AC += 1
    if X == "WA":
        c_WA += 1
    if X == "TLE":
        c_TLE += 1 
    if X == "RE":
        c_RE += 1
       

print("AC "+"x "+str(c_AC))
print("WA "+"x "+str(c_WA))
print("TLE "+"x "+str(c_TLE))
print("RE "+"x "+str(c_RE))

Measured memory_bytes: 9228
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cctype>
using namespace std;

int f(int m) {
    if (m % 2 == 0) return m / 2;
    else return 3*m+1;
}
int main() {
    int s, a[1000000];
    cin >> s;
    a[0] = s;
    for (int i = 1; i < 1000000; i++) {
        a[i] = f(a[i - 1]);
        bool k=0;
        for (int j=0; j < i; j++) {
            if (a[i] == a[j]) k = 1;           
        }
        if (k == 1) {
            cout << i+1 << endl;
            break;
        }
    }
}
     

Measured memory_bytes: 256
/*
Author: CNYALI_LK
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
	ll s=0;
	ll base=0;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=1;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	if(base)s=-s;
	return s;
}
ll f(ll a,ll b){
	if(!a)return 0;
	if(a>=b){
		return f(a%b,b)+b*(a/b)*2;
	}
	return f(b%a,a)+((b/a)*2-1)*a+b;

}

int main(){
#ifdef cnyali_lk
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
#endif
	ll n,x;	
	n=read();x=read();
	printf("%lld\n",f(x,n-x)+x);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <iterator>
using namespace std;

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


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

    // pos[i] = alphabet i の存在する位置の set
    vector<set<int>> pos('z'-'a'+1);
    REP(i, N) pos[S[i]-'a'].insert(i);

    REP(n, Q){
        int q;
        cin >> q;

        if(q == 1){
            int i;
            char c;
            cin >> i >> c; --i;
            pos[S[i]-'a'].erase(i);
            pos[c-'a'].insert(i);
            S[i] = c;
        }else{
            int l, r;
            cin >> l >> r; --l, --r;
            int ans = 0;
            REP(i, 'z'-'a'+1){
                if(distance(pos[i].lower_bound(l), pos[i].upper_bound(r)) > 0) ++ans;
            }
            cout << ans << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 24196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e6+5;
const ll MOD=1e9+7;
const ll MOD1=13;
ll n,m,nex[MAXN],len[2],vavid[MAXN],dist[MAXN],du[MAXN];
char str[2][MAXN];
vector<ll>G[MAXN];
ll myceil(ll x,ll y)
{
    if(x%y)
    {
        return x/y+1;
    }
    return x/y;
}
void ext()
{
    if(m>n)
    {
        ll mul=myceil(m,n);
        for(ll i=2;i<=mul;i++)
        {
            for(ll j=0;j<n;j++)
            {
                str[0][j+(i-1)*n]=str[0][j];
            }
        }
        n*=mul;
    }
    for(ll i=0;i<n;i++)
    {
        str[0][i+n]=str[0][i];
    }
    n*=2;
}
void get_nex()

{

    int i,j;

    i = 0;

    nex[0]=j = -1;

    while(i < m)

    {

        while(j!=-1&&str[1][i] != str[1][j])

        {

            j = nex[j];

        }

        nex[++i] = ++j;

    }

    return;

}

int kmp()

{

    int i,j;

    i = j = 0;

    while(i < n)

    {

        while(j!=-1&&str[0][i]!=str[1][j])

            j = nex[j];

        if(j == m-1)

        {

            vavid[i-m+1]=1;

            j = nex[j];

        }

        i ++;

        j ++;

    }


}
void solve()
{
    n=strlen(str[0]);
    m=strlen(str[1]);
    ll nn=n;
    ext();
    get_nex();
    kmp();

    for(ll i=0;i<n;i++)
    {
        if(vavid[i%nn])
        {
            ll nexv=(i+m)%n;
            G[i].push_back(nexv);
            du[nexv]++;
        }
    }
    for(ll i=0;i<n;i++)dist[i]=-1;
    queue<ll>q;
    for(ll i=0;i<n;i++)
    {
        if(!du[i])
        {
            q.push(i);
            dist[i]=0;
        }
    }
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();

        for(ll i=0;i<G[u].size();i++)
        {
            ll v=G[u][i];
            dist[v]=max(dist[v],dist[u]+1);
            du[v]--;
            if(!du[v])
            {
                q.push(v);
            }
        }
    }

    ll maxdist=0;
    for(ll i=0;i<n;i++)
    {
        if(dist[i]==-1)
        {
            printf("-1\n");
            return;
        }
        maxdist=max(maxdist,dist[i]);
    }
    printf("%lld\n",maxdist);
}
int main()
{
    scanf("%s",str[0]);
    scanf("%s",str[1]);
    solve();
}


Measured memory_bytes: 163072
x, k, d = map(int, input().split())
if x < 0:
    x *= -1

y = x-k*d
if y >= 0:
    print(y)
    exit()

a = x//d
xd = x%d
gk = [0, 0]
if a%2 == 1:
    gk[1] = xd
    gk[0] = abs(xd-d)
else:
    gk[1] = abs(xd-d)
    gk[0] = xd

if k%2 == 0:
    print(gk[0])
else:
    print(gk[1])

Measured memory_bytes: 9124
#include<stdio.h>
#include<string.h>
int main(void){
    char s[4],t[4];
    scanf("%s%s",s,t);
    if(strcmp(s,t)==0)
    printf("3");
    else if(strncmp(s,t,2)==0||(s[0]==t[0]&&s[2]==t[2])||(s[1]==t[1]&&s[2]==t[2]))
    printf("2");
    else if(s[0]==t[0]||s[1]==t[1]||s[2]==t[2])
    printf("1");
    else
    { printf("0");}
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(void){

	int ans,week,i,debt;
	
	debt=100000;				//ØàÌúl10
	scanf("%d",&week);

	ans=debt+debt*0.05;		//úqvZ
	
	for(i=1;i<week;i++){
		
		ans=ans+ans*0.05;
		
		if(ans%1000!=0){		//ç~¢Øèã°
			ans=ans-(ans%1000)+1000;
		}
	}
	printf("%d\n",ans);
}

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

using namespace std;

int main()
{
	int w, h, n;
	cin >> w >> h >> n;
	vector<int> vec(h);
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		vec[y] = max(vec[y], x);
	}
	int ans = 1000000, mob = 0;
	for (int i = h - 1; - 1 < i; i--)
	{
		ans = min(ans, i + mob);
		mob = max(mob, vec[i]);
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <cstring>
#include<cstdio>
#include <cmath>
#include<string>
#include<cmath>
using namespace std;

int main()
{
	int n, a,  all = 0;

	cin >> n >> a;

	all = (n / 500) * 500;

	all = n - all;

	if (all <= a)
		cout << "Yes" << endl;

	else
		cout << "No" << endl;


}

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

int main()
{
	using namespace std;
	long long a = 0, b = 0, c = 0, d = 0, e = 0, min = 0, ma = 0, ans = 0, count = 0, nagax = 0, nagay = 0, size = 0;
	int once[100020] = {}, info[100020] = {};
	std::string str[150], strs;

	bool okada = false, okada2 = true;
	cin >> a;
	for (int i = 1; i <= a; i++) {
		cin >> str[i];

	
	}
	for (int i = 2; i <= a; i++) {
		size = str[i-1].size();
		if (str[i].at(0) != str[i - 1].at(size-1)) {

			cout << "No" << endl;
			return 0;
		}
	
	}
	for (int i = 1; i <= a-1; i++) {
		for (int j = i + 1; j <= a; j++) {
	
			if (str[i] == str[j]) {
				okada2 = false;
				cout << "No" << endl;
				return 0;
			}
		}
	}

		cout << "Yes" << endl;




}





Measured memory_bytes: 256
N,M,L,Q;
D[301][301];
i,j,k;
a,b,c;
main()
{
	scanf("%d%d%d",&N,&M,&L);
	for(i=1;i<=N;i++)for(j=0;j<=N;j++)D[i][j]=1000000001;
	for(i=0;i<M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		D[a][b]=D[b][a]=c;
	}
	for(k=1;k<=N;k++)for(i=1;i<=N;i++)for(j=1;j<=N;j++)
		if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];
	for(i=1;i<=N;i++)for(j=0;j<=N;j++)
	{
		D[i][j]=D[i][j]>L?1000000000:1;
	}
	for(k=1;k<=N;k++)for(i=1;i<=N;i++)for(j=1;j<=N;j++)
		if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];
	scanf("%d",&Q);
	for(i=0;i<Q;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",D[a][b]<1000000000?D[a][b]-1:-1);
	}
}

Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
#define MAX 1<<17
#define F 114514810
using namespace std;

int dp[MAX];
int n,t[20][20];

int Fix(int q){
	int res=1;
	while(q--)res*=2;
	return res;
}
bool Vis(int now,int stage){
	int r=1;
	while(stage--)r*=2;
	if(now%(r*2)<r)return 0;
	return 1;
}

int main(){
	while(cin>>n&&n){
	for(int i=0;i<n;i++){
		cin>>t[i][n];
		for(int j=0;j<n;j++)cin>>t[i][j];
	}
	dp[0]=0;
	for(int i=1;i<Fix(n);i++)dp[i]=F;

	for(int i=0;i<Fix(n);i++){
		for(int j=0;j<n;j++){
			if(!Vis(i,j)){
				dp[i+Fix(j)]=min(dp[i+Fix(j)],dp[i]+t[j][n]);
				for(int k=0;k<n;k++){
					if(Vis(i,k)){
						dp[i+Fix(j)]=min(dp[i+Fix(j)],dp[i]+t[j][k]);
					}
				}
			}
		}
	}

	cout<<dp[Fix(n)-1]<<endl;
	}
	return 0;
}

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

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n;
    cin>>n;
    string s;
    cin>>s;

    int cnt = 0;
    for (int i=0; i<n; i++){
        cnt += (s[i]=='1');
    }
    
    int cntnp[2] = {cnt-1, cnt+1};
    int cr[2] = {0, 0};
    int rem[n][2];
    int tillnow[2] = {0, 0};
    for (int i=n-1; i>=0; i--){
        for (int j=0; j<2; j++){
            if (cntnp[j]==0) continue; 
            cr[j] = (1+tillnow[j])%cntnp[j];
            tillnow[j] += cr[j];
            rem[i][j] = cr[j];
        }
    }

    int sum[2] = {0, 0};
    for (int i=0; i<n; i++) {
        if (s[i]=='1'){
            for (int j=0; j<2; j++){
                sum[j]+=rem[i][j];
            }
        }
    }
    for (int i=0; i<n; i++){
//        int actual = 0;
//        for (int j=n-1; j>=0; j--){
//            if (i==j){
//                if (s[i]=='0'){
//                    actual += 1<<(n-1-j);
//                }
//            }
//            else if (s[j]=='1') actual += 1<<(n-1-j);
//        }
//        cout<<"actual -- "<<actual<<endl;

        int curr_cnt;
        int curr_sum;
        if (s[i]=='0'){
            curr_cnt = cntnp[1];
            curr_sum = sum[1]+rem[i][1];
        }
        else {
            curr_cnt = cntnp[0];
            curr_sum = sum[0]-rem[i][0];
        }

//        cout<<"actual mod"<<actual%curr_cnt<<endl;
        int ans = 1;
        if (curr_cnt==0){
            cout<<0<<endl;
            continue;
        }
        int now = curr_sum%curr_cnt;
        while(now>0){
//            cout<<"Now -- "<<now<<endl;
            int now_cnt = 0;
            int tmp = now;
            while(tmp>0){
                if (tmp&1) now_cnt++;
                tmp>>=1;
            }
            now = now%now_cnt;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 6852
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W = map(int,input().split())
h, w = map(int,input().split())
print(H*W - h*W - (H-h)*w)

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

using namespace std;

int N;

int main() {
	cin >> N;
	vector<int> a(N, 0);
	vector<int> b(N, 0);
	bool ans = true;
	for (int i = 0; i < N; i++) {
		cin >> b[i];
	}

	for (int i = N - 1; i >= 0; i--) {
		for (int j = i; j >= 0; j--) {
			if (b[j] == j + 1) {
				a[i] = b[j];
				for (int k = j; k < i; k++) { b[k] = b[k + 1]; }
				break;
			}
			if (j == 0) { ans = false; }
		}
	}

	if (ans == false) { cout << -1 << endl; }
	else {
		for (int i = 0; i < N; i++) { cout << a[i] << endl; }
	}
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v){stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modpow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}
void YN(bool z){cout<<(z?"YES\n":"NO\n");}
void Yn(bool z){cout<<(z?"Yes\n":"No\n");}
void yn(bool z){cout<<(z?"yes\n":"no\n");}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 32;
ll n, x[1000], y[1000];
string s = "LUDR";
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  ll d = -1;
  FOR(i, 0, n){
    cin >> x[i] >> y[i];
    if(d == -1){
      d = abs(x[i] + y[i]) % 2;
    }else{
      if(d != abs(x[i] + y[i]) % 2){
        cout << -1 << endl;
        return 0;
      }
    }
  }
  d++;
  cout << N+1 << endl;
  cout << d << " ";
  FOR(i, 0, N) cout << (1ll<<i) << (i==N-1 ? "\n" : " ");
  FOR(i, 0, n){
    ll k1, k2;
    k1 = x[i] + y[i] - d + (1ll<<N) - 1;
    k2 = x[i] - y[i] - d + (1ll<<N) - 1;
    cout << "R";
    FOR(j, 0, N){
      int idx = 0;
      k1 >>= 1;
      k2 >>= 1;
      if(k1&1) idx = idx + 1;
      if(k2&1) idx = idx + 2;
      cout << s[idx];
    }
    cout << endl;
  }
  return 0;
}

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

int main(){
    int n;
    cin >> n;
    
    vector<int> d(n);
    for (int i = 0; i < n; i++) cin >> d[i];
    
    sort(d.begin(), d.end());
    
    int index = n / 2;
    int former_number = d[index - 1];
    int latter_number = d[index];
    
    int ans = latter_number - former_number;
    cout << ans << endl;
}

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

void dfs(int node, vector<int> adj[],int dp[],bool vis[]){
    
    vis[node] = true;
    
    for(int i=0;i<adj[node].size();i++){
        if(!vis[adj[node][i]]){
            dfs(adj[node][i],adj,dp,vis);
        }
        
        dp[node] = max(dp[node],dp[adj[node][i]] +1);
    }
}

int longestpath(vector<int> adj[],int n){
    
    int dp[n+1];
    memset(dp,0,sizeof dp);
    
    bool vis[n+1];
    memset(vis,false, sizeof vis);
    
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i,adj,dp,vis);
        }
    }
    
    int ans =0;
    for(int i=1;i<=n;i++){
        ans = max(ans,dp[i]);
    }
    return ans;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    vector<int> adj[n+1];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
    }
    
    cout<<longestpath(adj,n);
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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 (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N,M;
    cin >>N>>M;
    ll ans;
    if(N==1 && M==1){
        ans=1;
    }else if(N==1){
        ans=M-2;
    }else if(M==1){
        ans = N-2;
    }else{
        ans=(N-2)*(M-2);
    }
    cout << ans << endl;


    return 0;
    

}


Measured memory_bytes: 3636
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;
 
public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        int count = int.Parse(Reader.ReadLine());

        long len = 2;
        for(int i=0; i<count; i++) {
            len = len+1 + len + 1;
        }

        Console.WriteLine(len);
    }



    public class Reader {
        public static bool IsDebug = true;
        private static System.IO.StringReader SReader;
        private static string InitText = @"



2


";
        public static string ReadLine() {
            if(IsDebug) {
                if(SReader == null) {
                    SReader = new System.IO.StringReader(InitText.Trim());
                }
                return SReader.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }
    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 2776