akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=sc.Ia;
		var h=a.Select((x,idx)=>new long[]{idx,x}).OrderByDescending(x=>x[1]).ToArray();
		var dp=new long[n+1];
		for(int i = 0;i<h.Length;i++) {
			for(int j = i+1;j>0;j--) {
				if(dp[j]==0){
					dp[j]=Abs((j-1)-h[i][0])*h[i][1]+dp[j-1];
				}
				else{
					dp[j]=Max(Abs((j-1)-h[i][0])*h[i][1]+dp[j-1],Abs((n-1-(i-j))-h[i][0])*h[i][1]+dp[j]);
				}
			}
			dp[0]+=Abs((n-1-i)-h[i][0])*h[i][1];
		}
		Console.WriteLine("{0}",dp.Max());
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

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

class Program
{
    static LinkedList<int> value(string s)
    {
        LinkedList<int> p = new LinkedList<int>();
        char prev =s[0];
        int k = 1;
        for(int i = 1; i < s.Length; i++)
        {
            if (s[i] == prev)
                k++;
            else
            {
                p.AddLast(k);
                k = 1;
                prev = s[i];
            }
        }
        p.AddLast(k);
        return p;
    }

    static int red(LinkedList<int> p)
    {
        int z = 0;
        for(var i= p.First?.Next; i != null; i = i.Next)
        {
            int k = Math.Min(i.Value, i.Previous.Value);
            if (k != 0)
            {
                i.Value -= k;
                i.Previous.Value -= k;
                z += k;
            }
        }
        for (var i = p.First;i!=null;i=i.Next)
        {
            if (i.Value == 0) {
                if (i.Previous == null && i.Next == null)
                    break;

                else if (i.Previous == null && i.Next != null)
                {
                    i = i.Next;
                    p.Remove(i.Previous);
                }
                else if (i.Previous != null && i.Next == null)
                {
                    p.Remove(i);
                }
                else
                {
                    i.Previous.Value += i.Next.Value;
                    i = i.Previous;
                    p.Remove(i.Next.Next);
                    p.Remove(i.Next);
                }
            }
        }
        return z;
    }
    public static void Main()
    {
        string s = Console.ReadLine();
        var yt = value(s);

        int a = 0,p;
        do
        {
            p = red(yt);
            a += p;
        }
        while (p != 0);
        Console.WriteLine(2 * a);
    }
}

Measured memory_bytes: 19676
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

const int N = 1e5 + 20 ;
int n , val[N] ;
vector <int> g[N] ;

inline int best (int x) {
	for (int i = 20 ; i >= 0 ; i --)
		if (x >> i & 1) return i ;

	return -1 ;
}

void dfs (int v , int par = -1) {
	int mx = -1 ;

	for (int u : g[v]) {
		if (u == par) continue ;

		dfs(u , v) ;

		mx = max(mx , best(val[v] & val[u])) ;

		val[v] |= val[u] ;
	}

	for (int i = 0 ; i <= 20 ; i ++) {
		if (i <= mx || (val[v] & (1 << i))) {
			val[v] = ((val[v] | (1 << i)) ^ (1 << i)) ;
			continue ;
		}

		val[v] = (val[v] | (1 << i)) ;
		break ;
	}
}

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

	cin >> n ;

	for (int i = 0 , u , v ; i < n - 1 ; i ++) {
		cin >> u >> v ;
		u -- , v -- ;
		g[u].push_back(v) ;
		g[v].push_back(u) ;
	}

	dfs(0) ;

	cout << best(val[0]) << '\n' ;
}


Measured memory_bytes: 11776
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <thread>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)

using namespace std;

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

	uint64_t vals[5];
	for (uint64_t& val : vals) {
		cin >> val;
	}

	uint64_t add = 0;
	for (uint64_t& val : vals) {
		uint64_t cur_add = n / val;
		if (n % val == 0) cur_add--;
		add = max(add, cur_add);
	}

	cout << (5 + add) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int H, A, B = 0;
    cin >> H >> A;
    if (H % A != 0){
        B = 1;
    }
    cout << H / A + B << endl;
}


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

#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define OUT(a) cout << (a) << "\n"
#define ll long long
#define uint unsigned int
#define ushort unsigned short
#define ulong unsigned long

ll MOD = 10e9 + 7;
int ruiseki[1001];
double expected_value[200001];

