akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll MOD = 1000000007;
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;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////
const int MAX = 510000;

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;
}
 



int main() {
	int ans = 0;
	int N,C;	cin >> N >> C;
	int D[C+2][C+2];
	for (int i = 1; i <= C; i++) //Dを格納
	{
		for (int j = 1; j <= C; j++)
		{
			cin >> D[i][j];
		}	
	}
	int c[N+2][N+2];
	for (int i = 1; i <= N; i++)//cを格納
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> c[i][j];
		}
	}
	ll p[C+1] = {};
	ll q[C+1] = {};
	ll r[C+1] = {};
	for (int pp = 1; pp <= C; pp++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if((i+j)%3 == 0){p[pp] += D[c[i][j]][pp];}
				else if((i+j)%3 == 1){q[pp] += D[c[i][j]][pp];}
				else if((i+j)%3 == 2){r[pp] += D[c[i][j]][pp];}
			}
		}
	}
	
	ans = p[1] + q[2] + r[3];
	for (int pp = 1; pp <= C; pp++)
	{
		for (int qq = 1; qq <= C; qq++)
		{
			for (int rr = 1; rr <= C; rr++)
			{
				if(pp == qq or qq == rr or rr == pp){continue;}
				ll n_ans = p[pp] + q[qq] + r[rr];
				if(n_ans < ans){ans = n_ans;}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define P pair<int,int>
#define PI 3.141592653589793
const int INF = 1001001001;
const ll MX = 1e18;

int main() {
	ll n;
	cin >> n;
	cout << n * (n - 1) / 2;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,a,b) for (int i = (a); i < (b); i++ )
typedef pair<int,int> P;
typedef long long ll;
const int INF = 100000000;
const double PI=3.14159265358979323846;

int main (){
    ll N;
    cin >> N;
    ll A[N],A_cum[N+1];
    ll L=0;
    A_cum[0] = 0;
    rep(i,0,N) {
        cin >> A[i];
        L+=A[i];
        A_cum[i+1] = A_cum[i]+A[i]; 
    }
    ll tmp1,tmp2;
    rep(i,0,N) {
        if (A_cum[i+1]==L/2 && L%2==0) {
            cout << 0 << endl;
            break;
        }
        else {
            if (A_cum[i+1]>L/2) {
                tmp2=A_cum[i+1];
                tmp1=A_cum[i];
                ll ans = min(2*tmp2-L,L-2*tmp1);
                cout << ans << endl;
                break;
            }
        }
    }

}





Measured memory_bytes: 3328
n, k = map(int, input().split())
a = [0]+list(map(int, input().split()))

num = 1
li = [1]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])

Measured memory_bytes: 32368
#include <bits/stdc++.h>
using namespace std;
int H,W;
int main(){
    cin>>H>>W;
    string s[H];
    for(int i=0;i<H;i++) cin>>s[i];

    for(int i=0;i<W+2;i++)cout<<'#';
    cout<<"\n";

    for(int i=0;i<H;i++)
        cout<<'#'<<s[i]<<'#'<<"\n";
    
    for(int i=0;i<W+2;i++)cout<<'#';
    cout<<"\n";


    return 0;
}



Measured memory_bytes: 256
a, b = map(int, input().split())

def f(n):
    # XOR([o to n])
    if (n+1)%2 == 0: # 総数が偶数
        if ((n+1)//2)%2 == 0: # ペアが偶数
            return 0
        else: # ペアが奇数
            return 1
    else: # 総数が奇数
        if ((n+1)//2)%2 == 0: # 2つ1組のペアが偶数
            return n
        else: # ペアが奇数
            return n+1
        
        
result = f(a-1) ^ f(b)
    
print(result)

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

#define MAXN (100010)
#define ll long long

int n, m;
std::vector<int> vec[MAXN];
int col[MAXN];
bool vis[MAXN];
int non_bi;

void dfs(int u, int c){
	col[u] = c;
	vis[u] = 1;
	for(int v : vec[u]){
		if(vis[v]){
			if(col[v] != (c ^ 1)) non_bi = 1;
			continue;
		}
		dfs(v, c ^ 1);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i){
		int u, v;
		scanf("%d%d", &u, &v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	ll n1 = 0, n2 = 0, a = 0;
	for(int i = 1; i <= n; ++ i){
		if(!vis[i]){
			if(vec[i].empty()){
			    a ++;
			    continue;
			}
			non_bi = 0;
			dfs(i, 0);
			if(non_bi){
				n2 ++;
			}
			else{
				n1 ++;
			}
		}
	}
	ll ans = (2ll) * a * n - a * a + n1 * n1 * 2 + n2 * n2 + n1 * n2 * 2;
	std::cout << ans << std::endl;
	return 0;
}

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

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

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection) (collection).begin(), (collection).end()  // begin to end
#define each(e, collection) for(auto& e: collection)              // for each
#define rep(i, begin, end) for (ll i = begin; i < end; i++)       // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)      // repeat reverse
#define size(collection) ((ll) (collection).size())               // collection size

#endif

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

	double ans;
	if (n == 1)
		ans = 1.0;
	else if (n % 2 == 1)
		ans = (double)((n / 2) + 1) / (double)n;
	else
		ans = 0.5;

	cout << ans;

	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int a[100'009];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  sort(a, a + n);
  printf("%d\n", a[n / 2] - a[n / 2 - 1]);
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define vmax 10000
constexpr ll inf = 100000000000000;
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/

static const int N=100;
static const int W=10010;
ll dp[N+1][2];

int main(){
    int l,k;
    ll sum=0;
    cin>>l>>k;
    for(int i=1;i<=l;i++){
        for(int j=0;j<2;j++){
            dp[i][j]=0;
        }
    }
    dp[1][0]=1;
    dp[k][0]=1;
    for(int i=1;i<=l;i++){
        for(int j=0;j<2;j++){
            if(j==0){
                if(l>=i+1){
                    dp[i+1][1]+=dp[i][0];
                }
            }else{
                if(l-i>=k){
                    dp[i+k][0]+=dp[i][1];
                }
                if(l>=i+1){
                    dp[i+1][0]+=dp[i][1];
                }
            }
        }
    }
    for(int i=1;i<=l;i++){
        sum+=dp[i][0];
    }
    cout<<sum<<endl;
    return 0;
}



Measured memory_bytes: 3084
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        int N = scanner.nextInt();

        if (N == 0) {
            System.out.println(X);
            System.exit(0);
        }

        int[] p;
        p = new int [N];

        for (int i = 0; i < N; i++) {
            p[i] = scanner.nextInt();
        }

        List<Integer> list = new ArrayList<>(p.length);
        for (int i = 0; i < p.length; i++) {
            list.add(p[i]);
        }

        int ans = 0;

        for (int i = 1; i < X+1; i++) {
            for (int j = -1; j < 2; j++) {
                ans  = X + j * i;
                if (Collections.frequency(list,ans) == 0) {
                    System.out.println(ans);
                    System.exit(0);
                }
            }
        }
    }
}


Measured memory_bytes: 27304
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<cassert>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<limits>
#include<ctime>
#include<stack>
#include<bits/stdc++.h>
#include<string>
#include<stdlib.h>
#include<stdio.h>
#define long long

using namespace std;
int main() {
	int n,ans=0;
	cin>>n;
	float a[n],sum=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	float avg;
	avg=round(sum/n);
	for(int i=0;i<n;i++){
		ans+=pow(abs(avg-a[i]),2);
	}
	cout<<ans;
}


Measured memory_bytes: 3716
{-# LANGUAGE TypeApplications #-}
module Main where

import           Data.Map.Strict                ( Map )
import qualified Data.Map.Strict               as Map
import           Data.IntMap                    ( IntMap )
import qualified Data.IntMap                   as IntMap
import           Data.HashMap.Strict            ( HashMap )
import qualified Data.HashMap.Strict           as HashMap
import           Data.Maybe                     ( fromMaybe )
import           Control.Monad

main :: IO ()
main = do
  n <- readLn :: IO Int
  let im = foldr (\tri m -> IntMap.insertWith (+) (f tri) (g tri) m) IntMap.empty $ combsWithRep [1..100] 3
  mapM_ (\i -> print @Int $ fromMaybe 0 (im IntMap.!? i)) [1..n]
  
f [x, y, z] = x*x + y*y + z*z + x*y + y*z + z*x
g [x, y, z]
  | x == y && y == z = 1
  | x /= y && y /= z && z /= x = 6
  | otherwise = 3

combsWithRep :: [a] -> Int -> [[a]]
combsWithRep xs k = combsBySize xs !! k
 where
  combsBySize = foldr f ([[]] : repeat [])
  f x = scanl1 $ (++) . map (x :)


Measured memory_bytes: 45788
import java.util.Scanner;

class Main{

public static void main(String [] args){

Scanner sc = new Scanner(System.in);

int W = sc.nextInt();

int H = sc.nextInt();

int x = sc.nextInt();

int y = sc.nextInt();

int r = sc.nextInt();

if((x - r) >= 0 && (x + r) <= W && (y - r) >= 0 && (y + r) <= H){
System.out.println("Yes");
}else{
System.out.println("No");
}


}
}



Measured memory_bytes: 26184
import itertools
N, M, Q = map(int, input().split())
L = [0 for _ in range(Q)]
for i in range(Q):
    L[i] = list(map(int, input().split()))

A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
ans = 0
for a in A:
    tmp = 0
    for l in L:
        if a[l[1] - 1] - a[l[0] - 1] == l[2]:
            tmp += l[3]
    else:
        ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 21440
(a, b, x) = map(int, input().split())

n_lt_a = a // x + 1
n_lt_b = b // x + 1

if a % x == 0:
    ans = n_lt_b - n_lt_a + 1
else:
    ans = n_lt_b - n_lt_a
print(ans)


Measured memory_bytes: 9164
import sys
sys.setrecursionlimit(10**6)

X = int(input())

temp_list = [0 for i in range(3761)]


def solve(n):
    if n == 0:
        return 100
    if temp_list[n] != 0:
        return temp_list[n]
    temp = solve(n - 1)
    a = temp + int(temp * 0.01)
    temp_list[n] = a
    return a


for i in range(3761):
    if solve(i) >= X:
        print(i)
        exit()

Measured memory_bytes: 9328
s = input()
t = input()
n = len(s)

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(alph)}

set_ = set(list(s))
for char in t:
    if char not in set_:
        print(-1)
        exit()

next_ = [[0] * 26 for i in range(n + 1)]
for i in range(n)[::-1]:
    for j, char in enumerate(alph):
        if s[i] == char:
            next_[i][j] = i + 1
        else:
            next_[i][j] = next_[i + 1][j]

ans = 0
pos = 0
for char in t:
    if next_[pos][to_int[char]] == 0:
        ans += len(s)
        pos = next_[0][to_int[char]]
    else:
        pos = next_[pos][to_int[char]]
print(ans + pos)

Measured memory_bytes: 73576
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>


using namespace std;

int main(){

	int N;
	string A, B, C;

	cin >> N >> A >> B >> C;

	int sum = 0;
	for(int i=0;i<N;i++){
		if(A[i] ==  B[i] && B[i] == C[i]){
			sum +=0;
		} else if(A[i] == B[i] || B[i] == C[i] || C[i] == A[i]){
			sum +=1;
		} else {
			sum +=2;
		}
	}
	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
            System.out.println("Bad");
        } else {
            System.out.println("Good");
        }
    }
}


Measured memory_bytes: 35608
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int N;
int s[5010] = {};
ll A[5010] = {},dp1[5010][5010] = {},dp2[5010][5010] = {};
//1:その点を根とした部分木の各点の値がすべて正
//2:負が含まれる
const ll inf = 2e18;
vector<vector<int>> v(5010);

void dfs(int n,int m){
    s[n] = 1;
    if(A[n]>0) dp1[n][0] = A[n];
    dp2[n][0] = A[n];
    for(auto x:v[n]){
        if(x==m) continue;
        dfs(x,n);
        vector<ll> merge1(N+1,inf),merge2(N+1,inf);
        for(int i=0;i<s[n];i++){
            for(int j=0;j<s[x];j++){
                if(dp1[x][j]!=inf){
                    merge1[i+j] = min(merge1[i+j],dp1[n][i]+dp1[x][j]);
                    merge1[i+j+1] = min(merge1[i+j+1],dp1[n][i]);
                    merge2[i+j+1] = min(merge2[i+j+1],dp2[n][i]);
                }
                if(dp2[x][j]!=inf){
                    merge2[i+j] = min(merge2[i+j],dp2[n][i]+dp2[x][j]);
                    if(dp2[x][j]<0){
                        merge2[i+j+1] = min(merge2[i+j+1],dp2[n][i]);
                        merge1[i+j+1] = min(merge1[i+j+1],dp1[n][i]);
                    }
                }
            }
        }
        for(int i=0;i<N;i++){dp1[n][i] = merge1[i]; dp2[n][i] = merge2[i];}
        s[n] += s[x];
    }
}

int main(){
    cin >> N;
    for(int i=1;i<=N;i++) cin >> A[i];
    int a,b;
    for(int i=1;i<=N-1;i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=N;i++) for(int j=0;j<=N;j++) {dp1[i][j] = inf; dp2[i][j] = inf;}
    dfs(1,0);
    int ans = N;
    for(int i=N-1;i>=0;i--){
        if(dp1[1][i]!=inf) ans = i;
        if(dp2[1][i]<0) ans = i;
    }
    cout << ans << endl;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v)                                                            \
  do {                                                                         \
    x = max(x, v);                                                             \
  } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll gcd(ll x, ll y) {
  if (x > y)
    swap(x, y);
  if (x == 0)
    return y;
  return gcd(y % x, x);
}

signed main() {
  ll a, b;
  cin >> a >> b;
  cout << a * b / gcd(a, b) << endl;
  return 0;
}


Measured memory_bytes: 256
//In The Name Of The God

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define F first
#define S second
#define X first.first
#define Y first .second
#define A second.first
#define B second.second
#define mp make_pair
#define pb push_back
#define pf push_front
#define P push
#define pob pop_back
#define pof pop_front
#define PO pop
#define rep(i,j,k) for(int i = j ; i <= k ; ++ i)
#define rrep(i,j,k) for(int i = j ; i>=k ; --i)
#define FR(i,j,k) for(int i = j ; i < k ; ++ i )
#define rFR(i,j,k) for(int i = j ; i > k ; -- i )
#define lb(x) x&-x
#define p2(x) (1LL<<x)
#define SZ size()
#define LB lower_bound
#define UB upper_bound
#define IT iterator
#define RIT reverse_iterator
#define E end()
#define BE begin()
#define RE rend()
#define RBE rbegin()
#define UN unsigned

typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll ;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<int,pll> pipl;
typedef pair<pll,int> ppli ;
typedef pair<pll,pll> plpl ;
typedef pair<ll,pii> lpip;
typedef pair<pii,ll> lppi;
typedef pair<pii,pii> lppp;
typedef pair<ll,pll> lpipl;
typedef pair<pll,ll> lppli ;
typedef pair<pll,pll> lplpl ;
typedef vector<int> vi ;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef set<int> sti;
typedef set<ll> stl;
typedef set<pii > stpi;
typedef set<pll> stpl;
typedef vi::IT vit;
typedef vl::IT vlt;
typedef vpi::IT vpit;
typedef vpl::IT vplt;
typedef sti::IT stit;
typedef stl::IT stlt;
typedef stpi::IT stpit;
typedef stpl::IT stplt;
typedef vpi::RIT rvpit;
typedef vpl::RIT rvplt;
typedef sti::RIT rstit;
typedef stl::RIT rstlt;
typedef stpi::RIT rstpit;
typedef stpl::RIT rstplt;

const int MAXN = 500000;
const int SUPERN = 5000000;
const int MAXS = 325;
const int SUPERS = 1000;
const int MD = 1e9+7;
//......Structures.......

//......Variables........
int a,b,c,d,e,f,re,x,y;
bool r[4000],g[4000];
ld t;
//......Funcs............
ll sum(ll a,ll b)
{
    return (a+b)%MD;
}
ll mu(ll a,ll b)
{
    return (a*b)%MD;
}
ll mn(ll a,ll b)
{
    return(a-b+MD)%MD;
}
//......Code.............
int main()
{
    cin>>a>>b>>c>>d>>e>>f;
    r[0]=true;
    g[0]=true;
    for(int i=1;i<=f;i+=1)
    {
        if((i-c>=0&&g[i-c])||(i-d>=0&&g[i-d]))
        {
            g[i]=true;
        }
    }

    for(int i=100;i<=f;i+=100)
    {
        if((i-a*100>=0&&r[i-a*100])||(i-b*100>=0&&r[i-b*100]))
        {
            r[i]=true;
            rrep(j,min(f-i,e*i/100),0)
            {
                if(g[j])
                {
                    if(100.0*j/(j+i)>t){x=i;y=j;t=100.0*j/(j+i);}
                }
            }
        }
    }
    if(x==0)
    {

        cout<<a*100<<' '<<0;
        return 0;
    }
    cout<<x+y<<' '<<y<<'\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mo 1000000007
#define ll long long
using namespace std;
ll dp[100010],d1[100010][2],n,A,B;
void add(ll &x,ll y){x=(x+y)%mo;}
ll po(ll y){ll z=1;for (int i=1;i<=y;i++)z=z*2%mo;return z;}
int main(){
	cin>>n>>A>>B;
	if (A<B) swap(A,B);
	dp[1]=1;
	for (int i=1;i<A;i++){add(dp[i+1],dp[i]);for (int j=i+B+1;j<=A;j++)add(dp[j],dp[i]);}
	for (int i=1;i<A;i++)d1[i][0]=dp[i+1];
	for (int i=1;i<B;i++)d1[i][1]=1;
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<i+A;j++)if (j==n)add(d1[j][0],d1[i][1]*dp[j-i+1]);else add(d1[j][0],d1[i][1]*dp[j-i]);
		for (int j=i+1;j<i+B;j++)add(d1[j][1],d1[i][0]);
	}
	cout<<(po(n)-d1[n][0]-d1[n][1]+mo+mo)%mo<<endl;
	return 0;
}

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

