akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

// #define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;
using P = pair<int, int>;
using ll = long long;
vector<int> to[100005];
int cost[100005];

ll calc(long a) {
    a++;
    ll ans = 0;
    rep(i, 50) {
        ll loop = (1LL << (i+1)); //2 4 8...
        ll cnt = (a/loop)*(loop/2); //回数*(loopの中の1)
        cnt += max(0LL, a%loop-loop/2); 
        if(cnt%2==1) ans += 1LL<<i;
    }
    return ans;
}

signed main(){
    long long a, b;
    cin >> a >> b;
    ll ans = calc(b)^calc(a-1);
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 2560
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int rate; cin >> rate;

    if(rate < 1200) {
        cout << "ABC" << endl;
    }
    else if(rate < 2800) {
        cout << "ARC" << endl;
    }
    else {
        cout << "AGC" << endl;
    }
    return 0;
}

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

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }


int main(){
    string Sa,Sb,Sc;
    cin >> Sa >> Sb >> Sc;

    char c = Sa[0];
    Sa.erase(0,1);
    if(Sa.size() == 0){
        cout << 'A' << endl;
        return 0;
    }



    while(1){
        if(c == 'a'){
            if(Sa.size() == 0){
                cout << 'A' << endl;
                return 0;
            }
            c = Sa[0];
            Sa.erase(0,1);
        }else if(c == 'b'){
            if(Sb.size() == 0){
                cout << 'B' << endl;
                return 0;
            }
            c = Sb[0];
            Sb.erase(0,1);
        }else{
            if(Sc.size() == 0){
                cout << 'C' << endl;
                return 0;
            }
            c = Sc[0];
            Sc.erase(0,1);
        }
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long int n,w;
    cin >> n >> w;
    long long int wt[n];
    long long int val[n];
    for(long long int i = 0; i< n; i++){
        cin >> wt[i] >> val[i];
    }
    
    long long int dp[w+1][n+1];
    for(long long int i = 0; i< w+1; i++) {
        for(long long int j = 0; j < n+1; j++){
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else {
                if(wt[j-1]<=i){
                    dp[i][j] = max(val[j-1] + dp[i-wt[j-1]][j-1], dp[i][j-1]);
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
    }
    cout << dp[w][n] << " ";
    
    
    // cout << 
    // cout << max(A[n-1], max(B[n-1], C[n-1]));
    

}

Measured memory_bytes: 82440
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
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 main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n ;
  cin >> n;
  int cnt = 0 ;
  REP(i,n){
    int a ;
    cin >>a  ;
    if(a%2==1){
      cnt++ ;
    }
  }
  if(cnt%2==0){
    cout <<"YES"<<endl ;
  }
  else{
    cout <<"NO"<<endl ;
  }
  
  
  return 0 ;
}




Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <cmath>
#include <ctime>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
#include <list>
#include <deque>
#include <numeric>
#include <set>
#include <climits>
#include <utility>
#include <map>
#include <float.h>
typedef long long ll;
typedef unsigned long long ull;
inline int max( int x, int y ){ return x > y ? x : y ; }
inline int min( int x, int y ){ return x < y ? x : y ; }
inline ll max( ll x, ll y ){ return x > y ? x : y ; }
inline ll min( ll x, ll y ){ return x < y ? x : y ; }
inline ull max( ull x, ull y ){ return x > y ? x : y ; }
inline ull min( ull x, ull y ){ return x < y ? x : y ; }
int GCD( int a, int b ) { return b ? GCD( b , a%b ) : a; }
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PIV 3.14159265358979323846
#define MAXN 100
typedef pair<ll, ll> P;
const int MAX_V = 400+1;

int main(){
	
	string a, b;
	cin >> a;
	cin >> b;
	
	int cnt = 0;
	for( int i=0; i<a.length(); ++i ){
		if( a[i] == b[i] ) cnt++;
	}
	cout << cnt;
	return 0;
}









Measured memory_bytes: 256
# -*- coding: utf-8 -*-

x, y = map(int, input().split())

CLASS_A = [1,3,5,7,8,10,12]
CLASS_B = [4,6,9,11]
CLASS_C = [2]

if x in CLASS_A:
    class_x = "A"
elif x in CLASS_B:
    class_x = "B"
else:
    class_x = "C"

if y in CLASS_A:
    class_y = "A"
elif y in CLASS_B:
    class_y = "B"
else:
    class_y = "C"

if class_x == class_y:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int x=Integer.parseInt(st.nextToken());
            if(n==0&&x==0) break;
            int count=0;
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    for(int k=j+1;k<=n;k++){
                        if(i+j+k==x) count++;
                    }
                }
            }System.out.println(count);
        }
        
    }
}

