akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(s) (int)(s.size())
#define all(v) v.begin(),v.end()
#define endl "\n"
using namespace std;
ll gcd(ll x, ll y) { return (!y) ? x : gcd(y, x % y); }
void Run() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("mex.in", "r", stdin);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin); freopen("outt.txt", "w", stdout);
#endif
}
const int N = 1e5 + 10;
int f[N];
int e[N];
int main()
{
    Run();
    int n; cin >> n;
    for (int i = -1000; i <= 1000; i++)
    {
        for (int j = -1000; j <= 1000; j++)
        {
            if (pow(i, 5) - pow(j, 5) == n)
            {
                cout << i << " " << j;
                return 0;
            }
        }
    }
}


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

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

int N, m;
int cum[1010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> m;
  for (int i = 0; i < m; i++) {
    int c, d;
    cin >> c >> d;
    cum[c]++;
    cum[d]--;
  }
  int ans = 0;
  for (int i = 0; i <= N; i++) {
    cum[i + 1] += cum[i];
    ans += cum[i] > 0 ? 3 : 1;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) for(int i = 0; i < (a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

int dp[100005][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	int a[n], b[n], c[n];
	rep(i, n){
		cin >> a[i] >> b[i] >> c[i];
	}
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];
	repn(i, 1, n){
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
	}
	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 2560
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	s := getNextString(scanner)

	for i := 0; i < len(s); i++ {
		fmt.Fprintf(writer, "%c", int('A')+(int(s[i]-'A')+n)%26)
	}

	fmt.Fprintln(writer, "")
	writer.Flush()
}


Measured memory_bytes: 768
import java.util.*;
// import java.io.*;
public class Main {
  public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
   String n = sc.next();
   int calc = 0;
   for(int i=0;i < n.length();i++){
     calc += n.charAt(i)-'0';
   }
   if (calc % 9 == 0) {
     System.out.println("Yes");
   }
   else{
     System.out.println("No");
   }
  }
}


Measured memory_bytes: 40156
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

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

const int MOD = 1000000007;

template<class T>bool chmax(T &a, const T &b){
	if(a<b){
		a=b;
		return true;
	}
	return false;
}

template<class T>bool chmin(T &a, const T &b){
	if(a>b){
		a=b;
		return true;
	}
	return false;
}

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	char c;cin>>c;
	cout<<char(c+1)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3005;
const int MOD = 998244353;
int dp[N][N];
int main()
{
    int A, B, C, D;
    scanf("%d%d%d%d", &A, &B, &C, &D);
    dp[A][B] = 1;
    for (int i = A; i <= C; i++) {
        for (int j = B; j <= D; j++) {
            if(i == A && j == B) continue;
            dp[i][j] = ((1LL * dp[i - 1][j] * j + 1LL * dp[i][j - 1] * i - 1LL * dp[i - 1][j - 1] * (i - 1) * (j - 1)) % MOD + MOD) % MOD;
        }
    }
    printf("%d\n", dp[C][D]);
    return 0;
}


Measured memory_bytes: 36916
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())
aaa = get_nums_l()

sum_rev = sum(map(lambda a: 1/a, aaa))
print(1/sum_rev)

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
 
int main () {
  string n;
  cin >> n;
  
  if(n[0] == '1') n[0] = '9';
  else 			  n[0] = '1';
  
  if(n[1] == '1') n[1] = '9';
  else 			  n[1] = '1';
  
  if(n[2] == '1') n[2] = '9';
  else 			  n[2] = '1';
  
  cout << n << endl;
  return 0;
}

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

map<string,int> mp;

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

  int n; cin >> n;
  for(int i = 0; i < n; i++){
    string s,t; cin >> s >> t;
    if(s == "insert") mp[t]++;
    if(s == "find"){
      if(mp.find(t) != mp.end()) cout << "yes" << endl;
      else cout << "no" << endl; 
    }
  }

  return 0;
}



Measured memory_bytes: 33344
#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)


Measured memory_bytes: 264700
#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 drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;
ll const MOD = 1000000007;


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

int N;
cin >> N;

vi a(N),even,odd;
rep(i,N) {
    cin >> a[i];
    if(i % 2 == 0) even.push_back(a[i]);
    else odd.push_back(a[i]);
}

int E = even.size();
int O = odd.size();