int main() {
  string S;
  cin >> S;
  
  int a = S.size();
  char b = S.at(a-1);
  char c = 's';
 
  
  if(b == c){
    cout << S << "es" << endl;
  }
  else{
	cout << S << "s" << endl;
  }
  
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define MOD 998244353

ll mod_inv(ll a)
{
  ll left=MOD-2;
  ll ks=a;
  ll ret=1;
  while(left>0)
  {
    if(left%2==1)
    {
      ret=(ret*ks)%MOD;
    }
    ks=(ks*ks)%MOD;
    left/=2;
  }
  return ret;
}

ll pows(ll a, ll b)
{
  ll left=b;
  ll ks=a;
  ll ret=1;
  while(left>0)
  {
    if(left%2==1)
    {
      ret=(ret*ks)%MOD;
    }
    ks=(ks*ks)%MOD;
    left/=2;
  }
  return ret;
}


int main()
{
  ll n,m,k;cin>>n>>m>>k;
  if(m==1)
  {
    if(k==n-1)cout<<1<<endl;
    else cout<<0<<endl;
  }
  else
  {
    ll ans=pows(m-1,n-1);
    ans=ans*m%MOD;
    ll comb=1;
    int i;
    for(i=1;i<=k;i++)
    {
      comb=(comb*(n-i)%MOD)*mod_inv(i);
      comb%=MOD;
      ll add=pows(m-1,n-i-1);
      add=(add*m)%MOD;
      add=(add*comb)%MOD;
      ans=(ans+add)%MOD;
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 3636
n = int(raw_input())
F = [0] * (n+1)



def fibonacci(n):
    global F
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n] != 0:
        return F[n]
    F[n] = fibonacci(n-2) + fibonacci(n-1)
    return F[n]

def makeFibonacci(n):
    global F
    F[0] = 1
    F[1] = 1
    for i in xrange(2,n+1):
        F[i] = makeFibonacci(i-2) + makeFibonacci(i-1)
    return F[n]

def main():
    ans = fibonacci(n)
    print ans
    return 0

main()

Measured memory_bytes: 6472
from sys import stdin
import numpy as np

N = stdin.readline().rstrip()
A = np.array([int(x) for x in stdin.readline().split()], dtype=int)
B = np.sort(A - np.arange(1, len(A) + 1))
b = B[len(B) // 2]
print(np.abs(B - b).sum())


Measured memory_bytes: 34204
// E - League
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
using vi = vector<int>;
#define rp(i,n) for(int i=0;i<(n);i++)

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

	vector<vi> A(N, vi(N-1));
	rp(s,N){
		rp(d,N-1){ cin>>A[s][d]; --A[s][d]; }
		reverse(A[s].begin(), A[s].end());
	}

	vector<P> q;//選手iの直近の試合を選手のペアで保持（重複発生あり）

	//qへ、選手sの直近の試合を登録する関数（ラムダ式）
	auto match_make = [&](int s){
		if(A[s].size()==0) return;
		int d = A[s].back();
		// if(A[d].size()==0) return;//sにあればdにもあるはずなのでいらない
		if(A[d].back()==s){
			if(s > d) swap(s,d);//後の重複削除のために、s<d にそろえておく
			q.push_back(P(s,d));
		}
	};

	rp(s,N) match_make(s);//全選手の直近の試合をqへ登録

	int day = 0;
	while(q.size()){
		++day;

		sort(q.begin(), q.end());
		q.erase(unique(q.begin(), q.end()), q.end());//重複削除

		vector<P> p; swap(p,q);//p<-q, q<-{} : copy & clear

		for(P e:p){
			int s,d; tie(s,d) = e;
			A[s].pop_back(); A[d].pop_back();//s,d 両選手の直近の対戦相手を削除
		}

		for(P e:p){
			int s,d; tie(s,d) = e;
			match_make(s); match_make(d);//s,d 両選手の直近の試合をqに再登録
		}
	}

	rp(s,N) if(A[s].size()){ cout<< -1 <<endl; return 0; }
	cout<< day <<endl;
}

Measured memory_bytes: 4224
S = input()
A = int(S[:2])
B = int(S[2:])

if 0 < A < 13:
    AisM = True
else:
    AisM = False
    
if 0 < B < 13:
    BisM = True
else:
    BisM = False
    
if AisM and BisM:
    print('AMBIGUOUS')
elif AisM and not BisM:
    print('MMYY')
elif not AisM and BisM:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;
lint Divide(lint input)
{
	if (input == 1)
		return 1;

	return 2 * Divide(input / 2) + 1;
}
void execute()
{
	lint N;
	cin >> N;

	cout << Divide(N) << endl;
	return;
}

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

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int i,j,v,A[100],N;

  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  for(j=0;j<N-1;j++) printf("%d ",A[j]);
  printf("%d",A[N-1]);
  printf("\n");
  
  for(i=1;i<=N-1;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
    for(j=0;j<N-1;j++) printf("%d ",A[j]); 
    printf("%d",A[N-1]);
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 604
#include <stdio.h>
 
int main(void)
{
    int A[100][100];
    int b[100];
    int c, i, j, n, m;
     
    scanf("%d %d", &n, &m);
     
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            scanf("%d", &A[i][j]);
        }
    }
    for(i = 0; i < m; i++){
        scanf("%d", &b[i]);
    }
     
    for(i=0;i<n;i++){
        c = 0;
        for(j = 0; j < m; j++){
            c += A[i][j] * b[j];
        }
        printf("%d\n", c);
    } 
    return 0;
}


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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto n = load<int>();
    auto height = loadMany<int>(n);
    auto dyn = vector<int>(n);
    dyn[0] = 0;
    for (auto i=1; i<n; ++i) {
        dyn[i] = dyn[i-1] + abs(height[i-1] - height[i]);
        if (i >= 2)
            dyn[i] = min(dyn[i], dyn[i-2] + abs(height[i] - height[i-2]));
    }

    cout << dyn[n-1] << '\n';
}


Measured memory_bytes: 1152
N = int(input())
R = {}
*A, = map(int, input().split())
for i, a in enumerate(A):
    R.setdefault(a, []).append(i)

if N == 1:
    print(+(min(A) > 0))
else:
    res = 1; ans = +(min(A) > 0)
    for k in sorted(R):
        for i in R[k]:
            if 0 < i < N-1:
                if A[i-1] <= A[i] > A[i+1]:
                    res -= 1
                if A[i-1] > A[i] <= A[i+1]:
                    res += 1
            elif i == 0:
                if A[i] > A[i+1]:
                    res -= 1
            else:
                if A[i-1] <= A[i]:
                    res -= 1
        ans = max(ans, res)
    print(ans)



Measured memory_bytes: 29412
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  string s;
  cin >> s;
  int n = s.size();

  ll ret = INF;
  REP(i, s.size()-2) {
    string t = s.substr(i, 3);
    ll x = stoll(t);
    chmin(ret, abs(x-753));
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int W = input.nextInt();
        int H = input.nextInt();
        int x = input.nextInt();
        int y = input.nextInt();
        int r = input.nextInt();
        
        if (x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 26304
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 2e5;
int N;
ll K;
ll A[Nmax];

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

	vector<ll> b(N+1), d(N+1);
	b[0] = 0;
	for(int i=0; i<N; i++){
		b[i+1] = b[i]+A[i]-K;
	}
	d = b;
	sort(d.begin(), d.end());

	vector<int> c(N+1);
	for(int i=0; i<=N; i++){
		c[i] = lower_bound(d.begin(), d.end(), b[i]) - d.begin();
	}

	vector<int> bit(N+2);
	ll ans = 0;
	for(int i=0; i<=N; i++){
		for(int k=c[i]+1; k>0; k-=k&-k){
			ans += bit[k];
		}
		for(int k=c[i]+1; k<=N+1; k+=k&-k){
			bit[k] += 1;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6528
a = set([1,3,5,7,8,10,12])
b = set([4,6,9,11])
c = set([2])
x,y = map(int,input().split())
d = set([x,y])
if d.issubset(a)==True or d.issubset(b)==True or d.issubset(c)==True:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3060
#include <iostream>
#include<algorithm>
#include <vector>
#define FOR(i,m,M) for(int i = m;i<M;i++)
using namespace std;
int main()
{
	int N;
	cin >> N;
	vector<int> A(N);
	FOR(i, 0, N)
	{
		cin >> A[i];
	}
	vector<int> rew(N);
	FOR(i, 0, N)
	{
		rew[A[i]-1] = i + 1;
	}
	FOR(i, 0, N)
	{
		cout << rew[i] <<" ";
	}
}


Measured memory_bytes: 1536
INF = 100000000
N, M, R = gets.chomp.split(' ').map(&:to_i)
r = gets.chomp.split(' ').map(&:to_i)

cost = Array.new(N+1) {Array.new(N+1, INF)}

M.times do
  a, b, c = gets.chomp.split(' ').map(&:to_i)
  cost[a][b] = c
  cost[b][a] = c
end

(1..N).each do |k|
  (1..N).each do |i|
    (1..N).each do |j|
      path = cost[i][k] + cost[k][j]
      cost[i][j] = path if path < cost[i][j]
    end
  end
end

ans = INF
r.permutation do |rr|
  temp = 0
  (1..(R-1)).each do |i|
    temp += cost[rr[i-1]][rr[i]]
  end
  ans = [ans, temp].min
end

puts ans

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


#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ll long long


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

    cin >> a >> b >> c;

    cout << (b / a < c ? b / a : c) << endl;


    return 0;
}


Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Chars;
use std::cmp::{max, min};
const alpha: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];

const Alpha: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
fn main() {
    input!(N: usize);
    let mut ans = vec![0; 1_000_000];
    for x in 1..=200 {
        for y in 1..=200 {
            for z in 1..=200 {
                let idx = x * x + y * y + z * z + x * y + y * z + z * x;
                ans[idx] += 1;
            }
        }
    }

    for i in 1..=N {
        println!("{}", ans[i]);
    }
}


Measured memory_bytes: 2752
/***********************************************/
/* 2014.06.28 S_Nakka                          */
/*              0000：九九計算                 */
/* take1:新規作成                              */
/***********************************************/

#include<stdio.h>

int main(){

	int multiply1;
	int multiply2;

	for(multiply1 = 1; multiply1 <= 9; multiply1++)
	{
		for(multiply2 = 1; multiply2 <= 9; multiply2++)
		{
			printf("%dx%d=%d\n", multiply1, multiply2, 
				multiply1*multiply2);
		}
	}
    return 0;
}

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

int main(){
    int n,k;
    cin>>n>>k;
    if(k==1)cout<<0<<endl;
    else cout<<n-k<<endl;
}

Measured memory_bytes: 256
def solve( p, t ):
	global isExist
	global n
	global A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( raw_input() )
A = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
q = int( raw_input() )
M = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Measured memory_bytes: 4256
#include <stdio.h>

int main(void) {
	int N, caseCount;
	if (scanf("%d", &N) != 1) return 1;
	for (caseCount = 0; caseCount < N; caseCount++) {
		int r, t;
		if (scanf("%d%d", &r, &t) != 2) return 1;
		if (r % 100 == 0 && t % 30 == 0) {
			printf("%d\n", 5 * (t / 30) + (r / 100));
		} else if (t % 30 == 0) {
			printf("%d ", 5 * (t / 30) + (r / 100));
			printf("%d\n", 5 * (t / 30) + (r / 100 + 1));
		} else if (r % 100 == 0) {
			printf("%d ", 5 * (t / 30) + (r / 100));
			printf("%d\n", 5 * (t / 30 + 1) + (r / 100));
		} else {
			printf("%d ", 5 * (t / 30) + (r / 100));
			printf("%d ", 5 * (t / 30) + (r / 100 + 1));
			printf("%d ", 5 * (t / 30 + 1) + (r / 100));
			printf("%d\n", 5 * (t / 30 + 1) + (r / 100 + 1));
		}
	}
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

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

    ll ans=0;
    rep(i,N){
        ans+=(ll)(N-i)*(i+1);
    }
    rep(i,N-1){
        int u,v; cin>>u>>v; u--; v--;
        if (u>v) swap(u,v);
        ans-=(ll)(u+1)*(N-v);
    }

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


Measured memory_bytes: 3668
from itertools import product
from string import digits

n = int(input())
s = input()

ret = 0
for perm in product(digits, repeat=3):
    i = 0
    for c in s:
        if c == perm[i]:
            i += 1
            if i == 3:
                break
    if i == 3:
        ret += 1

print(ret)


Measured memory_bytes: 42780
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        //var n = int.Parse(Console.ReadLine());
        int[] ks = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var k = ks[0];
        var s = ks[1];

        var ans = 0;
        for (int i = 0; i <= k; i++)
        {
            for (int t = 0; t <= k; t++)
            {
                var z = s - i -t;
                if (0 <= z && z <= k) ans++;
            }
        }

        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n;
int main() {
  lli e=0;
  cin >> n;
  for (lli i=0; i<n; ++i) {
    lli x; cin >> x;
    if (x%2==1) ++e;
  }
  cout << (e%2==0 ? "YES" : "NO") << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long k = in.nextLong();
		if(k<=9) {
			for(int i=1;i<=k;i++) {
				System.out.println(i);
			}
		}else if(k<=18) {
			printDigit1();
			for(int i=10;i<=k;i++) {
				System.out.println(10*(i-9)+9);
			}
		}else {
			printDigit1();
			printDigit2();
			long target = 109;
			long prevTargetDigit = 3;
			long add=10;
			for(long i=19;i<=k;i++) {
				while(true) {
					if(prevTargetDigit!=getDigit(target)) {
						target = (long) Math.pow(10, getDigit(target)-1) + (long) Math.pow(10, getDigit(target)-getDigit(getDigitSum(target))) -1;
						prevTargetDigit = getDigit(target);
					}
					boolean found = false;
					long test = target + add;
					long limit = (1+getFirstNumber(target))*(long) Math.pow(10, getDigit(target)-1);
					while(!found && test<limit) {
						if((double)target/getDigitSum(target) > (double)test/getDigitSum(test)) {
							found = true;
							break;
						}
						test += add;
					}
					if(found) {
						target += add;
					}else {
						System.out.println(target);
						add = (long) Math.pow(10, getDigit(target)-getDigit(getDigitSum(target)));
						target += add;
						break;
					}
				}
			}
		}
	}
	
	public static void printDigit1() {
		for(int i=1;i<10;i++) {
			System.out.println(i);
		}
	}
	
	public static void printDigit2() {
		for(int i=1;i<10;i++) {
			System.out.println(10*i+9);
		}
	}
	
	public static long getDigitSum(long num) {
		long sum = 0;
		while(num>0) {
			sum += num % 10;
			num /= 10;
		}
		return sum;
	}
	
	public static long getDigit(long num) {
		long digit = 0;
		while(num>0) {
			digit++;
			num /= 10;
		}
		return digit;
	}
	
	public static long getFirstNumber(long num) {
		while(num>=10) {
			num /= 10;
		}
		return num;
	}

}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long n,s;
inline long long f(long long x,long long n) {
    long long ret=0;
    while (n) {
        ret+=n%x;
        n/=x;
    }
    return ret;
}
int main()
{
    cin>>n>>s;
    if (s>n) return cout<<-1<<endl,0;
    long long qn=1;
    while ((qn+1)*(qn+1)<=n) ++qn;
    for (long long i=2;i<=qn;++i)
        if (i<=n&&f(i,n)==s) {
            cout<<i<<endl;
            return 0;
        }
    if (n==s) {
        cout<<n+1<<endl;
        return 0;
    }
    long long mmin=inf;
    for (long long i=1;i<=qn;++i)
        if ((n-s)%i==0) {
            long long b=(n-s)/i+1;
            if (b>qn&&f(b,n)==s) mmin=min(mmin,b);
        }
    if (mmin==inf) mmin=-1;
    return cout<<mmin<<endl,0;
}


Measured memory_bytes: 3648
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  #k  = [i,j].min
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n,m,k = inm()
ufinit(n+1)
friend = [{} for i in range(n+1)]
for i in range(m):
    a,b = inm()
    friend[a][b] = 1
    friend[b][a] = 1
    ufconn(a,b)
blk = [{} for i in range(n+1)]
for i in range(k):
    a,b = inm()
    blk[a][b] = 1
    blk[b][a] = 1
gr = {}
for i in range(1,n+1):
    r = ufroot(i)
    if r in gr:
        gr[r] += 1
    else:
        gr[r] = 1
for i in range(1,n+1):
    r = ufroot(i)
    x = gr[r]-1
    for f in friend[i]:
        if ufroot(f)==r:
            x -= 1
    for f in blk[i]:
        if ufroot(f)==r:
            x -= 1
    printn(str(x)+' ')
print("")


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

int main(){
  string str_abc = "ABC";

  int N = 0;
  string str = "";

  cin >> N;
  cin >> str;

  int cnt = 0;
  int pos_abc = 0;
  for (int i = 0; i < N; i++) {
    if ( str[i] == str_abc[0] ) {
      pos_abc = 1;
    } else if ( str[i] == str_abc[pos_abc] ) {
      pos_abc++;

      if ( 2 < pos_abc ){
        cnt++;
        pos_abc = 0;
      }
    } else {
      pos_abc = 0;
    }
  }

  cout << cnt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
	string s;    cin >> s;
	int cnt = 0,ret=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'S') {
			cnt++;
		}
		else {
			cnt--;
			if (cnt < 0) {
				cnt = 0;
				ret++;
			}
		}
	}
	cout << ret + cnt << endl;
	return 0;
}

Measured memory_bytes: 640
#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 ll long long
#define INF 999999999
using namespace std;
int main() {
  int W,H,N,x,y,a;
  std::cin >> W >> H >> N;
  std::vector<int> F = {0,W,0,H};
  for (size_t i = 0; i < N; i++) {
    std::cin >> x >> y >> a;
    if (a == 1) {
      F[0] = max(x,F[0]);
    }
    if (a == 2) {
      F[1] = min(x,F[1]);
    }
    if (a == 3) {
      F[2] = max(y,F[2]);
    }
    if (a == 4) {
      F[3] = min(y,F[3]);
    }
  }
  if (F[0] >= F[1] || F[2] >= F[3]) {
    std::cout << 0 << '\n';
  }
  else{
    std::cout << (F[1]-F[0])*(F[3]-F[2]) << '\n';
  }
}


Measured memory_bytes: 256
/**
 * author: Dhakad@123
 **/

#include<bits/stdc++.h>
using namespace std;

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

  int X , A ;
  cin >> X >> A;

  if(X < A){
	  cout << 0 <<"\n";
  }
  else{
	 cout << 10 <<"\n";
  }
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define f first
#define s second
#define pb push_back
#define pp push
#define RETURN exit(0)
#define pow(x,y) (int)(pow(x,y))
#define ceil(x) (int)(ceil(x))
#ifndef ONLINE_JUDGE
#define debug(x) cout<<x<<endl;
#else
#define debug(x) 42
#endif
const int MAX=1e7;
const int MOD=1e9+7;
const int MAAX=1e15;
const long double EPS=1e-6;
const int N=1e6;
int power(int x,int y)
{
    if (y == 0)
        return 1;
    int a=power(x,y/2)%MOD;
    if (y % 2 == 0)
        return a * a % MOD;
    else
        return x * a % MOD * a % MOD;
}
long double sq(int x){
    long double s=0,e=x,mid;
    while(e-s>=EPS){
        mid=(s+e)/2;
        if(mid*mid<=x){
            s=mid;
        }
        else{
            e=mid-EPS;
        }
    }
    return s;
}
vector<int> primes;
bool visted[N+5];
void sieve(){
    visted[0]=visted[1]=1;
    for(int i=2;i*i<=N;i++){
        if(visted[i]==0){
            primes.pb(i);
            for(int j=i*i;j<=N;j+=i){
                visted[j]=1;
            }
        }
    }
    for(int i=sqrt(N)+1;i<=N;i++){
        if(visted[i]==0)
            primes.pb(i);
    }
    return;
}

int n,m;
pair<int,int>c[100010];
int arr[100010];

in main()
{
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    int tc=1;
    //sieve();
    //scanf("%lld",&tc);
    while(tc--)
    {
        cin>>n>>m;
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            sum+=arr[i];
        }
        sort(arr,arr+n);
        for(int i=0;i<m;i++){
            cin>>c[i].s>>c[i].f;
            c[i].f*=-1;
        }
        sort(c,c+m);
        int x=0;
        int mx=sum;
        for(int i=0;i<n&&x<m;i++){
            sum-=arr[i];
            sum+=c[x].f*-1;
            c[x].s--;
            if(c[x].s==0)
                x++;
            mx=max(mx,sum);
        }
        cout<<mx<<endl;
    }
    RETURN;
}


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