Measured memory_bytes: 25408
#include<stdio.h>
#include<string.h>
int main(void)
{
	int i,j,len,n,flg;
	char s[100],t[100],box;
	scanf("%s %s",s,t);
	len=strlen(s);
	n=strlen(t);
	for(i=0;i<len-1;i++){
		for(j=i+1;j<len;j++){
			if(s[i]>s[j]){
			     box=s[i];
				s[i]=s[j];
				s[j]=box;
			}
		}
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(t[i]<t[j]){
				box=t[i];
				t[i]=t[j];
				t[j]=box;
			}
		}
	}
	if(strcmp(s,t)<0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

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

struct data{
	int num;
	int counted;
};

int main(){
	data a[4];
	data b[4];
	while(cin >> a[0].num >> a[1].num >> a[2].num >> a[3].num
		>> b[0].num >> b[1].num >> b[2].num >> b[3].num)
	{
		int hit = 0;
		int blow = 0;
		for(int i = 0; i < 4; i++){
			a[i].counted = 1;
			b[i].counted = 1;
		}
		for(int j = 0; j < 4; j++){
			if(a[j].num == b[j].num){
				a[j].counted = b[j].counted = 0;
				hit++;
			}
		}
		for(int k = 0; k < 4; k++){
			for(int l = 0; l < 4; l++){
				if(a[k].counted == 1 && b[l].counted == 1){
					if(a[k].num == b[l].num){
						a[k].counted = b[l].counted = 0;
						blow++;
					}
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

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

int main(){
    char str[20];
    scanf("%s",str);
    if(strlen(str)<4 ){
        printf("No");
    }
    else if(str[0]=='Y'&&str[1]=='A'&&str[2]=='K'&&str[3]=='I'){
        printf("Yes");
    }
    else printf("No");

}


Measured memory_bytes: 256
import sys

N = int(input())
saveN = N
B = list(map(int,input().split()))
B.insert(0, -1) 
rem = []
while N > 0:
    sch = N
    while sch >= 0:
        if B[sch] == sch:
            rem.append(B.pop(sch))
            N -= 1
            break
        sch -= 1
    if sch == -1: 
        print("-1")
        sys.exit()

for i in range(saveN):
    print(str(rem[saveN-1 - i]))

Measured memory_bytes: 3064
#include<iostream>
#include<string>

using namespace std;

int main(){
	int n,c=1,r=0;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	for(int i = 2; i < n; i++){
		if(a[i-2] < a[i-1] || r == 1){
			r = 1;
			if(a[i-1] > a[i]){
				c++;
				i++;
				r=0;
			}
		}
		else if(a[i-2] > a[i-1] || r == -1){
			r = -1;
			if(a[i-1] < a[i]){
				c++;
				i++;
				r=0;
			}
		}
	}
	
	cout << c << endl;
	
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
using namespace std;
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a<=c)
	{
		if(b<=c)
		{
			printf("0"); 
		}
		else if(b<=d)
		{
			printf("%d",b-c);
		}
		else
		{
			printf("%d",d-c);
		}
	}
	else
	{
		if(d<=a)
		{
			printf("0");
		}
		else if(d<=b)
		{
			printf("%d",d-a);
		}
		else
		{
			printf("%d",b-a);
		}
	}
	
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
			StringBuilder answer = new StringBuilder();
			String lb = System.getProperty("line.separator");
			
			String str = input.readLine();
			while (!"-".equals(str)) {
				final int m = Integer.parseInt(input.readLine());
				for (int i = 0; i < m; i++) {
					final int h = Integer.parseInt(input.readLine());
					str = str.substring(h) + str.substring(0, h);
				}
				answer.append(str).append(lb);
				str = input.readLine();
			}
			
			System.out.print(answer.toString());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 17188
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	
	cin>>N;
	
	cout<<(N+1)/2<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
import os
import sys


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(max=10 ** 6 * 2 + 100, mod=MOD)


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb.ncr(n + r, r)


# @debug
def g(r, c):
    ret = 0
    for i in range(1, c + 2):
        ret += f(r, i)
        ret %= MOD
    return ret


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)


Measured memory_bytes: 130560
class LCM():
    #a、bに最小公倍数または最大公約数を求めたい二つの整数の組を入れる
    def __init__(self,a,b):
        if a < b:a,b = b,a
        self.a = a
        self.b = b

    #最大公約数
    def gcd(self):
        a,b = self.a,self.b
        def nono(a,b):
            if a < b:a,b = b,a
            if a % b == 0:return b
            else:return nono(b,a % b)
        return nono(a,b)

    #最小公倍数
    def lcm(self):
        a,b = self.a,self.b
        def nono(a,b):
            if a < b:a,b = b,a
            if a % b == 0:return b
            else:return nono(b,a % b)
        num = nono(a,b)
        return a*b//num
a,b,c,d = map(int,input().split())
a -= 1
#a
numa = 0
numa += a // c
numa += a // d
cc = LCM(c,d).lcm()
numa -= a // cc

numb = 0
numb += b // c
numb += b // d
numb -= b // cc
print((b-a) - (numb - numa))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (ll i = ll(s); i < ll(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

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

int main(){
    ll n; cin >> n;
    for(int i=1; i<=3500; i++){
        for(int j=1; j<=3500; j++){
            if((4*i*j - n*i - n*j) != 0 && (n*i*j) % (4*i*j - n*i - n*j) == 0){
                ll ans = (n*i*j)/(4*i*j - n*i - n*j);
              if(ans > 0){
                cout << i << " " <<  j << " " << ans <<endl;
                return 0;
              }
            }
        }
    }
}

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

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int D = Integer.parseInt(sc.next());
        int[] c = new int[26];
        int[] cd = new int[26];
        for (int i = 0; i < 26; i++) {
            c[i] = Integer.parseInt(sc.next());
        }
        int[][] s = new int[D][26];
        int[] max = new int[D];
        for (int i = 0; i < D; i++) {
            int maxd = 0;
            int maxdd = 0;
            for (int j = 0; j < 26; j++) {
                int temp = Integer.parseInt(sc.next());
                s[i][j] = temp;
                if (maxd < temp) {
                    maxd = temp;
                    maxdd = j + 1;
                }
            }
            max[i] = maxdd;
        }
        int[] t = new int[D];
        StringBuilder sb = new StringBuilder();
        int ans = 0;
        for (int i = 0; i < D; i++) {
            int temp = Integer.parseInt(sc.next());
            t[i] = temp;
//            temp = max[i];
//            cd[temp - 1] = i + 1;
//            ans += s[i][temp - 1] - totalSubC(c, cd, i + 1);
//            sb.append(ans);
//            sb.append("\n");
        }
        int m = Integer.parseInt(sc.next());
        for (int i = 0; i < m; i++) {
            int d = Integer.parseInt(sc.next());
            int q = Integer.parseInt(sc.next());
            int old = t[d - 1];
            t[d - 1] = q;
            ans = total(c, cd, s, t, D);
//            t[d - 1] = old;
            Arrays.fill(cd, 0);
            sb.append(ans);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    private static int totalSubC(int[] c, int[] cd, int d) {
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += c[i] * (Math.max(0, d - cd[i]));
        }
        return ans;
    }

    private static int total(int[] c, int[] cd, int[][] s, int[] t, int D) {
        int ans = 0;
        for (int i = 0; i < D; i++) {
            cd[t[i] - 1] = i + 1;
            ans += s[i][t[i] - 1] - totalSubC(c, cd, i + 1);
//            System.out.println(ans);
        }
        return ans;
    }
}

Measured memory_bytes: 60040
#include <bits/stdc++.h>
using namespace std;
int isprime[100001]={1,1,0},prime[100001],s[100001];
int main()
{
	int i,j;
	int total=0,c=0;
	int n,l,r;
	scanf("%d",&n);
	for(i=2;i<=100000;i++)
	{
		if(isprime[i]==0)
		{
			prime[c++]=i;
			if(isprime[(i+1)/2]==0)
			{
				total++;
			}
		}
		s[i]=total;
		for(j=0;j<c&&i*prime[j]<=100000;j++)
		{
		    isprime[i*prime[j]]=1;
		    if(i%prime[j]==0)
		        break;
		}
	}
	for(i=0;i<n;i++)
	{
		scanf("%d %d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);
	}
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  if((a % 2) == 1 && (b % 2) == 1) {
  	cout << "Odd" << endl;
  }
  else {
  	cout << "Even" << endl;
  }

}

Measured memory_bytes: 3620
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
int n, a[100010];
long long ans = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = a[n + 1] = 0;
    for (int i = 1; i <= n + 1; i++) ans += std::abs(a[i] - a[i - 1]);
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans - std::abs(a[i] - a[i - 1]) - std::abs(a[i] - a[i + 1]) + std::abs(a[i - 1] - a[i + 1]));
    }
    return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <random>
#include <utility>
#include <set>

using namespace std;
typedef long double ld;
const ld EPS = 10e-12;

struct data_t {
	ld l, r;
	int e, d;
	data_t() {}
	data_t(ld vl, ld vr, int ve, int vd) {
		l = vl;
		r = vr;
		e = ve;
		d = vd;
	}
};

int solve(void);

int main(void) {

	while (solve()) {}

	return 0;

}

int solve(void) {


	int K, R, L;
	double P, E, T;
	cin >> K >> R >> L >> P >> E >> T;

	vector<vector<int>> v(K + 1, vector<int>(K+1,0) );
	stack<data_t> s;
	s.push(data_t((double)L, (double)R, 0, 0));

	while (!s.empty()) {

		data_t current = s.top();
		data_t right(current), wrong(current);

		double h = (current.l + current.r) / 2.0;

		s.pop();

		if (abs(current.r - T) <= E && abs(current.l - T) <= E) {
			v[current.d][current.e] ++;
			continue;
		}

		else if ( current.r > T + E || current.l < T - E) {
			continue;
		}
		if (current.d == K) {
			if (abs(h - T) <= E ) {
				v[K][current.e] ++;
			}
			continue;
		}

		right.d = current.d + 1;
		wrong.d = current.d + 1;
		wrong.e = current.e + 1;

		if (h >= T) {
			wrong.r = h;
			right.l = h;
		}
		else {
			wrong.l = h;
			right.r = h;
		}

		if (right.d <= K) {
			s.push(right);
			s.push(wrong);
		}

	}

	double PP = 0.0;
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].size(); j++) {
			if (P <= 0.0) {
				if (j == 0)
					PP += (double)v[i][j] * pow(1.0 - P, (double)(i - j));
			} else if( P + EPS >= 1.0 ) {
				if( i == j )
					PP += (double)v[i][j] * pow(P, (double)j);
			}
			else {
				PP += (double)v[i][j] * pow(P, (double)j)*pow(1.0 - P, (double)(i - j));
			}
		}
	}
	cout << setprecision(6) << fixed << PP << endl;

	return 0;

}

Measured memory_bytes: 3492
require 'scanf'
require 'matrix'

n = STDIN.gets.to_i
for i in 0..n-1 do
	str = STDIN.gets
    list = \
      str.scanf("%d %d %d %d %d " \
                "%d %d %d %d %d")
    flag = true
    for i in 0..10-1 do 
        for j in i+1..10-1 do
            for k in j+1..10-1 do
                flag = false \
                    if list[i]>list[j] and list[j]>list[k]
            end
        end
    end
    print "YES\n" if flag
    print "NO\n" if not flag
end

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

using namespace std;

const int N = 3456;

int n, a[N];
vector<int> adj[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1, x, y; i < n; ++i) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  vector<int> answer;
  for (int i = 1; i <= n; ++i) {
    function<bool (int, int)> dfs = [&] (int x, int f) {
      for (auto y : adj[x]) {
        if (y != f) {
          if (a[y] < a[x] && !dfs(y, x)) {
            return true;
          }
        }
      }
      return false;
    };
    if (dfs(i, 0)) {
      answer.push_back(i);
    }
  }
  for (int i = 0; i < answer.size(); ++i) {
    cout << answer[i] << " \n"[i + 1 == answer.size()];
  }
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
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...));
}
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 main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int n = S.size();
    REP(i, n) cout << 'x';
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define  endl '\n'
#define all(s) s.begin(),s.end()
#define lowbit(x) (x&-x)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define pb push_back
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int mod=1e9+7;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,m,num;
char mp[10][10];
int main()
{
	cin>>n>>m>>num;
	for(int i=1;i<=n;i++) cin>>mp[i]+1;
	int ans=0,res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='#') res++;
		}
	}
	//cout<<res<<endl;
	for(int i=0;i<(1<<(m+n));i++){
		int tot=0;
		for(int j=1;j<=n;j++){
			for(int k=1;k<=m;k++){
				if(((1<<(j-1))&i||(1<<(n+k-1))&i)&&mp[j][k]=='#') tot++;
			}	
		}
		if(res-tot==num) ans++;
	}	
	cout<<ans;
}



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

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

  char ans = 'D';
  if ((a == 'H' && b == 'H') || (a == 'D' && b == 'D'))
    ans = 'H';
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#define N_MAX 200
int P[N_MAX];
int main(){
    int N, X;
    std::cin >> X >> N;
    for(int i=0; i<N; i++){
        int tmp;
        std::cin >> tmp;
        P[tmp] = 1;
    }
    for(int i=0;i<=100; i++){
        if(X-i>=0 && P[X-i] == 0){
            printf("%d\n", X-i);
            break;
        }else if(X+i<=101 && P[X+i] == 0){
            printf("%d\n", X+i);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3240
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <functional>
using ll = long long;
using namespace std;
int main() {
	ll n, m;
	cin >> n >> m;
	if (n > m)
		cout << n - 1 << endl;
	else
		cout << n << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second

int main()
{
	int a, b, c;
	read(a, b, c);
	int ans = 0;
	while(a%2==0 && b%2==0 && c%2==0){
		int x=0, y=0, z=0;
		x = b/2 + c/2;
		y = c/2 + a/2;
		z = a/2 + b/2;
		if(make_tuple(x, y, z) == make_tuple(a, b, c)){
			puts("-1");
			return 0;
		}
		tie(a, b, c) = make_tuple(x, y, z);
		++ans;
	}
	printf("%d\n", ans);
    return 0;
}


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

int main(void) {
  int a, n, cou = 0;
  int arr[100] = {0};
  cin >> a >> n;
  for (int i = 0; i < a; i++) {
    cin >> arr[i];
  }
  for (int i = 0; i < a; i++) {
    if (arr[i] <= (n - arr[i])) {
      cou += 2 * arr[i];
    } else {
      cou += 2 * (n - arr[i]);
    }
  }
  cout << cou << endl;
  return 0;
}


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

const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

struct UnionFind {
    vector<int> par;
    UnionFind(int N)
        : par(N)
    { //最初は全てが根であるとして初期化
        for (int i = 0; i < N; i++)
            par[i] = i;
    }
    int root(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)
            return;
        par[rx] = ry;
    }
    bool same(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    REP(i, m)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        uf.unite(x,y);
    }
    vector<int> vi(n,0);
    REP(i,n){
        vi[uf.root(i)]++;
    }
    int ans=0;
    REP(i,n){
        ans=max(ans,vi[i]);
    }
    cout<<ans<<endl;
}

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

int main(){
  int r;
  cin >> r;
  if(r<1200){
    cout << "ABC" << endl;
  }else if(2800<=r){
    cout << "AGC" << endl;
  }else{
    cout << "ARC" <<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc079/tasks/abc079_c

string A;
string OP;

static bool dfs(string op, int sum) {
    if (op.length() == 3) {
        OP = op;
        return sum == 7;
    }

    if (dfs(op+"+", sum + (A[op.length()+1]-'0'))) return true;
    if (dfs(op+"-", sum - (A[op.length()+1]-'0'))) return true;

    return false;
}

int main() {
    cin >> A;

    if (dfs("", A[0]-'0')) {
        printf("%c%c%c%c%c%c%c=7\n", A[0], OP[0], A[1], OP[1], A[2], OP[2], A[3]);
    }

    return 0;
}


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

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

const int MAX = 100010;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;

vector <int> adj[MAX];
int disb[MAX], disw[MAX];

void dfs(int p, int* dis, int q) {
    for (auto nex : adj[p]) {
        if (dis[nex] == INF && nex != q) {
            dis[nex] = dis[p] + 1;
            dfs(nex, dis, q);
        }
    }
    return;
}

void solve(void){
    int N;
    cin >> N;
    rep(N-1, i) {
        int a, b;
        scanf("%d %d\n", &a, &b);
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    rep(N, i) {
        disb[i] = disw[i] = INF;
    }
    disb[0] = disw[N-1] = 0;
    dfs(0, disb, N-1);
    dfs(N-1, disw, 0);
    int cnt = 0;
    rep(N, i) {
        if (disb[i] <= disw[i]) cnt++;
        else cnt--;
    }
    cout << (cnt>0?"Fennec":"Snuke") << endl;
}

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


Measured memory_bytes: 11136
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = Integer.parseInt(sc.next());
    int B = Integer.parseInt(sc.next());
    int C = Integer.parseInt(sc.next());
    int result = 0;
    if(A == B) result = C;
    if(B == C) result = A;
    if(A == C) result = B;

    System.out.println(result);

  }
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

struct unionfind {
	vector<int> par, siz;
	unionfind(int N) : par(N), siz(N,1) {
		for (int i = 0; i < N; i++) par[i] = i;
	}
	int root(int x) {
		while (par[x] != x) x = par[x];
		return x;
	}
	void unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return;
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y]; par[y] = x;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	int size(int x) {
		return siz[root(x)];
	}
};

int main() {
	int n, m; cin >> n >> m;
	VI a(m), b(m); 
	REP(i, m) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}
	unionfind uf(n);
	VI s(m); ll ans = (((ll)n - 1)*(ll)n) / 2;
	for (int i = m - 1; i >= 0; i--) {
		s[i] = ans;
		if (uf.same(a[i], b[i]))continue;
		ans -= (ll)uf.size(a[i]) * (ll)uf.size(b[i]);
		uf.unite(a[i], b[i]);
	}
	REP(i, m)cout << s[i] << endl;
	return 0;
}

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a + b + c >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
}

Measured memory_bytes: 3560
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#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 gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}

const int MX = 100005, INF = 1000010000;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;



int main() {
  int n;
  scanf("%d",&n);
  int a = 1;
  string s;
  cin >> s;
  vi t(n);
  rep(i,n) scanf("%d",&t[i]), t[i]--;
  --a;
  vi d;
  rep(i,n*3) {
    d.pb(a);
    a = t[a];
  }
  int c = 0;
  drep(i,sz(d)-1) {
    ++c;
    if (d[i] == d.back()) {
      break;
    }
  }
  int cs = (sz(d)-c)/c*c;
  int ans = -10;
  if (sz(s) <= 8) {
    int w = atoi(s.c_str());
    if (w < sz(d)) ans = d[w];
    else ans = d[cs+w%c];
  } else {
    int mod = 0;
    rep(i,sz(s)) {
      mod = (mod*10+(s[i]-'0'))%c;
    }
    ans = d[cs+mod];
  }
  cout<<ans+1<<endl;
  return 0;
}








Measured memory_bytes: 7908
use std::collections::HashMap;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<usize>();
    let mut hm = HashMap::new();
    for i in 0..n {
        let a = read::<usize>();
        hm.insert(i, vec![]);
        for _ in 0..a {
            let xy = read_vec::<usize>();
            (*hm.entry(i).or_insert_with(|| vec![])).push((xy[0], xy[1]));
        }
    }

    let mut ans = 0;

    for b in 1..2<<(n-1) {
        let mut c = b;
        let mut index = 0;
        let mut check = true;
        'a: while c > 0 {
            if c & 1 == 1 {
                if let Some(v) = hm.get(&index) {
                    for &(x, y) in v {
                        let x = x-1;
                        if (b & (1 << x)) as usize != y << x {
                            check = false;
                            break 'a;
                        }
                    }
                }
            }
            c >>= 1;
            index += 1;
        }
        if check {
            ans = std::cmp::max(ans, (b as u32).count_ones());
        }
    }
    println!("{}", ans);

}

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

