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

using namespace std;

#define ll					long long
#define vi					vector<int>
#define vii					vector<vi>
#define ALL(s)			(s).begin(),(s).end()
#define pii					pair<int, int> pii;
#define pll					pair<ll, ll>
#define si					set<int>
#define F						first
#define S						second
#define pb					push_back
#define tc(t)				int t; cin >> t; while(t--)
#define _						ios_base::sync_with_stdio(false); cin.tie(NULL); 
const ll MOD = 1e9 + 7;
const ll INF = 1<<29;
const ll MAX_N = 1e6 + 7;

int main() {_
	int n;
	cin >> n;
	set<int>  pos;
	int count = 0;
	char s[n];

	for(int i = 0; i < n; ++i) {
		cin >> s[i];
		if(s[i] == 'A')
			pos.insert(i);
	}

	for(auto itr : pos) {
		if(itr < n - 2 && s[itr+1] == 'B' && s[itr+2] == 'C')
			count++;
	}

	cout << count << "\n";

}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define N 55
#define ll long long
#define db double
#define dbg1(x) cout<<#x<<"="<<x<<" "
#define dbg2(x) cout<<#x<<"="<<x<<"\n"
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if(a>b) swap(a,b);
	if(b>c) swap(b,c);
	if(a>c) swap(a,c);
	
	if((a&1)^(b&1))
	{
		printf("%d\n",(b-a-1)/2+1+(c-b)+1);
	}
	else
	{
		printf("%d\n",(c-b)+(b-a)/2);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
const ll LINF = 1e18;
using namespace std;

#define rep(i, n) for (int(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (int i = (a); i < (b); i++)
#define rrrep(i, a, b) for (int i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl

ll n, cnt, ans, a, b, c, d[ohara], tmp, tmpp, m, h, w, x, y, sum, pos, k, l[ohara], r[ohara];
ld doua;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
bool fl;
struct edge
{
    int to, cost;
};
vector<ll> g[ohara];
int vi[ohara];
map<pair<ll, ll>, ll> cost;
map<pair<ll, ll>, ll> judge;
map<ll, ll> cou;

//-------------------------↓↓↓↓↓↓------------------------

struct UnionFind
{
    vector<ll> data;

    UnionFind(ll n)
    {
        data.assign(n, -1);
    }

    void unite(ll x, ll y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (data[x] > data[y])
            swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    ll find(ll k)
    {
        if (data[k] < 0)
            return k;
        return data[k] = find(data[k]);
    }
};

void dfs(ll pa, ll now, ll depth)
{
    if (vi[now] == 1)
        return;
    vi[now] = 1;
    judge[{pa, now}] = depth;
    rep(i, Size(g[now]))
    {
        dfs(pa, g[now][i], depth + cost[{now, g[now][i]}]);
    }
}

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

    cin >> n >> m;
    UnionFind uf(n + 10);
    int toku[ohara]={};
    rep(i, m)
    {
        cin >> l[i] >> r[i] >> d[i];
        l[i]--;
        r[i]--;
        cost[{l[i], r[i]}] = d[i];
        g[l[i]].push_back(r[i]);
        toku[r[i]]=1;
        //g[r[i]].push_back(l[i]);
        uf.unite(l[i], r[i]);
    }
    queue<ll> pa;
    int sugita[ohara] = {};
    rep(i, n)
    {
        if (toku[i]==0)
        {
            pa.push(i);
            cnt++;
        }
    }
    while (!pa.empty())
    {
        ll root = pa.front();
        pa.pop();
        dfs(uf.find(root), root, 0LL);
    }
    rep(i, m)
    {
        ll group = uf.find(l[i]);
        ll couho;
        couho = judge[{group, r[i]}] - judge[{group, l[i]}];
        //cout<<judge[{group, r[i]}]<<" "<<judge[{group, l[i]}]<<"\n";
        if (couho != d[i])
        {
            Cout("No");
            return 0;
        }
    }
    Cout("Yes");
    return 0;
}


Measured memory_bytes: 66176
#include<iostream>
using namespace std;
long long n,m,k,ans;
int main()
{
    cin>>n>>m>>k;
    if(n<=m)
    {
        cout<<"1\n";
        return 0;
    }
    if(m<=k)
    {
        cout<<"-1\n";
        return 0;
    }
    cout<<((n-m)%(m-k)==0?(n-m)/(m-k):(n-m)/(m-k)+1)*2+1<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int INF = 1 << 28;
		while (true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if ((n | m) == 0)
				break;
			char[] ch = new char[n + 2];
			for (int i = 1; i <= n; i++) {
				ch[i] = '#';
			}
			for (int i = 0; i < m; i++) {
				char p = sc.next().charAt(0);
				switch (p) {
				case 'A':
					for (int j = 1; j <= n; j++) {
						if (ch[j] == '#') {
							ch[j] = 'A';
							break;
						}
					}
					break;
				case 'B':
					boolean flag = true;
					for (int j = n; j >= 1; j--) {
						if (ch[j - 1] != 'A' && ch[j + 1] != 'A'
								&& ch[j] == '#') {
							ch[j] = 'B';
							flag = false;
							break;
						}
					}
					if (flag) {
						for (int j = 1; j <= n; j++) {
							if (ch[j] == '#') {
								ch[j] = 'B';
								break;
							}
						}
					}
					break;
				case 'C':
					flag = true;
					for (int j = 1; j <= n; j++) {
						if (ch[j] != '#') {
							flag = false;
							if (ch[j + 1] == '#') {
								ch[j + 1] = 'C';
								break;
							} else if (ch[j - 1] == '#') {
								ch[j - 1] = 'C';
								break;
							}
						}
					}
					if (flag) {
						ch[n / 2 + 1] = 'C';
					}
					break;
				case 'D':
					int num = 0;
					int max = 0;
					int dis[] = new int[n + 1];
					Arrays.fill(dis, INF);
					for (int j = 1; j <= n; j++) {
						for (int k = 1; k <= n; k++) {
							if (ch[k] != '#') {
								dis[j] = Math.min(dis[j], Math.abs(j - k));
							}
						}
					}
					for (int j = 1; j <= n; j++) {
						if (dis[j] > max) {
							max = dis[j];
							num = j;
						}
					}
					ch[num] = 'D';
					break;
				}
			}
			System.out.println(new StringBuilder().append(ch).substring(1,n+1));
		}
	}
}

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


