akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)
#define rrep(i,x) for(int i=(int)x-1;i>=0;--i)
#define rrep1(i,x) for(int i=(int)x;i>=1;--i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int N;
int A[3][3];
bool B[3][3];

bool check() {
    rep(i, 3) {
        if (B[i][0] && B[i][1] && B[i][2]) return true;
        if (B[0][i] && B[1][i] && B[2][i]) return true;
    }
    if (B[0][0] && B[1][1] && B[2][2]) return true;
    if (B[0][2] && B[1][1] && B[2][0]) return true;

    return false;
}

signed main()
{
    rep(i, 3) rep(j, 3) {
        cin >> A[i][j];
    }

    cin >> N;

    rep(i, N) {
        int b; cin >> b;
        rep(j, 3) rep(k, 3) if (A[j][k] == b) B[j][k] = true;
    }

    bool f = check();

    cout << (f ? "Yes" : "No") << endl;
}


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

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

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		ABC053A a = new ABC053A();
	}
}

class ABC053A {
	
	ABC053A() {
		Scanner cin = new Scanner(System.in);
		String str = cin.next();
		
		int left = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == 'A') {
				left = i;
				break;
			}
		}
		int right = str.length() - 1;
		for (int i = right; i >= 0; i--) {
			if (str.charAt(i) == 'Z') {
				right = i;
				break;
			}
		}
		
		int length = right - left + 1;
		System.out.println(length);
	}
}

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

#define mp make_pair
#define pb push_back

#define int int64_t

const int MOD = 1e9+7;
 

int m;

int findlcm(int arr[], int n) 
{ 
    // Initialize result 
    int ans = arr[0]; 
  
    // ans contains LCM of arr[0], ..arr[i] 
    // after i'th iteration, 
    for (int i = 1; i < n; i++) 
    {
        ans = (((arr[i] * ans)) / 
                (__gcd(arr[i], ans))); 
        if(ans/2>m)
        	return -1;
    }
  
    return ans; 
} 

int getFirstSetBitPos(int n) 
{ 
    return log2(n & -n) + 1; 
} 

int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n>>m;
    int arr[n];
    for(int i=0;i<n;i++)
    	cin>>arr[i];

    int lcm = findlcm(arr, n);
    if(lcm==-1)
    {
    	cout<<0;
    	return 0;
    }

    int lol = getFirstSetBitPos(arr[0]);
    //cout<<lol<<"\n";
    for(int i=0;i<n;i++) {
    	if(getFirstSetBitPos(arr[i])!=lol)
    	{
    		cout<<0;
    		return 0;
    	}
    }

    cout<<(m+lcm/2)/lcm;




	return 0;
}

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

// Begin Header {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) x.begin(), x.end()
#define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)

constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class T>
inline istream& operator>>(istream &is, vector<T> &vec) {
    for (auto &e: vec) {
        is >> e;
    }
    return is;
}

inline void output() { cout << "\n"; }
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) {
        cout << " ";
    }
    output(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e: vec) {
        os << e << delim[&e == &vec.back()];
    }
    return os;
}

template <class T>
inline vector<T> makeVector(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeVector(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

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

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

template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}
// End Header }}}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(size_t, N);
    var(string, s);

    size_t res = 0;
    reps(i, 0, N - 3) {
        if (s.substr(i, 3) == "ABC") {
            res++;
        }
    }

    output(res);

    return 0;
}


Measured memory_bytes: 384
import java.util.*
//b>g>r
fun main(args: Array<String>) {
    val scan = Scanner(System.`in`)
    var (red,green,blue) = scan.nextLine().split(" ").map{ it.trim().toInt() }.toTypedArray()
    var k=scan.nextLine().toInt()
        var flag = false
    for(i in 1..k)
    {
        if(green<=red)
            green*=2
        else if(blue<=green)
            blue*=2

        if(green>red && blue>green)
        {
            flag=true
            break
        }
    }

    if(flag)
        println("Yes")
    else
        println("No")
}


Measured memory_bytes: 38480
def is_kaibun(st):
  f = True
  for x,y in zip(st, st[::-1]):
    if x != y:
      f = False
      break
  return f
 