typedef long long LL;
const int Mod = 1000000007;
const int MN = 100005;

int N, M, A[MN], B[MN];
int K, p[MN], x[MN], y[MN], cx, cy;

inline void Compress(int *a, int &c) {
	static int d[MN];
	for (int i = 1; i <= K; ++i) d[++c] = a[i];
	std::sort(d + 1, d + c + 1), c = std::unique(d + 1, d + c + 1) - d - 1;
	for (int i = 1; i <= K; ++i) a[i] = std::lower_bound(d + 1, d + c + 1, a[i]) - d;
}
inline void Init() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	for (int i = 1; i <= M; ++i) scanf("%d", &B[i]);
	int j = 0;
	for (int i = 1; i <= N; ++i) {
		while (j < M && B[j + 1] < A[i]) ++j;
		if (j >= 1 && j < M) {
			++K, p[K] = K;
			x[K] = A[i] - B[j];
			y[K] = B[j + 1] - A[i];
		}
	}
	Compress(x, cx), Compress(y, cy);
	std::sort(p + 1, p + K + 1, [](int a, int b) {
		return x[a] == x[b] ? y[a] > y[b] : x[a] < x[b];
	});
	K = std::unique(p + 1, p + K + 1, [](int a, int b) {
		return x[a] == x[b] && y[a] == y[b];
	}) - p - 1;
}

