akhauriyash/Code-Regression huggingface dataset:
from collections import deque

n = int(input())
match = [deque([int(i)-1 for i in input().split()]) for _ in range(n)]
q = deque(range(n)) # 走査対象を格納したキュー
wait = [-1] * n # 次に試合する相手リスト
finish_day = [0] * n # 参加者の全日程終了日
match_count = 0 # 試合数

while q:
    x = q.popleft()
    y = match[x].popleft()
    if wait[y] != x: # 次に試合したい相手を記録
        wait[x] = y
    else:
        match_count += 1
        match_day = max(finish_day[x], finish_day[y]) + 1
        finish_day[x] = finish_day[y] = match_day
        wait[x], wait[y] = -1, -1
        if match[x]: q.append(x)
        if match[y]: q.append(y)

if match_count != (n*(n-1)) /2:
    print(-1)
else:
    print(max(finish_day))


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

int main()
{
    int x, a, b;
    cin >> x >> a >> b;

    if( abs(x-a) < abs(x-b) ){
        cout << "A" << endl;
    }else{
        cout << "B" << endl;
    }

    return 0;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)


void aryan_p() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return;
}
const int N = 50000;

void player_1() {
	cout << "Ashishgup" << endl;
}

void player_2() {
	cout << "FastestFinger" << endl;
}