int main() {
    ruiseki[0] = 0;
    for (int i=1; i<=1000; i++) {
        ruiseki[i] = ruiseki[i-1] + i;
    }
    int n, k;
    cin >> n >> k;
    int p;
    cin >> p;
    expected_value[0] = (1.0/static_cast<double>(p)) * ruiseki[p];
    for (int i=1; i<n; i++) {
        cin >> p;
        expected_value[i] = expected_value[i-1] + ((1.0/static_cast<double>(p)) * ruiseki[p]);
    }
    double maxxxx = 0.0;
    if (n == 1) {
        maxxxx = expected_value[0];
    } else if (n == k) {
        maxxxx = expected_value[n-1];
    } else {
        for (int i=k; i<n; i++) {
            if (maxxxx < (expected_value[i]-expected_value[i-k])) {
                maxxxx = expected_value[i]-expected_value[i-k];
            }
        }
    }
    printf("%.12lf\n", maxxxx);
    return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;
typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


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


Measured memory_bytes: 256
A, B, C = map(int, input().split())
cnt = 0
while(1):
    if A%2!=0 or B%2!=0 or C%2!=0:
        break
    A_tmp = A
    B_tmp = B
    C_tmp = C
    A = (B_tmp+C_tmp)/2
    B = (A_tmp+C_tmp)/2
    C = (A_tmp+C_tmp)/2
    cnt += 1
    if A_tmp==A and B_tmp==B and C_tmp==C:
        cnt = -1
        break
print(cnt)

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

const int MAX_Q = 100000;
bool isPrime[MAX_Q + 1];
bool isLike_2017[MAX_Q + 1];
int like_2017s[MAX_Q + 1];

void init() {
  for (int i=0; i<=MAX_Q; i++) {
    isPrime[i] = true;
    isLike_2017[i] = false;
    like_2017s[i] = 0;
  }
  isPrime[0] = isPrime[1] = false;
  for (int i=2; i<=MAX_Q; i++) {
    if (!isPrime[i]) continue;
    isPrime[i] = true;
    for (int j=2*i; j<=MAX_Q; j+=i) {
      isPrime[j] = false;
    }
  }
  for (int i=1; i<=MAX_Q; i+=2) {
    isLike_2017[i] = (isPrime[i] && isPrime[(i+2)/2]) ? true : false;
  }
  for (int i=3; i<=MAX_Q; i+=2) {
    like_2017s[i] = like_2017s[i-2];
    if (isLike_2017[i]) like_2017s[i]++;
  }
}

int solve(int l, int r) {
  int res = like_2017s[r];
  if (l != 1) res -= like_2017s[l-2];
  return res;
}

int main() {
  int Q, l, r;
  init();
  cin >> Q;
  for (int i=0; i<Q; i++) {
    cin >> l >> r;
    cout << solve(l, r) << endl;
  }
  return 0;
}


Measured memory_bytes: 1152
H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            continue
        for di, dj in d:
            ni, nj = i+di, j+dj
            if 0 <= ni < H and 0 <= nj < W and s[ni][nj] == '#':
                break
        else:
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 39408
#include <cstdio>
#include <iterator>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int main() {
    LL H, W;
    while (~scanf("%lld %lld", &H, &W)) {
          LL ans = H * W;
          for (int i = 1; i < H; i++) {
              LL a1 = i * W;
              LL rem = (H - i) * W;
              LL a2 = (H - i) / 2 * W;
              LL a3 = (H - i) * (W / 2);
              if (a2 != 0)
                 ans = min(ans, max({a1, a2, rem - a2}) - min({a1, a2, rem - a2}));
              if (a3 != 0)
                 ans = min(ans, max({a1, a3, rem - a3}) - min({a1, a3, rem - a3}));
          }
          for (int i = 1; i < W; i++) {
              LL a1 = i * H;
              LL rem = (W - i) * H;
              LL a2 = (W - i) / 2 * H;
              LL a3 = (W - i) * (H / 2);
              if (a2 != 0)
                 ans = min(ans, max({a1, a2, rem - a2}) - min({a1, a2, rem - a2}));
              if (a3 != 0)
                 ans = min(ans, max({a1, a3, rem - a3}) - min({a1, a3, rem - a3}));
          }
          printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 256
import math
import itertools
import statistics
#import numpy as np
import collections
a, b = list(map(int, input().split()))
#print(a/0.08)
price = math.ceil(a/0.08)
if b==price*0.1//1:
    ans = int(price//1)
    print(ans)
else:
    price += 1
    while math.floor(price*0.08)==a:
        if b==price*0.1//1:
            ans = int(price//1)
            print(ans)
            exit()
        price += 1

    print("-1")


# print(a/0.08*0.1//1)
#print(b/0.1)



Measured memory_bytes: 5148
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

using ll=long long;
//space complexity: O(N), N is the number of days
//time complexity: O(N), only one loop, max_element is also O(N)
ll maxHappiness(vector<vector<int>> &activities) {
    int N = activities.size();
    ll res = 0;
    if (!N) return 0;
    vector<vector<ll>> dp(N,vector<ll>(3,0));
    dp[0][0] = activities[0][0];
    dp[0][1] = activities[0][1];
    dp[0][2] = activities[0][2];
    for (int i = 1; i < N; ++ i) {
        dp[i][0] = activities[i][0] + max(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = activities[i][1] + max(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = activities[i][2] + max(dp[i-1][1], dp[i-1][0]);
    }
    return *max_element(dp[N-1].begin(), dp[N-1].end());
}

int main(){
    int N; cin>>N;
    vector<vector<int>> activities;
    activities.reserve(N);
    for (int i = 0; i < N; ++ i) {
        vector<int> row{0,0,0};
        for (auto& e : row) cin>>e;
        activities.push_back(row);
    }
    cout<<maxHappiness(activities);
    return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>road[200005],train[200005];
bool vis1[200005],vis2[200005];
int id;
int component1[200005],component2[200005],ans[200005];
void dfs1(int node)
{
    if(vis1[node]) return;
    vis1[node]=true;
    component1[node]=id;
    for(int u:road[node])
    {
        dfs1(u);
    }
    return;
}

void dfs2(int node)
{
    if(vis2[node]) return;
    vis2[node]=true;
    component2[node]=id;
    for(int u:train[node])
    {
        dfs2(u);
    }
    return;
}


main()
{
    int n,k,l;
    cin>>n>>k>>l;
    for(int i=1;i<=k;i++)
    {
        int a,b;
        cin>>a>>b;
        road[a].push_back(b);
        road[b].push_back(a);
    }
    for(int i=1;i<=l;i++)
    {
        int a,b;
        cin>>a>>b;
        train[a].push_back(b);
        train[b].push_back(a);
    }
    memset(vis1,false,sizeof vis1);
    id=1;
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            dfs1(i);
            id++;
        }
    }
    memset(vis2,false,sizeof vis2);

    id=1;
    for(int i=1;i<=n;i++)
    {
        if(!vis2[i])
        {
            dfs2(i);
            id++;
        }
    }

    map<pair<int,int>,int >mp;
    for(int i=1;i<=n;i++)
    {
        mp[{component1[i],component2[i]}]++;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<mp[{component1[i],component2[i]}]<<' ';
    }
}

Measured memory_bytes: 28288
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N;
    cin >> N;
    vector<pair<int,int>> A(N);
    for(int i = 1; i <= N; i++){
        cin >> A[i - 1].fi;
        A[i - 1].se = i;
    }
    sort(all(A));
    for(auto a : A) cout << a.se << endl;
}

Measured memory_bytes: 3988
#include<iostream>
#include<cstring>
#define N 400
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL memo[N+1][N+1];
LL sigma[N+1][N+1]; //params n and alpha
LL xpow[N+1][N+1];
LL A[N+1];
LL B[N+1];
LL mod_pow(LL base, LL exp)
{
	if(exp==0) return 1;
	if(exp&1) return (base*mod_pow(base,exp-1))%MOD;
	else return mod_pow((base*base)%MOD, exp/2);
}
LL g(LL c, LL n)
{
	if(n==0) return c==0;
	if(memo[c][n]!=-1)
		return memo[c][n];
		
	LL ans = 0;
	for(int alpha = 0; alpha <= c; alpha++)
		ans = (ans+g(c-alpha,n-1)*sigma[n][alpha])%MOD;
	return memo[c][n] = ans;
}
LL solve()
{
	LL n, c; cin >> n >> c;
	for(int i = 1; i <= n; i++)
		cin >> A[i];
	for(int i = 1; i <= n; i++)
		cin >> B[i];
	
	for(LL x = 1; x <= N; x++)
	{
		xpow[x][0] = 1;
		for(int alpha = 1; alpha <= N; alpha++)
			xpow[x][alpha] = (xpow[x][alpha-1]*x)%MOD;
	}
	
	memset(sigma,0,sizeof sigma);
	for(int i = 1; i <= n; i++)
		for(int alpha = 0; alpha <= N; alpha++)
			for(int x = A[i]; x <= B[i]; x++)
				sigma[i][alpha] = (sigma[i][alpha]+xpow[x][alpha])%MOD;
		
	memset(memo,-1,sizeof memo);
	return g(c,n);
}
int main()
{
	cout<<solve()<<endl;
	return 0;
}

Measured memory_bytes: 4096
// C - Linear Approximation
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	int N; cin>>N;
	vector<ll> B(N);
	for(int i=0; i<N; ++i){ cin>>B[i]; B[i] -= (i+1); }
	sort(B.begin(), B.end());
	ll r,l = r = B[N/2];
	if(N%2 == 0) --l;
	ll ans_l = 0, ans_r = 0;
	for(ll bi:B){
		ans_l += abs(bi - l);
		ans_r += abs(bi - r);
	}
	cout<< min(ans_l, ans_r) <<endl;
}


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

int main(int argc, char const *argv[])
{
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	int l[n];
	for (int i = 0; i < n; ++i)
	{
		cin>>l[i];
	}
	int memo[n+5]={},ans=1000000,x,y,z;
	while (memo[n]==0)
	{
		x=0;y=0;z=0;
		int tmp=-30;
		for (int i = 0; i < n; ++i)
		{
			if (memo[i]==1)
			{
				x+=l[i];
				tmp+=10;
			}
			if (memo[i]==2)
			{
				y+=l[i];
				tmp+=10;
			}
			if (memo[i]==3)
			{
				z+=l[i];
				tmp+=10;
			}
		}
		if (x>0&&y>0&&z>0)
		{
			tmp+=abs(a-x)+abs(b-y)+abs(c-z);
			ans=min(ans,tmp);
		}
		for (int i = 0; i <= n; ++i)
		{
			++memo[i];
			if (memo[i]==4)
			{
				memo[i]=0;
			}
			else
			{
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000+7;
const long long INF=-mod;

//マクロ
//型エイリアス
using ll = int;
using P=pair<long long,long long>;
using vl=vector<long long>;
//ショートカット
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,k,n) for(int i=k;i<n;i++) //半開区間
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
//入力
#define vin(v,N) for(long long i=0;i<N;i++) cin>>v.at(i)
#define lin(n) long long n;cin>>n
#define vlin(v,N) vector<long long>v(N);for(long long i=0;i<N;i++)cin>>v.at(i)

//関数
//最大公約数
long long gcd(long long m,long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m,long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x,long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//nCr
long long C(long long n, long long r);
//nCr (mod)
long long modC(long long n, long long r) {
    vector<long long> f(n+1),inv(n+1),invf(n+1);
    f[0]=f[1]=1;
    invf[0]=invf[1]=1;
    inv[1]=1;
    for (long long i=2;i<n+1;i++) {
        f[i]=(i*f[i-1])%mod;
        inv[i]=mod-((mod/i)*inv[mod%i])%mod;
        invf[i]=(inv[i]*invf[i-1])%mod;
    }
    long long cmb=f[n]*(invf[r]*invf[n-r]%mod)%mod;
    if (n>=r) return cmb;
    else return 0;
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  lin(N);lin(K);lin(r);lin(s);lin(p);
  string t;cin>>t;
  
  map<char,ll>hand;
  hand['s']=r;
  hand['p']=s;
  hand['r']=p;
  
  vector<ll>seq(K);
  
  ll res=0;
  
  rep(i,N){
    if(i-K<0){
      res+=hand[t[i]];
    }
    else{
      if(t[i]!=t[i-K]){
        res+=hand[t[i]];
        seq[i%K]=0;
      }
      else{
        seq[i%K]++;
        if(seq[i%K]%2==0)
          res+=hand[t[i]];
      }
    }
    //cout<<res<<endl;
  }
  
  cout<<res;
}

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

using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin >> n;
  map<int, int> dp;
  for(int i = 0; i < n; i++) {
    int t;
    cin >> t;
    dp[t]++;
  }
  int ret = 0;
  while(dp.size()) {
    int x = dp.rbegin()->first;
    if(--dp[x] == 0) dp.erase(x);
    for(int a = 30; a >= 0; a--) {
      int want = (1<<a) - x;
      if(dp.count(want)) {
        ret++;
        if(--dp[want] == 0) {
          dp.erase(want);
        }
        break;
      }
    }
  }
  cout << ret << endl;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
#define ll long long int 
#define pb push_back
#define mp make_pair
#define ff first
#define se second
#define MAX 1000001
#define MAXN 300010
#define mod 1000000007 
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,x,y,z;
    string s;
    cin>>s;
    x=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3])-'0';
    y=(s[5]-'0')*10+(s[6]-'0');
    z=(s[7]-'0')*10+(s[8]-'0');
    if((y<=04 && z<=30)||(y<=04 && z<=31)){
        cout<<"Heisei";
    }
    else{
        cout<<"TBD";
    }
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Combination{
	constexpr static int atcoder_mod = 1000000007;
	vector<ll> fac,finv,inv;
public:
	Combination(ll N){
		fac.resize(N+1);
		finv.resize(N+1);
		inv.resize(N+1);
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for(int i=2;i<=N;i++){
			fac[i] = fac[i-1] * i % atcoder_mod;
			inv[i] = atcoder_mod - inv[atcoder_mod%i] * (atcoder_mod/i) % atcoder_mod;
			finv[i] = finv[i-1] * inv[i] % atcoder_mod;
		}
	}
	ll Caluclation(ll n,ll r){
		if(n < r) return 0;
		if (n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n-r] % atcoder_mod) % atcoder_mod;
	}
	ll GetFInv(ll i){
		return finv[i];
	}
};

ll safemod(ll a,ll m){
	return (a%m+m)%m;
}

ll powermod(ll a,ll b,ll m){
	if(b==0){
		return 1LL;
	}
	if(b%2){
		return (a*powermod(a,b-1LL,m))%m;
	}
	return powermod((a*a)%m,b/2LL,m);
}

ll extend_gcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x = 1;
		y = 0;
		return a;
	}
	ll d = extend_gcd(b,a%b,y,x);
	y -= a/b * x;
	return d;
}

ll modinv(ll a,ll m){
	ll x,y;
	extend_gcd(a,m,x,y);
	return safemod(x,m);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in(),A=in(),B=in();
	string S=in<string>();

	int CA=0,CB=0;

	REP(i,N){
		if(S[i]=='a'){
			if(CA+CB<A+B){
				out("Yes");
				CA++;
			}
			else out("No");
		}
		else if(S[i]=='b'){
			if(CA+CB<A+B && CB<B){
				out("Yes");
				CB++;
			}
			else out("No");
		}
		else out("No");
	}

	return 0;
}


Measured memory_bytes: 848
import java.util.*;

public class Main {
    long MOD = 1000000007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int minCount = 0;
        int absmin = Math.abs(a[0]);
        boolean zero = false;
        for (int i = 0; i < n; i++) {
            if (a[i] < 0)
                minCount++;
            absmin = Math.min(absmin, Math.abs(a[i]));
            if (a[i] == 0)
                zero = true;
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.abs(a[i]);
        }
        if (!zero && minCount % 2 != 0) {
            ans -= 2L * absmin;
        }

        System.out.println(ans);

    }
}

Measured memory_bytes: 50736
readlines[0...-1].map { |s| s.split.map &:to_i }.each { |h,w|
    puts ("#"*w<<"\n")
    (1...h-1).each{ print "#","."*(w-2),"#\n" }
    puts ("#"*w<<"\n") if h > 1
    puts
}

Measured memory_bytes: 8732
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
    // Your code here!
    char s[5], s1[3]={}, s2[3]={};
    
    scanf("%s", s);
    
    s1[0]=s[0];
    s1[1]=s[1];

    s2[0]=s[2];
    s2[1]=s[3];

    if(00==atoi(s1) || 12<atoi(s1)){
        if(00==atoi(s2) || 12<atoi(s2)) printf("NA");
        else printf("YYMM");
    }else{
        if(00==atoi(s2) || 12<atoi(s2)) printf("MMYY");
        else printf("AMBIGUOUS");
    }
}