int bit[MN];
inline void Add(int i, int v) { for (; i <= cy + 1; i += i & -i) bit[i] -= (bit[i] += v) >= Mod ? Mod : 0; }
inline int Qur(int i) { int s = 0; for (; i; i -= i & -i) s -= (s += bit[i]) >= Mod ? Mod : 0; return s; }

int main() {
	Init();
	Add(1, 1);
	for (int i = 1; i <= K; ++i) {
		int pos = y[p[i]];
		Add(pos + 1, Qur(pos));
	}
	printf("%d\n", Qur(cy + 1));
	return 0;
}

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

#define F first
#define S second
#define pb push_back
#define ld  double
#define ll long long
#define int long long


using namespace std;

const int MAXN = 101 * 1001 , MOD = 1e9 + 7  ;

int a[MAXN] ;

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

   int n , x , ans = 0 ;
   cin >> n >> x ;
   for(int i = 0 ; i < n ; i ++ ){
    cin >> a[i] ;
    if(a[i]>x)
        ans += a[i]-x,a[i] = x ;
   }
   for(int i = 0 ; i < n - 1 ; i ++ )
    ans += max(0ll,a[i]+a[i+1]-x) , a[i+1] -= max(0ll,a[i]+a[i+1]-x) ;
    cout<<ans;


}