if(N % 2 == 0) {
    drep(i,O) cout << odd[i] << endl;
    rep(i,E) cout << even[i] << endl;
}else{
    drep(i,E) cout << even[i] << endl;
    rep(i,O) cout << odd[i] << endl;
}

return 0;
}

Measured memory_bytes: 4084
/* << IN THE NAME OF GOD >> */
#include <bits/stdc++.h>
using namespace std;



#define err(x) cerr << #x  << " = "<<  x << '\n'
#define out(x) cout << x << '\n'
#define forp(i, r, l) for(int i = int(r); i < int(l); i++)
#define forn(i, r, l) for(int i = int(r); i > int(l); i--)
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll ,ll> pll;
const int maxn = 1e2 + 120;
 

int n ,m;
char str[maxn][maxn];
bool f(){
    if(str[0][0] == '#' && str[1][0] == '.' && str[0][1] == '.')
        return cout << "No",0;
    if(str[n - 1][m - 1] == '#' && str[n - 1][m - 2] == '.' && str[n - 2][m - 1] == '.')
        return cout << "No",0;
     if(str[n - 1][0] == '#' && str[n - 2][0] == '.' && str[n - 1][1] == '.')
        return cout << "No",0;
    if(str[0][m - 1] == '#' && str[1][m - 1] == '.' && str[0][m - 2] == '.')
        return cout << "No",0;
    return 1;
}
int main(){FAST;
    cin >> n >> m;
    forp(i ,0 ,n)
        forp(j ,0 ,m)
           cin >> str[i][j];
    
       if(!f())
            return 0;
    
   forp(i ,0 ,n)
       forp(j ,0 ,m){
    if(str[i][j] == '#'){
    
        if(i == 0 && j > 0 && j < m - 1){
            if(str[i][j - 1] == '.' && str[i][j + 1] == '.' && str[i + 1][j] == '.')
                return cout << "No" ,0;
        }
        else if( i == n - 1 && j > 0 && j < m - 1){
            if(str[i][j + 1] == '.' && str[i-1][j] == '.' && str[i][j - 1] == '.')
                return cout << "No" ,0;
        }
        else if(j == 0 && i > 0 && i < n - 1){
            if(str[i + 1][j] == '.' && str[i][j + 1] == '.' && str[i - 1][j] == '.')
                return cout << "No" ,0;
        }
        else if(j == m - 1 && i > 0 && i < n - 1){
               if(str[i + 1][j] == '.' && str[i][j - 1] == '.' && str[i - 1][j] == '.')
                        return cout << "No" ,0;
        }
         if(i > 0 && i < n - 1 && j > 0 && j < m - 1)
            if(str[i][j-1] == '.' && str[i][j + 1] == '.' && str[i + 1][j] == '.' && str[i - 1][j] == '.')
                    return cout << "No" ,0;
                
        }
    }

        cout << "Yes";
   return 0;
}
 












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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for(int i = 1; i <= n; i++){
    if(!(i % 2)) continue;
    int c = 0;
    for(int j = 1; j <= n; j++){
      if(i % j) continue;
      c++;
    }
    if(c == 8) ans++;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
s=list(input())
t=list(input())
if s==t:
    print(n)
else:
    cnt=0
    for i in range(n):
        for j in range(n-i):
            if s[i+j]!=t[j]:
                break
            if j==n-i-1:
                cnt=n-i
    print(2*n-cnt)
            
        


Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 100010
using namespace std;
int n,m,cnt,x[N],d[N];
ll ans,v[N];
int main()
{
	int i,s,a,b,j,k;
	int l,r;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d%lld",&x[i],&v[i]);
	l=1;r=n;x[0]=m;
	while(l<=r)
	{
		if(m<=x[l])
		{
			ans+=x[r]-m,d[cnt+1]=r;
			break;
		}
		if(x[r]<=m)
		{
			ans+=m-x[l];d[cnt+1]=l;
			break;
		}
		if(v[l]<v[r])d[++cnt]=l,v[r]+=v[l++];
		else d[++cnt]=r,v[l]+=v[r--];
	}
	for(i=1;i<=cnt;i++)ans+=abs(x[d[i]]-x[d[i+1]]);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1792
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


int main() {
	string S;
	cin >> S;
	ll ans = 0;
	for (int i = 0; i < (1 << (S.size() - 1)); i++) {
		vector<int> pos;
		pos.push_back(0);
		for (int j = 0; j < S.size() - 1; j++) {
			if ((1 << j) & i)pos.push_back(j+1);
		}
		pos.push_back(S.size());
		vector<string> a;
		for (int j = 0; j < pos.size() - 1; j++) {
			a.push_back(S.substr(pos[j], pos[j + 1] - pos[j]));
		}

		for (int j = 0; j < a.size(); j++) {
			ans += stoll(a[j]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
from itertools import product


def read():
    H, W = list(map(int, input().strip().split()))
    S = list()
    S.append(list('#' * (W+2)))
    for i in range(H):
        s = list(input().strip())
        S.append(['#'] + s + ['#'])
    S.append(list('#' * (W+2)))
    return H, W, S


def solve(H, W, S, INF=10000):
    field = [[INF for j in range(W+2)] for i in range(H+2)]
    field[1][1] = 1 if S[1][1] == '#' else 0
    for j in range(2, W+1):
        u = 1 if S[1][j-1] == '.' and S[1][j] == '#' else 0
        field[1][j] = field[1][j-1] + u
    for i, j in product(range(2, H+1), range(1, W+1)):
        # 上から
        if S[i-1][j] == '.' and S[i][j] == '#':
            u = field[i-1][j] + 1  
        else:
            u = field[i-1][j]
        # 左から
        if S[i][j-1] == '.' and S[i][j] == '#':
            v = field[i][j-1] + 1  
        else:
            v = field[i][j-1]
        field[i][j] = min(u, v)
    return field[H][W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	map<int, map<int, int>> mp;
	vector<int> p(m), y(m);
	for (int i = 0; i < m; i++) {
		cin >> p[i] >> y[i];
		mp[p[i]][y[i]]++;
	}

	for (auto& imp : mp) {
		int i = 1;
		for (auto& it : imp.second) {
			it.second = i++;
		}
	}

	for (int i = 0; i < m; i++) {
		string sp = to_string(p[i]);
		string yp = to_string(mp[p[i]][y[i]]);

		cout << string(6 - sp.length(), '0') + sp + string(6 - yp.length(), '0') + yp << "\n";
	}
}

Measured memory_bytes: 16384
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod=1000000007;
const int INF=1e18;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5])
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
S = input()[::-1]

MOD = 2019
tmp = [0]*MOD
tmp[0] += 1
tens = 1
num = 0
for s in S:
    num += int(s) * tens
    num = num % MOD
    tmp[num] += 1
    tens *= 10
    tens %= MOD

ans = 0
for i in tmp:
    ans += i*(i-1)//2

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 9716
/*
    STARK_BOY
*/
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repe(i,a,b) for(ll i=a;i<=b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
typedef pair<ll,ll> pii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setbitc(x) __builtin_popcount(x)
#define init(x,a) memset(x,a,sizeof(x))
#define PI           3.14159265358979323846  /* pi */
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
#define N 1000005
//Variables Start
ll inf=1e18,MOD=1e9+7;
ll n,m,k,ar[N],br[N];
string s,s1;
//Variables End

ll sub(ll a, ll b){return (a-b+MOD)%MOD;}
ll add(ll a, ll b){return (a+b)%MOD;}
ll mul(ll a, ll b){return (a*b)%MOD;}
int main()
{
    ios
    int ti=1;
    //cin>>ti;
    while(ti--)
    {
		cin>>n>>k;

		vi dp_cur(k+2,0),dp_prev(k+2,0),in(n+1,0);
		rep(i,0,n)cin>>in[i];
		dp_prev[0]=1;
		rep(i,0,n)
		{

			rep(j,0,k+1)
			{
				dp_cur[min(k+1,j+in[i]+1)]=sub(dp_cur[min(k+1,j+in[i]+1)],dp_prev[j]);
				dp_cur[j]=add(dp_cur[j],dp_prev[j]);
			}
			rep(j,1,k+1)dp_cur[j]=add(dp_cur[j],dp_cur[j-1]);
			dp_prev=dp_cur;
			rep(j,0,k+2)dp_cur[j]=0;
			
		}

		cout<<dp_prev[k]<<endl;

    }
    return 0;
        
}

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

int main(){
    int cnt1 = 0, cnt2 = 0;
    string s; cin >> s;
    vector<char> t,u;

    rep(i,s.size()){
        if(i mod 2 == 0){
            t.push_back('0');
            u.push_back('1');
        }else{
            t.push_back('1');
            u.push_back('0');
        }
    } 

    rep(i,s.size()){
        if(t[i] != s[i]) cnt1++;
        if(u[i] != s[i]) cnt2++;
    }

    cout << min(cnt1,cnt2) << endl;

}

Measured memory_bytes: 640
#include <iostream>
#define NIL 2000000001
using namespace std;
typedef struct{
	int key;
	int lch;//??????id
	int rch;//??????id
}NODE;
NODE node[500001];
int root;
int n,a;
string s;

void insert(int id,int num){
	int node1=root;
	int parent=-1;
	while(node1!=-1){
		parent=node1;
		if(num<node[node1].key){
			node1=node[node1].lch;
		}else{
			node1=node[node1].rch;
		} 
	}
	//parent=node1;
	if(parent==-1){
		root=id;
		node[id].lch=node[id].rch=-1;
		node[id].key=num;
	}else if(num<node[parent].key){
		node[parent].lch=id;
		node[id].key=num;
		node[id].rch=node[id].lch=-1;
	}else{
		node[parent].rch=id;
		node[id].key=num;
		node[id].rch=node[id].lch=-1;
	}
}

void inordertreewalk(int id){
	if(node[id].lch!=-1)inordertreewalk(node[id].lch);
	//if(id==root){
	//	cout << node[id].key;	
	//}else if(node[id].key>node[root].key){
		cout << " "<< node[id].key;
	//}else{
	//	cout << node[id].key<<" ";
	//}
	if(node[id].rch!=-1)inordertreewalk(node[id].rch);
	return;
}

void preordertreewalk(int id){
	//if(id==root){
	//	cout << node[id].key;	
	//}else{
		cout << " "<< node[id].key;
	//}
	if(node[id].lch!=-1)preordertreewalk(node[id].lch);
	if(node[id].rch!=-1)preordertreewalk(node[id].rch);
	return;
}

int main(){
	root=-1;
	cin >>n;
	for(int i=0;i<n;i++){
		cin >>s;
		if(s=="insert"){
			cin >>a;
			insert(i,a);
		}else if(s=="print"){
			if(root==-1)continue;
			inordertreewalk(root);
			cout <<endl;
			preordertreewalk(root);
			cout <<endl;
		}

	}
}

Measured memory_bytes: 8952
/*Author : Kartik Bansal
 *Date : 02/08/19
 *Time : 17:46 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define tc int t ;cin>>t ;while(t--)
#define pb push_back
#define FOR(i,n) for(int i =0;i<n;i++)
#define Sort(v) sort(v.begin() ,v.end())
int32_t main()
{
  ll n ;
  cin>>n  ;
  ll dp[100005][3] ;
  ll a[100005] , b[100005] , c[100005] ;
  FOR(i , n )
    cin>>a[i+1]>>b[i+1] >>c[i+1] ;
  for(ll i=1 ;i<=n;i++)
  {
    // dp[i][0] = max(dp[])
    dp[i][0] = max(dp[i-1][1] + a[i] , dp[i - 1][2] + a[i]);
    dp[i][1] = max(dp[i-1][0] + b[i] , dp[i - 1][2] + b[i]);
    dp[i][2] = max(dp[i-1][1] + c[i] , dp[i - 1][0] + c[i]);
  }
  ll z = max(dp[n][0] , max(dp[n][1] ,dp[n][2])) ;

  cout<<z  ;


  return 0 ;
}


Measured memory_bytes: 4992
#!/usr/bin/env python3
import sys
import itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    paths = list(zip(a, b))

    permutations = []
    for permutation in itertools.permutations(range(1, N + 1)):
        if permutation[0] == 1:
            permutations.append(permutation)
        else:
            break
    # print(permutations)
    result = 0
    for permutation in permutations:
        able = True
        for i in range(N - 1):
            if (
                permutation[i : i + 1 + 1] in paths
                or tuple(reversed(list(permutation[i : i + 1 + 1]))) in paths
            ):
                pass
            else:
                able = False
                break

        if able:
            result += 1

    print(result)

    return


# 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)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = (int)1e9 + 7;
const int INF = (int)1e9;
const int N = 2005;
const int MAXA = (int)3e6;
ll pref[N],dp[N][N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");
    int s;
    cin >> s;
    dp[0][0] = 1;
    pref[0] = dp[0][0];
    for(int j = 1;j <= s;j++)pref[j] = pref[j - 1] + dp[0][j],pref[j] %= mod;
    for(int i = 1;i <= (s / 3);i++){
        for(int j = (i * 3);j <= s;j++){
            dp[i][j] += pref[j - 3];
            dp[i][j] %= mod;
        }
        pref[0] = dp[i][0];
        for(int j = 1;j <= s;j++)pref[j] = pref[j - 1] + dp[i][j],pref[j] %= mod;
    }
    ll ans = 0;
    for(int i = 1;i <= (s / 3);i++)ans += dp[i][s],ans %= mod;
    cout << ans;
    return 0;
}



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

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
int main() {
	scanf("%lld%lld%lld",&n,&a,&b);
	long long zq=n/(a+b);
	long long q=zq*(a+b);
	long long ans=zq*a+min(n-q,a);
	printf("%lld",ans);
	return 0;
}

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

#define _u(i,a,b) for(int i=a;i<=b;++i)
#define _d(i,a,b) for(int i=a;i>=b;--i)
#define endl "\n"
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define FIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FI(task) freopen(task".inp","r",stdin)
#define FO(task) freopen(task".out","w",stdout)

using namespace std;

const int N = 2e5+7;
const int M = 1e9+7;

ll bit[N], a[N], h[N];
int n;
ll res;

void upd(int i, ll val){
    for(;i<=200000;i+=i&-i) bit[i] = max(bit[i], val);
}

ll getm(int i){
    ll res(0);
    for(;i>0;i-=i&-i) res = max(res, bit[i]);
    return res;
}

#define task "test"

int main(){
    FIO();
    //FI(task);
    ///FO(task);

    cin >> n;
    _u(i,1,n) cin >> h[i];
    _u(i,1,n) cin >> a[i];

    _u(i,1,n){
        ll tmp = getm(h[i]-1) + a[i];
        upd(h[i], tmp);
        res = max(res, tmp);
    }
    cout << res;
    return 0;
}


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

vector <int> a;
template <class T>
T c(T mid) {
    T sum = 0LL;
    rep (i, a.size()) {
        sum += (abs(a[i] - (mid + i)));
    }
    return sum;
}

template<class T>
T findMin(T L, T R) { //[L, R)
    T lo = L - 1, hi = R - 1;
    while (lo + 1 != hi) {
        T mi = (lo + hi) / 2;
        if (c(mi) <= c(mi + 1)) hi = mi;
        else lo = mi;
    }
    return hi;
}

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

    long long b = findMin(-1000000000000000000LL, 1000000000000000000LL);

    long long ans = 0;
    rep (i, n) {
        ans += (abs(a[i] - (b + i)));
    }

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int x,a,b,c;
  cin >> a >> b >> c >> x;
  ll ans = 0;
  REP(i,c+1){
    REP(j,b+1){
      int y = x - (i*50 + j*100);
      if(y>=0 && y<=a*500 && y%500==0) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {
  long long  q, h, s, d, n;
  long long price[4];
  long long ans = 0;

  vector<pair<long long, int> > pairs(4);
  cin >> q;
  price[0] = q;
  pairs[0] = make_pair(q * 8, 8);
  cin >> h;
  price[1] = h;
  pairs[1] = make_pair(h * 4, 4);
  cin >> s;
  price[2] = s;
  pairs[2] = make_pair(s * 2, 2);
  cin >> d;
  price[3] = d;
  pairs[3] = make_pair(d,1);

  cin >> n;
  sort(pairs.begin(), pairs.end());

  for (int i = 0; i < 4; i++) {
    //cerr << pairs[i].first << "," << pairs[i].second << endl;
  }

  if (pairs[0].second == 1 && n % 2 == 1) {
    ans += (long long)(n/2) * d;
    ans += pairs[1].first / 2;
  } else {
    ans += n * pairs[0].first / 2;
  }

  cout << ans << endl;

  return 0;
}


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

using pii = pair<int, int>;

int main(){
    int N, M;
    cin >> N >> M;
    
    vector<pii> AB(N);
    for(int i = 0; i < N; ++i){
        cin >> AB[i].first >> AB[i].second;
    }

    sort(begin(AB), end(AB));

    priority_queue<pii, vector<pii>, function<bool(pii, pii)>> q(
        [](const pii& a, const pii& b){
            return (a.second == b.second) ? (a.first > b.first) : (a.second < b.second);
        }
    );

    int ans = 0;
    int d = 0;
    int j = 0;
    while(d <= M && j <= N){
        if(!q.empty()){
            ans += q.top().second;
            q.pop();
        }
        
        ++d;
        for(int i = j; i < N; ++i){
            if(AB[i].first == d){
                q.emplace(AB[i]);
                ++j;
            }else{
                break;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  int a,b;
  cin >> a >> b;
  int ans=1;
  while(ans<10000){
    if((int)(ans*0.08)==a && (int)(ans*0.10)==b){break;}
    ans++;
  }
  if(ans>=10000){ans=-1;}

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


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
struct modint {
    ll x;
    constexpr modint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    ll value() const {
        return x;
    }
    constexpr modint operator-() const {
        return modint(-x);
    }
    constexpr modint& operator+=(const modint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr modint& operator-=(const modint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr modint& operator*=(const modint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    constexpr modint operator+(const modint a) const {
        modint res(*this);
        return res += a;
    }
    constexpr modint operator-(const modint a) const {
        modint res(*this);
        return res -= a;
    }
    constexpr modint operator*(const modint a) const {
        modint res(*this);
        return res *= a;
    }
    constexpr modint pow(ll t) const {
        if (t == 0) return 1;
        modint a = pow(t >> 1);
        a *= a;
        if (t % 2 == 1) a *= *this;
        return a;
    }
    constexpr modint inv() const {
        return pow(MOD - 2);
    }
    constexpr modint& operator/=(const modint a) {
        return (*this) *= a.inv();
    }
    constexpr modint operator/(const modint a) const {
        modint res(*this);
        return res /= a;
    }
};

int n;
vector<vector<int>> g;
auto memo = make_vec<ll>(100100, 2);
modint dp(int now, int pre, int color) {
    if (memo[now][color] != -1) return modint(memo[now][color]);
    modint ret = 1;
    for (auto nxt : g[now]) {
        if (nxt == pre) continue;
        modint x = 0;
        x += dp(nxt, now, 0);
        if (color == 0) x += dp(nxt, now, 1);
        ret *= x;
    }
    return memo[now][color] = ret.value();
}
int main() {
    cin >> n;
    g.resize(n);
    rep(i, n - 1) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    rep(i, 100100) rep(j, 2) memo[i][j] = -1;
    cout << (dp(0, -1, 0) + dp(0, -1, 1)).value() << endl;
}


Measured memory_bytes: 22272
# There are N cities numbered 1 through N, and M bidirectional roads numbered 1
# through M. Road i connects City A_i and City B_i.
# 
# Snuke can perform the following operation zero or more times:
# 
#  * Choose two distinct cities that are not directly connected by a road, and
#    build a new road between the two cities.
# 
# After he finishes the operations, it must be possible to travel from any city to
# any other cities by following roads (possibly multiple times).
# 
# What is the minimum number of roads he must build to achieve the goal?

# Solution:
#   Use UnionFind to start with groups 1..N and merge as directed by the roads data.
#   If there are G distinct groups after all the merges, then G-1 roads are required
#   to provide the necessary linkages.

class UnionFind:
    # The nodes will be numbered 1..n.
    def __init__(s, n):
        s.n_ = n
        s.ngroups_ = n
        s.parent_  = [i for i in range(n+1)]
          # index zero is ignored

    # Number of nodes.
    def n(s):
        return s.n_

    # Number of distict groups.
    def ngroups(s):
        return s.ngroups_

    # Returns the ultimate parent node of node i, and resets the parent so the chain is
    # shorter for future queries.
    def find(s, i):
        x = i
        while True:
            y = s.parent_[x]
            if x == y:
                # We've found the root of the group.
                s.parent_[i] = x
                return x
            else:
                x = y

    # -> True/False
    def same_group(s, i, j):
        return s.find(i) == s.find(j)

    # Generator of (node_id, group_id) for all nodes.
    def items(s):
        return ((i, s.find(i)) for i in range(1, s.n_ + 1))

    # Merges two groups. Returns True if a merge actually took place, or False if they
    # were in the same group anyway.
    def union(s, i, j):
        x, y = s.find(i), s.find(j)
        if x == y:
            # Same group already.
            return False
        else:
            s.parent_[x] = y
            s.parent_[i] = y
            s.ngroups_ -= 1
            return True

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]

U = UnionFind(N)

# Process each road and merge groups accordingly.
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    U.union(a, b)

# Get and print the answer.
answer = U.ngroups() - 1
print(answer)


Measured memory_bytes: 73144
N, M = map(int, input().split())
A = list(map(int, input().split()))
C=[]
E=[]
for i in range(M):
    D, B = map(int, input().split())
    C.append([B, D])
A.sort()
C.sort(reverse=True)

for i in range(M):
    for j in range(C[i][1]):
        E.append(C[i][0])
        if len(E)>=N:
            break
    else:
        continue
    break
#print(E)

for i in range(len(E)):
    if E[i]>A[i]:
        A[i]=E[i]
    else:
        break
total=0

for i in range(N):
    total+=A[i]

print(total)

Measured memory_bytes: 24884
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T &a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T &a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
vector<string>split(string s, char c = ' ') {
	vector<string>vec;
	string h = "";
	for (int i = 0; i < s.size();) {
		int j = i;
		while (j < s.size() && s[j] != ' ') {
			h += s[j++];
		}
		if (h.size() > 0) vec.push_back(h);
		h = "";
		i = j + 1;
	}
	return vec;
}
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
signed main() {
	string s;
	cin >> s;
	int ans = Inf;
	for (int i = 0; i < s.size() - 2; i++) {
		string h = "";
		h += (char)s[i];
		h += (char)s[i + 1];
		h += (char)s[i + 2];
		int k = stoll(h);
		ans = min(ans, abs(k - 753));
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int ABS(int a){return max(a,-a);}
long long C[3000][3000];
int main(){
	int a,b,c,d,e,f;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
	int m=1;
	if(2*ABS(e-c)==a)m*=2;
	if(2*ABS(f-d)==b)m*=2;
	int P=min(ABS(e-c),a-ABS(e-c));
	int Q=min(ABS(d-f),b-ABS(d-f));
	C[0][0]=1;
	int mod=100000007;
	C[1][0]=C[1][1]=1;
	for(int i=2;i<3000;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	printf("%lld\n",(C[P+Q][P]*m)%mod);
}

Measured memory_bytes: 69676
s = input()
ls = len(s)
isOk = True
for i in range(ls):
    if(i%2==1 and s[i]=='R'):
        isOk = False
    if(i%2==0 and s[i]=='L'):
        isOk = False

if isOk:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <utility>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<int>a;
int n;
bool check(int x){
    // cerr << "x = " << x << endl;
    vector<pii>vec;//文字,個数
    int len = 0;
    for(int d:a){
        // cerr << "d = " << d << endl;
        if(len < d){
            if(vec.size()==0)vec.push_back(pii(0,d-len));
            else if(vec.back().first == 0)vec.back().second+=d-len;
            else vec.push_back(pii(0,d-len));
        }else{
            while(len!=d){
                int k = min(len-d,vec.back().second);
                vec.back().second-=k;
                len-=k;
                // cerr << "len = " << len << endl;
                if(vec.back().second==0)vec.pop_back();
            }
            if(vec.back().second == d and vec.back().first == x-1)return false;
            if(vec.back().first == x-1){
                auto p = vec.back();
                vec.pop_back();
                vec.back().second--;
                if(vec.back().second == 0){
                    int k = vec.back().first+1;
                    vec.pop_back();
                    if(vec.size() and vec.back().first == k)vec.back().second++;
                    else vec.push_back(pii(k,1));
                }else{
                    vec.push_back(pii(vec.back().first+1, 1));
                }
                vec.push_back(pii(0,p.second));
            }else{
                vec.back().second--;
                if(vec.back().second==0){
                    int k = vec.back().first+1;
                    vec.pop_back();
                    if(vec.size() and vec.back().first == k)vec.back().second++;
                    else vec.push_back(pii(k,1));
                }else{
                    vec.push_back(pii(vec.back().first+1,1));
                }
            }
        }
        len = d;
        // for(auto p:vec){
        //     cout << p.first << " " << p.second << " " ;
        // }
        // cout << endl;
    }
    return true;
}
int main(){
    cin >> n;
    a.resize(n);
    rep(i,n)cin >> a[i];
    int ng = 0,ok = n;
    while(ok-ng>1){
        int mid = (ng+ok)/2;
        if(check(mid)){
            ok = mid;
        }else ng = mid;
    }
    cout << ok << endl;
}

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

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

    ll A, B, N;
    cin >> A >> B >> N;
    ll ans = 0;

    if (N >= B - 1) {
        ll i = B - 1;
        ll temp = (A * i) / B - A * (i / B);
        ans = temp;
    } else {
        ll temp = (A * N) / B - A * (N / B);
        ans = temp;
    }

    cout << ans << endl;
}

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

using namespace std;

void Solve() {
	string s;
	cin >> s;

	string w;
	vector<int> cnt(s.length() + 5);
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == 'x') {
			cnt[w.length()] += 1;
		} else {
			w += s[i];
		}
	}

	int ans = 0;

	// cout << w << "\n";

	for (int i = 0; i <= (int)w.length() - i - 1; ++i) {
		int j = (int)w.length() - i - 1;
		// cout << i << " " << j << "\n";
		if (w[i] != w[j]) {
			cout << "-1\n";
			return;
		} else {
			ans += max(cnt[i], cnt[j+1]) - min(cnt[i], cnt[j+1]);
		}
	}

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

int main() {
	int tests = 1;

	for (;tests; --tests) {
		Solve();
	}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<ull> A(N), S(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]--;
		S[i + 1] = (S[i] + A[i] + K) % K;
	}

	map<int, int> mp;
	ull ans = 0;
	for (int i = 0; i <= N; i++) {
		if (i - K >= 0) mp[S[i - K]]--;
		ans += mp[S[i]];
		mp[S[i]]++;

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

Measured memory_bytes: 12800
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

int N,A;

int main(){
    cin>>N>>A;
    out(N*N-A);
}


Measured memory_bytes: 256
n = int(input())
a_list = list(map(int, input().split(" ")))
sorted_a_list = sorted(a_list, reverse=True)
total_comfort = 0
if n%2==0:
    right_index = n/2
    for i, i_comfort in enumerate(sorted_a_list):
        if i==right_index:
            break
        if i==0:
            total_comfort+=i_comfort
        else:
            total_comfort+=i_comfort*2
else:
    right_index = (n+1)/2
    for i, i_comfort in enumerate(sorted_a_list):
        if i==right_index:
            break
        if i==0 or i==right_index-1:
            total_comfort+=i_comfort
        elif i==right_index-1:
            total_comfort+=i_comfort
        else:
            total_comfort+=i_comfort*2
print(total_comfort)

Measured memory_bytes: 31600
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<numeric>
using namespace std;
typedef long long int ll;
 
ll gcd(ll a, ll b){
    if (b == 0) return a;

    return gcd(b, a % b);
}

int main(){
    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    ll tmp = C*D / gcd(C, D);
    ll A_C_num, A_D_num, A_CD_num, A_num;
    if (A % C == 0) A_C_num = A / C - 1;
    else A_C_num = A / C;
    if (A % D == 0) A_D_num = A / D - 1;
    else A_D_num = A / D;
    if (A % tmp == 0) A_CD_num = A / tmp - 1;
    else A_CD_num = A / tmp; 
    A_num = A_C_num + A_D_num - A_CD_num;

    ll B_C_num, B_D_num, B_CD_num, B_num;
    B_C_num = B / C;
    B_D_num = B / D;
    B_CD_num = B / tmp; 
    B_num = B_C_num + B_D_num - B_CD_num;

    cout << (B - A - B_num + A_num + 1) << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int n, x, ans;
    
    while(1){
        cin >> n >> x;
        ans = 0;
        if(n == 0 && x == 0) break;
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                for(int k = j + 1; k <= n; k++){
                    int sum = i + j + k;
                    if ( sum == x){
                        ans += 1;
                    }
                }
            }
        }
        
        cout << ans <<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  ll n, m;
  cin >> n >> m;

  vector<ll> a(n);
  ll total = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    total += a[i];
  }

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] * 4 * m < total) {
      continue;
    }

    cnt++;
  }

  if (cnt >= m) {
    cout << "Yes" << ln;
  } else {
    cout << "No" << ln;
  }

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
inline int getInt() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//---------------------------------------------------------------
#define fastio std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
//--------------------------------------------------------------
// [gcd]
template<class T> T gcd(T a, T b)
{if (a < b) swap(a,b);return b ? gcd(b, a % b) : a;}
template<class T> T lcm(T a, T b)
{return a * b / gcd(a, b);}

int main(int argc,char** argv){ fastio; myio;
  int n;
  cin>>n;
  ll s;
  cin>>s;
  vl x(n,0ll);
  vl y(n,0ll);
  cin>>x;
  x.pb(s);
  sort(rng(x));
  rep(i,n){
    y[i]=(x[i+1]-x[i]);
  }
  ll ng = y[0];
  rep(i,n){
    ng = gcd(ng,y[i]);
  }
  cout<<ng;
}

Measured memory_bytes: 2560