Measured memory_bytes: 128
/*
 push yourself until you succeed
*/
#include <bits/stdc++.h>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define set_zero(a) memset(a,0,sizeof(a));
#define ll long long int
#define PI 2 * acos(0.0)
#define MAX 10000000000000000
#define in(a) scanf("%d",&a);
#define out(a) printf("%d",a);
#define INF 1000000 
#define M 1000000007
#define pi 3.14159265 
using namespace std; 
int main(){ 
   fast_io
   ll ans = 0;
   ll k;
   cin>>k;
   for(ll i = 1;i<=k;i++){
       for(ll j = 1;j<=k;j++){
           for(ll m = 1;m<=k;m++){
               ll y = __gcd(i,j);
               ans += __gcd(y,m);
           }
       }
   }
   cout<<ans<<endl;
   return 0;
} 

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

using namespace std;

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

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  int l = 0, r = 1e9;
  while (l + 1 < r) {
    int m = l + r >> 1;
    long long kk = k;
    for (int i = 0; i < n; ++i) {
      kk -= (a[i] - 1) / m;
    }
    if (kk >= 0) {
      r = m;
    } else {
      l = m;
    }
  }
  cout << r;

  return 0;
}


Measured memory_bytes: 3932
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int N=110;
int a[N];

int main()
{
	int n;
	cin>>n;
	
	for(int i=0; i<n-1; i++) cin>>a[i];
	
	long long sum=a[0]+a[n-2];
	for(int i=0; i<n-2; i++)
		sum+=min(a[i],a[i+1]);
	cout<<sum<<endl;
	
	return 0;
}