S = input()
ans = False
if is_kaibun(S):
  if is_kaibun(S[:(len(S)-1)//2]):
    ans = is_kaibun(S[(len(S)+3)//2-1:])
if ans:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9148
import java.util.ArrayList;
import java.util.Scanner;


public class Main {

    public static String Y = "Yes";
    public static String N = "No";
    public static String I = "IMPOSSIBLE";
    public static String B = "Bad";
    public static String G = "Good";

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {

        int k = ni();
        ArrayList<Long> lunlunList = new ArrayList<>();

        for (long i = 1; i < 10; i++) {
            lunlunList.add(i);
        }

        for (int i = 0;; i++) {
            long moto = lunlunList.get(i);
            long mod10 = moto % 10;

            if (moto % 10 != 0) {
                lunlunList.add(10 * moto + mod10 - 1);
            }
            lunlunList.add(10 * moto + mod10);
            if (mod10 != 9) {
                lunlunList.add(10 * moto + mod10 + 1);
            }

            if (i > 100000) {
                break;
            }
        }

        out(lunlunList.get(k - 1));
    }

    /*
     * 以下メソッド集
     */
    static int ni() {

        return sc.nextInt();
    }

    static long nl() {

        return sc.nextLong();
    }

    static String n() {

        return sc.next();
    }

    static char[] nc() {

        return sc.next().toCharArray();
    }

    static int kaijo(int n) {

        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * kaijo(n - 1);
        }
    }

    static int fib(int n) {

        return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
    }

    static long lcm(long m, long n) {

        return m * n / gcd(m, n);
    }

    static int lcm(int m, int n) {

        return m * n / gcd(m, n);
    }

    static long gcd(long a, long b) {

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

    static int gcd(int a, int b) {

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

    static void out(String info) {

        System.out.println(info);
    }

    static void out(int info) {

        System.out.println(info);
    }

    static void out(double info) {

        System.out.println(info);
    }

    static void out(long info) {

        System.out.println(info);
    }

    static void out(char info) {

        System.out.println(info);
    }

    static void outn(String info) {

        System.out.print(info);
    }

    static void outn(int info) {

        System.out.print(info);
    }

    static void outn(double info) {

        System.out.print(info);
    }

    static void outn(long info) {

        System.out.print(info);
    }

    static void outn(char info) {

        System.out.print(info);
    }

    static int max(int a, int b) {

        return Math.max(a, b);
    }

    static long max(long a, long b) {

        return Math.max(a, b);
    }

    static int min(int a, int b) {

        return Math.min(a, b);
    }

    static long min(long a, long b) {

        return Math.min(a, b);
    }
}

Measured memory_bytes: 32468
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef long long LL;
const int INF = 999999999;

struct UnionFind{
    vector<int> data;

    UnionFind(int sz){
        data.assign(sz, -1);
    }

    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return(false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return(true);
    }

    int find(int k){
        if(data[k] < 0) return(k);
        return(data[k] = find(data[k]));
    }

    int size(int k){
        return(-data[find(k)]);
    }
};

int main(){
    int n,q;
    cin >> n >> q;
    UnionFind UF(n);
    rep(i, q){
        int a, x, y;
        cin >> a >> x >> y;
        if(a == 0){
            UF.unite(x, y);
        }else{
            cout << (UF.find(x) == UF.find(y) ? 1 : 0) << endl;
        }
    }
}


Measured memory_bytes: 3136
import math


# 数列が何番目かを返却するメソッド
def junban(N, str):
    int_list = str.split()  # 入力文字を配列化
    int_list = [int(i) for i in int_list]
    used_list = []
    num = 0
    for element in int_list:
        N -= 1
        used_count = 0
        for used in used_list:
            if element > used:
                used_count += 1
        num += (element - 1 - used_count) * math.factorial(N)
        used_list.append(element)
    # print(num)
    return num


# 大きさNを受け取る
N = int(input())
# 数列Pを受け取る
P = input()
# 数列Qを受け取る
Q = input()
# それぞれが何番目か求める
p_int = junban(N, P)
q_int = junban(N, Q)
print(abs(p_int - q_int))


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

public class Main {
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		int h = in.nextInt();
		int w = in.nextInt();
		String[] a = new String[h];
		for (int i = 0; i < h; i++) {
			a[i] = in.next();
		}

		boolean[] row = new boolean[h];
		Arrays.fill(row, false);
		boolean[] col = new boolean[w];
		Arrays.fill(col, false);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (a[i].charAt(j) == '#') {
					row[i] = true;
					col[j] = true;
				}
			}
		}

		for (int i = 0; i < h; i++) {
			if (row[i]) {
				for (int j = 0; j < w; j++) {
					if (col[j]) {
						System.out.print(a[i].charAt(j));
					}
				}
				System.out.println();
			}
		}
	}
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-5;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(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 U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

const int64 mod = 1e9+7;

int main(void) {
	vector<int64> A(5);
	int64 sum = 0;
	REP(i, 5) {
		cin >> A[i];
		sum += (A[i] % 10 ? A[i] + (10 - A[i]%10) : A[i]);
	}
	int64 res = INF_LL;
	REP(i, 5) {
		res = min(res, sum - (A[i]%10 ? (10 - A[i]%10) : 0));
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i=0; i<n; i++) {
    cin >> v[i];
  }

  sort(v.begin(), v.end());

  double pre = v[0];
  for (int i=1; i<n; i++) {
    pre = (pre + (double)v[i]) / 2.0;
  }

  cout << pre << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

int main(){
	int n; cin >> n;
	for(int i=1;i<=10000;i++){
		if(n < i*100) continue;
		int zan = n-i*100;
		if(zan <= 5*i){
			cout << 1 << endl; return 0;
		}
	}
	cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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

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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n), b(n), c(n);
    rep(i, n)
    {
        cin >> a[i];
    }

    rep(i, n)
    {
        cin >> b[i];
    }

    rep(i, n)
    {
        cin >> c[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    ll ans = 0;

    rep(i, n)
    {
        ll a_num = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        ll c_num = n - (upper_bound(c.begin(), c.end(), b[i]) - c.begin());

        ans += a_num * c_num;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef float us;

int main() {
  us N, M, total = 0;
  cin >> N >> M;
  vector<us>v(N);
  for (us i = 0; i < N; ++i) {
    cin >> v[i];
    total += v[i];
  }

  sort(v.begin(), v.end());
  cout << ( v[int(N - M)]/total >= 1/(4*M) ? "Yes" : "No");

}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>


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

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long MOD = 1'000'000'007LL;
const long long mod = 998244353LL;

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

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

	ll N, M;
	cin >> N >> M;
	cout << N * M << endl;
	return 0;

}



Measured memory_bytes: 3100
// inputに入力データ全体が入る
  function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	//文字列から10進数に変換するときはparseIntを使います
  var input = Number(input[0]);
  var count500 = Math.floor(input/500);
  var count5 = Math.floor(input%500/5);
  var ans = 1000*count500 + 5*count5;

	//出力
	console.log('%d', ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7624
S = input()
if 1 <= int(S[:2]) <= 12 and 1 <= int(S[2:]) <= 12:
  print("AMBIGUOUS")
elif 1 <= int(S[:2]) <= 12:
  print("MMYY")
elif 1 <= int(S[2:]) <= 12:
  print("YYMM")
else:
  print("NA")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int main(){
  int N, res;
  rd(N);
  res = N * (N+1) / 2;
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190721-1

// --- original code ---
// {
//   int N, res;
//   rd(N);
//   res = N * (N+1) / 2;
//   wt(res);
// }


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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

#define keta setprecision(10) //10桁表示


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int r;
	cin >> r;
	cout << r * r << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

ll mypow(ll a, ll b) {
  ll two;
  ll tmp;
  ll ans = 1;
  while(b>0) {
    two = 1;
    tmp = a;
    while(2*two<b) {
      two *= 2;
      tmp *= tmp;
      tmp %= mod1;
    }
    b -= two;
    ans *= tmp;
    ans %= mod1;
  }
  return ans;
}

int main() {
  int N;
  cin>>N;
  int D[N];
  map<int, ll> amap;
  for(int i=0;i<N;++i) {
    cin>>D[i];
    amap[D[i]]++;
  }
  bool ok = true;
  int maxnum;
  bool tmp = false;
  for(int i=0;i<=N;++i) {
    if(amap[i]==0) {
      if(!tmp) maxnum = i-1;
      tmp = true;
    }
    else {
      if(tmp) ok = false;
    }
  }
  if(D[0]!=0 || amap[0]>1 || !ok) {
    cout<<0<<endl;
    return 0;
  }
  ll ans = 1;
  for(int i=1;i<=maxnum;++i) {
    ans *= mypow(amap[i-1], amap[i]);
    ans %= mod1;
  }
  cout<<ans<<endl;
}



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

int main(){
  int k;
  string s;
  cin >> k >> s;
  if((int)s.size()<=k)cout << s << endl;
  else{
    rep(i,k){
      cout << s[i];
    }
    cout << "...\n";
  }
  return 0;
}

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

const int MAX_N = 1e5;
int N;
typedef pair<int, int> P;
P A[MAX_N];

void solve() {
    sort(A, A + N);
    for(int i = 0; i < N; i++) {
        P p = A[i];
        cout <<  p.second << " ";
    }
    cout << "\n";
    return ;
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++) {
        int j;
        cin >> j;
        P p;
        p.first = j;
        p.second = i + 1;
        A[i] = p;
    }
    solve();
    return 0;
}


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

int main(){
  int n,m;
  cin >> n >> m;
  if(m==0 && n==1){
    cout << 0 << endl;
    return 0;
  }
  vector<bool> ok(n+1,false);
  vi ans(n+1);
  rep(i,m){
    int s,c;
    cin >> s >> c;
    if(s == 1 && c == 0 && n != 1){
      cout << -1 << endl;
      return 0;
    }
    if(ok[s] && ans[s] != c){
      cout << -1 << endl;
      return 0;
    }
    ok[s] = true;
    ans[s] = c;
  }
  for(int i=1; i<=n; i++){
    if(ok[i]) continue;
    if(i == 1) ans[1] = 1;
    else ans[i] = 0;
  }
  rep(i,n) cout << ans[i+1];
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int q = scan.nextInt();
		for(int i = 0 ; i < q ;i++) {
			int c = scan.nextInt();
			int a = scan.nextInt();
			int n =scan.nextInt();
			int cun = 0;
			while(true) {
				if(c >0 && a > 0 && n >0) {
					++cun;
					--c;
					--a;
					--n;
				}else if(c >1 && a > 0) {
					++cun;
					c = c-2;
					--a;
				}else if(c > 2) {
					++cun;
					c =c-3;
				}else {
					break;
				}
			}
			System.out.println(cun);
		}
	}
}



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

using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  
  vector<int> s(M), c(M);
  for(int j = 0; j < M; j++){
    cin >> s[j] >> c[j];
    s[j]--;
  }
  
  int t = 1;
  int x[N];
  x[0] = -1;
  for(int i = 1; i < N; i++){
    t *= 10;
    x[i] = -1;
  }
  
  bool ok = true;
  for(int i = t; i < t * 10; i++){
    for(int j = 0; j < M; j++){
      if(x[s[j]] == c[j] || x[s[j]] == -1){
        x[s[j]] = c[j];
      }else{
        ok = false;
      }
      if(x[0] == 0 && N > 1) ok = false;
    }
  }
  
  if(ok){
    if(x[0] == -1){
      if(N == 1) cout << 0;
      else cout << 1;
    }else cout << x[0];
    for(int i = 1; i < N; i++){
      if(x[i] == -1) cout << 0;
      else cout << x[i];
    }
    cout << endl;
  }else cout << -1 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	ll t1, t2, a1, a2, b1, b2;
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
	ll x = (a1 - b1)*t1, y = (a2 - b2)*t2;
	ll dif = abs(x+y);
	if (dif == 0)cout << "infinity" << endl;
	else if ((x < 0 &&x + y < 0) || (0<x && 0<x + y))cout << 0 << endl;
	else
	{
		ll z = abs(x / dif);
		if (x%dif == 0)cout << 2 * z << endl;
		else cout << 2*z + 1 << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <math.h>
#include <stdlib.h>
#include <numeric>


int main(){
	long int w, h, x, y;
	bool is = false;
	std::cin >> w >> h >> x >> y;
	is = ((x * 2 == w) && (y * 2 == h));
	std::cout << (long double)(w * h) / 2 << ' ';
	if(is){
		std::cout << 1 << std::endl;
	}else{
		std::cout << 0 << std::endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (1e9)

int main(){
  int n, a[100];
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int counter = 0;

  for(int i = 0; i < n - 1; i++) {
    int minj = i;
    for(int j = i; j < n; j++) {
      if(a[j] < a[minj]) {
        minj = j;
      }
    }
    if(i != minj) {
      swap(a[i], a[minj]);
      counter++;
    }
  }

  cout << a[0];
  for(int i = 1; i < n; i++) {
    cout << " " << a[i];
  }

  cout << endl << counter << endl;

  return 0;
}


Measured memory_bytes: 3096
N=int(input())
l = input()
count0 = l[1:].count("E")
count=count0
mi=count0
for i in range(1, N):
    if l[i-1]=="W":
        count+=1
    if l[i]=="E":
        count-=1
    mi=min(mi,count)
print(mi)

Measured memory_bytes: 3676
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
#define f first
#define s second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P>PP;
int n,m,x,y,t,d[51][501][2],v0,a,b,c;
vector<P>G[501];
int dijkstra(){
    priority_queue<PP,vector<PP>,greater<PP> >q;
    r(i,51)r(j,501)r(k,2)d[i][j][k]=1e17;
    q.push(PP(P(0,v0),P(0,0)));
    while(!q.empty()){
        PP p=q.top();q.pop();
        if(d[p.f.s][p.s.f][p.s.s]<p.f.f)continue;
        if(!p.s.f&&p.s.s)return p.f.f;
        if(p.s.f==n-1&&!p.s.s)if(d[p.f.s][p.s.f][1]>p.f.f){
            q.push(PP(P(p.f.f,p.f.s),P(p.s.f,1)));
            d[p.f.s][p.s.f][1]=p.f.f;
        }
        r(i,G[p.s.f].size()){
            int v=(a*p.f.s+b)%c;
            int cost=p.f.f+p.f.s*G[p.s.f][i].s;
            int to=G[p.s.f][i].f;
            if(d[v][to][p.s.s]>cost){
                d[v][to][p.s.s]=cost;
                q.push(PP(P(cost,v),P(to,p.s.s)));
            }
        }    
    }
}
main(){
    cin>>n>>m;
    r(i,m){
        cin>>x>>y>>t;
        x--;y--;
        G[x].push_back(P(y,t));
        G[y].push_back(P(x,t));
    }
    cin>>v0>>a>>b>>c;
    cout<<dijkstra()<<endl;
}

Measured memory_bytes: 11724
import numpy as np
from fractions import gcd

n, x = [int(i) for i in input().split()]
coord = [int(i) for i in input().split()]

diff = np.diff(sorted(coord + [x])).tolist()
while len(diff) > 1:
    diff.append(gcd(diff.pop(), diff.pop()))

print(diff.pop())


Measured memory_bytes: 25012
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1e17;
#define int long long


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	VE a(n); rep(i, n)cin >> a[i];
	int ans = 0;
	int ans2 = 0;
	int sum = 0;
	rep(i, n) {
		sum += a[i];
		if (i % 2 == 0) {
			if (sum <= 0) {
				ans += 1 - sum;
				sum = 1;
			}
		}
		else {
			if (sum >= 0) {
				ans += sum + 1;
				sum = -1;
			}
		}
	}
	sum = 0;
	rep(i, n) {
		sum += a[i];
		if (i % 2 == 1) {
			if (sum <= 0) {
				ans2 += 1 - sum;
				sum = 1;
			}
		}
		else {
			if (sum >= 0) {
				ans2 += sum + 1;
				sum = -1;
			}
		}
	}
	COUT(min(ans, ans2));
	return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

namespace flw {
	const int N = 1000000 + 7;
	struct flow {
		int n, st, ed;
		int lay[N], gap[N], cur[N], pre[N];
		struct edge {
			int to, nex, cap;
		} e[N];
		int fir[N], eid = 1;

		void addedge(int u, int v, int c);
		void addflow(int u, int v);
		int isap();
	};

	void flow::addedge(int u, int v, int c) {
		e[++eid] = (edge){ v, fir[u], c }, fir[u] = eid;
	}
	void flow::addflow(int u, int v) {
		addedge(u, v, 1), addedge(v, u, 0);
	}
	int flow::isap() {
		std::queue<int> q; q.push(ed);
		std::fill(lay + 1, lay + n + 1, -1), lay[ed] = 0;
		for (int s; q.size(); ) {
			s = q.front(), q.pop();
			for (int i = fir[s]; i; i = e[i].nex)
				if (lay[e[i].to] == -1 && e[i ^ 1].cap)
					++gap[lay[e[i].to] = lay[s] + 1], q.push(e[i].to);
		}
		std::copy(fir + 1, fir + n + 1, cur + 1);

		int maxflow = 0, s = st;
		while (lay[st] < n) {
			if (s == ed)
				for (++maxflow; s != st; s = pre[s], --e[cur[s]].cap, ++e[cur[s] ^ 1].cap);
			for (int &i = cur[s]; i; i = e[i].nex)
				if (lay[s] == lay[e[i].to] + 1 && e[i].cap)
					{ pre[e[i].to] = s; break; }
			if (cur[s]) { s = e[cur[s]].to; continue; }
			if (!--gap[lay[s]]) break;
			++gap[++lay[s]], cur[s] = fir[s];
			if (s != st) s = pre[s];
		}
		return maxflow;
	}
}

const int N = 400000 + 7;

int n;
flw::flow f;
int u[N];
std::vector<int> v[N];
int g[N], h[N], k;

int fa[N];
int getfa(int x) {
	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	f.st = n * 2, f.ed = f.n = f.st + 1;
	for (int i = 1, x, y; i < n; ++i) {
		scanf("%d", &y);
		while (y--) scanf("%d", &x), f.addflow(x, n + i), v[x].push_back(i);
		f.addflow(f.st, i), f.addflow(n + i, f.ed);
	}
	if (f.isap() < n - 1) return printf("-1"), 0;
	for (int i = 1; i < n; ++i)
		for (int j = f.fir[n + i]; j; j = f.e[j].nex)
			if (f.e[j].cap) u[i] = f.e[j].to;
	for (int i = 1; i <= n; ++i) fa[i] = i;
	std::queue<int> q; q.push(n);
	for (int s; q.size(); ) {
		s = q.front(), q.pop();
		for (auto i : v[s])
			if (u[i]) q.push(u[i]), fa[getfa(g[i] = s)] = getfa(h[i] = u[i]), u[i] = 0;
	}
	for (int i = 1; i <= n; ++i)
		if (getfa(i) != getfa(1)) return printf("-1"), 0;
	for (int i = 1; i < n; ++i)
		printf("%d %d\n", g[i], h[i]);
	return 0;
}


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

using namespace std;

const int N = 1e5 + 2;
int n, tin[N], tout[N], curT;
vector<int>g[N];
int col[N], Father[N];
int cnt1, cnt2;
int nod1, nod2;
void dfs(int nod, int father) {
	++curT;
	tin[nod] = curT;
	for (auto itr : g[nod])
		if (itr - father) dfs(itr, nod);
	++curT;
	tout[nod] = curT;
	Father[nod] = father;
}

bool in_subtree(int nod, int ask) {
	return tin[ask] >= tin[nod] && tout[ask] <= tout[nod];
}

bool stop1;
int go1() {
	if (stop1) return -1;
	for (auto i : g[nod1]) {
		if (in_subtree(i, nod2) && !col[i]) {
			return i;
		}
	}
	return -1;
}

void dfs(int nod) {
	col[nod] = 1;
	for (auto i : g[nod]) {
		if (i != Father[nod] && col[i] != 2) {
			dfs(i);
		}
	}
}
int main() {
	//freopen("oj.in", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}

	dfs(1, 0);
	col[1] = 1;
	col[n] = 2;
	int step = 0;
	bool cha = 0;
	nod1 = 1;
	nod2 = n;
	while (true) {
		cha = 0;
		if (step == 0) {
			int son = go1();
			if (son == -1) {
				stop1 = true;
				cha = 1;
			}
			else {
				nod1 = son;
				col[nod1] = 1;
				cha = 1;
			}
		}
		else {
			if (!col[Father[nod2]]) {
				nod2 = Father[nod2];
				col[nod2] = 2;
				cha = 1;
			}
		}
		if (!cha) break;
		step ^= 1;
	}
	dfs(1);
	int Cnt1 = 0, Cnt2 = 0;
	for (int i = 2; i < n; ++i) {
		if (col[i] == 1)++Cnt1;
		else ++Cnt2;
	}
	if (Cnt1 > Cnt2) {
		cout << "Fennec";
	}
	else cout << "Snuke";
}


Measured memory_bytes: 11904
#include<iostream>

const int MAX_N = 1 << 18, MOD = 100000;//ちょっと多いけど気にしないし(少なかったし)
class SegmentTree{
public:
	SegmentTree(int _n){
		n = 1;
		while(n < _n)n *= 2;
		std::fill(data, data+MAX_N, 0);
	}

	void update(int k, int i){
		k += n - 1;
		data[k] = i;
		while(k > 0){
			k = (k - 1) / 2;
			data[k] = (data[k*2+1] + data[k*2+2]) % MOD;
		}
	}

	int query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l)return 0;

		if(a <= l && r <= b)return data[k];
		else{
			int cl = query(a, b, k*2+1, l, (l + r) / 2),
				cr = query(a, b, k*2+2, (l + r) / 2, r);
			return (cl + cr) % MOD;
		}
	}

	int getN(){
		return n;
	}

private:
	int n, data[MAX_N];
};

int main(){
	int n, m;
	std::cin >> n >> m;
	SegmentTree st(--n);

	for(int i=0;i<n;i++){
		int d;
		std::cin >> d;
		st.update(i, d);
	}

	int from = 0, to, res = 0;
	for(int i=0;i<m;i++){
		int a;
		std::cin >> a;
		to = from + a;
		int lower = std::min(from, to), upper = std::max(from, to);
		res = (res + st.query(lower, upper, 0, 0, st.getN())) % MOD;
		from = to;
	}

	std::cout << res << std::endl;
}

Measured memory_bytes: 2188
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <numeric>
#include <complex>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
typedef long long int ll;
#define iceil(x,y) (x+y-1)/y

using namespace std;
typedef pair<int, int> P;

int a[505][505], jx[505][505];

int main() {
	FAST;
	int N,M,Q;
	cin >> N >> M >> Q;

	int l,r;
	rep(i,1,M+1) {
		cin >> l >> r;
		a[l][r]++;
	}
	rep(i,1,N+1) {
		rep(j,1,N+1) {
			jx[i][j] = a[i][j]+jx[i-1][j]+jx[i][j-1]-jx[i-1][j-1];
		}
	}
	rep(i,1,Q+1) {
		cin >> l >> r;
		cout << jx[r][r]+jx[l-1][l-1]-jx[r][l-1]-jx[l-1][r] << "\n";
	}

	return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int n;
  cin >> n; 
  vector<int64_t> cont(n+1);
  
  for(int i = 0 ; i < n ; i++){
    cin >> cont.at(i);
  }
  cont.at(n) = 0;
  
  int sum = 0;
  int max_sum = 0;
  
  for(int i = 0 ; i < n ; i++){
    if(cont.at(i+1) > cont.at(i) || i == n-1){
      max_sum = max(max_sum , sum);
      sum = 0;
    }
    else{
      sum++;
    }
  }
  cout << max_sum << endl;
} 

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  int ans=N;
  for(int i=0; i<=N; i++){
    int a=i, temp=0, b=N-i;
    while(a>0){
      temp+=a%6;
      a/=6;
    }
    while(b>0){
      temp+=b%9;
      b/=9;
    }
    ans=min(ans, temp);
  }
  cout << ans << endl;
}



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

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

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

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

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

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

	ll N=in<ll>(),K=in<ll>();
	auto A=vecin<ll>(N);
	auto F=vecin<ll>(N);
	sort(ALL(A));
	sort(ALL(F),greater<ll>());

	ll left = 0,right = 0;
	REP(i,N){
		right = max(right,A[i]*F[i]);
	}
	while(right-left>0){
		ll mid = (left+right)/2;
		ll sum = 0;
		bool flag = true;
		REP(i,N){
			sum += min(A[i],max(0LL,(ll)ceil((A[i]*F[i]-mid)/(double)F[i])));
			if(sum>K){
				flag = false;
				break;
			}
		}
		if(flag) right = mid;
		else left = mid+1;
	}
	
	out(right);
	return 0;
}

Measured memory_bytes: 3456
#include <stdio.h>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

typedef pair<int,int> s;
typedef long long int ll;

int abs(int x){
  return x > 0 ? x : -x;
}

int length(char c[]){
  int cnt=0;
  for(cnt=0;c[cnt]!='\0';cnt++){
  }
  return cnt;
}


int n,k;
int dp[20];

int main(){
  scanf("%d %d",&n,&k);
  dp[0] = 1;
  FOR(i,1,n+1){
    dp[i] = min(2*dp[i-1],dp[i-1]+k);
  }
  printf("%d\n",dp[n]);
}


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

typedef long long int ll;
#define endl "\n"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pair<int, int>>
#define mems(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define forn(i, s, e) for(int i = s; i < (e); ++i)
#define FASTIO                                                                                     \
	ios_base::sync_with_stdio(false);                                                              \
	cin.tie(NULL);
#define FILEIO                                                                                     \
	freopen("./input.txt", "r", stdin);                                                            \
	freopen("./output.txt", "w", stdout);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                                                  \
	for(auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); blockTime.second;  \
		debug("%s : %lld ms\n ",                                                                   \
			  d,                                                                                   \
			  chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() -   \
														  blockTime.first)                         \
				  .count()),                                                                       \
			 blockTime.second = false)
const int M = 1e9 + 7;

template <class T>
T ABS(const T& x) {
	return x > 0 ? x : -x;
}
ll gcd(ll n1, ll n2) { return n2 == 0 ? ABS(n1) : gcd(n2, n1 % n2); }
ll lcm(ll n1, ll n2) { return n1 == 0 && n2 == 0 ? 0 : ABS(n1 * n2) / gcd(n1, n2); }
ll ceil2(ll a, ll b) { return (a + b - 1) / b; }

// ll modularExpo(ll b, ll p, ll m) {
// 	ll res = 1;
// 	b = b % m;
// 	if(b == 0) return 0;

// 	while(p > 0) {
// 		if(p & 1) res = (res * b) % m;
// 		p >>= 1;
// 		b = (b * b) % m;
// 	}
// 	return res;
// }

ll modularExpo(ll d, ll n, ll M) {
	ll ans = 1;
	for(int i = 0; i < n; ++i) {
		ans *= d;
		ans %= M;
	}
	return ans % M;
}

int main() {
	FASTIO
#ifdef LOCAL
	FILEIO
#endif
	ll n;
	cin >> n;
	ll t1 = (2LL * modularExpo(9, n, M)) % M;
	ll t2 = (modularExpo(10, n, M) - t1) % M;

	ll ans = (t2 + modularExpo(8, n, M)) % M;
	if(ans < 0) ans += M;
	cout << ans << endl;

	return 0;
}

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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

// Math
inline ll gcd(ll a, ll b) {
  for (; a; swap(b %= a, a));
  return b;
}
inline ll lcm(ll a, ll b) {
  return a * (b / gcd(a, b));
}

signed main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> as(N);
    ll maxa = 0;
    ll gcda = 0;
    rep(i, N) {
        ll a;
        cin >> a;
        gcda = gcd(a, gcda);
        maxa = max(a, maxa);
    }
    cout << (K <= maxa && K%gcda == 0 ? "POSSIBLE" : "IMPOSSIBLE") << nl;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<ll, int> P;
typedef tuple<int, int, int> T;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, x, y;
int d[2010];

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            int k = j - i;
            k = min(k, abs(i-x)+1+abs(y-j));
            k = min(k, abs(i-y)+1+abs(x-j));
            d[k]++;
        }
    }
    for (int i = 1; i < n; i++) {
        cout << d[i] << endl;
    }
}

void input() {
    cin >> n >> x >> y;
}

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

    input();
    solve();
}


