akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

vector<int> makeTable(string &s){
    int n = s.size();
    vector<int> ret(n+1);
    ret[0] = -1;
    int j = -1;
    for (int i=0; i<n; i++) {
        while (j >= 0 && s[i] != s[j]) j = ret[j];
        ret[i+1] = ++j;
    }

    return ret;
}

vector<int> kmp(string &str, string &word){
    vector<int> table = makeTable(word), ret;
    int m = 0, i = 0, n = str.size();
    while(m + i < n){
        if(word[i] == str[m+i]){
            if(++i == (int)(word.size())){ 
                ret.emplace_back(m);
                m = m + i - table[i];
                i = table[i];
            }
        }
        else{
            m = m + i - table[i];
            if (i > 0) i = table[i];
        }
    }
    
    return ret;
}

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

    string s, t; cin>>s>>t;
    int m = t.size();

    string s2 = s;
    while((int)s2.size() <= m * 2) s2 += s;

    int n = s2.size();
    s2 += s2;
    auto v = kmp(s2, t);

    vector<bool> sindex(n, false);
    for(auto i : v){
        sindex[i % n] = true; 
    }

    int ans = 0;
    vector<bool> visited(n, false);
    for(int i=0; i<n; i++){
        if(!sindex[i] || visited[i]) continue;
 
        visited[i] = true;
        int sum = 1;
 
        int nxt = i;
        while(1){
            nxt = (nxt + m) % n;
            if(nxt == i){
                cout << -1 << endl;
                return 0;
            }
            else if(sindex[nxt] && !visited[nxt]){
                sum++;
                visited[nxt] = true;
            }
            else{
                break;
            }
        }
 
        int pre = i;
        while(1){
            pre = (pre - m + n) % n;
            if(pre == i){
                cout << -1 << endl;
                return 0;
            }
            else if(sindex[pre] && !visited[pre]){
                sum++;
                visited[pre] = true;
            }
            else{
                break;
            }
        }
 
        chmax(ans, sum);
    }
 
    cout << ans << endl;
}


Measured memory_bytes: 26072
s = input()
t = input()

ns = len(s)
nt = len(t)

ans = 10000000
for i in range(ns-nt+1):
    tmp = 0
    for j in range(nt):
        if s[i+j] != t[j]:
            tmp += 1
    ans = min(tmp, ans)

print(ans)