int main(){
  int a, b, c, d;
  
  cin >> a >> b;
  
  c = a/b;
  d = a%b;
  
  if (d == 0)
  {
        cout << c << endl;
  }
  else
  {
       cout << (c+1) << endl;
  }
}
  



Measured memory_bytes: 256
N = int(input())
W_li = list(map(int,input().split()))

i = 0
j = 1
top = 0
bot = 0
while i+j-1 < N:
    
    if top <= bot:
        top += W_li[i]
        i += 1
    else:
        bot += W_li[-j]
        j += 1

print(str(abs(top-bot)))

Measured memory_bytes: 38256
#include<cstdio>
#include<algorithm>
using namespace std;

int a[222222], b[222222];

int main(){
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d", b+i,a+i);

    bool found = false;
    for(int i=0;i<n;i++) if(a[i]>b[i]) found = true;
    if(!found) return !printf("0\n");

    long long sum = 0;
    for(int i=0;i<n;i++) sum += a[i];
    int mina = 2e9;
    for(int i=0;i<n;i++) if(a[i] < b[i]) mina = min(mina, a[i]);
    printf("%lld\n", sum - mina);
}


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

int a[3];

bool mv() {
	sort(a, a + 3);
	if (a[0] < a[2] && a[1] < a[2])
		a[0]++, a[1]++;
	else if (a[0] < a[2])
		a[0] += 2;
	else
		return 0;
	return 1;
}

int main() {
	for (int i = 0; i < 3; i++)
		cin >> a[i];
	int ans = 0;
	while (mv())
		ans++;
	cout << ans;
}

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

typedef long long ll;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	int ans = s.length() - (s.front() == s.back()?3:2);
	cout << (ans&1?"First":"Second") << '\n';
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n, p;
        cin >> n >> p;
        if(n == 1){
            cout << p << '\n';
            continue;
        }
        map<int, int> cnt;
        for(int i = 2; i * i <= p; i++){
            while(p % i == 0){
                cnt[i]++;
                p /= i;
            }
        }
        for(auto &it : cnt){
            it.ss /= n;
        }
        int ans = 1;
        for(auto &it : cnt){
            for(int i = 0; i < it.ss; i++){
                ans *= it.ff;
            }
        }
        cout << ans << '\n';
    }
}

Measured memory_bytes: 31488
<?php
$n = trim(fgets(STDIN));
$a_array = explode(" ", fgets(STDIN));
$b_array = explode(" ", fgets(STDIN));
$c_array = explode(" ", fgets(STDIN))+[0];
$ans = 0;
for($i=0; $i<count($a_array); $i++){
	$ans+=$b_array[$i];
	if((int) $a_array[$i]===$a_array[$i-1]+1){
		$ans += $c_array[$a_array[$i]-2];
	}
}
echo $ans ."\n";



Measured memory_bytes: 4984
#include <stdio.h>

int main(void){
  int x, y, z, count;
  scanf("%d %d %d\n", &x, &y, &z);
  count = 0;
  x -= z;
  while (x >= (y + z)) {
    count++;
    x -= (y + z);
  }
  printf("%d\n", count);
  return 0;
}


Measured memory_bytes: 128
S = input()
T = input()

S_ans = S
N = len(S)
RESTORABLE = False