Measured memory_bytes: 256
export class Main {
  static main(input: string): string {
    const tmp: string[] = input.split("\n");
    const [x, y, z]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    return `${z} ${x} ${y}`;
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 7372
import sys
input = sys.stdin.buffer.readline

n = int(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((x, y, i))

import heapq
def prim_heap():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
        used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not  used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res

P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

print(prim_heap())

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

long long n,ans,dp[10000100],hxt[10000100];

void dfs(long long a)
{
	if(a<=10000000)
	{
		ans+=dp[a];
		ans+=hxt[a];
		return;
	}
	ans++;
	dfs(a/2);
	dfs(a/2);
}

int main()
{
	scanf("%lld",&n);
	if(n==1)
	{
		printf("1\n");
		return 0;
	}
	dp[2]=1,dp[3]=1;hxt[2]=2,hxt[3]=2;
	for(int i=4;i<=10000000;i++)
	{
		dp[i]=dp[i/2]*2+1;
		hxt[i]=hxt[i/2]*2;
	}
	dfs(n);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 156544
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
using namespace std;

int main(){
    int n;
    string s;
    map<string, int> mp;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        mp[s] += 1;
    }
    cout << mp.size() << endl;
    return 0;
}


Measured memory_bytes: 19260
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true;
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }

    // 全頂点が訪問済みになるまで探索
    int count = 0;
    seen.assign(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue; // v が探索済みだったらスルー
        dfs(G, v); // v が未探索なら v を始点とした DFS を行う
        ++count;
    }
    cout << count - 1 << endl;
}

Measured memory_bytes: 9596
//#define M_PI 3.14159265358979323846
#define _USE_MATH_DEFINES

//#define _GLIBCXX_DEBUG
//#define all(x) (x).begin(),(x).end()
#pragma comment(linker,"/STACK:256000000")

#include <bits/stdc++.h>

#define TASK ""
#define sqr(x) ((x)*(x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll INFLL = numeric_limits<ll>::max();
const ll INFINT = numeric_limits<int>::max();
const ld EPS = 1e-7;
const ll MOD = 1000000000;
const ll MAXN = 123456;

void run()
{
    string s;
    ll k;
    cin >> s >> k;
    for (int i = 0; i < s.size(); i++)
    {
        s[i] -= 'a';
        if (s[i] != 0)
            if (26 - s[i] <= k)
            {
                k -= (26 - s[i]);
                s[i] = 0;
            }
    }
    s[s.size() - 1] += k % 26;
    s[s.size() - 1] %= 26;
    for (int i = 0; i < s.size(); ++i)
    {
        s[i] += 'a';
    }
    cout << s;
}

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

#ifdef LOCAL
//#define STRESS
#ifdef STRESS
    freopen("input.txt", "w", stdout);
    cout << "1000 50\n";
    for (int i = 0; i < 999; i++)
    {
        for (int j = 0; j < 999; j++) cout << ".";
        cout << "X\n";
    }
    for (int j = 0; j < 1000; j++)
        if (j != 1000 / 50)cout << "X";
        else cout << ".";
    return 0;

#endif
    if (strcmp(TASK, "-") != 0)
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#else
    if (strcmp(TASK, "")   != 0)
    {
        freopen(TASK".in", "r", stdin)  ;
        freopen(TASK".out", "w", stdout)  ;
    }
#endif
    run();