typedef long long ll;

int
main(void)
{
  int x; cin >> x;
  if(x == 2){
    cout << x << endl;
    return 0;
  }   
  while(true){
    bool is_prime = true;
    for(int i = 2; i < x; ++i){
      if(x % i == 0){
        is_prime = false; 
        break;
      }
    }
    if(is_prime){
      cout << x << endl;
      return 0;
    }
    ++x;
  }

  return 0;
}

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

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void write(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

inline void writeln(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
     puts("");
}

signed main(){
    char a;
    a=getchar();
    
    if(a>='A' && a<='Z')
        puts("A");
    else
        puts("a");
        
    return 0;        
}

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

int main() {
    int N;
    cin >> N;
    vector<pair<pair<string, int>, int>> pairs;
    string s; int p;
    rep(i, N){
        cin >> s >> p;
        pairs.push_back(make_pair(make_pair(s, -p), i + 1));
    }
    sort(pairs.begin(), pairs.end());

    rep(i, N){
        cout << pairs.at(i).second << endl;
    }
}


Measured memory_bytes: 3552
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

void solve()
{

}

int f[1000005];

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

rep(i,1,200)
{
	rep(j,1,200)
	{
		rep(k,1,200)
		{
			int kk=i*i+j*j+k*k+i*j+j*k+k*i;
			f[kk]++;
		}
	}
}
rep(i,1,n)
{
	ol(f[i]);on;
}
return 0;
}



Measured memory_bytes: 4548