#isrestは0でtrue、1でfalse
for i in range(N):
    isrest = 0
    for j in range(1,len(T)+1):
        if S[N-i-j] != T[-j] and S[N-i-j] != "?":
            isrest += 1
            break
        elif i+j>N:
            isrest += 1
            break
        else:
            temp = list(S_ans)
            temp[N-i-j] = T[-j]
            S_ans = "".join(temp)
    if isrest==0:
        RESTORABLE = True
        break
    S_ans = S
    
if RESTORABLE:
    print(S_ans.replace("?","a"))
else:
    print("UNRESTORABLE")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
struct circle{
	ld x, y, r;
};
ld dist(circle a, circle b){
	return max((ld) 0.0, sqrt(((b.x - a.x) * (b.x - a.x)) + ((b.y - a.y) * (b.y - a.y))) - b.r - a.r);
}
circle c[1005];
ld INF = 1e18;
ld d[1005][1005];
ll n;
bool sptset[2005];
ld rd[1005];
ll mindis(){
	ld mn = INF + 1, mdex;
	for (ll v = 0; v <= n + 1; v++){
		if ((sptset[v] == 0) && (rd[v] <= mn)){
			mn = rd[v]; mdex = v;
		}
	}
	return mdex;
} 
void dijkstra(ll src){
	for (ll i = 0; i <= n + 1; i++) rd[i] = INF;
	rd[src] = 0;
	for (ll cnt = 0; cnt <= n; cnt++){
		ll u = mindis(); sptset[u] = 1;
		for (ll v = 0; v <= n + 1; v++){
			if (!sptset[v] && rd[u] != INF && rd[u] + d[u][v] < rd[v]) rd[v] = rd[u] + d[u][v];
		}
	}
}
int main(){
	fastio;
	cout << fixed << setprecision(12);
	ld xs, ys; cin >> xs >> ys;
	circle s; s.r = 0; s.x = xs; s.y = ys; 
	ld xe, ye; cin >> xe >> ye;
	circle e; e.r = 0; e.x = xe; e.y = ye; 
	cin >> n;
	c[0] = s; c[n + 1] = e;
	for (ll i = 1; i <= n; i++) cin >> c[i].x >> c[i].y >> c[i].r;
	for (ll i = 0; i <= n + 1; i++){
		for (ll j = i + 1; j <= n + 1; j++) d[i][j] = dist(c[i], c[j]);
		d[i][i] = 0;
		for (ll j = 0; j < i; j++) d[i][j] = d[j][i];
 	}
 	dijkstra(0);
	cout << rd[n + 1] << endl;
}

Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    ll n,m; cin >> n >> m;
    vector<ll> x(m);
    rep(i,m){
        cin >> x[i];
    }
    sort(all(x));
    for(int i=m-1;i>=0;i--) x[i] -= x[0];

    if(n >= m){
        cout << 0 << endl;
        return 0;
    }


    vector<pair<ll,ll>> v;
    rep(i,m-1) v.push_back(make_pair(x[i+1]-x[i],i));
    sort(all(v));
    reverse(all(v));

    ll sum = 0;
    for(auto vv : v) sum += vv.first;

    for(int i=0;i<n-1;i++){
        sum -= v[i].first;
    }
    cout << sum << endl;
}


Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;

namespace UOA_PCKWU_1045
{
    class Program
    {
        static void Main(string[] args)
        {
            string input;
            while( (input = Console.ReadLine()) != "0")
            {
                List<int> data = Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToList();
                Console.WriteLine(new Solver().Solve(data));
            }
        }
    }
    class Solver
    {
        protected static List<int> List { get; set; }
        public int A { get; set; }
        public int B { get; set; }
        public int Depth { get; set; }

        public int Solve(List<int> list)
        {
            List = list;
            return Solve();
        }

        protected int Solve()
        {
            if (Depth == List.Count) return Math.Abs(A - B);
            var a = new Solver() { A = A + List[Depth], B = B, Depth = Depth + 1}.Solve();
            var b = new Solver() { A = A, B = B + List[Depth], Depth = Depth + 1}.Solve();
            return Math.Min(a, b);
        }
    }
}



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

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


    long double a;

    long double b;
    cin>>a>>b;
    ll ans = floor(a*b);

    cout<<ans<<"\n";
}


Measured memory_bytes: 3808
import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.Unite(a-1, b-1)

ans = 0

for i in range(n):
    ans = max(ans, uf.Count(i))

print(ans)

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