bool check_prime(int n) {
	if (n == 2) {
		return true;
	}
	for (int i = 2; i < min(N, n); i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int32_t main() {
	

	int n ;
	cin >> n;

	mk(a, n, int);
	for (int i = 0; i < n ; i++) {
		cin >> a[i];
	}
	int sum = 0;
	for (int i = 0 ; i < n ; i++) {
		for (int j = i + 1 ; j < n ; j++) {
			sum += (a[i] * a[j]);
		}
	}
	cout << sum;

	return 0 ;
}



Measured memory_bytes: 3532
#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;

template<class T> 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=5005,mod=1e9+7;
int f[N][N][2],g[N][N],h[N],n,A,B;

void add(int &x,int y){
	x=(x+y>=mod?x+y-mod:x+y);
}

int main(){
	read(n),read(A),read(B);
	if(A<B) swap(A,B);

	add(f[1][1][0],1);
	rep(i,1,n){
		if(i<B) add(f[i][0][1],1);
		else add(f[i][i][1],1);
	}

	rep(i,1,n){
		add(h[i],h[i-1]);
		add(f[i][0][1],h[i]);

		add(f[i+1][1][0],f[i][0][1]);
		
		rep(j,1,A-1){
			add(g[i][j],g[i-1][j-1]);
			add(f[i][j][1],g[i][j]);

			add(h[i+1],f[i][j][0]);
			add(h[min(n+1,i+B)],mod-f[i][j][0]);
			add(f[i+1][j+1][0],f[i][j][0]);
			if(i+B<=n){
				add(g[i+B][j+B],f[i][j][0]);
			}
						
			add(f[i+1][j+1][0],f[i][j][1]);
		}
	}

	int ans=0,tot=1;
	rep(i,1,n){
		tot=2ll*tot%mod;
	}
	rep(j,0,A-1){
		add(ans,f[n][j][0]);
		add(ans,f[n][j][1]);
	}
	ans=((tot+mod-ans)%mod+mod)%mod;
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 296892
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n , cont = 0;
	cin >> n;
	int arreglo[n];
	for(int i = 0 ; i < n ; i++){
		cin >> arreglo[i];
	}
	for(int i = 0 ; i < n ; i++){
		bool cuenta = true;
		for(int j = 0 ; j < i ; j++){
			if(arreglo[j] > arreglo[i]){
			   cuenta = false;
			}
		}
		if(cuenta) cont++;
	}
	cout << cont << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main() {
    int N;
    cin >> N;
    char S[100001];
    cin >> S;

    int ans = 0;
    int before = -1;
    for (int i=0; S[i]!=0; i++) {
        if (before != S[i]) {
            ans++;
        }
        before = S[i];
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner S = new Scanner(System.in);
        long N = S.nextLong();
        long K = S.nextLong();
        long Nx = N % K;
        System.out.println(replace(Nx, K));
        S.close();
    }

    public static long replace(long x, long K) {
        long div = x - K;
        if (div < 0) {
            div = -div;
        }
        if (x <= div) {
            return x;
        }
        return replace(div, K);
    }
}

Measured memory_bytes: 35540
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import itertools
import math
import sys

INF = float('inf')


def solve(R: int):
    return 2*R*math.pi


def main():

    sys.setrecursionlimit(10 ** 6)

    R = int(input())  # type: int
    print(solve(R))


if __name__ == '__main__':
    main()


Measured memory_bytes: 69304
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>

#define LLI long long int

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());
	cout<<d[N/2]-d[N/2-1]<<endl;
	
	return 0;
}



Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>

int main(){
    int N;
    std::cin >> N;
    std::vector<int> a(N);
    for(int i=0;i<N;i++){
       std::cin >> a[i];
    }
    int sum=0;
    std::sort(a.begin(),a.end());
    for(int i=0;i<N;i++){
        if(i%2==0){
            sum+=a[i];
        }else{
            sum-=a[i];
        }
    }
    if(N%2==1){
        std::cout << sum << std::endl;
    }else{
        std::cout << -sum << std::endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000009;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-10;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int p[210000];
int q[210000];
pair<int,int>z[210000];
int segtree[524288];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return -mod;
	if(c<=a&&b<=d)return segtree[e];
	return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=262144;
	while(a){
		segtree[a]=max(segtree[a],b);
		a/=2;
	}
}
int main(){
	int X0,X1,Y0,Y1;
	scanf("%d%d%d%d",&X0,&Y0,&X1,&Y1);
	int a;scanf("%d",&a);
	int sz=0;
	for(int i=0;i<a;i++){
		int x,y;scanf("%d%d",&x,&y);
		if(x<min(X0,X1)||x>max(X0,X1)||y<min(Y0,Y1)||y>max(Y0,Y1))continue;
		z[sz]=make_pair(x,y);
		p[sz]=x;
		q[sz++]=y;

	}
	long double ret=0;
	std::sort(z,z+sz);
	if(X0==X1){
		 ret=100.0*ABS(Y0-Y1);
		ret+=sz*(10*PI-20);
	}else if(Y0==Y1){
		ret=100.0*ABS(X0-X1);
		ret+=sz*(10*PI-20);
	}else{
		if(X0>X1){
			swap(X0,X1);
			swap(Y0,Y1);
		}
		std::sort(q,q+sz);
		int val=0;
		if(Y0<Y1){
			for(int i=0;i<sz;i++){
				int at=lower_bound(q,q+sz,z[i].second)-q;
				int tmp=query(0,262143,0,at,1)+1;
				val=max(val,tmp);
				update(at,tmp);
			}
		}else{
			for(int i=0;i<sz;i++){
				int at=lower_bound(q,q+sz,z[i].second)-q;
				int tmp=query(0,262143,at,sz-1,1)+1;
				val=max(val,tmp);
				update(at,tmp);
			}
		}
		if(val>min(ABS(Y0-Y1),ABS(X0-X1))){
			ret+=(10*PI-20);val--;
		}
		ret+=100.0*(ABS(Y0-Y1)+ABS(X0-X1));
		ret-=val*20.0;
		ret+=val*5*PI;
	}
	printf("%.18Lf\n",ret);
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<int,int>
#define mod 1000000007
#define eps 0.000000001
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define dbg(x) cout<<#x<<": "<<x<<endl;
const double PI = acos(-1.0);
using namespace std;

map<int, int> fre;
bool marked[2005][2005];

void bfs(int st, vector<vector<int>> &adj)
{
    vector<bool> vis(2005, false);
    queue<pii> q;
    q.push(mp(st, 0));
    while(!q.empty())
    {
        pii u = q.front();
        q.pop();
        vis[u.ff] = true;
        if(!marked[st][u.ff])
        {
            fre[u.ss]++;
            marked[st][u.ff] = true;
            marked[u.ff][st] = true;
        }
        for(int x : adj[u.ff])
        {
            if(!vis[x])
            {
                vis[x] = true;
                q.push(mp(x, u.ss + 1));
            }
        }
    }
}

void cp()
{
    int n, x, y;
    cin >> n >> x >> y;
    memset(marked, false, sizeof(marked));
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++)
    {
        adj[i].pb(i + 1);
        adj[i + 1].pb(i);
    }
    adj[x].pb(y);
    adj[y].pb(x);
    for(int i = 1; i <= n; i++)
    {
    	bfs(i, adj);
    }
    for(int i=1;i<n;i++)
    {
    	cout<<fre[i]<<endl;
    }
}

int main()
{
    FASTIO;
    int t;
    t = 1;
    // cin>>t;
    while(t--)
    {
        cp();
    }
    return 0;
}

Measured memory_bytes: 4352
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

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

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

void solve(ll N, ll A, ll B, ll C, ll X) {
	vector<int> y(N); for (int i = 0; i < N; i++) scanf("%d", &y[i]);
	int res = 0;
	queue<int> q;
	for (int i = 0; i < N; i++) q.push(y[i]);
	for (int i = 0; i <= 10000; i++) {
		if (q.empty()) break;
		if (X == q.front()) {
			chmax(res, i);
			q.pop();
		}
		X = (X * A + B) % C;
	}
	if (!q.empty()) puts("-1");
	else printf("%d\n", res);
}
int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	while (1) {
		int n, a, b, c, x;
		scanf("%d %d %d %d %d", &n, &a, &b, &c, &x);
		if (n == 0) break;
		solve(n, a, b, c, x);
	}
	return 0;
	/*
		おまじないを使ったらscanfとprintf関連注意！！！！！！！！！！！！
	*/
}



Measured memory_bytes: 3196
#include<stdio.h>
#include<math.h>

int so(int A)
{
  int i;
  int count=0;
  
  if( A == 2 )return 1;
  if( A < 2 || A % 2 == 0 )return 0;
  for( i = 3 ; i*i <= A; i+=2){
    if( A % i == 0)return 0;
  }
  return 1;
}

int main()
{
  int a;
  int i;
  int n;
  int A;
  int count = 0;
  
  scanf("%d",&n);
  for( i = 0 ; i < n ; i++ ){
    scanf("%d",&A);
    a = so(A);
    if( a == 1 )count++;
  }
  
  printf("%d\n",count);
  
  return 0;
  
}



Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==v.size()?"":" ");
    return os;
}

// 0:左, 1:右
struct T{
    int lr,range;ll toku;
    T(int lr,ll toku,int range):lr(lr),toku(toku),range(range){}
    T(){}
};