Measured memory_bytes: 1024
n=int(input())
num=list(map(int,input().split()))
s=sum(num)
a=num[0]
check=s-2*a
ans=abs(check)
for i in range(1,n-1):
  check-=2*num[i]
  if abs(check)<ans:
    ans=abs(check)
print(ans)


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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
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;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}

//char->int
int ctoi(char c){
    return c-'0';
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}



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

    if((n-1)/2+1>=k){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}


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

int main() {
    int h, w, m;
    cin >> h >> w >> m;
    vector<int> rowcnt(h, 0), colcnt(w, 0);
    int hi[m], wi[m];
    for (int i = 0; i < m; ++i) {
        cin >> hi[i] >> wi[i];
        hi[i]--, wi[i]--;
        rowcnt[hi[i]]++;
        colcnt[wi[i]]++;
    }

    int rowmx = 0, rowmxcnt = 0;
    for (int i = 0; i < h; ++i) {
        if(rowmx < rowcnt[i]) {
            rowmx = rowcnt[i];
            rowmxcnt = 1;
            continue;
        }
        if(rowmx == rowcnt[i]) rowmxcnt++;
    }

    int colmx = 0, colmxcnt = 0;
    for (int i = 0; i < w; ++i) {
        if(colmx < colcnt[i]) {
            colmx = colcnt[i];
            colmxcnt = 1;
            continue;
        }
        if(colmx == colcnt[i]) colmxcnt++;
    }

    int bombatintersect = 0;
    for (int i = 0; i < m; ++i) {
        if(rowmx == rowcnt[hi[i]] && colmx == colcnt[wi[i]]) bombatintersect++;
    }

    int ans = rowmx + colmx;
    if(rowmxcnt * colmxcnt == bombatintersect) ans--;
    cout << ans << endl;
}