int main(){
  int X, N;
  cin >> X >> N;
  /*if(N==0){
    cout << X;
    return 0;
  }*/
  vector<int> p(N);
  rep(i, N) cin >> p[i];
  
  vector<int> nums(102);
  rep(i,102) nums.at(i) = i;
  auto it = nums.begin();
  it = nums.insert(it,-1);
  
  rep(i,N) nums[p[i]+1] = 1000;
  sort(nums.begin(), nums.end());
  nums.push_back(10000);
  //rep(i, 102) cout <<nums[i]<<endl;
  int index = 0;
  rep (i, nums.size()) {
      //cout << nums[i] << endl;
    if(nums[i] <= X && X < nums[i+1]) {
      index = i;
     break;
    }
  }

  int target;
  //cout << nums[index] <<endl;
  //cout << nums[index+1]<<endl;
  if((X-nums[index])<= nums[index+1]-X){
    target = nums[index];
  }else{
    target = nums[index+1];
  }
  cout << target;

  return 0;
}

Measured memory_bytes: 3632
import math

N, D = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))

ans = 0

for i in range(N):
    for j in range(i + 1, N):
        dist = 0
        for k in range(D):
            dist += (X[i][k] - X[j][k]) ** 2
        if dist == (math.floor(math.sqrt(dist))) ** 2:
            ans += 1
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0) return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1;  // 分母
  ll numerator = 1;    // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

vector<ll> burgerSize;
vector<ll> numberOfPatties;

// B BPPPB P BPPPB B
ll solve(ll n, ll x) {
  if (n == 0) return 1;

  ll size = burgerSize[n-1];
  ll patties = numberOfPatties[n-1];

  if (x <= 1) {
    return 0;
  } else if (x <= size + 1) {
    return solve(n-1, x-1);
  } else if (x <= size + 2) {
    return 1 + patties;
  } else if (x <= 2 * size + 2) {
    return solve(n - 1, x - (size + 2)) + patties + 1;
  } else {
    return 2 * patties + 1;
  }
}