    return 0;
}

Measured memory_bytes: 640
# n , m , l = map(int , input().split())

# list_n = list(map(int , inpuut().split()))<Paste>

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]


A, B, C = map(int, input().split())

n = 0
while A % 2 == 0 and B % 2 == 0 and C % 2 == 0:
    if A == B and B == C:
        n = -1
        break

    An = (B + C) // 2
    Bn = (A + C) // 2
    Cn = (A + B) // 2

    A = An
    B = Bn
    C = Cn
    n += 1

print(n)


Measured memory_bytes: 9188
#include<stdio.h>

int n, a[50];

int solve(int i, int m){

        if(m == 0) return 1;
        if( i >= n)  return 0;
        int res = solve(i + 1, m)  || solve(i + 1, m - a[i]);

        return res;
}

int main()
{
    int i, m, q;

    scanf("%d", &n);

    for(i = 0; i < n; i++){

        scanf("%d", &a[i]);

    }
    scanf("%d", &q);

    for(i = 0; i < q; i++){

        scanf("%d", &m);
        if(solve(0, m)) printf("yes\n");
        else printf("no\n");

    }

    return 0;
}


Measured memory_bytes: 1992
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    A = list(map(int, input().split()))

    cnt = {}
    for a in A:
        if a not in cnt:
            cnt[a] = 1
        else:
            cnt[a] += 1

    num_cnt_even = 0
    num_cnt_odd = 0
    for v in cnt.values():
        if v % 2 == 0:
            num_cnt_even += 1
        else:
            num_cnt_odd += 1

    if num_cnt_even % 2 == 0:
        print(num_cnt_even + num_cnt_odd)
    else:
        print(num_cnt_even + num_cnt_odd - 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 64760
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;

const ll mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int K, S, ans = 0;
  cin >> K >> S;
  for(int X = 0; X <= K; X++) {
    for(int Y = 0; Y <= K ; Y++) {
      int Z = S - X - Y;
      if(0 <= Z && Z <= K) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
/*
** 通过先序遍历和中序遍历，重建树，并输出后序遍历
** 本例题的解法并没有生成树，而是一次到位生成了后序遍历
*/

# include <iostream>
# include <algorithm>
# include <vector>
# include <cstdio>
using namespace std;

int n, pos;
vector<int> pre, in, post;

void init() {
    scanf("%d", &n);
    int node;
    for (int i = 0; i < n; i++) {
        scanf("%d", &node);
        pre.push_back(node);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &node);
        in.push_back(node);
    }
}

void rec(int l, int r) {
    if (l >= r)
        return;
    int root = pre[pos++];
    int m = distance(in.begin(), find(in.begin(), in.end(), root));
    rec(l, m);
    rec(m + 1, r);
    post.push_back(root);
}

void solve() {
    pos = 0;
    rec(0, pre.size());
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", post[i]);
    }
    printf("%d\n", post[n - 1]);
}

int main() {
    // freopen("infile", "r", stdin);
    // freopen("outfile", "w", stdout);
    init();
    solve();
    return 0;
}


Measured memory_bytes: 3296
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  int N;
  cin >> N;
  vector<vector<pair<int, int64_t>>> G(N + 1);
  rep(i, N - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    G[a].emplace_back(b, c);
    G[b].emplace_back(a, c);
  }
  int Q, K;
  cin >> Q >> K;

  // dijkstra
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>,
                 greater<pair<int64_t, int>>>
      que;
  que.emplace(0, K);
  vector<int64_t> D(N + 1, INT64_MAX);
  D[K] = 0;
  while (!que.empty()) {
    int64_t dist;
    int v;
    tie(dist, v) = que.top();
    que.pop();
    if (D[v] < dist) continue;

    for (auto& nv : G[v]) {
      int64_t ndist = dist + nv.second;
      if (D[nv.first] <= ndist) continue;
      D[nv.first] = ndist;
      que.emplace(ndist, nv.first);
    }
  }

  rep(i, Q) {
    int x, y;
    cin >> x >> y;
    cout << D[x] + D[y] << endl;
  }
  return 0;
}