Measured memory_bytes: 7992
#include<bits/stdc++.h>
#define ll long long;
#define dbg(x) cout<<#x<<"--------------"<<x<<endl;
#define dl cout<<"LINE"<<__LINE__<<endl;
using namespace std;
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;long long a[200005];
	cin>>n;
	for(register int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(register int i=1;i<n;i++){
		if(a[i]==a[i-1]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	
	
		
	return 0;
}

Measured memory_bytes: 1792
// わーい考察！あかり考察だーいすき！
// 嘘、嫌い
#include <iostream>
#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

typedef long long ll;
int n, a[100000];

bool solve(){
	cin >> n;
	ll sum=0;
	REP(i, n){
		cin >> a[i];
		sum += a[i];
	}
	if(sum % ((ll)n * (n+1) / 2) != 0ll) return false;
	int k = sum / ((ll)n * (n+1) / 2); // 操作回数
	REP(i, n){
		int now = a[i], next = a[(i+1)%n];
		if(now - next < -k) return false;
		if((k + now - next) % n != 0) return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	cout << (solve() ? "YES" : "NO") << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pint;

int main()
{
    int N; cin>>N;
    vector<vector<int>> a(N,vector<int>(N-1));

    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            cin>>a[i][j];
            a[i][j]--;
        }
        reverse(a[i].begin(),a[i].end());
    }

    set<pint> st;
    auto check=[&](int i){
        if(a[i].empty()) return;
        int j=a[i].back();
        if(a[j].back()==i){
            st.insert({min(i,j),max(i,j)});
        }
    };
    for(int i=0;i<N;i++){
        check(i);
    }

    int ans=0;
    while(!st.empty()){
        ans++;
        set<pint> st2;
        swap(st,st2);
        for(pint p:st2){;
            a[p.first].pop_back();
            a[p.second].pop_back();
        }
        for(pint p:st2){
            check(p.first);
            check(p.second);
        }
    }

    for(int i=0;i<N;i++) if(!a[i].empty()){
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4224
from heapq import heappop, heappush

N, C, *STC = map(int, open(0).read().split())

A = [[] for _ in range(C + 1)]
for s, t, c in zip(*[iter(STC)] * 3):
    A[c].append((s, t))

ST = []
for a in A:
    if not a:
        continue
    a = sorted(a)
    B = [a[0]]
    for s2, t2 in a[1:]:
        s1, t1 = B[-1]
        if t1 == s2:
            B[-1] = (s1, t2)
        else:
            B.append((s2, t2))
    ST += B

ST.sort(key=lambda x: x[0])

ans = 0
Q = []
for s, t in ST:
    while Q and Q[0] < s:
        heappop(Q)
    heappush(Q, t)
    ans = max(ans, len(Q))

print(ans)

Measured memory_bytes: 30504
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>

using namespace std;

typedef pair<int,bool> Pair;

int main(){

  int N;
  int count = 0;
	
  cin >> N;
  
  for(int i = 1; i <= N; ++i){

  	
  	if(int(i/10) == 0) ++count;
  	else if(0 < int(i/100) && int(i/100) < 10) ++count;
  	else if(0 < int(i/10000) && int(i/10000) < 10) ++count;

  }

    cout << count << endl;

  return 0;

}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d", $n);

$format = join(' ', array_map(function () { return '%d'; }, range(1, $n)));
$nums = fscanf(STDIN, $format);

$revs = array_reduce($nums, function ($carry, $item) { return array_merge(array($item), $carry); }, array());
echo join(' ', $revs)."\n";

Measured memory_bytes: 6632
#include <cstring>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)<0?(-(a)):(a))
#define CS while(cases())
#define I(n) int n = gi()
#define II(n) n = gi()
#define L(n) ll n = gli()
#define LL(n) n = gli()
#define F0(i, n) for (int i = 0; i < n; i++)
#define F1(i, n) for (int i = 1; i < n; i++)
#define Fi(n, a) for (int i = 0; i < n; i++) a[i] = gi()
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

template<class T>
T gcd(T a, T b) {
    return (b == 0 ? a : gcd(b, a%b));
}

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int cases() {
    static int t = gi();
    return t--;
}

#define MD 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i < 6; i++)
        if (gi() == 0) {
            printf("%d\n", i);
            break;
        }

    return 0;
}


Measured memory_bytes: 3808
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(X, Y, Z, K, A, B, C):
    q = []
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    if len(A) > K:
        A = A[:K]
    if len(B) > K:
        B = B[:K]
    if len(C) > K:
        C = C[:K]

    for a in A:
        for b in B:
            heapq.heappush(q, a+b)
            if len(q) > K:
                heapq.heappop(q)

    qq = []
    for c in C:
        for d in q:
            heapq.heappush(qq, d+c)
            if len(qq) > K:
                heapq.heappop(qq)
    qq.sort(reverse=True)
    return qq

def main():
    X, Y, Z, K = read_int_n()
    A = read_int_n()
    B = read_int_n()
    C = read_int_n()
    print(*slv(X, Y, Z, K, A, B, C), sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 86492