int main() {
  ll N, X;
  cin >> N >> X;

  burgerSize.push_back(1);
  numberOfPatties.push_back(1);
  for (ll i = 0; i < N; i++) {
    burgerSize.push_back(2 * burgerSize[i] + 3);
    numberOfPatties.push_back(2 * numberOfPatties[i] + 1);
  }

  cout << solve(N, X) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
  char s[11];
  int len,check=0,i;
  scanf("%s",s);
  len=strlen(s);
  if(s[0]!='A' || (s[1]-'a'<0 || 26<s[1]-'a')){
    puts("WA");
    return 0;
  }
  for(i=2;i<len;i++){
    if(s[i]=='C' && i!=len-1)
      check++;
    else if(s[i]-'a'<0 || 26<s[i]-'a'){
      puts("WA");
      return 0;
    }
  }
  if(check==1)
    puts("AC");
  else
    puts("WA");
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	char w[4];
	cin>>w[0]>>w[1]>>w[2]>>w[3];
	a=w[0]-'0';b=w[1]-'0';c=w[2]-'0';d=w[3]-'0';
	if(a+b+c+d==7) cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7";
	else if(a+b+c-d==7) cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7";
	else if(a+b-c+d==7) cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7";
	else if(a-b+c+d==7) cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7";
	else if(a-b-c+d==7) cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7";
	else if(a-b+c-d==7) cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7";
	else if(a+b-c-d==7) cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7";
	else if(a-b-c-d==7) cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7";
	cout<<endl;
	return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


ll N, M;
int color[100000];
vector<int> adj[100000];

bool dfs(int ver, int col){
    if(color[ver] == 1 - col){
        return false;
    }else if(color[ver] == col){
        return true;
    }
    color[ver] = col;
    bool ret = true;
    for(int next : adj[ver]){
        ret = ret && dfs(next, 1 - col);
    }
    return ret;
}

signed main(){
    cin >> N >> M;
    int A, B;
    REP(i, N) color[i] = -1;
    REP(i, M){
        cin >> A >> B;
        adj[A - 1].push_back(B - 1);
        adj[B - 1].push_back(A - 1);
    }
    if(dfs(0, 0)){
        ll w = 0;
        REP(i, N) w += color[i];
        PRINT(w * (N - w) - M);
    }else{
        PRINT(N * (N - 1) / 2 - M);
    }
    return 0;
}

Measured memory_bytes: 6400
using System;

namespace ITP1_5_A{
    class Rectangle{
        static void Main(string[] args){
            int h,w;
            string[] arr;
            while(true){
                arr = Console.ReadLine().Split(' ');
                h = int.Parse(arr[0]);
                w = int.Parse(arr[1]);
                if((h==0)&&(w==0)) break;
                for(int i=0; i<h; i++){
                    for(int j=0; j<w; j++){
                        Console.Write("#");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }
    }
}


Measured memory_bytes: 17776
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

const LL INF = 1LL << 61;

struct Edge {
  int to;
  LL len;
};

int U, V;
int N, M;
LL var[214514];
bool used[214514];
vector<Edge> es[214514];

bool Check(int s) {
  var[s] = 0;
  queue<int> que;
  que.push(s);

  LL mn[2] = {INF, INF};
  while (!que.empty()) {
    int v = que.front(); que.pop();

    used[v] = true;
    MN(mn[v >= U], var[v]);

    for (auto &e : es[v]) {
      int u = e.to;
      if (used[u]) {
        if (var[u] + var[v] != e.len) return false;
        continue;
      }

      var[u] = e.len - var[v];
      que.push(u);
    }
  }

  if (mn[0]+mn[1] < 0) return false;
  return true;
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> U >> V;
  N = U+V;
  cin >> M;
  rep(i, M) {
    int r, c;
    LL d;
    cin >> r >> c >> d;
    --r;
    --c;
    c += U;
    es[r].eb(Edge{c, d});
    es[c].eb(Edge{r, d});
  }

  rep(v, U) {
    if (used[v]) continue;
    if (!Check(v)) {
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
}


Measured memory_bytes: 93352
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
#define mod 1000000007
signed main(){
    int n;
    cin>>n;
    int count=0;
    int a[114514];
    a[0]=0;
    a[n+1]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        count+=abs(a[i]-a[i-1]);
    }
    count+=abs(a[n+1]-a[n]);
    for(int i=1;i<=n;i++){
        cout<<count-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])<<endl;
    }
    return 0;
}



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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int A,B;
    cin>>A>>B;
    int res;
    if(A<=9 && B<=9)
    {
        cout<<A*B<<"\n";
    }
    else
    {
        cout<<"-1"<<"\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
// In the name of God

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;
const int mod = 1e9+7;

long long fac[N], pw[N];

long long fast_exp(long long x, long long y) {
	long long ret=1;
	for(;y;y>>=1) {
		if(y&1) ret=(ret*x)%mod;
		x=(x*x)%mod;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	fac[0] = 1;
	pw[0] = 1;
	for(int i=1;i<N;i++) {
		fac[i] = (fac[i-1]*i)%mod;
		pw[i] = (pw[i-1]*2)%mod;
	}
	int n;	
	cin >> n;

	vector<long long>v(n);

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

	long long ans = 0;
	for(int i=0;i<v.size();i++) {
		long long c = pw[i];
		c = (c*v[i])%mod;
		
		int top = (int)v.size()-i-1;
		c = (c*(top+2))%mod;
		c = (c*pw[top])%mod;
		c = (c*fast_exp(2, mod-2))%mod;
		
		ans = (ans+c)%mod;
	}
	ans = (ans*pw[n])%mod;
	
	cout << ans;

	return 0;
}


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

signed main(){
  int N,X;
  cin>>N>>X;
  int minD=X;
  rep(i,N){
    int I;
    cin>>I;
    X-=I;
    minD=min(minD,I);
  }
  int ans=N+(X/minD);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

long long dfs(long long N, long long M, long long K, long long d, long long sum) {
    if (d == N) return max(1LL, sum - K);
    long long ret = 0;
    for (long long i = 1; i <= M; i++) {
        ret += dfs(N, M, K, d + 1, sum + i);
    }
    return ret;
}

int main() {

    while (true) {

        long long N, M, K;
        cin >> N >> M >> K;

        if (!(N | M | K)) break;

        long long nomi = dfs(N, M, K, 0, 0);
        double deno = 1;
        for (int i = 0; i < N; i++) deno *= M;

        cout << fixed << setprecision(10) << (double) nomi / deno << endl;

    }

    return 0;
}






























































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

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

		if( a < b ) cout<<"a < b"<<endl;
		if( a > b ) cout<<"a > b"<<endl;
		if( a == b ) cout<<"a == b"<<endl;

		return 0;
}


Measured memory_bytes: 3096
N = int(input())
AC=0
WA=0
TLE=0
RE=0
for i in range(0,N):
  j = str(input())
  if j == "AC":
    AC+=1
  elif j == "WA":
    WA+=1
  elif j == "TLE":
    TLE+=1
  else:
    RE+=1
print("AC x {}".format(AC))
print("WA x {}".format(WA))
print("TLE x {}".format(TLE))
print("RE x {}".format(RE))

Measured memory_bytes: 9208
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<utility>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
//using ll=long long;
//static const ll mod = 1e9;
//static const ll INF = 1LL << 50;
using namespace std;

int num = 0;

void bubblesort(vector<int>& v, int n) {//参照渡ししないと反映されない
	for (int i = 0; i < n - 1; ++i) {
		for (int j =0; j < n-1; ++j) {
			if (v[j] > v[j+1]) {
				swap(v[j], v[j+1]);
				++num;
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	vector<int>v(n);
	repp(i, 0, n)cin >> v[i];
	bubblesort(v, n);
	repp(i, 0, n) {
		if (i)cout << " ";
		cout << v[i];
	}cout << endl;
	cout << num << endl;
	return 0;
}


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

const ll INF = 1001001001001;
ll tb[50][50][100];

vector<ll> v;
ll ans = -INF;

ll dfs(int l, int r, int K) {
    if (l > r || K <= 0) return 0;
    if (l == r) return v[l] <= 0 ? 0 : v[l];
    if (tb[l][r][K] != -INF) return tb[l][r][K];
    ll a, b, c, d;
    // 取り出したものを最終的に使う
    a = dfs(l+1, r, K-1);
    b = dfs(l, r-1, K-1);

    // 取り出したものを最後に戻す
    c = dfs(l+1, r, K-2);
    d = dfs(l, r-1, K-2);

    return tb[l][r][K] = max(v[l] + a, max(v[r] + b, max(c, d)));
}

void solve() {
    int N, K;
    cin >> N >> K;
    v.resize(N);
    rep(i,N) cin >> v[i];

    rep(i,50) rep(j,50) rep(k,100) tb[i][j][k] = -INF;
    cout << dfs(0,N-1,K) << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector <int> B(N - 1);
  for (int i = 0; i < N - 1; i++) {
	  cin >> B[i];
	}
  int ans = B[0] + B[N - 2];
  for (int i = 1; i < N - 1; i++) {
	  ans += min(B[i], B[i - 1]);
	}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        long a = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        long c = Long.parseLong(sc.next());
        long x = c - a - b;
        if(x <= 0) {
            System.out.println("No");
            return;
        }
        long y = 4 * a * b;
        String ans = (x * x - y > 0) ? "Yes" : "No";
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl;
#define Vecpr vector<pair<lli,lli>>
#define mod 1000000007;
bool is_prime(lli x) {
  for(lli i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}
int main() {
  lli A,B,C=1,D=0,E=0,F=0,G=0,H=0,N,M;
  cin >> A >> B >> C;
  rep(i,0,A){
    cin >> D >> E;
    if(B<=D&&C<=E)F++;
  }
  Out(F);
}

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

int main() {
	vector<int> p = {0,300000,200000,100000};
	int x,y;
	cin >> x >> y;
	cout << p[x] + p[y] + (x == 1 && y == 1) * 400000 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin>>x;
double r=0;
int a[x]={0};
for(int i=1;i<=x;i++)
{
    cin>>a[i];
}
for(int i=1;i<=x;i++)
{
   r=r+1.0/a[i];
}
cout<<1.0/r;




   return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = BIT(10 ** 5 + 1)
for x in a: fwk.add(x, x)
Q = int(input())
for _ in range(Q):
  b, c = map(int, input().split())
  fwk.add(c, fwk.get(b) // b * c)
  fwk.add(b, -fwk.get(b))
  print(fwk.sum(10 ** 5))

Measured memory_bytes: 84804
from itertools import combinations
import math
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n = int(readline())
m = map(int,read().split())
points = [(x, y) for x, y in zip(m, m)]

if n == 2:
    [(a, b), (c, d)] = points
    print(math.hypot(a - c, b - d) / 2)
    quit()


def center(a, b, c):
    M = pow(a[0], 2) - pow(b[0], 2) + pow(a[1], 2) - pow(b[1], 2)
    N = pow(a[0], 2) - pow(c[0], 2) + pow(a[1], 2) - pow(c[1], 2)
    Yab = a[1] - b[1]
    Xab = a[0] - b[0]
    Yac = a[1] - c[1]
    Xac = a[0] - c[0]
    d = Yac * Xab - Yab * Xac
    if d == 0:
        return None
    x = (M * Yac - N * Yab) / (2 * d)
    y = - (M * Xac - N * Xab) / (2 * d)
    r = math.hypot(x - a[0], y - a[1])
    return (x, y, r)


centers = []
for a, b, c in combinations(points, 3):
    cen = center(a, b, c)
    if cen is None:
        continue
    centers.append(cen)

dsq = 0
for a, b in combinations(points, 2):
    tmp = pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)
    if dsq > tmp:
        continue
    dsq = tmp
    cen = ((a[0] + b[0]) / 2, (a[1] + b[1]) / 2, math.sqrt(dsq) / 2)
centers.append(cen)

res = 1000
for cx, cy, cr in centers:
    for x, y in points:
        tr = math.hypot(x - cx, y - cy)
        if tr > cr + 10e-6:
            break
    else:
        if cr < res:
            res = cr
print(res)


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

int main() {
    string S;
    cin >> S;
    for(int i=0;i<S.size();i++) {
        if(i%2==0) {
            if(S[i]=='L') {
              puts("No"); 
              return 0;
            }
        }
        else {
            if(S[i]=='R') {
              puts("No"); 
              return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}


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

int main() {
long long N,A,B;
cin>>N>>A>>B;
long long X[100010];
for(long long i=0; i<N; i++){
    long long a;
    cin>>a;
    X[i]=a;
}
long long res=0;
for(long long i=0; i<N-1; i++){
    long long t=X[i+1]-X[i];
    if(t*A>=B) res+=B;
    else res+=t*A;
    
}
cout<<res<<endl;
}


Measured memory_bytes: 1024
// B

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;

int main(){
  int N,T,A,H[1000];
  cin>>N>>T>>A;
  for (int i(0);i<N;i++) cin>>H[i];
  int ans(0);
  double tmp(1e9);
  for (int i(0);i<N;i++){
    if (tmp > abs(A-(T - H[i] * 0.006))){
      tmp = abs(A-(T-H[i]*0.006));
      ans = i+1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()

using namespace std;

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

    vector<ll> a;
    
    rep(i,n){
        int  tmp;
        cin >> tmp;
        a.pback(tmp);
    }

    ll ans = 0;

    if(n != 1){

        ll r = 0;
        ll sum = 0;

        for(ll l = 0;  l <= n - 1; l++){

            if(l == r){
                sum = a[l];
                r++;
            }

            while(r <= n - 1 && !(sum & a[r])){
                sum += a[r];
                r++;
            }

            sum -= a[l];
            ans += r - l;
        }

    }else ans = 1;

    cout << ans << endl;
    
    return 0;
}


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

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

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

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

fn main() {
    input!{
        n: usize,
        x: usize1,
        y: usize1
    }
    let mut g = vec![vec![]; n];
    for i in 0..n - 1 {
        g[i].push(i + 1);
        g[i + 1].push(i);
    }
    g[x].push(y);
    g[y].push(x);
    let mut dist = vec![vec![n; n]; n];
    for i in 0..n {
        dist[i][i] = 0;
        let mut q = VecDeque::new();
        q.push_back(i);
        while let Some(v) = q.pop_front() {
            for &c in &g[v] {
                if dist[i][c] < n {
                    continue;
                }
                dist[i][c] = min(dist[i][c], dist[i][v] + 1);
                q.push_back(c);
            }
        }
    }
    let mut c = vec![0; n + 1];
    for i in 0..n {
        for j in i + 1..n {
            c[dist[i][j]] += 1;
        }
    }
    for k in 1..n {
        println!("{}", c[k]);
    }
}


Measured memory_bytes: 45308
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in, n) for(int i=0; i<n; i++) cin>>in[i]
#define forout(out, n) for(int i=0; i<n; i++) cout<<out[i]<<endl

int binary_search(const vector<ll>& a ,ll key){
    int ng=-1, ok=(int)a.size();
    while(abs(ok-ng)>1){
        int mid=(ok+ng)/2;
        if(a[mid] >= key){
            ok=mid;
        }else{
            ng=mid;
        }
    }
    return ok;
}
int binary_search1(const vector<ll>& a ,ll key){
    int ng=-1, ok=(int)a.size();
    while(abs(ok-ng)>1){
        int mid=(ok+ng)/2;
        if(a[mid] <= key){
            ng=mid;
        }else{
            ok=mid;
        }
    }
    return ng;
}


int main(){
    ll N; cin>>N;
    vector<ll> A(N);
    vector<ll> B(N);
    vector<ll> C(N);
    forin(A, N); sort(A.begin(), A.end());
    forin(B, N);
    forin(C, N); sort(C.begin(), C.end());

    ll ans=0;
    for(int i=0; i<N; i++){
        ll A2=binary_search(A, B[i]), C2=N-binary_search1(C, B[i])-1;
        if(C[N-C2] == B[i]) C2--;
        ans+=A2*C2;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5604
#include<bits/stdc++.h>
using namespace std;
int main() {
  char a, b, c;cin >> a >> b >> c;
  int co;
  if(a == 'S') {
    if(b == 'S') {
      if(c == 'S') {
        co = 0;
      }
      else {
        co = 1;
      }
    }
    else {
       if(c == 'S') {
         co = 1;
       }
       else {
         co = 2;
       }
    }
  }
  else {
    if(b == 'S') {
      if(c == 'S') {
        co = 1;
      }
      else {
        co = 1;
      }
    }
    else {
       if(c == 'S') {
         co = 2;
       }
       else {
         co = 3;
       }
    }
  }
  cout << co << endl;
}

Measured memory_bytes: 3632
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    def main(x):
        xlen=len(x)
        if x==x[:xlen//2]*2:
            return True
        else:
            return False
    s=input()
    for i in range(2,len(s),2):
        x=s[:-i]
        if main(s[:-i]):
            print(len(s[:-i]))
            break
resolve()

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#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 endl '\n'
#define dbg(x) cout<<#x<<": "<<x<<endl
#define clr(x,v) memset(x, v, sizeof(x))
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
bool vis[1005][1005];
bool vis2[1005][1005];

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


deque<pair<pi, int>> q;
void cp()
{
    int n, m, sx, sy, ex, ey;
    cin >> n >> m >> sx >> sy >> ex >> ey;
    sx--, sy--, ex--, ey--;
    vector<string> arr(n);
    for(string &x : arr)
        cin >> x;

    int ans = INT_MAX;

    if(arr[sx][sy] != '#')
        q.push_back({{sx, sy}, 0});

    while(!q.empty())
    {
        auto node = q.front();
        q.pop_front();
        int x = node.ff.ff, y = node.ff.ss, d = node.ss;
        vis[x][y] = vis2[x][y] = true;

        if(x == ex && y == ey)
        {
            ans = min(ans, d);
            continue;
        }
        // move A
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && arr[nx][ny] == '.')
                q.push_front({{nx, ny}, d}), vis[nx][ny] = true;
        }

        // moveB
        for(int i = -2; i <= 2; i++)
        {
            for(int j = -2; j <= 2; j++)
            {
                if(!i && !j)
                    continue;
                int nx = x + i, ny = y + j;
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && !vis2[nx][ny] && arr[nx][ny] == '.')
                    q.push_back({{nx, ny}, d + 1}), vis2[nx][ny] = true;
            }
        }
    }
    if(ans == INT_MAX)
        cout << -1;
    else
        cout << ans;
}

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

Measured memory_bytes: 6688
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
D = defaultdict(int)
for a in A:
    D[a] += 1
Q = int(input())
S = sum( k*v for k, v in D.items())
for _ in range(Q):
    B, C = inpl()
    S += (C-B) * D[B]
    D[C] += D[B]
    del D[B]
    print(S)


Measured memory_bytes: 91364
#include<bits/stdc++.h>
using namespace std;
int n, k, s, a[1000], t[1000];
int ok(int x) {
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		t[i] = a[i] % x;
		tmp += t[i];
	}
	sort(t, t + n);
	int xxx = 0;
	for (int i = 0; i < n - tmp/x; i++) {
		xxx += t[i];
	}
	return xxx <= k ? x : 0;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		s += a[i];
	}
	int ans = 1;
	for (int i = 1; i * i <= s; i++) {
		if (s % i == 0) {
			ans = max(ans, ok(i));
			ans = max(ans, ok(s / i));
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define FORV(a, A) for (auto &a : A)

using namespace std;

using ll = long long;
typedef pair<int, int> p;

void Main()
{
    int N, Q;
    cin >> N >> Q;
    vector<tuple<int, int, int>> a(N);
    int t, s, x;
    REP(i, 0, N - 1)
    {
        cin >> t >> s >> x;
        t -= x;
        s -= x;
        a[i] = tie(x, t, s);
    }
    sort(a.begin(), a.end());

    int d;
    set<p> S;
    REP(i, 0, Q - 1)
    {
        cin >> d;
        S.insert(p(d, i));
    }

    vector<int> ans(Q, -1);
    int l, r;
    REP(i, 0, N - 1)
    {
        tie(x, l, r) = a[i];
        auto it = S.lower_bound(p(l, -1)); // 引数以上のうち最小の値を返す(見つからない場合end)
        while (it != S.end())
        {
            if (it->first >= r)
                break;
            ans[it->second] = x;
            S.erase(it++); // eraseして次の要素を指す
        }
    }

    FORV(a, ans)
    {
        cout << a << endl;
    }
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;
typedef pair<int,int> ii;



int main() {
  ll n;
  cin >> n;
  string s = "";
  while( n > 0 ) {
    --n;
    int c = n % 26;
    s += (char)('a'+c);
    n -= c;
    n /= 26;
  }
  reverse(ALL(s));
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3628
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Stack struct {
	xs [1000]string
	i  int
}

func (s *Stack) push(x string) {
	s.i++
	s.xs[s.i] = x
}

func (s *Stack) pop() string {
	x := s.xs[s.i]
	s.i--
	return x
}

func toInt(s string) int {
	x, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return x
}

func nextStr(sc *bufio.Scanner) string {
	sc.Scan()
	s := sc.Text()
	return s
}

func main() {
	sc := bufio.NewScanner(os.Stdin)

	stack := Stack{}

	sc.Scan()
	ss := sc.Text()
	for _, s := range strings.Split(ss, " ") {
		switch s {
		case "*":
			r := toInt(stack.pop())
			l := toInt(stack.pop())
			stack.push(strconv.Itoa(l * r))
		case "+":
			r := toInt(stack.pop())
			l := toInt(stack.pop())
			stack.push(strconv.Itoa(l + r))
		case "-":
			r := toInt(stack.pop())
			l := toInt(stack.pop())
			stack.push(strconv.Itoa(l - r))
		default:
			stack.push(s)
		}
	}
	fmt.Println(stack.pop())
}



Measured memory_bytes: 1164