Measured memory_bytes: 11120
def main():
    n = int(input())
    s = input()
    r, g, b = [], [], []
    for i in range(n):
        t = s[i]
        if t == 'R':
            r.append(i)
        elif t == 'G':
            g.append(i)
        else:
            b.append(i)
    ans = len(r) * len(g) * len(b)

    for i in range(1, n // 2 + 1):
        for k in range(n):
            try:
                if {s[k], s[k + i], s[k + 2 * i]} == {'R', 'G', 'B'}:
                    ans -= 1
            except IndexError:
                break
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9312
i = list(map(int,input().split()))
k = int(input())
p = 0
q = 0
while i[0] >= i[1]:
    i[1] = 2 * i[1] 
    p = p + 1

while i[1] >= i[2]:
    i[2] = 2 * i[2]
    q = q + 1
r = p + q
if r <= k:
    print("Yes")
else:
    print("No")

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

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=1e6+10;
int L[MAXN],R[MAXN];
int head[MAXN],preh[MAXN],pret,tot;
int n,x[MAXN],y[MAXN],nd;P dsp[MAXN];
struct edge{int nxt,to;}e[MAXN<<2];
void add(int x,int y)
{e[++tot]=(edge){head[x],y};head[x]=tot;}

int cnt,top,st[MAXN],bel[MAXN];
int idx,low[MAXN],dfn[MAXN],vis[MAXN],ist[MAXN];
void tarjan(int x)
{
    st[++top]=x;
    ist[x]=vis[x]=1;
    low[x]=dfn[x]=++idx;
    
    for(int i=head[x];i;i=e[i].nxt)
        if(!vis[e[i].to]) 
            tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
        else if(ist[e[i].to])
            low[x]=min(low[x],low[e[i].to]);
    if(low[x]==dfn[x])
    {
        cnt++;
        while(st[top]!=x)
            bel[st[top]]=cnt,ist[st[top]]=0,top--;
        bel[st[top]]=cnt;ist[st[top]]=0;top--;
    }
}

#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r
int id[MAXN];
void build(int k,int l,int r)
{
    if(l==r)
    {id[k]=(dsp[l].Y)>n?dsp[l].Y-n:dsp[l].Y+n;return;}
    id[k]=++nd;build(lc);build(rc);
    add(id[k],id[ls]);add(id[k],id[rs]);
}
void upd(int a,int b,int x,int k,int l,int r)
{
    if(a>b) return;
    if(a<=l&&r<=b){add(x,id[k]);return;}
    if(a<=mid) upd(a,b,x,lc);
    if(b>mid) upd(a,b,x,rc);
}

bool check(int itv)
{
    // cout<<itv<<endl;
    int cur=1;
    for(int i=1;i<=2*n;i++)
    {
        while(cur<=2*n&&dsp[cur].X-dsp[i].X<itv) cur++;
        R[i]=cur-1;
    }
    cur=2*n;
    for(int i=2*n;i>=1;i--)
    {
        while(cur>=1&&dsp[i].X-dsp[cur].X<itv) cur--;
        L[i]=cur+1;
    }
    // for(int i=1;i<=2*n;i++)
    //     cout<<i<<" "<<L[dsp[i].Y]<<" "<<R[dsp[i].Y]<<endl;
    
    tot=pret;cnt=top=idx=0;
    for(int i=1;i<=nd;i++) 
        head[i]=preh[i],vis[i]=ist[i]=bel[i]=low[i]=dfn[i]=0;
    for(int i=1;i<=2*n;i++)
        upd(L[i],i-1,dsp[i].Y,1,1,2*n),upd(i+1,R[i],dsp[i].Y,1,1,2*n);
    for(int i=1;i<=nd;i++)
        if(!vis[i]) tarjan(i);
    // for(int i=1;i<=nd;i++) cout<<bel[i]<<" ";
    // cout<<endl;
    
    for(int i=1;i<=n;i++)
        if(bel[i]==bel[i+n]) return false;
    return true;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]),
        dsp[++nd]=P(x[i],i),dsp[++nd]=P(y[i],i+n);
    sort(dsp+1,dsp+nd+1);nd=2*n;build(1,1,2*n);
    pret=tot;for(int i=1;i<=nd;i++) preh[i]=head[i];
    
    int l=0,r=1e9;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(check(m)) l=m+1;
        else r=m-1;
    }
    printf("%d",r);
    return 0;
}

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