Measured memory_bytes: 9056
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int is[maxn],fac[maxn],prime[maxn],n,cnt,pre[maxn];
void factor() {
	is[1]=1;
	fac[1]=1;
	for(int i=1; i<=n; i++) {
		if(!is[i]) {
			prime[++cnt]=i;
			fac[i]=2;
			pre[i]=1;
		}
		for(int j=1; j<=cnt&&i*prime[j]<=n; j++) {
			is[prime[j]*i]=1;
			if(i%prime[j]) {
				fac[i*prime[j]]=2*fac[i];
				pre[i*prime[j]]=1;
			} else {
				pre[i*prime[j]]=pre[i]+1;
				fac[i*prime[j]]=fac[i]/(pre[i]+1)*(pre[i]+2);
				break;
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	factor();
	long long ans=0;
	for(int i=1;i<n;i++){
		ans+=fac[i];
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(){
  int cnt=0;
  string W,T;
  cin >> W;
  while(1){
      cin >> T;
      if(T == "END_OF_TEXT") break;
      for(auto &x : T) x=tolower(x);
      if( T == W) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3180
using System;

namespace CSharp_0426
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            if (a == "A") Console.WriteLine("T");
            else if (a == "T") Console.WriteLine("A");
            else if (a == "C") Console.WriteLine("G");
            else if (a == "G") Console.WriteLine("C");
            else Console.WriteLine("not found."); ;
        }
    }
}

Measured memory_bytes: 11092
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << 63) - 1;
const LL mod = 1000000007;
const int N = 1e5 + 5;
const double Pi = acos(-1.0);
const int maxn = 2e5 + 5;
priority_queue<int>Q;
int main() {
#ifdef local
    freopen("in", "r", stdin);
    //  freopen("w","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int res = 0;
    int x;
    for(int i = 0; i < 2 * n; i++){
        cin>>x;
        Q.push(x);
    }
    for(int i = 0 ; i < 2 * n;i++){
        x = Q.top();
        Q.pop();
        res += (i&1) ? x : 0;
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	auto E = abs(B - A);

	auto ans = "NO";
	for (auto i = 0; i <= N - 1; i += 2)
	{
		auto minE = (-D + C) * i / 2 + (N - 1 - i) * C;
		auto maxE = (D - C) * i / 2 + (N - 1 - i) * D;
		if (minE <= E && E <= maxE)
		{
			ans = "YES";
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;



int main(){
  ios_base::sync_with_stdio(false);

  int x, a, b;

  cin >> x >> a >> b;

  x -= a;
  x %= b;

  cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue = BinaryHeap!(Array!long, "a<b");
// dfmt on

void main()
{
    long N = lread();
    long sum;
    while (N)
        sum += N % 10, N /= 10;
    writeln(sum == 1 ? 10 : sum);
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
       
       if(A<=8 && B<=8){
           System.out.println("Yay!");
       }
       
       else{
           System.out.println(":(");
       }
    }
}

Measured memory_bytes: 23764
N, T = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)])

dp = [[0] * N for _ in range(T)]

for i in range(1, T):
    for j in range(N-1):
        if AB[j][0] <= i:
            dp[i][j] = max(dp[i][j-1], dp[i-AB[j][0]][j-1] + AB[j][1])
        else:
            dp[i][j] = dp[i][j-1]

ans = 0
for j in range(1, N):
    ans = max(ans, dp[-1][j-1] + AB[j][1])

print(ans)

Measured memory_bytes: 145828
#include<iostream>
#include<cstdio>

using namespace std;

int left(int i) {
	return 2 * i;
}
int right(int i) {
	return 2 * i + 1;
}

int H;
int C[1000000];
void maxHeapify(int i) {
	int l = left(i);
	int r = right(i);
	int largest;
		// 左の子、自分、右の子で値が最大のノードを選ぶ
	if (l <= H && C[l] > C[i]) {
		largest = l;
	}
	else {
		largest = i;
	}
	if (r <= H && C[r] > C[largest]) {
		largest = r;
	}

	if (largest != i) { // i の子の方が値が大きい場合
		swap(C[i], C[largest]);//A[i] と A[largest] を交換
		maxHeapify(largest); // 再帰的に呼び出し
	}
}

void buildMaxHeap(int A[]) {
	for (int i = H / 2;i >= 1; i--) {
		maxHeapify(i);
	}
}

int main() {
	cin >> H;

	for (int i = 1; i <= H;i++) {
		cin >> C[i];
	}

	/*for (int i = H / 2; i > 0; i--) {
		maxHeapify(i);
	}

	for (int i = 1; i <= H; i++) {
		cout << C[i] << " ";
	}*/

	buildMaxHeap(C);

	for (int i = 1; i <= H; i++) {
		cout <<" "<< C[i];
	}
	
	cout << endl;

	return 0;
}


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


void solve(long long N, long long M, std::vector<long long> A){
  long long as = accumulate(A.begin(), A.end(), 0);
  long long ans =  (N >= as) ? N - as : -1;
  cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, M, std::move(A));
    return 0;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
typedef long long ll;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl

 
int main()
{ 
	FIN;
	
	#ifdef input
		freopen("test2.txt", "r", stdin);
	#endif
	
	int n, k;
	cin >> n >> k;
	vector <ll> v(n);
	forn(i,n) cin >> v[i];
	
	vector <ll> dp(100005,0), aux(100005,0), prefix(100005,0);
	int modu = 1000000007;
	forn(i,v[0]+1) dp[i]=1;
	prefix[0]=dp[0];
	forr(i,1,k+1) prefix[i]=prefix[i-1]+dp[i];
	int suma = v[0];
	forr(i,1,n)
	{
		forn(j,k+1)
		{
			aux[j]=prefix[j];
			aux[j]%=modu;
			if(j-v[i] > 0) aux[j]+=modu-prefix[j-v[i]-1];
			aux[j]%=modu;
		}
		forn(j,k+1) 
		{
			dp[j]=aux[j];
			if(j==0)
			{
				prefix[j]=aux[j];
				aux[j]=0;
				continue;
			}
			prefix[j]=aux[j]+prefix[j-1];
			prefix[j]%=modu;
			aux[j]=0;
		}
		//forn(j,k+1) cout << dp[j] << " "; cout << endl;
	}
	cout << dp[k] << endl;
	return 0;
}


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

int main(){
	// sengen
	string s;
	// nyuryoku
	cin >> s;
	// keisan
	if(s[0] == s[1] && s[1] == s[2]){
		cout << "No";
	}else{
		cout << "Yes";
	}
	// syutsuryoku
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        String enki = sc.next();
        
        if(enki.equals("A")){
            System.out.println("T");
            
        }else if(enki.equals("T")){
            System.out.println("A");
            
        }else if(enki.equals("G")){
            System.out.println("C");
            
        }else if(enki.equals("C")){
            System.out.println("G");
        }
        
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
bool kt(string a,int n){
	if(n%2!=0){
		return false;
	}else{
		for(int i=0;i<n/2;i++){
			if(a[i]!=a[n/2+i]){
				return false;
			}
		}
		return true;
	}
}
int main(){
	int n;
	cin>>n;
	string a;
	cin>>a;
	if(kt(a,n)){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<string> s(n);
    VI t(n);
    REP(i,n){
        cin>>s[i]>>t[i];
    }
    string x;
    cin>>x;
    int res=0;
    for (int i=n-1;i>=0;i--){
        if (s[i]==x) break;
        res+=t[i];
    }
    printf("%d\n",res);
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) begin(c), end(c)
template<class T> void read(T& x){ cin>>x; }
void read(int& x){ scanf("%d", &x); }
void read(int64_t& x){ scanf("%lld", &x); }
void read(double& x){ scanf("%lf", &x); }
template<class T, class U, class... V>
void read(T& x, U& y, V&... z){ read(x); read(y, z...); }

int main(){
    int a,b;
    read(a,b);
    if(b >= a) printf("%d", a);
    else printf("%d",a-1);
}

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

long long n, a = 1, b = 0;

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) {
    int q, x;
    cin >> q >> x;
    if(q == 1)
      a *= x, b *= x;
    else if(q == 2)
      b += x;
    else
      b -= x;
  }

  cout << -b << " " << a << endl;
  return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> res(n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		res[a]++; res[b]++;
	}
	bool ok = true;
	rep(i, n) if (res[i] % 2 == 1) ok = false;
	if (ok) printf("%s\n", "YES");
	else printf("%s\n", "NO");
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<string>
#include<string.h>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {
	int a, b, c, d;
	cin >> a;
	int ans = 0;
	int l, r;
	rep(i, a) {
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
	return 0;
}

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

int N;
const int MAX_N = 2.0e5 + 100;
ll A[MAX_N];

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

    ll acc[N+1];
    acc[0] = 0;
    for (int i = 0; i < N; i++) acc[i+1] = acc[i] + A[i];

    map<ll, ll> mp;
    for (int i = 0; i <= N; i++) {
        mp[acc[i]]++;
    }

    ll ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        ll val = itr->second;
        ans += val*(val-1)/2;
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int L = A + B;
    int R = C + D;
    if (L > R) {
        cout << "Left" << endl;
    } else if (L < R) {
        cout << "Right" << endl;
    } else if (L == R) {
        cout << "Balanced" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字数の入力
		int N = sc.nextInt();
		// 文字列の入力
		String S = sc.next();
        int count = 0; 
        
		
		// replaceでABCを抜く
		S = S.replace("ABC","");
        count = ( N - S.length() )/3; 
        System.out.println(count);
	}
}

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

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

	cin >> N >> K >> S;

	string ans = S;
	char c = tolower( S[K - 1] );
	ans[K - 1] = c;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	int n,k;
	cin>>n>>k;
	double s=0;
	loop(i,1,n+1){
		int t=i;
		double a=1./n;
		while(t<k){
			t*=2;a/=2;
		}
		s+=a;
	}
	cout<<shosu(9)<<s<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    char x;
    cin >> x;
    int a = x-'a';
    if(0 <= a && a < 26) cout << 'a' << endl;
    else cout << 'A' << endl;
}

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

using namespace std;
#define int int64_t
#define fi first
#define se second
#define endl '\n'
vector<vector<int>> g;
vector<int> color;
vector<int> was;

void dbfs(int v, int d, int col) {
     queue<pair<int, int>> q;
     q.push({d, v});
     while (q.size()) {
          auto fr = q.front();
          int v = fr.second;
          int len = fr.first;
          q.pop();
          was[v] = max(was[v], len);
          if (color[v] == 0) {
               color[v] = col;
          }
          for (auto u : g[v]) {
               if (was[u] < len - 1) {
                    q.push({len - 1, u});
               }
          }
     }
}

signed main()
{
     srand(time(nullptr));
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int n, m, q;
     cin >> n >> m;
     g.resize(n);
     was.resize(n, -1);
     color.resize(n, 0);
     for (int i = 0; i < m; ++i) {
          int a, b;
          cin >> a >> b;
          a--, b--;
          g[a].push_back(b);
          g[b].push_back(a);
     }
     cin >> q;
     vector<pair<int, pair<int, int>>> qu(q);
     
     for (int qq = 0; qq < q; ++qq) {
          int v, d, c;
          cin >> v >> d >> c;
          v--;
          qu.push_back({v, {d, c}});
     }
     reverse(qu.begin(), qu.end());
     for (int qq = 0; qq < q; ++qq) {
          int v = qu[qq].first;
          int d = qu[qq].second.first;
          int col = qu[qq].second.second;
          dbfs(v, d, col);
     }
     for (int i = 0; i < n; ++i) {
          cout << color[i] << ' ';
     }
     return 0;
}


Measured memory_bytes: 14796
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    int calc=max(a,b);
    if(a>=b)
        a--;
    else
        b--;
    calc+=max(a,b);
    cout << calc << "\n";

    return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    ns = list(map(int, input().split(' ')))
    _ = int(input())
    qs = list(map(int, input().split(' ')))
    count = 0
    start = 0
    end = n
    target = int((start + end) / 2)
    for q in qs:
        while end > start:
            if ns[target] > q:
                end = target
            elif ns[target] < q:
                start = target + 1
            else:
                count += 1
                break
            target = int((start + end) / 2)
        start = 0
        end = n
        target = int((start + end) / 2)
    print(count)


if __name__ == '__main__':
    main()



Measured memory_bytes: 16712
#include <iostream>
#include <vector> #include <string>
#include <algorithm> #include <numeric> #include <functional>
#include <unordered_map>
#include <unordered_set>
#include <array>

#define rep(i, n) for (auto i = 0; i < (n); i++)

using namespace std;

#define ll long long
#define all(v) v.begin(),v.end()
#define bootstrap ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

// custom hash can be a standalone function object:
struct MyHash {
    std::size_t operator()(pair<long, long> const &p) const noexcept {
        std::size_t h1 = std::hash<long>{}(p.first);
        std::size_t h2 = std::hash<long>{}(p.second);
        return h1 ^ (h2 << 1); // or use boost::hash_combine (see Discussion)
    }
};

struct MyComp {
    template<typename T>
    std::size_t operator()(T &l, T &r) const noexcept {
        return l < r;
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> l(k), r(k);
    rep(i, k) { cin >> l[i] >> r[i]; }
    vector<ll> dp(n + 1), dpsum(n + 1);
    dp[1] = 1;
    dpsum[1] = 1;
    long CON = 998244353;
    for (int i = 2; i <= n; i++) {
        rep(j, k) {
            int idx_r = i - l[j];
            int idx_l = i - r[j];
            if (idx_r < 1) {
                continue;
            }
            idx_l = max(1, idx_l);
            dp[i] += (dpsum[idx_r] - dpsum[idx_l - 1]);
            dp[i] %= CON;
        }
        dpsum[i] = (dpsum[i - 1] + dp[i]) % CON;
    }
    //rep(i, n) {
    //    cout << dp[i] << " ";
    //}
    //cout << endl;
    //rep(i, n) {
    //    cout << dpsum[i] << " ";
    //}
    //cout << endl;
    cout << (dp[n] >= 0? dp[n]:dp[n] + CON)<< endl;
}

int main() {
    bootstrap
    solve();
}


Measured memory_bytes: 5992
// AOJ 2618: Trip to Kyoto
// 2018.1.25 bal4u@uu

#include <stdio.h>

#define ABS(a)    ((a)>=0?(a):-(a))
#define MIN(a,b)  ((a)<=(b)?(a):(b))

int x1[10002], y1[10002], x2[10002], y2[10002];
char *msg[2] = { "%d.0\n", "%d.5\n" };

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	if (c == '-') {
		c = getchar_unlocked();
		do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
		while (c >= '0');
		return -n;
	}
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int calc(int x1, int y1, int x2, int y2)
{
	x1 += 200000000, y1 += 200000000;
	x2 += 200000000, y2 += 200000000;
	if (x1%20 == 0 && x2%20 == 0) {
		if      (x1 == x2) return ABS(y1-y2);
		else if (y1/20 == y2/20) return ABS(x1-x2) + MIN(y1%20+y2%20, 40-y1%20-y2%20);
	} else if (y1%20 == 0 && y2%20 == 0) {
		if      (y1 == y2) return ABS(x1-x2);
		else if (x1/20 == x2/20) return ABS(y1-y2) + MIN(x1%20+x2%20, 40-x1%20-x2%20);
	}
	return ABS(x1-x2) + ABS(y1-y2);
}

int main()
{
	int n, x, y, i, j, k, s, t, ans;
	int xmin, xmax, ymin, ymax;
	int x0, y0;

	n = in();
	x = in() << 1, y = in() << 1;
	x1[0] = x, y1[0] = y, xmin = xmax = x2[0] = x+y, ymin = ymax = y2[0] = x-y;
	for (i = 1; i < n; i++) {
		x = in() << 1, y = in() << 1;
		x1[i] = x,   y1[i] = y;
		x2[i] = x+y, y2[i] = x-y;
		if      (x2[i] < xmin) xmin = x2[i];
		else if (x2[i] > xmax) xmax = x2[i];
		if      (y2[i] < ymin) ymin = y2[i];
		else if (y2[i] > ymax) ymax = y2[i];
	}
 
	x = (xmin + xmax) >> 1, y = (ymin + ymax) >> 1;
	x0 = (x + y) >> 1, y0 = (x - y) >> 1;

	ans = 0x7fffffff;
	for (i = x0-20; i <= x0+20; i++) {
		for (j = y0-20; j <= y0+20; j++) {
			if (i%20 && j%20) continue;
			t = 0; for (k = 0; k < n; k++) if (t < (s = calc(i, j, x1[k], y1[k]))) t = s;
			if (ans > t) ans = t;
		}
	}
	printf(msg[ans & 1], ans >> 1);
	return 0;
}


Measured memory_bytes: 2080
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
using namespace std;

int main(){

  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    double xa, ya, ra;
    double xb, yb, rb;
    cin >> xa >> ya >> ra >> xb >> yb >> rb;
    double d = sqrt( (xa-xb)*(xa-xb) + (ya-yb)*(ya-yb) );
    int ans = 0;

    if( ra > d + rb ) ans = 2;
    else if( rb > d + ra ) ans = -2;
    else if( (ra)+(rb) >= d ) ans = 1;


    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int x=s.size()-1;
	if (s[x]=='2' || s[x]=='4' || s[x]=='5' || s[x]=='7' || s[x]=='9')
		cout<<"hon"<<endl;
 	else if (s[x]=='0' || s[x]=='1' || s[x]=='6' || s[x]=='8')
		cout<<"pon"<<endl;
	else cout<<"bon"<<endl;
	return 0;
}

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

int main(){
	int a, b;
	while(cin >>a >>b){
		int tmp=a+b;
		for(int i=0; ;i++){
			tmp /= 10;
			if(tmp==0){
				cout << i+1 << endl;
				break;
			}
		}
	}

    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

  int a;
  string s;
  cin >> a;
  cin >> s;
  if(3200<=a){
    cout << s << endl;
  } else {
    cout << "red" << endl;
  }

	return 0;
}

Measured memory_bytes: 256
import sys
from collections import defaultdict
from math import gcd
def input(): return sys.stdin.readline().strip()
mod = 1000000007

def main():
    N = int(input())
    fish = defaultdict(int)

    """
    b / aで値を管理するのは浮動小数点誤差が怖いので、
    g = gcd(a, b) として(a//g, b//g)のタプルで管理するのが良い。
    """

    zero = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0 and b == 0: zero += 1
        elif a == 0: fish[(0, 1)] += 1
        elif b == 0: fish[(1, 0)] += 1
        else:
            g = gcd(a, b)
            if a < 0: a, b = -a, -b
            fish[(a // g, b // g)] += 1
    #print(fish)
    
    """
    仲の悪い組を(S1, T1), (S2, T2),...とすれば(Si, Ti)からの魚の選び方と
    (Sj, Tj)からの魚の選び方は独立じゃん。
    なぜ気づかなかったのか。。。
    """
    
    ans = 1
    finished = set([])
    for a, b in fish:
        if (a, b) in finished: continue
        finished.add((a, b))
        s = fish[(a, b)]
        if b > 0:
            t = fish[(b, -a)] if (b, -a) in fish else 0
            finished.add((b, -a))
        else:
            t = fish[(-b, a)] if (-b, a) in fish else 0
            finished.add((-b, a))
        ans *= pow(2, s, mod) + pow(2, t, mod) - 1
        ans %= mod
        #print("(a, b)=({}, {}) -> s={}, t={}, val={}".format(a, b, s, t, pow(2, s, mod) + pow(2, t, mod) - 1))
    print((ans + zero - 1) % mod)



if __name__ == "__main__":
    main()


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

using namespace std;

int main()
{
    char c1;
    cin>>c1;
    int d1=(int)c1;
   // cout<<d1;
    if(d1<97){
        cout<<"A";
    }
    if(d1>=97){
        cout<<"a";
    }
    return 0;
}


Measured memory_bytes: 3628
N = int(input())

*A, = map(int, input().split())

M1 = 0
for i in range(N):
  if (i % 2) == 0:
    M1 += A[i]
  else:
    M1 -= A[i]

M = []
M.append(M1)

for i in range(1,N):
  M.append(2*A[i-1] - M[-1])

print(*M)


Measured memory_bytes: 14092
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int[] h = new int[n];
        for(int i = 0;i<h.length;i++) {
            h[i] = stdIn.nextInt();
        }
        int[] count = new int[n];
        int k = 0;
        for(int i = 0;i<h.length-1;i++) {
            if(h[i]>=h[i+1]) {
                count[k] += 1;
            } else {
                k++;
            }
        }
        Arrays.sort(count);
        System.out.println(count[count.length-1]);

    }
}

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

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

  int alpha[26] = {};
  for (int i = 0; i < S.size(); i++) alpha[S[i] - 97]++;

  char ans = 0;
  for (int i = 0; i < 26; i++) {
    if (!alpha[i]) {
     ans = i + 97;
     break;
    }
  }

  if (ans) cout << ans << endl;
  else cout << "None" << endl;

  return 0;
}

Measured memory_bytes: 512
#1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求める
while true
n,x=gets.split(" ").map(&:to_i) #n とx数字をとる
break if n==0 && x==0       #値ゼロの場合終了

count=0                 #resultをまずゼロにする
#loopを始める
for a in 1..n           #a を n回繰り返す　an1,an2,an3....
    for b in 1+a..n     
        for c in b+1..n
            count += 1 if a+b+c==x  #abcのsum　xに同じ場合countを１を足してまた繰り返す
        end
    end
end
puts count
end



Measured memory_bytes: 8892
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
using ull =unsigned long long;
const ll INF =1001001001;

//10億7。　　　100000007

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}


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

int K,A,B;
  cin>>K>>A>>B;
  bool OK=false;

  for(int i=A;i<B+1;i++){
    if(i%K==0){
      OK=true;
    }
  }
  
  if(OK){
    cout<<"OK"<<endl;
  }else{
    cout<<"NG"<<endl;
  }
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define incant() cin.tie(0), ios::sync_with_stdio(false)
#define int long long
#define double long double
template <class T> using vec = vector<T>;
template <class T> using que = queue<T>;
template <class T> using pque = priority_queue<T>;
template <class... T> using tup = tuple<T...>;
using vint = vec<int>;
using vstr = vec<string>;
using pint = pair<int, int>;
using vp = vec<pint>;
using tint = tup<int, int, int>;
using vt = vec<tint>;
using mint = map<int, int>;
using dict = map<string, int>;
using qint = que<int>;
using qp = que<pint>;
using pqint = pque<int>;
using pqp = pque<pint>;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define sz(x) x.size()
#define all(x) begin(x), end(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload3(__VA_ARGS__, revi, _rev,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define space() cout << " "
#define indent() cout << '\n'
#define print(x) out(x), indent()
#define debug(x) cerr << __LINE__ << ": " << #x << ": " << (x) << '\n'
#define YN(x) print((x) ? "YES" : "NO")
#define Yn(x) print((x) ? "Yes" : "No")
#define yn(x) print((x) ? "yes" : "no")
#define POS(x) print((x) ? "POSSIBLE" : "IMPOSSIBLE")
#define Pos(x) print((x) ? "Possible" : "Impossible")
#define pos(x) print((x) ? "possible" : "impossible")
const int INF = LLONG_MAX - INT_MAX, MOD = 1e9 + 7, LIMIT = 100001;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
// const int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
int gcd(int a, int b){return b == 0 ? a : gcd(b, a%b);}
int lcm(int a, int b){return a / gcd(a, b)*b;}
int factorial(int a){return a < 2 ? 1 : factorial(a - 1)*a;}
int summation(int a){return a < 1 ? 0 : (a*a + a) / 2;}
int combination(int n, int r){int res = 1; rep(i, 1, r + 1) res *= n--, res /= i; return res;}
struct UF{
    vint data;
    UF(int size): data(size, -1){}
    int root(int x){return data[x] < 0 ? x : data[x] = root(data[x]);}
    bool unite(int x, int y){
        x = root(x), y = root(y);
        if(x != y){
            if(data[y] < data[x]) swap(x, y);
            data[x] += data[y], data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y){return root(x) == root(y);}
    int size(int x){return -data[root(x)];}
};
int a, b, c, k, n, m, x, y, z, w, h, res = 0, cnt = 0, sum = 0, mx = -INF, mn = INF;
string s, t;

signed main(){
    incant();
    cin >> s;
    print(2*min(count(all(s), '0'), count(all(s), '1')));
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

const int MAX = 100010;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// NのP乗をMで割った余りを返す
ll pow_mod(ll n,ll k,ll m){
  if(k==0){
    return 1;
  }else if(k%2==1){
    return pow_mod(n,k-1,m)*n%m;
  }else{
    ll t=pow_mod(n,k/2,m);
    return (t*t)%m;
  }
}

//(10*9*8)/(3*2*1);
//10*9*8 -> ansMul
//3*2*1 -> ansDiv
long calcComb(int a, int b) {
	if (b > a - b) return calcComb(a, a - b);


	long ansMul = 1;
	long ansDiv = 1;
	for (int i = 0; i < b; i++)
	{
		ansMul *= (a - i);
		ansDiv *= (i + 1);
		ansMul %= MOD;
		ansDiv %= MOD;
	}
	//ansMul / ansDivをやりたい
	//ansDivの逆元を使って求めよう！

	long ans = ansMul * pow_mod(ansDiv,MOD - 2,MOD);
	return ans;
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  vector<double> a;
  cin >> n;
  double t;
  for(int i=0;i<n;i++){
    cin >> t;
    a.push_back(t);
  }
  sort(a.rbegin(),a.rend());
  COMinit();
  int ans1=a[0],ans2=a[n];
  double cnt=a[0]/2.0;
  for(int i=0;i<n;i++){
    if(abs(a[i]-a[0]/2.0)<cnt){
      ans2=a[i];
      cnt=abs(a[i]-a[0]/2.0);
    }
  }
  printf("%d %d\n",ans1,ans2);
  return 0;
}


Measured memory_bytes: 3572
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
// UnionFind
class UnionFind {
public:
  UnionFind(int size_) : parent(size_, -1), __size(size_) {}
  void unite(int x, int y) {
    if ((x = find(x)) != (y = find(y))) {
      if (parent[y] < parent[x])
        std::swap(x, y);
      parent[x] += parent[y];
      parent[y] = x;
      __size--;
    }
  }
  bool is_parent(int x) { return find(x) == x; }
  bool is_same(int x, int y) { return find(x) == find(y); }
  int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
  int size(int x) { return -parent[find(x)]; }
  int size() const { return __size; }

private:
  std::vector<int> parent;
  int __size;
};
// UnionFind

int N, M;
vector<int> A;
using P = priority_queue<int, vector<int>, greater<int>>;

ll result;
int main() {
  cin >> N >> M;
  A.resize(N);
  for (auto &val : A) {
    cin >> val;
  }
  UnionFind ut(N);
  map<int, P> nodes;
  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    ut.unite(x, y);
  }
  if (M == N - 1) {
    cout << 0 << endl;
    return 0;
  }
  if (N < 2 * (N - M - 1)) {
    cout << "Impossible" << endl;
    return 0;
  }

  for (int i = 0; i < N; i++) {
    int p = ut.find(i);
    nodes[p].emplace(A[i]);
  }

  vector<int> ones;
  P p_que;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (nodes[i].empty()) {
      continue;
    }
    result += nodes[i].top();
    nodes[i].pop();
    cnt++;
    while (!nodes[i].empty()) {
      p_que.push(nodes[i].top());
      nodes[i].pop();
    }
  }

  while (cnt < 2 * (N - M - 1)) {
    result += p_que.top();
    p_que.pop();
    cnt++;
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 10748
#include <iostream>
#include <array>
#include <string>

namespace Direction { enum { N, S, E, W }; };

bool judge(std::string S)
{
	std::array<unsigned, 4> a = { {0, 0, 0, 0} };
	
	for (char c : S) {
		switch (c)
		{
		case 'N':
			++a[Direction::N];
			break;
		case 'S':
			++a[Direction::S];
			break;
		case 'E':
			++a[Direction::E];
			break;
		case 'W':
			++a[Direction::W];
			break;
		}
	}

	return (
		(a[Direction::N] > 0 && a[Direction::S] > 0)
		||
		(a[Direction::N] == 0 && a[Direction::S] == 0)
	) && (
		(a[Direction::E] > 0 && a[Direction::W] > 0)
		||
		(a[Direction::E] == 0 && a[Direction::W] == 0)
	);
}

int main()
{
	std::string S;
	std::cin >> S;
	std::cout << (judge(S) ? "Yes" : "No") << std::endl;
	return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define per(i,n) for(int i = n; i >= 0; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);


  ll n, k;
  cin >> n >> k;
  vector<P> vp;
  rep(i,n) {
    int a, b;
    cin >> a >> b;
    vp.emplace_back(a,b);
  }
  sort(all(vp));
  for(P p : vp) {
    if(k <= p.se) {
      cout << p.fi << endl;
      return 0;
    }
    k -= p.se;
  }
}

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

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

#define dbs cout<<"Debug\n";
#define dbar(arr,n) cout<<"DBAR: "; for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<'\n';

#define fl(i,n) for(ll i=0;i<n;i++)
#define al(z) for(auto it : z)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1; //cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        vector<pair<ll,ll>>v(n);
        fl(i,n)
        {
            cin>>v[i].first;
            cin>>v[i].second;
        }
        ll dp[n+1][k+1];
        fl(i,n+1) fl(j,k+1) dp[i][j] = 0;
        for(ll i=1;i<=n;i++)
        {
            for(ll j=1;j<=k;j++)
            {
                if(v[i-1].first<=j)
                {
                    dp[i][j] = max(v[i-1].second + dp[i-1][j-v[i-1].first], dp[i-1][j]);
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        cout<<dp[n][k];
    }
    return 0;
}


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

#define ll long long
#define pi (acos(-1))
#define rep(i, n) for (unsigned long long i = 0; i < (unsigned long long)(n); ++i)
using namespace std;
std::vector<unsigned ll> genprimevec(const unsigned ll N);

int main()
{
    int n, ans = 0;
    cin >> n;
    string s;
    cin >> s;

    rep(i, n)
    {
        if (s[i] == 'A')
        {
            if ((i + 1 < s.size() && s[i + 1] == 'B') && (i + 2 < s.size() && s[i + 2] == 'C')) { ans++; }
        }
    }
    cout<<ans<<endl;
    return 0;
}

/*author  https://qiita.com/drken/items/0c88a37eec520f82b788*/
ll extgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


std::vector<unsigned ll> genprimevec(const unsigned ll N)
{
    std::vector<bool> is_prime(N + 1);
    for (unsigned ll i = 0; i <= N; i++) { is_prime[i] = true; }
    std::vector<unsigned ll> P;
    for (unsigned ll i = 2; i <= N; i++)
    {
        if (is_prime[i])
        {
            for (unsigned ll j = 2 * i; j <= N; j += i) { is_prime[j] = false; }
            P.emplace_back(i);
        }
    }
    return P;
}


Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
ll size(int n) {
	if (n == 0) return 1;
	else return size(n - 1) * 2 + 3;
}
ll pathi(int n) {
	if (n == 0) return 1;
	else return pathi(n - 1) * 2 + 1;
}
ll calc(int n, ll x) {
	if (x == 0) return 0;
	if (n == 0) return 1;
	if (x < 2 + size(n - 1)) return calc(n - 1, x - 1);
	else if (x == 2 + size(n - 1)) return pathi(n - 1) + 1;
	else if (x > 2 + size(n - 1)) return pathi(n - 1) + 1 + calc(n - 1, x - size(n - 1) - 2);
}
int main() {
	int n; ll x;
	cin >> n >> x;
	cout << calc(n, x) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;


int main(void){
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;

	int l=0,r=0;
	if(s[0] == 'L')l++;
	else r++;

	int ans = 0;
	rep(i,n-1){
		if(s[i+1] == 'L' && s[i] == 'R')l++;
		else if(s[i+1] == 'L' && s[i] == 'L')ans++;
		else if(s[i+1] == 'R' && s[i] == 'L')r++;
		else ans++;
	}

	if(l <= k || r <= k)ans = n-1;
	else ans += k*2;

	cout << ans << endl;

	return 0;
}


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

const int inf = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };
int h, w;
string s[20];
int g[400][400];
int main() {
  cin >> h >> w;
  for (int i = 0; i < h; ++i) {
    cin >> s[i];
  }
  
  const int n = h * w;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      g[i][j] = i == j ? 0 : inf;
    }
  }
  
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (s[i][j] == '#') continue;
      for (int k = 0; k < 4; ++k) {
        int ni = i + di[k];
        int nj = j + dj[k];
        if (ni < 0 || ni >= h) continue;
        if (nj < 0 || nj >= w) continue;
        if (s[ni][nj] == '#') continue;
        g[i * w + j][ni * w + nj] = 1;
        g[ni * w + nj][i * w + j] = 1;
      }
    }
  }
  
  for (int i = 0; i < n; ++i) {
    for (int k = 0; k < n; ++k) {
      for (int j = 0; j < n; ++j) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  
  for (int i = 0; i < n; ++i) {
    for (int k = 0; k < n; ++k) {
      for (int j = 0; j < n; ++j) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  
  int mx = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (g[i][j] == inf) continue;
      mx = max(mx, g[i][j]);
    }
  }
  cout << mx << endl;
}

Measured memory_bytes: 896