Measured memory_bytes: 3200
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

using ll =  long long;

constexpr double EPS = 1e-10;

vector<ll> factorize(ll n) {
    vector<ll> factors;
    for(ll i=2LL;i*i<=n&&n>1LL;++i) {
        while(n % i == 0LL) {
            factors.push_back(i);
            n /= i;
        }
    }
    if(n != 1LL) factors.push_back(n);
    return factors;
}

int main() {
    ll n;
    cin >> n;
    cout << n << ":";
    for(ll factor: factorize(n)) {
        cout << " " << factor;
    }
    cout << endl;
}



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

def solve():
    S = input()
    res_l = []
    r,l = 0,1
    for i,s in enumerate(S+'R'):
        if s == 'R':
            if l:
                if res_l:
                    res_l[i-l] = r//2 + (l+1)//2
                    res_l[i-l-1] = (r+1)//2 + l//2

                r,l = 1,0
            else:
                r += 1
            res_l.append(0)
        else:
            l += 1
            res_l.append(0)

    res = ' '.join(list(map(str,res_l[:-1])))
    return str(res)

if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 11128
#import <Foundation/Foundation.h>
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)

int main() {
	@autoreleasepool {
		NSMutableArray *A = [NSMutableArray array];
		int n;
		scanf("%d", &n);
		rep(i,n) [A addObject: [NSMutableSet set]];
		int ans=0;
		rep(i,n) {
			int a;
			scanf("%d",&a);
			a--;
			NSMutableSet *set = (NSMutableSet*)[A objectAtIndex:a];
			[set addObject:@(i)];
			set = (NSMutableSet*)[A objectAtIndex:i];
			if([set containsObject:@(a)]) ans++;
		}
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 32612
main(N){
	int i,S;
	for(;scanf("%d",&N)*N;){
		S=-N;
		for(i=1;i*i<N;i++){
			if(N%i==0)
				S+=i+N/i;
		}
		if(i*i==N)
			S+=i;
		printf("%st number\n",S<N?"deficien":S>N?"abundan":"perfec");
	}
}

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define setmin(x,y) if(x>y){x=y;}
int n,k,s;
int tmp;
int x[2000],y[2000],z[2000],p[2000];
int inf = 1e9+7;
int g[2000][2000];
int is_connected(int i, int j) {
    int dx = abs(x[j] - x[i]);
    int dy = abs(y[j] - y[i]);
    int dz = abs(z[j] - z[i]);
    return dx <= s && dy <= s && dz <= s;
}
int intersecting_area(int i, int j) {
    if (!is_connected(i, j)) return 0;
    int dx = s - abs(x[j] - x[i]);
    int dy = s - abs(y[j] - y[i]);
    int dz = s - abs(z[j] - z[i]);
    return 2 * (dx * dy + dy * dz + dz * dx);
}
int dfs(int i, int prev, int depth, int first) {
    if (depth == k) {
        if (3 <= k && is_connected(i, first)) {
            return 6*s*s - intersecting_area(i, first);
        }
        return 6*s*s;
    } else {
        int ans = inf;
        for (int j=0;j<p[i];j++) if (g[i][j] != prev) {
            setmin(ans, 6*s*s - intersecting_area(i, g[i][j]) + dfs(g[i][j], i, depth + 1, first));
        }
        return ans;
    }
}
int main(void){
    while(1){
        scanf("%d%d%d",&n,&k,&s);
        if(n==0&&k==0&&s==0) break;
        rep(i,n) scanf("%d %d %d",&x[i],&y[i],&z[i]);
        rep(i,n){
            tmp=0;
            rep(j,n)
            if (i != j) {
                if (is_connected(i, j)) {g[i][tmp]=j; tmp++;}
            }
            p[i]=tmp;
        }
        int ans = inf;
        rep(i,n) setmin(ans, dfs(i, -1, 1, i));
        if (ans == inf) ans = -1;
        printf("%d\n",ans);
        /*rep(i,n){
            rep(j,p[i]){
                printf("%d ",g[i][j]);
            }
            puts("");
        }*/
    }
    return 0;
}



Measured memory_bytes: 2840