int main() {
  int a,b,c,x; cin >>a >>b >>c >>x;
  int cnt = 0;
  
  for (int i=0; i<=a; i++){
    for (int j=0; j<=b; j++){
      for (int k=0; k<=c; k++){
        if (500*i+100*j+50*k == x){
          cnt++;
        }
      }
    }
  }
  
  cout <<cnt <<endl;
  
  /*
  if (ans) cout <<"Yes" <<endl;
  else cout <<"No" <<endl;
  */
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string> //文字列
#include <iomanip> //doubleの桁数指定 setprecision()
#include <list> //前後に数値を入れれる配列
#include <map> //map
#include <vector> //vecror

#define REP(i,m,n) for(ll i = (ll) (m);i < (ll) (n);i++) //forの短縮
#define rep(i,n) REP(i,0,n) //REPが0の時
#define ll long long int

using namespace std;

double PI = acos(-1); //円周率
ll mod = 1e9 + 7;


//提出コード

vector<ll> IP;
ll q, L[100010], r[100010];

bool IsPrime(ll num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (ll i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}




int main() {

	cin >> q;

	rep(i,100001){
		if (IsPrime(i)) {
			if (IsPrime((i + 1) / 2)) {
				if (i != 2) {
					IP.push_back(i);
				}
			}
		}
	}

	rep(i, q) {
		cin >> L[i] >> r[i];
		
	}
	rep(i, q) {
		int cnt = 0;
		for (auto itr = IP.begin(); itr != IP.end(); itr++) {
			if (L[i] <= *itr && r[i] >= *itr) cnt++;
		}
		cout << cnt << endl;
	}
	




	return 0;
}



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

using i64 = int_fast64_t;
using f64 = double;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n;
    vector<string> s(n);
    for (auto& e : s) cin >> e;

    i64 ans = -1;
    for (i64 i = 0; i < n; i++) {
        vector<i64> depth(n, -1);
        depth[i] = 1;
        queue<i64> q;
        q.push(i);
        i64 can = 0;
        while (!q.empty()) {
            i64 t = q.front(); q.pop();

            bool suc = true;
            for (i64 j = 0; j < n; j++) {
                if (s[t][j] == '0') continue;
                if (depth[j] != -1) {
                    if (abs(depth[t] - depth[j]) == 1) continue;
                    suc = false;
                    break;
                }
                depth[j] = depth[t] + 1;
                can = max(can, depth[j]);
                q.push(j);
            }

            if (!suc) {
                can = 0;
                break;
            }
        }

        if (can) ans = max(ans, can);
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main()
        {
            int a = int.Parse(Console.ReadLine());
            
            int b = int.Parse(Console.ReadLine());

            a = a * a;
            Console.Write(a - b);
        }
    }
}


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

int main(){
    int n;
    cin >> n;
    long long x;
    cin >> x;
    for(int i = 1; i < n; i++){
        long long a;
        cin >> a;
        x ^= a;
    }
    long long y = x ^ x;
    if(x == y){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main() {
  int N;
  cin >> N;
  vector<int>a(N);
  for(int i=0; i<N; i++){
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  int Alice=0;
  int Bob=0;
  for(int i=0; i<N; i++){
    if(i%2 == 0){
      Alice += a.at(i);
    }else if(i%2 == 1){
      Bob += a.at(i);
    }
  }
  int ans = Alice - Bob;
  cout << ans << endl;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
account=0
wacount=0

a=[0]*n

for i in range(m):
  p,s=input().split()
  p=int(p)
  p-=1
  if a[p]==-1:
    continue
  if s=="AC":
    account+=1
    wacount+=a[p]
    a[p]=-1
  else:
    a[p]+=1

print(account, wacount)


Measured memory_bytes: 3828
import java.util.*;
import java.awt.Point;

public class Main{

   public static void main(String[] args){
      new Main().solve();  
   }

   public void solve(){
      Scanner scanner = new Scanner(System.in);
      long H = scanner.nextLong();
      long W = scanner.nextLong();
      int N = scanner.nextInt();

      Point[] point = new Point[N];
      for(int i=0; i<N; i++){
         int row = scanner.nextInt();
         int col = scanner.nextInt();
         point[i] = new Point(col, row);
      }

      HashMap<Point,Integer> hashmap = new HashMap<Point,Integer>();

      for(int i=0; i<N; i++){
         for(int y=-1; y<2; y++){
            for(int x=-1; x<2; x++){
               Point p = new Point(point[i].x+x, point[i].y+y);
               if(hashmap.get(p) == null){
                  hashmap.put(p,1);
               }else{
                  hashmap.put(p,hashmap.get(p)+1);
               }
            }
         }
      }

      long[] counter = new long[10];
      for(int i=0; i<counter.length; i++){
         counter[i] = 0;
      }
      long sum = (H-2)*(W-2);
      for(HashMap.Entry<Point,Integer> map : hashmap.entrySet()){
         if(1<map.getKey().x && map.getKey().x<W && 1<map.getKey().y && map.getKey().y<H){
            counter[map.getValue()]++;
            sum--;
         }
      }
      counter[0] = sum;
      for(int i=0; i<counter.length; i++){
         System.out.println(counter[i]);
      }

      
  }
}
        
        

Measured memory_bytes: 170096
from copy import deepcopy
m = 43
table = [[] for i in range(43)]
table[0].append(set([0]))
table[1].append(set([1]))
for i in range(2,m):
    table[i].append(set([i]))
    for j in range(1, i):
        k = i-j
        for t in table[j]:
            if k in t:
                continue
            tmp = deepcopy(t)
            tmp.add(k)
            table[i].append(tmp)
    l = max(len(a) for a in table[i])
    tmp = []
    for a in table[i]:
        if len(a) == l:
            tmp.append(a)
    table[i] = tmp
table = [max(len(j) for j in i) for i in table]

n = int(input())
def factorization(n):
    ret = {}
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            ret[i] = ret.get(i, 0) + 1
            n //= i
    if n != 1:
        ret[n] = ret.get(n, 0) + 1
    return ret

d = factorization(n)
ans = 0
for k,v in d.items():
    ans += table[v]
print(ans)


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

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  
  int result;
  int count = 0;
  int start = A > B ? B : A;
  for (int i = start; i > 0; i--) {
    if (A % i == 0 &&
        B % i == 0) {
      count++;
      if (count == K) {
        result = i;
        break;
      }
    }
  }
   cout << result;
}


Measured memory_bytes: 256