void solve(){
    int n;cin>>n;
    int k[n];ll l[n],r[n];
    vector<T> v;
    ll ans=0;
    rep(i,n){
        cin>>k[i]>>l[i]>>r[i];
        if(l[i]>r[i]){
            if(k[i]) v.push_back(T(0,l[i]-r[i],k[i]));
            ans+=r[i];
        }else{
            if(n-k[i]>0) v.push_back(T(1,r[i]-l[i],n-k[i]));
            ans+=l[i];
        }
    }
    sort(ALL(v),[](T a,T b){
        return a.toku>b.toku;
    });
    // cout<<ans<<endl;
    // for(auto x:v){
    //     cout<<x.lr<<" "<<x.range<<" "<<x.toku<<endl;
    // }

    int lc=0,rc=0;
    rep(i,v.size()){
        if(v[i].lr==0) lc++;
        else rc++;   
    }

    set<int> ls,rs;

    for(int i=1;i<=lc;i++) ls.insert(i);
    for(int i=1;i<=rc;i++) rs.insert(i);

    for(auto t:v){
        if(t.lr==0){
            // l
            auto ite=ls.lower_bound(t.range+1);
            if(ite==ls.begin()) continue;
            ite=prev(ite);
            ls.erase(ite);
            ans+=t.toku;
        }else{
            // r
            auto ite=rs.lower_bound(t.range+1);
            if(ite==rs.begin()) continue;
            ite=prev(ite);
            rs.erase(ite);
            ans+=t.toku;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    int q;cin>>q;
    while(q--) solve();
    return 0;
}


Measured memory_bytes: 19680
<?php
list($a, $b) = ints();
$gcd = gcd($a,$b);
$divs = divisor($gcd);
$c = 0;
foreach($divs as $div){
  if(isPrime($div)){
    $c++;
  }
}
echo $c;

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
//約数
function divisor($n){
    for($i = ceil(sqrt($n)); $i >= 1; $i--){
        if($n % $i == 0){
            $f[] = $i;
            $f[] = $n / $i;
        }
    }
    sort($f);
    return array_unique($f);
}
function isPrime($n){
    $sqrtn = sqrt($n)+0.01;
    for($i = 2; $i < $sqrtn; $i++){
        if($n % $i == 0)return false;
    }
    return true;
}

Measured memory_bytes: 4856
def resolve():
    import math
    K = int(input())
    ans = []
    for i in range(1, K+1):
        for j in range(1, K+1):
            for p in range(1, K+1):
                q = math.gcd(i, j)
                ans.append(math.gcd(q, p))
    print(sum(ans))
resolve()

Measured memory_bytes: 71488
#include <stdio.h>

int
main(int argc, char *argv[])
{
        int secs;
        int h, m, s;

        scanf("%d", &secs);
        h = secs / 3600; secs -= h * 3600;
        m = secs / 60; secs -= m * 60;
        s = secs;
        printf("%d:%d:%d\n", h, m, s);

        return 0;
}

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

typedef long long ll;

void solve(std::string S){
  vector<ll> rst(S.size(), 0);

  for(ll i=0; i<S.size()-1; i++){

    if(S[i] == 'R' && S[i+1] == 'L'){
      rst[i]++;
      for(ll j=i-1; S[j]=='R'; j--){
        if((i-j)%2==0) rst[i]++;
      }
      for(ll j=i+1; S[j]=='L'; j++){
        if((i-j)%2==0) rst[i]++;
      }
    }
  }

  for(ll i=1; i<S.size(); i++){
    if(S[i-1] == 'R' && S[i] == 'L'){
      rst[i]++;
      for(ll j=i-1; S[j]=='R'; j--){
        if((i-j)%2==0) rst[i]++;
      }
      for(ll j=i+1; S[j]=='L'; j++){
        if((i-j)%2==0) rst[i]++;
      }
    }
  }

  for(ll i=0; i<S.size(); i++){
    cout << rst[i];
    if(i < S.size()-1) cout << " ";
  }
  cout << endl;
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

int N;

long long encode(const int *a)
{
  long long n = 0;
  for (int i = 0; i < N; i++) {
    n = 10*n + a[i];
  }
  return n;
}

void decode(int *a, long long n)
{
  for (int i = 0; i < N; i++) {
    a[N-i-1] = n % 10;
    n /= 10;
  }
}

void bfs(map<long long, int>& dist, long long start)
{
  queue<pair<long long, int> > q;
  dist[start] = 0;
  q.push(make_pair(start, 0));
  while (!q.empty()) {
    int a[10];
    decode(a, q.front().first);
    const int d = q.front().second;
    q.pop();
    for (int i = 0; i < N; i++) {
      for (int j = i+1; j < N; j++) {
        int b[10];
        copy(a, a+N, b);
        reverse(b+i, b+j+1);
        const long long n = encode(b);
        const map<long long, int>::const_iterator it = dist.find(n);
        if (it == dist.end()) {
          dist.insert(make_pair(n, d+1));
          if (d+1 < 4) {
            q.push(make_pair(n, d+1));
          }
        }
      }
    }
  }
}

int main()
{
  cin >> N;
  int a[10], b[10];
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    --a[i];
    b[i] = i;
  }
  map<long long, int> m1, m2;
  bfs(m1, encode(a));
  bfs(m2, encode(b));
  int ans = 9;
  for (map<long long, int>::const_iterator it = m1.begin(); it != m1.end(); ++it) {
    map<long long, int>::const_iterator jt = m2.find(it->first);
    if (jt != m2.end()) {
      ans = min(ans, it->second + jt->second);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 33072
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

int main()
{
  bool finished = false;

  int N,M;

  cin >> N  ;

  vector<int> A(N);
  vector<int> B(N);
  vector<int> C(N);
  //vector<vector<int>> A(N, vector<int>(30));

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

  for (int k = 0; k < N; k++)
  {
    C.at(k) = A.at(k);
  }
  sort(C.begin(), C.end());

  int tmp;
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j <= i;j++){
      for (int k = 0; k < N;k++){
        B.at(k) = A.at(k);
      }
      tmp = B.at(j);
      B.at(j) = B.at(i);
      B.at(i) = tmp;
      //cout << "p";
      if (B == C)
      {
        cout << "YES" << endl;
        finished = true;
        break;
      }
      
    }
    if (finished)
    {
      break;
    }
  }
  if (finished == false){
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
//using namespace std;
int main()
{
    int x,a,b;
     scanf("%d%d%d",&x,&a,&b);
    if(abs(a-x)<abs(b-x))
        printf("A");
    else
        printf("B");
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    long long n,z,w;
    while(cin >> n >> z >> w)
    {
        long long a,a1,a2;
        if(n==1)
        {
           cin >> a;
           cout << abs(a-w) << endl;
           continue;
        }
        for(long long i=0; i<n; i++)
        {
            cin >> a;
            if(i==n-2)
                a1=a;
            if(i==n-1)
                a2=a;
        }
        cout << max(abs(a2-a1),abs(a2-w)) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import heapq
n = int(input())
a = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(a)
i = 1
alice = 0
bob = 0
while i <= n:
  if i % 2 == 1:
    alice += heapq.heappop(a)*(-1)
  else:
    bob += heapq.heappop(a)*(-1)
  i += 1
print(alice - bob)

Measured memory_bytes: 3064
import java.math.*

fun main(args: Array<String>) {
    val (H, W) = readInputLine().split(" ").map { it.toLong() }
    
    var ans = Long.MAX_VALUE
    
    // 縦に切るだけの3分割
    for (w in LongRange(W / 3L, W / 3L + if (W % 3L != 0L) 1L else 0L)) {
        val S1 = H * w
        val S2 = H * ((W - w) / 2L)
        val S3 = H * ((W - w) / 2L + if ((W - w) % 2L != 0L) 1L else 0L)
        val max = Math.max(S1, Math.max(S2, S3))
        val min = Math.min(S1, Math.min(S2, S3))
        ans = Math.min(ans, max - min)
    }
    
    // 横に切るだけの3分割
    for(h in LongRange(H / 3L, H / 3L + if (H % 3L != 0L) 1L else 0L)) {
        val S1 = h * W
        val S2 = ((H - h) / 2L) * W
        val S3 = ((H - h) / 2L + if ((H - h) % 2L != 0L) 1L else 0L) * W
        val max = Math.max(S1, Math.max(S2, S3))
        val min = Math.min(S1, Math.min(S2, S3))
        ans = Math.min(ans, max - min)
    }

    // 縦方向に分割した後、残りを横方向に分割
    for(w in LongRange(W / 3L, W / 3L + if (W % 3L != 0L) 1L else 0L)) {
        val S1 = H * w
        val S2 = (H / 2L) * (W - w)
        val S3 = (H / 2L + if (H % 2L != 0L) 1L else 0L) * (W - w)
        val max = Math.max(S1, Math.max(S2, S3))
        val min = Math.min(S1, Math.min(S2, S3))
        ans = Math.min(ans, max - min)
    }

    // 横方向に分割した後、残りを縦方向に分割
    for(h in LongRange(H / 3L, H / 3L + if (H % 3L != 0L) 1L else 0L)) {
        val S1 = h * W
        val S2 = (H - h) * (W / 2L)
        val S3 = (H - h) * (W / 2L + if (W % 2L != 0L) 1L else 0L)
        val max = Math.max(S1, Math.max(S2, S3))
        val min = Math.min(S1, Math.min(S2, S3))
        ans = Math.min(ans, max - min)
    }

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37852
#include <iostream>
using namespace std;
int main(){
    int n, cnt = 0; cin >> n;
    int a[n]; for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i){
        int minj = i;
        for(int j = i; j < n; ++j){
            if(a[j] < a[minj]){
                minj = j;
            }
        }
        if(minj != i){
            swap(a[minj], a[i]);
            cnt++;
        }
    }
    for(int i =  0; i < n;++i){
        if(i) cout << " ";
        cout << a[i];
    }
    cout << endl;
    cout << cnt << endl;
    return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key){
    return u;
  }
  if(k < u->key){
    return treeSearch(u->left,k);
  } else
    return treeSearch(u->right, k);
}

Node treeSuccessor(Node x){


}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y=x;
    if(z->key < x->key){
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;

  if(y == NIL){
    root = z;
  } else if(z->key < y-> key){
    y->left = z;
  } else{
    y->right = z;
  }
}

void inorder(Node u){
  if(u == NIL){
    return;
  }
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if (u == NIL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,i;
	cin>>n;
	string s,a,b;
	cin>>s;
	for(i=0;i<n;i++){
	    if(i<n/2)a+=s[i];
	    else 
	    b+=s[i];
	}
//	cout<<a<<" "<<b<<"\n";
	if(a==b)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

ll a,b,c,d,px,py,pz,ret,prx,pry,prz;
vector<PII> v;
void add(int a) {
	if (a>=123456) {
		for (int i=1;i<=d;i++) v.pb(mp(i,a));
		for (int i=a-1-d;i<a;i++) v.pb(mp(i,a));
	} else {
		for (int i=1;i<a;i++) v.pb(mp(i,a));
	}
}
ll seg(ll p,ll q,ll a) {
	return min(p+d+1,a)-min(q+d+1,a);
}
int main() {
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	add(a); add(b); add(c);
	sort(all(v),[&](PII a,PII b){ return (ll)a.fi*b.se<(ll)a.se*b.fi; });
	px=min(a,d+1); py=min(b,d+1); pz=min(c,d+1);
	ret=px*py%mod*pz%mod;
	prx=0, pry=0, prz=0;
	for (auto p:v) {
		ll curx=p.fi*a/p.se,cury=p.fi*b/p.se,curz=p.fi*c/p.se;
		ret=(ret+seg(curx,prx,a)*py%mod*pz+seg(cury,pry,b)*px%mod*pz+seg(curz,prz,c)*px%mod*py)%mod;
		px=min(curx+d,a-1)-max(curx-d,0ll)+1;
		py=min(cury+d,b-1)-max(cury-d,0ll)+1;
		pz=min(curz+d,c-1)-max(curz-d,0ll)+1;
		prx=curx; pry=cury; prz=curz;
	}
	printf("%lld\n",ret);
}


Measured memory_bytes: 6384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		double ab = Math.sqrt(Integer.parseInt(a + b));
		System.out.println((int)ab == ab? "Yes": "No");
	}
}

Measured memory_bytes: 21712
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    
    int kuri = 10 - (s[0] - '0'), notkuri = s[0] - '0';
    for (int i = 1; i < s.size(); i++) {
        int now = s[i] - '0';
        int afterkuri = min(10 - (now + 1) + kuri, 10 - now + notkuri);
        int afternotkuri = min((now + 1) + kuri, now + notkuri);
        kuri = afterkuri, notkuri = afternotkuri;
    }

    cout << min(kuri + 1, notkuri) << endl;
    return 0;
}

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

int main() {
  int n;cin>>n;
  vector<int> h(n);
  rep(i,n)cin>>h[i];
  int ans=0,cnt=0;
  rep(i,n-1){
    if(h[i]<h[i+1])cnt=0;
    else cnt++;
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3716
#include<iostream>
#include<vector>
// #include<map>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> xors(n);
    for(int i=0; i<n; i++){
        cin >> xors[i];
    }
    int base = xors[0];
    for(int i=1; i<n; i++){
        base = base^xors[i];
    }

    for(int i=0; i<n; i++){
        cout << (base^xors[i]) << " ";
    }
    cout << endl;
    
    
    
    return 0;
}

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

using namespace std;

int main()
{
    int N,K;
    int ans = 0;
    scanf("%d",&N);
    scanf("%d",&K);
    int xi;
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&xi);
        ans += min(xi,K-xi);
    }
    printf("%d\n",2*ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define     ll          long long int
#define     ld          double
#define     REP(i,x,n)    for(ll i=x;i<n;i++)
#define     SZ(v)       (ll)v.size()
#define     endl        "\n"
#define     ff          first
#define     ss          second
#define     PQ_MIN      priority_queue <ll, vector<ll>, greater<ll> >
#define     PQ          priority_queue <int>
#define     pbds        tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define     setbit(x)   __builtin_popcount(x)
#define     prec(n)     fixed<<setprecision(n)
#define     pb(n)       push_back(n)
#define     mp(a,b)     make_pair(a,b)
#define     clr(n)      memset(n,0,sizeof(n))
#define     reset(n)    memset(n,-1,sizeof(n))
#define     ii          pair<ll,ll>
#define     vll         vector<ll>
#define     PI          3.1415926535897932384626433832795028841971693993751

using namespace std;
using namespace __gnu_pbds;
bool comp(pair<ll,ll> a,pair<ll,ll> b) {       }
const ll MOD=1e9+7;
void print(vector<vector<ll> >&v)
{
    ll n=v.size();
    ll m=v[0].size();
    cout<<"\n";
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<m;j++)
            cout<<v[i][j]<<" ";
        cout<<"\n";
    }
}
void print(vector<ll>&v)
{
    ll n=v.size();
    cout<<"\n";
    for(ll i=0;i<n;i++)
    {
            cout<<v[i]<<" ";
    }
        cout<<"\n";

}
void print(set<ll>&s)
{

cout<<endl;

set<ll>::iterator it;
for(it=s.begin();it!=s.end();it++)
    cout<<*it<<" ";
cout<<endl;
}
ll __lcm(ll a,ll b)
{
    return ((a*b)/__gcd(a,b));
}
ll power(ll a,ll p)
{
    ll res=1;
    while(p>0)
    {
        if(p&1){
            res=(res*a)%MOD;
            p--;
        }
            a=(a*a)%MOD;
            p/=2;
    }

    return res%MOD;
}
const ll INF=1e16;
const ll nxm=2e5+5;

ll spf[nxm];
void sieve()
{
    memset(spf,-1,sizeof(spf));

    spf[0]=spf[1]=1;

    for(ll i=2;i<nxm;i++)
    {
        if(spf[i]==-1)
            spf[i]=i;
        for(ll j=i*i;j<nxm;j+=i)
        {
            if(spf[j]==-1)
                spf[j]=i;

        }

    }
//    while(x>1)
//    {
//        ll s=spf[x];
//        temp[s]++;
//        x/=s;
//    }


// log n prime factor
}
void solve(){


ll n,ans=0;
cin>>n;
int a[n];

REP(i,0,n) cin>>a[i];

REP(i,1,n)
{
    if(a[i-1]>a[i])
        ans+=a[i-1]-a[i],a[i]=a[i-1];
}
cout<<ans<<endl;











}
int main(){
//    freopen("timber_input", "r", stdin);
//    freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
    REP(i,1,t+1)
    {
//    cout<<"Case #"<<i<<": ";
		solve();
    }
	return 0;
}
//  bitset<64>(x).to_ullong() // in my com  _ulong()
//  cout<<bitset<64>(ans).to_string().substr(64-m)<<endl;
/*

const int INF = 0x3f3f3f3f;


char s[100];

fgets(s,100,stdin);

stringstream stram(s);

string abc;

bool ok1=0,ok2=0;

while(stram>>abc)

ternary operator for(int i=0;i<23;i++) or while(r-l>eps)


*/


Measured memory_bytes: 4392
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    int len = 0;
    rep(i, N){
        if(A[i] == len + 1) len++;
    }

    if(len == 0) cout << -1 << endl;
    else cout << N - len << endl;

}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;

// Inserted snippets: io, root
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
// End snippets

int D, c[27];
int s[366][27];

chrono::steady_clock::time_point program_begin;

double runtime() {
	chrono::steady_clock::time_point program_end = chrono::steady_clock::now();

	return chrono::duration_cast<chrono::microseconds>(program_end - program_begin).count() / 1000000.0;
}

int calc(vector<int> sc) {
	vector<int> last(27, 0);
	int val = 0;
	rep(d, 1, D + 1) {
		val += s[d][sc[d]];
		last[sc[d]] = d;
		rep(i, 1, 27)
			val -= c[i] * (d - last[i]);
	}
	return val;
}

int myrand(int a, int b) {
	return a + rand() % (b - a + 1);
}

void solve() {
	vector<int> ans(366), best_ans(366);
	int best_ans_val;

	for (int i = 1; i <= 365; i++)
		ans[i] = i % 26 + 1;
	best_ans = ans;
	best_ans_val = calc(ans);

	cerr << "Begin: " << best_ans_val << endl;

	while (runtime() <= 1.8) {
		int d = myrand(1, 365), n = myrand(1, 26);
		if (ans[d] == n)
			continue;
		vector<int> new_ans = ans;
		new_ans[d] = n;
		int new_val = calc(new_ans);
		double accept_proc = exp(-5.0 * runtime() / 1.8);
		if (chmax(best_ans_val, new_val)) {
			best_ans = new_ans;
		}
	}

	cerr << "Final: " << best_ans_val << endl;
	
	rep(i, 1, D + 1)
		write(best_ans[i]);
}

void test() {}

int main(int argc, char *argv[]) {
	//cin.tie(0)->sync_with_stdio(0);
	//cin.exceptions(cin.failbit);

	srand(time(NULL));

	program_begin = chrono::steady_clock::now();

	if (argc >= 2 && string(argv[1]) == "test") {
		test();
		return 0;
	}

	read(D);
	rep(i, 1, 27) read(c[i]);
	rep(i, 1, D + 1) rep(j, 1, 27) read(s[i][j]);
	
	solve();
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct E{
	int to;
	int clr;
	int len;
};
vector<E> g[100005];
int anc[18][100005],d[100005];
void dfs(int u,int fa){
	for(auto v:g[u]){
		if(v.to==fa){
			continue;
		}
		anc[0][v.to]=u;
		d[v.to]=d[u]+1;
		dfs(v.to,u);
	}
}
int LCA(int x,int y){
	if(d[x]>d[y]){
		swap(x,y);
	}
	for(int ind=0;d[x]<d[y];++ind){
		if((d[y]-d[x])>>ind&1){
			y=anc[ind][y];
		}
	}
	if(x==y){
		return x;
	}
	for(int ind=18;ind--;){
		if(anc[ind][x]!=anc[ind][y]){
			x=anc[ind][x],y=anc[ind][y];
		}
	}
	return anc[0][x];
}
struct info{
	int ind;
	char typ;
	int clr;
	int cnt;
	info(){}
	info(int in,char ty,int cl,int cn){
		ind=in,typ=ty,clr=cl,cnt=cn;
	}
}; 
vector<info> q[100005];
ll sum[100005];
ll cnt[100005];
ll ans[100005];
void DFS(int u,int fa,ll len){
	for(auto now:q[u]){
		if(now.typ=='d'){
			ans[now.ind]+=len*now.cnt;
		}
		else if(now.typ=='s'){
			ans[now.ind]+=sum[now.clr]*now.cnt;
		}
		else{
			ans[now.ind]+=cnt[now.clr]*now.cnt;
		}
	}
	for(auto v:g[u]){
		if(v.to==fa){
			continue;
		}
		sum[v.clr]+=v.len;
		cnt[v.clr]++;
		DFS(v.to,u,len+v.len);
		sum[v.clr]-=v.len;
		cnt[v.clr]--;
	}
}
int main(){
	int n,Q;
	cin>>n>>Q;
	for(int i=1;i<n;++i){
		int u,v,clr,leng;
		cin>>u>>v>>clr>>leng; 
		u--,v--,clr--;
		E a;
		a.to=v,a.len=leng,a.clr=clr;
		E b;
		b.to=u,b.len=leng,b.clr=clr;
		g[u].push_back(a),g[v].push_back(b);
	}
	dfs(0,0);
	for(int ind=0;ind<17;++ind){
		for(int u=0;u<n;++u){
			anc[ind+1][u]=anc[ind][anc[ind][u]];
		}
	}
	for(int i=0;i<Q;++i){
		int clr,leng,u,v;
		cin>>clr>>leng>>u>>v;
		clr--;
		u--;
		v--;
		int lca=LCA(u,v);
		q[u].emplace_back(i,'d',0,1);
		q[u].emplace_back(i,'s',clr,-1);
		q[u].emplace_back(i,'c',clr,leng);
		q[v].emplace_back(i,'d',0,1);
		q[v].emplace_back(i,'s',clr,-1);
		q[v].emplace_back(i,'c',clr,leng);
		q[lca].emplace_back(i,'d',0,-2);
		q[lca].emplace_back(i,'s',clr,2);
		q[lca].emplace_back(i,'c',clr,-2*leng);
	}
	DFS(0,0,0);
	for(int i=0;i<Q;++i){
		cout<<ans[i]<<'\n';
	}
	return 0;
}


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

struct bydol
{
  int C;
  int vals[3];
};

int do_dp(const vector<bydol>& v, int M, int n)
{
  const int N = v.size();
  vector<int> dp(M+1, 0);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= M; j++) {
      if (j + v[i].C <= M) {
        dp[j+v[i].C] = max(dp[j+v[i].C], dp[j] + v[i].vals[n]);
        ans = max(ans, dp[j+v[i].C]);
      }
    }
  }
  return ans;
}

int main()
{
  string line;
  while (getline(cin, line)) {
    int N, M;
    {
      istringstream iss(line);
      iss >> N >> M;
    }
    vector<bydol> v(N);
    for (int i = 0; i < N; i++) {
      getline(cin, line); // ignore name
      getline(cin, line);
      {
        istringstream iss(line);
        iss >> v[i].C >> v[i].vals[0] >> v[i].vals[1] >> v[i].vals[2];
      }
    }

    int w = do_dp(v, M, 0);
    int d = do_dp(v, M, 1);
    int l = do_dp(v, M, 2);
    cout << max(w, max(d, l)) << endl;
  }
  return 0;
}

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

int main() {
  int n, m;
  vector<int> vec_t;
  
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int time; cin >> time;
    vec_t.push_back(time);
  }
  cin >> m;
  
  for (int i = 0; i < m; ++i) {
    int p, x; 
    cin >> p >> x;
    --p; // indexに変換
    vector<int> copy_v;
    copy(vec_t.begin(), vec_t.end(), back_inserter(copy_v));
    copy_v[p] = x;
    cout << accumulate(copy_v.begin(), copy_v.end(), 0) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1000000007;
const int INF = 1e+9;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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 w[110], v[110];
ll dp[110][100100] = {};

int main () {
  int N, W; cin >> N >> W;
  rep(i,N) cin >> w[i] >> v[i];

  for (int n = 0; n < N; n++) {
    for (int sum_w = 0; sum_w <= W; sum_w++) {
      if (sum_w - w[n] >= 0) {
        dp[n+1][sum_w] = max(dp[n+1][sum_w], dp[n][sum_w-w[n]]+v[n]);
      }
      dp[n+1][sum_w] = max(dp[n+1][sum_w], dp[n][sum_w]);
    }
  }

  cout << dp[N][W] << endl;
}

Measured memory_bytes: 79360
sel='A'
#A
if sel=='A':
    N,M=map(int,input().split())
    ans=0
    ans+=M*(M-1)//2
    ans+=N*(N-1)//2
    print(ans)

#B
if sel=='B':
    def ispal(s):
        for i in range(len(s)//2+1):
            if s[i]!=s[-(i+1)]:
                return False
        return True

    S=input()
    if ispal(S) and ispal(S[:(N-1)//2]) and ispal(S[(N+3)//2-1:]):
        print('Yes')
    else:
        print('No')

#C
if sel=='C':
    L=int(input())
    print((L**3)/27)

#D
if sel=='D':    
    N=int(input())
    A=[int(i) for i in input().split()]
    kin=list(set(A))
    cnt={}
    for k in kin:
        cnt[k]=0
    for a in A:
        cnt[a]+=1
    SUM=0
    for k in kin:
        SUM+=cnt[k]*(cnt[k]-1)//2
    for a in A:
        if cnt[a]>=2:
            print(SUM-cnt[a]+1)
        else:
            print(SUM)
        
#E
if sel=='E':
    a=0

#F
if sel=='F':
    N,S=map(int,input().split())
    A=[int(i) for i in input().split()]

    for l in range(N):
        for r in range(l,N):
            print(tab[l][r])



Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	string s;
	cin >> s;
	ll n = s.size();
	map<ll, ll> mp;
	
	vector<P> v;
	ll bit = 0;
	mp[0] = bit;
	zep(i, 0, n){
		ll c = s[i]-'a';
		bit ^= (1LL << c);
		
		if(mp.find(bit) != mp.end()){
			v.push_back(P(mp[bit], i+1));
		}
		zep(j, 0, 26){
			if(mp.find(bit ^ (1LL << j)) != mp.end()){
				v.push_back(P(mp[bit ^ (1LL << j)], i+1));
			}
		}
		mp[bit] = i+1;
	}
	
	ll dp[2][n+1];
	rep(i, 0, n){
		dp[0][i] = INF;
		dp[1][i] = INF;
	}
	dp[0][0] = 0;
	
	zep(i, 0, v.size()){
		ll l = v[i].first;
		ll r = v[i].second;
		if((r-l)%2 == 0){
			dp[0][r] = min(dp[0][l], dp[0][r]);
			dp[1][r] = min(dp[1][l], dp[1][r]);
		}
		else{
			dp[1][r] = min(min(dp[0][l]+1, dp[1][l]+1), dp[1][r]);
		}
	}
	print(max(min(dp[0][n], dp[1][n]), 1LL))
	//zep(i, 0, v.size()){cout << v[i].first << v[i].second << endl;}
	return 0;
}

Measured memory_bytes: 134004
import std.stdio;
import std.conv, std.array, std.algorithm, std.string;
import std.math, std.random, std.range, std.datetime;
import std.bigint;
import std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

void main(){
	long n = read.to!long;
	long[] as = readln.split.map!(to!long).array;
	
	as.sort!"a>b"();
	
	const long th = 1000;
	long count = 0;
	
	debug as.writeln;
	
	while(as[0] >= th + n){
		long k = (as[0] - th) / n;
		count += k;
		as[0] -= k * n;
		for(int j = 1; j < as.length; j ++) as[j] += k * 1;
		debug as.writeln;
		as.sort!"a>b"();
		}
	
	while(as[0] >= n){
		count += 1;
		as[0] -= n;
		for(int j = 1; j < as.length; j ++) as[j] += 1;
		debug as.writeln;
		as.sort!"a>b"();
		}
	
	count.writeln;
	}

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

int main()
{
   int n,k;
   cin>> n >> k;
   int a[n];
   for(int i =0;i<n;i++)
    cin>>a[i];
   sort(a,a+n);
   ll sum=0;
   for(int i=0;i<k;i++){
    sum=sum+a[i];
   }
   cout<<sum<<endl;
}

/// A L H A M D U L I L L A H


Measured memory_bytes: 3636
#include<stdio.h>

int main(){

    int N;
    double n,ans;

    scanf("%d",&N);
  	n = N;

    if ( N%2==0){
        ans = n/2/n;

    }

    else{

        ans = (n/2 +0.5)/n;

    }

    printf("%lf",ans);
  
 	return 0;

}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <map>
using namespace std;


int main() {
	int n,m;
	cin >>n;
	cin >>m;
	map<unsigned long, int> intMap;
	for(int i=0;i<n;i++){
		long tmpPri;
		int tmpQua;
		cin >>tmpPri;
		cin >>tmpQua;
		if(intMap.end() != intMap.find(tmpPri)) {
			intMap[tmpPri] = intMap[tmpPri] + tmpQua;
		} else {
			intMap.insert(map<unsigned long,int>::value_type(tmpPri,tmpQua));
		}
	}
	unsigned long answer = 0;
	std::map<unsigned long,int>::iterator itr=intMap.begin();
	for(itr = intMap.begin() ; itr != intMap.end() ; ++itr) {
		if(itr->second > m) {
			answer += m * itr->first;
			break;
		} else {
			answer += itr->first * itr->second;
			m -= itr->second;
		}
    }
    cout <<answer <<endl;
	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
     
    using namespace std;
    #define pb push_back
    #define ld long double
    #define ll unsigned long long
    string s, t;
    vector<ll>v[150];
    int main()
    {
        /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif*/
        cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin >> s >> t;
        ll lp = 0, rest = 0, pa = -1;
        for(int i = 0 ; i < s.size(); ++i)
            v[s[i] - 'a'].pb(i);
     
        for(auto ch : t)
        {
            if(v[ch - 'a'].empty())
            {
                cout << -1;
                return 0;
            }
     
            auto k = lower_bound(v[ch - 'a'].begin(), v[ch - 'a'].end(), pa + 1);
     
            if(k == v[ch - 'a'].end())
            {
                rest++;
                pa = v[ch - 'a'][0];
            }
            else pa = *k;
     
        }
        cout << 1LL * rest * s.size() + pa + 1;
        return 0;
    }

Measured memory_bytes: 1736
# coding: utf-8

import math
import sys


def split_3(h, w):
    cand = []
    cand.extend([(h // 3 + i, w, h - (h // 3 + i), w) for i in range(3)])
    cand.extend([(h, w // 3 + i, h, w - (w // 3 + i)) for i in range(3)])
    return cand


def split_2(h, w):
    cand = []
    cand.extend([((h // 2 + i) * w, (h - (h // 2 + i)) * w) for i in range(2)])
    cand.extend([(h * (w // 2 + i), h * (w - (w // 2 + i))) for i in range(2)])
    return cand


def main():
    h, w = map(int, input().split())
    if h % 3 == 0 or w % 3 == 0:
        return 0

    cand = split_3(h, w)
    score = float("inf")
    for h1, w1, h2, w2 in cand:
        r1 = h1 * w1
        for r2, r3 in split_2(h2, w2):
            score = min(score, max(r1, r2, r3) - min(r1, r2, r3))
    return score


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 3064
import re
S2 = input()
T = input()

S2 = S2.replace('?', '.')
S2 = S2[::-1]
T = T[::-1]

ans = ""
i = 0
find = False
while i < len(S2):
    if find == False and len(T) > len(S2) - i:
        break
    p = S2[i:i+len(T)]
    m = re.match(p, T)
    if m and find == False:
        find = True
        ans = ans + T
        i += len(T)
    else:
        if S2[i] == '.':
            ans = ans + 'a'
        else:
            ans = ans + S2[i]
        i += 1

if len(ans) == len(S2):
    print(ans[::-1])
else:
    print('UNRESTORABLE')


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

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

  rep(i, s.size()) { s[i] = 'A' + (s[i] - 'A' + n) % 26; }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll INF=1e18;
vector<ll> x[210005];
vector<ll> used(210005,0);
vector<ll> c(2);
ll cx,cy;

void dfs(ll t){
  //used[n][t]=1;
  if (t>=100005)cy++;
  if (t<100005)cx++;
  used[t]=1;
  for(ll to:x[t]){
    if (used[to])continue;
    dfs(to);
  }
}


int main() {
  ll N;
  cin >> N;
  vector<P> v(N);


  rep(i,N){
    ll a1,b1;
    cin>>a1>>b1;
    a1--;b1+=100005;
    v[i]=make_pair(a1,b1);
    x[a1].push_back(b1);
    x[b1].push_back(a1);
  }
ll ans=0;
  rep(i,N){
    c[0]=0;c[1]=0;
cx=0;cy=0;
    dfs(v[i].first);
  //  cout<<"i"<<i<<cx<<" "<<cy<<endl;
    ans+=cx*cy;

  }

  ans-=N;
  cout<<ans;

}


Measured memory_bytes: 17408