akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second 
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
//#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
inline ll read(){
	ll x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	return x*f;
}
inline void out(int x){
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int s,w;
	cin>>s>>w;
	if(s<=w)cout<<"unsafe\n";
	else cout<<"safe\n";
	return 0;
}

Measured memory_bytes: 3632
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
ans=0
for i in range(n):
    a = list(map(int,input().split()))
    d = c
    for k in range(m):
        d+=a[k]*b[k]
    if d>0:
        ans+=1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
signed main()
{
    IOS
    string str; cin>>str;
    if(str == "Sunny") cout<<"Cloudy";
    else if(str == "Cloudy") cout<<"Rainy";
    else cout<<"Sunny";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;//typo用
using itn = int;//typo用
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a) - 1; i >= (intl)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl//1次元配列の出力
#define rrdebug(i, j, x) rep(i, alength(x))rep(j, alength(x[i]))cout << #x << "[" << i << "][" << j << "]:" << x[i][j] << endl//二次元配列の出力
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = acos(-1);
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
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; }
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl kai(intl k){//k!を求める関数,
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl digit10(intl a){//aを10進数で表したときの桁数を求める関数
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}


signed main(){
    cout << fixed << setprecision(10);
    intl n,m;
    cin >> n >> m;
    intl a[n];
    rep(i,n)cin >> a[i];
    priority_queue<intl> q;
    rep(i,n)q.push(a[i]);
    rep(i,m){
        intl a = q.top();
        q.pop();
        a /= 2;
        q.push(a);
    }
    intl cnt = 0;
    rep(i,n){
        cnt += q.top();
        q.pop();
    }
    cout << cnt << endl;
    return 0;
}

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

public class Main {

	Scanner sc = new Scanner(System.in);
	final static long LNF = 1L << 60;
	final static double EPS = 1e-9;

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {

		int n = ni();
		int k = ni();
		long[] h = new long[110000];
		long[] dp = new long[110000];

		for (int i = 0; i < n; i++) {
			h[i] = ni();
		}
		for (int i = 0; i < dp.length; i++) {
			dp[i] = LNF;
		}

		dp[0] = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 1; j <= k; ++j) {
				dp[i + j] = Util.min(dp[i + j], dp[i] + Math.abs(h[i] - h[i + j]));

			}
		}
		System.out.println(dp[n - 1]);
//		debug(dp);
	}

	int ni() {
		return Integer.parseInt(sc.next());
	}

	long nl() {
		return sc.nextLong();
	}

	double nd() {
		return Double.parseDouble(sc.next());
	}

	void debug(Object... os) {
		System.out.println(Arrays.deepToString(os));
	}

	static class Util {
		static <T extends Comparable<T>> T max(T a, T b) {
			if (a.compareTo(b) > 0) {
				return a;
			} else {
				return b;
			}
		}

		static <T extends Comparable<T>> T min(T a, T b) {
			if (a.compareTo(b) < 0) {
				return a;
			} else {
				return b;
			}
		}
	}

}


Measured memory_bytes: 153528
import java.util.*;
import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int C = sc.nextInt();
    ArrayList<Integer> list = new ArrayList<Integer>();
    int ans = 0;
    for (int i = 0; i < M; i++) {
      list.add(sc.nextInt());
    }
    for (int i = 0; i < N; i++) {
      int total = 0;
      for (int j = 0; j < M; j++) {
        total += list.get(j) * sc.nextInt();
      }
      if (total + C > 0) {
        ans++;
      }
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 23892
###############################################################################

from bisect import bisect_left as binl
from math import log10, log2

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################


def main():
    a, b = intin()
    bits = {}

    if not b:
        print(0)
        return 0

    for i in range(int(log2(b)) + 1):
        msbs_a = a >> i
        msbs_b = b >> i
        lsbs_a = a % (2**i)
        lsbs_b = b % (2**i)
        bit_a = msbs_a & 1
        bit_b = msbs_b & 1
        lsbs_count_a = (2**i) - lsbs_a
        lsbs_count_b = lsbs_b + 1

        if bit_a == 0 and bit_b == 0:
            bits[i] = 0
            continue

        if bit_a == 1 and bit_b == 1:
            bits[i] = 1 if (lsbs_count_a + lsbs_count_b) % 2 else 0
            continue

        if bit_a:
            bits[i] = 1 if lsbs_count_a % 2 else 0
            continue

        if bit_b:
            bits[i] = 1 if lsbs_count_b % 2 else 0
            continue

    if a % 2:
        if (b - a + 1) % 2:
            odd_count = (b - a + 1) // 2 + 1
        else:
            odd_count = (b - a + 1) // 2
    else:
        odd_count = (b - a + 1) // 2
    bits[0] = odd_count % 2

    ans = 0
    for i in bits:
        if bits[i]:
            ans += 2 ** i
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if(n%2==0) {
			System.out.println((n/2)-1);
		}
		else {
			System.out.println(n/2);
		}
	}

}


Measured memory_bytes: 23636
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
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; }

constexpr int MOD = 1'000'000'007;

long long power(long long x, long long n, long long mod = MOD) {
    if (n == 0) return 1;
    if (n % 2 == 0) return power(x * x % mod, n/2, mod);
    else return x * power(x, n-1, mod) % mod;
}

// auto mod int
struct mint {
    LL x;
    mint(LL x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(const LL &t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
    LL operator()() const {
        return x;
    }
};
using VM = vector<mint>;
using VVM = vector<VM>;

void solve() {
    int n;
    cin >> n;
    VLL c(n);
    REP(i,0,n) cin >> c[i];
    sort(all(c));
    mint pat = power(2,n-1) * power(2,n-1);


    mint ans = 0;
    mint sum = 0;
    REP(i,0,n) {
        ans += sum;
        ans += 2 * c[i];
        sum += c[i];
    }
    ans *= pat;
    cout << ans() << endl;
}

signed main() {
    solve();
    
    return 0;
}

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

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// typedef
typedef long long llint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double pi = 3.14159265358979323846;

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

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

  int n, k;
  cin >> n >> k;
  vector<int> ans;
  while (n != 0) {
    ans.emplace_back(n % k);
    n /= k;
  }
  reverse(all(ans));
  cout << ans.size() << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var count = 0;
        for(int i = 1; i <= N; i = i + 2)
        {
            if (CountDivisor(i) == 8) count++;
        }

        Console.WriteLine(count);
    }

    private static int CountDivisor(int num)
    {
        var count = 0;
        for(int i = 1; i <= num; i++)
        {
            if (num % i == 0) count++;
        }
        return count;
    }
}



Measured memory_bytes: 27288
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,e;
    cin>>a>>b;
    c=a+b,d=a-b,e=a*b;
    c=max(c,d);
    c=max(c,e);
    printf("%d",c);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

/*
using PAIR = pair<string, int>;
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA() cerr << "AAAAA" << endl
#define debug_() cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;

using Graph = vector<vector<int>>;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    ll SUM = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        SUM += a[i];
    }
    ll tmp = 0;
    for (int i = 0; i < n; i += 2)
    {
        tmp += a[i];
    }
    vector<int> ans(n);
    ans[0] = 2 * tmp - SUM;
    for (int i = 1; i < n; i++)
    {
        ans[i] = 2 * a[i - 1] - ans[i - 1];
    }
    for (int i = 0; i < n; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n;
    cin >> n;
    vector<int> a;
    long long sum = 0;
    long long tmp = 0;
    REP(i, n)
    {
        int v;
        cin >> v;
        sum += v;
        a.push_back(v);
    }
    sort(a.begin(), a.end());
    if (a[n / 2] != a[n / 2 - 1])
    {
        cout << a[n / 2] - a[n / 2 - 1] << endl;
    }
    else
    {
        cout << "0" << endl;
    }
}

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

int main() {
    int64_t n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for(int i=0;i<n;i++){
        cin>>vec.at(i);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    if(k>=n){
        cout<<"0"<<endl;
    }else if(k<n){
        for(int i=0;i<k;i++){
            vec.at(i)=0;
        }
        int64_t sum=0;
        for(int i=0;i<n;i++){
            sum+=vec.at(i);
        }
        cout<<sum<<endl;
    }
}

Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
 long long int a,b,s,d;
 while(scanf("%lld %lld",&a,&b)!=EOF)
  {
      d=0;
      s=a+b;
     while(s!=0)
     {
      s=s/10;
      d++;
     }
     printf("%lld\n",d);
  }
return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;void solve();int main(){ios::sync_with_stdio(0);cin.tie(0);solve();};typedef long long ll;
template<typename Type>void print_collection(Type coll){cout<<"{ ";for(auto e:coll)cout<<e<<' ';cout<<"}\n";}
void solve() {
  int n, k;
  string s;
  cin >> n >> s >> k;
  for (int i=0; i < n; ++i)
    if (s[i] != s[k-1])
      s[i] = '*';
  cout << s << '\n';
}

Measured memory_bytes: 256
fn main() {
 let v:Vec<usize>=z();
 let (r,c)=(v[0],v[1]);
 let mut s=vec![0;c+1];
 for _ in 0..r{
  let v:Vec<isize>=z();
  y(&v);
  let t=v.iter().sum::<isize>();
  println!(" {}",t);
  for (x,y) in v.iter().enumerate(){s[x]=s[x]+y}
  s[c]+=t;
 }
 y(&s);
 println!();
}
fn z<T:std::str::FromStr>()->Vec<T>{
 let mut b=String::new();
 let s=std::io::stdin();
 s.read_line(&mut b).unwrap();
 b.split_whitespace().flat_map(str::parse).collect()
}
fn y(v:&Vec<isize>)->(){
 print!("{}",v.iter().map(std::string::ToString::to_string).collect::<Vec<_>>().join(" "));
}


Measured memory_bytes: 5056
lis=list(input().split())
l=""
for i in range(len(lis)-1):
    for j in lis[i]:
        if j==str.upper(j):
            l+=str.lower(j)
        else:
            l+=str.upper(j)
    print(l,end=" ")
    l=""
for k in lis[-1]:
    if k==str.upper(k):
            l+=str.lower(k)
    else:
        l+=str.upper(k)
print(l)


Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
const int mod = 100000;
int main()
{
    int N, M, S;
    while(cin >> N >> M >> S, N || M || S) {
        int dp[55][3005] = {};
        dp[0][0] = 1;
        for(int p = 1; p <= M; p++) {
            for(int i = N * N; i >= 0; i--) {
                for(int j = S; j >= 0; j--) {
                    if(j + p <= 3000) (dp[i + 1][j + p] += dp[i][j]) %= mod;
                }
            }
        }
        cout << dp[N * N][S] << endl;
    }
    return (0);
}



Measured memory_bytes: 3696
#include <stdio.h>

int main(void) {
  int i, j, k, n;
  scanf("%d", &n);
  if(n == 3) {
    printf("2 3 25");
  } else {
    int now = 9;
    printf("2 4 3 9");
    if(n & 1) {
      printf(" 6");
      for(i = 5; i < n; ++i) {
        if(now % 6 == 3 || !(now % 6)) now += 6;
        else if(now % 6 == 2) now += 2;
        else now += 4;
        if(now > 30000) {
          if(now % 6 == 3) now = 8;
          else now = 12;
        }
        printf(" %d", now);
      }
    } else {
      for(i = 4; i < n; ++i) {
        if(now % 6 == 3 || !(now % 6)) now += 6;
        else if(now % 6 == 2) now += 2;
        else now += 4;
        if(now > 30000) {
          if(now % 6 == 3) now = 8;
          else now = 6;
        }
        printf(" %d", now);
      }
    }
  }
  return 0;
}

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

const int64_t MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

ll pCount(int x){
  if(x==0) return 1;
  return pCount(x-1)*2 + 1;
}

ll allCount(int x){
  if(x==0) return 1;
  return allCount(x-1)*2 + 3;
}


signed main() {
  ll n,x;
  cin >> n >> x;
  
  //n = 1;
  //x = allCount(n);
  //cout << n << "," << x << "," << pCount(n) << endl;
  // (pCount-3)/2
  
  // (allCount-3) / 2 + 2 < x
  //  --> pCount(n-1) +　
  ll pNum = 0;
  int level = n;
  while(x>0 && level>=1){
    ll rCount = allCount(level-1);
    //cout << rCount << "," << x << endl;
    if( rCount + 2 <= x ){
      x -= rCount + 2;
      pNum += pCount(level-1) + 1;
    }
    else if( rCount + 1 <= x ){
      x -= rCount + 1;
      pNum += pCount(level-1);
    }
    else{
      x -= 1; // 最下部のBを引く
    }
    level--;
  }
  if(x>=1) pNum++;
  cout << pNum << endl;
  
  // 0         P
  // 1       BPPPB
  // 2     B[BPPPB]P[BPPPB]B
  // 3   B[B[BPPPB]P[BPPPB]B]P[B[BPPPB]P[BPPPB]B]B
  // 4 B[B[B[BPPPB]P[BPPPB]B]P[B[BPPPB]P[BPPPB]B]B]P[BBBPPPBPBPPPBBPBBPPPBPBPPPBBB]B  
  
  //  
  // f(0) = 1
  // f(1) = f(0)*2 + 1;
  // f(x) = f(x-1)*2 +1;
  
  // (f(x)-1)/2 = f(0)
  
  return 0;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

int main(){
  ll h,w,k;
  cin >> h >> w >> k;
  vector<vector<char>>s(h,vector<char>(w));
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cin >> s[i][j];
    }
  }
  
  vector<vector<ll>>ans(h,vector<ll>(w));
  ll start=0;
  ll count=0;
  for(int i=0; i<h; i++){
    ll c = 0;
    for(int j=0; j<w; j++){
      if(s[i][j]=='#') c++;
      if(c==0 || c==1){
        ans[i][j]=count+1;
      }
      else{
        ans[i][j]=count+c;
      }
    }
    if(c==0 && count==0){
      start++;
    }
    if(c==0 && count!=0){
      for(int j=0; j<w; j++){
        ans[i][j]=ans[i-1][j];
      }
    }
    count+=c;
  }
  
  for(int i=0; i<start; i++){
    for(int j=0; j<w; j++){
      ans[i][j]=ans[start][j];
    }
  }
  
  
  
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
  
  
}
       
        
      
  
    

Measured memory_bytes: 4424
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void swap(pair<char,int> &a, pair<char,int> &b)
{
	pair<char, int> temp;
	temp = a;
	a = b;
	b = temp;
}

int main(void)
{
	int n, minj, second;
	bool ok = true;
	char first;
	cin >> n;
	vector<pair<char, int> >A(n), B(n);
	for (int i = 0; i < n; i++) {
		cin >> first >> second;
		A[i].first = B[i].first = first;
		A[i].second = B[i].second = second;
	}
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j >= i + 1; j--) {
			if (A[j].second < A[j - 1].second)
				swap(A[j], A[j - 1]);
		}
	}
	for (int i = 0; i < n; i++) {
		cout << A[i].first << A[i].second;
		if (i != n - 1)
			cout << " ";
		else
			cout << endl;
	}
	cout << "Stable" << endl;
	for (int i = 0; i < n; i++) {
		minj = i;
		for (int j = i + 1; j < n; j++) {
			if (B[j].second < B[minj].second)
				minj = j;
		}
		if (i != minj)
			swap(B[minj], B[i]);
	}
	for (int i = 0; i < n; i++) {
		cout << B[i].first << B[i].second;
		if (i != n - 1)
			cout << " ";
		else
			cout << endl;
	}
	for (int i = 0; i < n; i++) {
		if (A[i] == B[i])
			continue;
		else
			ok = false;
	}
	if (ok)
		cout << "Stable" << endl;
	else
		cout << "Not stable" << endl;
	return 0;
}


Measured memory_bytes: 3120
a, b, c, x, y = map(int, input().split())
if x < y: print(min(c * 2 * x + b * (y - x), c * 2 * y, a * x + b * y))
else: print(min(c * 2 * y + a * (x - y), c * 2 * x, a * x + b * y))


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
using ll = long long int;
using namespace std;

int main() {
  ll N, M;
  cin >> N >> M;
  vector<ll> balls(N + 1, 1);
  vector<bool> red_ball(N + 1, false);
  red_ball[1] = true;
  ll count = 1;
  for (ll m = 0; m < M; m++) {
    ll x, y;
    cin >> x >> y;
    balls[x]--;
    balls[y]++;
    if (red_ball[x]) {
      if (!red_ball[y]) {
        red_ball[y] = true;
        count++;
      }
      if (balls[x] == 0) {
        red_ball[x] = false;
        count--;
      }
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
#define FASTI0 ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
    string str;
    cin>>str;
    int sum=0;
    for(int i=0;i<str.size();i++)
    {
        sum+=str[i]-'0';
    }
    if(sum%9==0)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}



Measured memory_bytes: 3708
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define frw(i, a, b) for(int i = a; i < b; i++)
#define fi first
#define se second
#define pb push_back
#define in insert
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int(a.size())
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define vpii vector<pii>
#define vpiii vector<piii>
#define vpll vector<pll>
#define vplll vector<plll>
#define mod 1000000007

ll maax=1000001;
ll p[10000001];
int modInverse(ll a, ll m) 
{ 
    ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) 
      return 0; 
    while (a > 1) 
    { 
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    } 
    if (x < 0) 
       x += m0; 
    return x; 
} 
 ll dp[200000];

int po(ll x,ll y)
{
	ll res=1;
	while(y>0)
	{
		if(y&1)
			res=(res*x)%mod;
		y=y>>1;
		x=(x*x)%mod;
	}
	return res;
}
void seive()
{
	p[0]=1;
	p[1]=1;
	for(int i=2;i<maax;i++)
	{
		if(p[i]==0)
		{
			for(int j=2*i;j<maax;j+=i)
			{
				if(p[j]==0)
					p[j]=i;
			}
			p[i]=i;
		}
	}
}

int main()
{
	int n;
	cin>>n;
	ll a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	seive();
	unordered_map<int ,int>mx;
	for(int i=0;i<n;i++)
	{
		int num=a[i];
		unordered_map<int ,int>t;
		while(num>1)
		{
			int f=p[num];
			t[f]++;
			num/=f;
		}
		for(auto it:t)
			mx[it.first]=max(mx[it.first],it.second);
	}
	ll ans=1;
	for(auto it:mx)
	{
		ans=(ans*po(it.first,it.second))%mod;
	}
	//cout<<ans<<endl;
	ll a2=0;
	for(int i=0;i<n;i++)
	{
		a2=(a2+(ans*modInverse(a[i],mod))%mod)%mod;
	}
	cout<<a2;
}


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


int main()
{	
	int n;
	cin>>n;
	vector<pair<int,int>>v;
	for(int i=1;i<=n;i++)
	{
		int k=i,cnt=0;
		while(k%2==0)
		{
			k/=2;
			cnt++;
		}
		v.push_back(make_pair(cnt,i));
	}
	sort(v.begin(),v.end());
	cout<<v[n-1].second<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define LEN 100005
typedef struct pp
{
	char name[100];
	int t;
}P;

P Q[LEN];
int head,tail, n;
void enqueue(P x)
{
	Q[tail]=x;
	tail =(tail+1) % LEN;
}
P dequeue()
{
	P x=Q[head];
	head=(head+1)%LEN;
	return x;
}

int min(int a,int b)
{
	return a<b ? a:b;
}
int main()
{
	int elaps =0,c;
	int i,q;
	P u;
	scanf("%d %d",&n,&q);
	for(i=1;i<=n;i++)
	{
		scanf("%s",Q[i].name);
		scanf("%d",&Q[i].t);
	}
	head =1;
	tail = n+1;
	
	while(head !=tail)
	{
		u=dequeue();
		c=min(q,u.t);
		u.t-=c;
		elaps+=c;
		if(u.t>0) enqueue(u);
		else
		{
			printf("%s %d\n",u.name,elaps);
		}
	}
return 0;
}


Measured memory_bytes: 11884
#include<bits/stdc++.h>
#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 rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

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

	vector<ll> divmin1 = divisor(n - 1);
	vector<ll> div = divisor(n);

	ll ans = 0;
	ans += divmin1.size() - 1;

	rep (i, div.size()) {
		if (div[i] == 1) continue;
		ll tmp = n;
		while (tmp % div[i] == 0) tmp /= div[i];
		if (tmp % div[i] == 1) ans++;
	}

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

Measured memory_bytes: 384
#include <cstdio>
#include <functional>
#include <vector>
#include <tuple>
#include <algorithm>
#include <deque>
#include <memory>

using namespace std;

using ll = long long;
int n, m;
int digits[9];
int sticks_for_digits[10] = {-1,2,5,5,4,5,6,3,7,6};
bool called[10000];
bool reachable[10000];

struct Node {
  int value;
  shared_ptr<Node> next;
  Node(int v, shared_ptr<Node> n) : value(v), next(n) {};
  // ~Node() { printf("~Node(%d)\n", value); }
};
struct LinkedList {
  shared_ptr<Node> root;
  int length;
  LinkedList() : length(0) {};
  LinkedList(int v, LinkedList& tail) : length(tail.length+1), root(make_shared<Node>(v, tail.root)) {};
  bool empty()
  {
    return length == 0;
  }
  int size()
  {
    return length;
  }
};
LinkedList nil;
LinkedList cons(int value, LinkedList& list)
{
  return LinkedList(value, list);
}
LinkedList cons(int value, LinkedList&& list)
{
  return LinkedList(value, list);
}
LinkedList dp[10000];

bool is_left_ge(LinkedList& left, LinkedList& right)
{
  if (left.length > right.length) return true;
  if (left.length < right.length) return false;
  shared_ptr<Node> l = left.root;
  shared_ptr<Node> r = right.root;
  while (!((l == nullptr) && (r == nullptr))) {
    if (l->value > r->value) return true;
    if (l->value < r->value) return false;
    l = l->next;
    r = r->next;
  }
  return true;
}

void solve(int sticks)
{
  if (called[sticks]) return;
  called[sticks] = true;
  LinkedList cur;// = nil;
  //printf("entering solve(%d)\n", sticks);
  //cur.push_back(0);
  for (int i = 0; i < m; i++) {
    int to_consume = sticks_for_digits[digits[i]];
    if (sticks < to_consume) continue;
    solve(sticks-to_consume);
    /*printf("solve(%d) =", sticks-to_consume);
    Node *ptr = dp[sticks-to_consume];
    while (ptr) {
      printf("%d", ptr->value);
      ptr = ptr->next;
    }
    printf("\n");*/
    if (!reachable[sticks-to_consume]) continue;
    LinkedList newlist = cons(digits[i], dp[sticks-to_consume]);
    if (is_left_ge(newlist, cur)) {
      cur = newlist;
    }
  }
  if (cur.length == 0) {
    int c = 0;
    for (int i = 0; i < m; i++) {
      if (sticks_for_digits[digits[i]] == sticks) {
        c = max(c, digits[i]);
      }
    }
    if (c != 0) {
      cur = cons(c, nil);
    }
  }
  else if (cur.length == 1) {
    for (int i = 0; i < m; i++) {
      if (sticks_for_digits[digits[i]] == sticks) {
        cur.root->value = max(cur.root->value, digits[i]);
      }
    }
  }
  if (cur.length != 0) {
    dp[sticks] = cur;
    reachable[sticks] = true;
  }
}

int main()
{
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &(digits[i]));
    //int sticks = sticks_for_digits[digits[i]];
    //digits_for_sticks[sticks] = max(digits_for_sticks[sticks], digits[i]);
  }
  reachable[0] = true;
  called[0] = true;
  dp[0] = LinkedList();
  solve(n);
  shared_ptr<Node> ptr = dp[n].root;
  vector<int> ds;
  while (ptr) {
    ds.push_back(ptr->value);
    ptr = ptr->next;
  }
  for (auto d : ds) {
    printf("%d", d);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(){
	int N,M,C;
	int i,j;
	int sum;
	int ans;
	
	scanf("%d %d %d",&N,&M,&C);
	
	int B[M];
	int A[N][M];
	
	for(i=0;i<M;i++){
		scanf("%d",&B[i]);
	}
	for(i=0;i<N;i++){
		for(j=0;j<M;j++){
			scanf("%d",&A[i][j]);
		}
	}
	
	ans=0;
	for(i=0;i<N;i++){
		sum=0;
		for(j=0;j<M;j++){
			sum+=A[i][j]*B[j];
		}
		if(sum+C>0)	ans++;
	}
	
	printf("%d",ans);
	
	return 0;
}

Measured memory_bytes: 128
object Main{
  case class Job (days: Int, pay: Int)

  def main(args: Array[String]) : Unit = {
    val sc = new java.util.Scanner(System.in)
    val n,m = sc.nextInt
    val jobs = (1 to n)
      .map{_ => Job(sc.nextInt,sc.nextInt) }
      .groupBy { job => job.days }

    val candidate = collection.mutable.PriorityQueue[Job]()(Ordering.by{job => job.pay})
    var result = 0
    (1 to m).foreach { x =>
      //candidate.addAll(jobs.getOrElse(x,List.empty))
      jobs.getOrElse(x,List.empty).foreach{job => candidate += job }

      if(! candidate.isEmpty) {
        val select:Job = candidate.dequeue
        result += select.pay
      }
    }
    println(result)
  }
}



Measured memory_bytes: 154792
import java.util.*;

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

		int n = scanner.nextInt();
		int v[][] = new int[n][];
		int d[] = new int[n];
		
		for (int i = 0; i < n; i ++) {
			d[i] = -1;
			
			int u = scanner.nextInt() - 1;
			int k = scanner.nextInt();
			
			v[u] = new int[k];
			
			for (int j = 0; j < k; j ++) {
				v[u][j] = scanner.nextInt() - 1;
			}
		}

		scanner.close();
		
		Queue<Integer> queue = new ArrayDeque<>(n);
		
		d[0] = 0;
		queue.add(0);
		while(!queue.isEmpty()) {
			int u = queue.remove();
			for (int i = 0; i < v[u].length; i ++) {
				if (d[v[u][i]] == -1) {
					d[v[u][i]] = d[u] + 1;
					queue.add(v[u][i]);
				}
			}
		}
		
		for (int j = 0; j < n; j ++) {
			System.out.println((j + 1) + " " + d[j]);
		}
	}
} 



Measured memory_bytes: 28276
#include <vector> 
#include <list> 
 #include <map>
 #include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;

/*
数列が偶数になる時ではなく奇数になる時を考えて
全体からその場合を引く。

aが奇数の時はaそのままの１通り
aが偶数の時はa+1,a-1の２通り
*/
int N;
int a;
int main(){
    int n=1,odd=1;
    cin>>N;
    REP(i,N){
        cin>>a;
        n*=3;
        if(a%2==0){odd*=2;}
    }
    cout<<n-odd<<endl;







}


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

int GCD(int a, int b)
{
	if (b > 0) {
		return GCD(b, a%b);
	}else {
		return a;
	}
}

int LCM(int a, int b)
{
	return a / GCD(a, b) * b;
}

int main()
{
	int a, b;
	while (cin >> a >> b)
		cout << GCD(a, b) << " " << LCM(a, b) << endl;
	
	return 0;
}

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

using namespace std;

int main(){
    int h,w,k;
    cin>>h>>w>>k;
    
    // int val[h+1][w+1];
    // for(int i=0;i<=w;i++)
    //     val[0][i] = 0;
    // for(int i=0;i<=h;i++)
    //     val[i][0] = 0;
    // for(int i=1;i <=h ; i++){
    //     for(int j=1;j<=w;j++){
    //         char c;
    //         cin>>c;
    //         // cout<<c;
    //         val[i][j] = val[i-1][j] + val[i][j-1] - val[i-1][j-1];
    //         if(c=='#'){
    //             val[i][j]++;
    //         }
    //     }
    // }
    // int total = val[h][w];
    // int ans=0;
    // for(int r1=1; r1<=h; r1++){
    //     for(int r2=r1; r2<=h; r2++){
    //         for(int c1=1; c1<=w; c1++){
    //             for(int c2=c1; c2<=w; c2++){
    //                 int col = val[h][c2] - val[h][c1-1];
    //                 int row = val[r2][w] - val[r1-1][w];
    //                 int res = val[r2][c2] + val[r1-1][c1-1] - val[r2][c1-1] - val[r1-1][c2];
    //                 int left = col + row - res;
    //                 if((total - left) == k){
    //                     ans++;
    //                 }
    //             }
    //         }
    //     }
    // }

    int val[h][w];
    int total = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            cin>>c;
            val[i][j] = 0;
            if(c=='#'){
                val[i][j] = 1;
                total++;
            }
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<h);i++){
        for(int j=0;j<(1<<w);j++){
            int sum = 0;
            for(int p=0;p<h;p++){
                if((i&(1<<p))==0){
                    for(int q=0;q<w;q++){
                        if((j&(1<<q))==0){
                            sum = sum + val[p][q];
                        }
                    }
                }
            }
            if((sum) == k)
                ans++;
        }
    }
    cout<<ans;
    return 0; 
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int X = sc.nextInt();
		int pattern = 0;
		for(int i = 0; i < A + 1; i++) {
			int sumi = 500 * i;
			if(!(sumi > X)) {
				for(int j = 0; j < B + 1; j++) {
					int sumj = sumi + 100 * j;
					if(!(sumj > X)) {
						if(!((X - sumj) / 50 > C)) {
							pattern++;
						}
					} else {
						break;
					}
				}
			} else {
				break;
			}
		}
		System.out.println(pattern);
	}

}


Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
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;
}
void debug() { cerr << "\n"; }
template <class T> void debug(const T &x) { cerr << x << "\n"; }
template <class T, class... Args> void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
template <class T> void debugVector(const vector<T> &v) {
    for(const T &x : v) {
        cerr << x << " ";
    }
    cerr << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int N;
vector<ll> a;
ll dp[3010][3010];
bool f[3010][3010] = {false};

ll dfs(int l, int r) {
    if(f[l][r]) {
        return dp[l][r];
    }
    f[l][r] = true;
    if(l + 1 >= r) {
        return dp[l][r] = a[l];
    }
    return dp[l][r] = max(a[l] - dfs(l + 1, r), a[r - 1] - dfs(l, r - 1));
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    a.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    cout << dfs(0, N) << endl;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    ll l, r; cin >> l >> r;

    if (r - l >= 2020) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = LINF;
    for (ll i = l; i < r; ++i) {
        for (ll j = i+1; j <= r; ++j) {
            ans = min(ans, (i * j) % 2019);
        }
    }

    cout << ans << endl;
}

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

int main(){
  int n,a,sum=0;
  cin>>n;
  vector<int> l(n);
  for(int i=0; i<n; i++) {
    cin>>l[i];
    sum += l[i];
  }
  sort(l.begin(),l.end());
  if(sum - 2*l[n-1] > 0) cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int num[N],s[N];
long long int n,k,x,b,c,count1;
long long int sum;
int main()
{
	scanf("%lld",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&x);
		num[x]++;
		sum+=x;
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	{
		scanf("%lld%lld",&b,&c);
		count1=num[b];
		sum-=count1*b;
		sum+=count1*c;
		num[b]-=count1;
		num[c]+=count1;
		printf("%lld\n",sum);
	}
} 

Measured memory_bytes: 4028
#include <iostream>
#include <cmath>

using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,n) FOR(i,0,n)

const double PI = acos(-1);

double angToRad(double angle) {
	return angle * PI / 180.0;
}

int main() {
	double a, b, c, d;
	while (cin >> a >> b >> c >> d, a != -1.0 || b != -1.0 || c != -1.0 || d != -1.0) {
		a = angToRad(a);
		b = angToRad(b);
		c = angToRad(c);
		d = angToRad(d);
		int ans = round(6378.1 * acos(sin(a) * sin(c) + cos(a) * cos(c) * cos(d - b)));
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1288
#include "bits/stdc++.h"
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

struct Rectangle { 
        int height, pos;
        Rectangle(int h, int p) : height(h), pos(p) {}
};
//1と0のグリッドにおいて1のマスのみを使って作る長方形の中で面積が最大のものの面積を返す
int LargestRectangle(vector<vector<int> > &s, int h, int w) { 
        vector<vector<int> > t(h, vector<int> (w));
        for (int x = 0; x < w; x ++) for (int y = 0; y < h; y ++) {
                if (s[y][x] == 1) t[y][x] = 0;
                else t[y][x] = (y > 0) ? t[y - 1][x] + 1 : 1;
        }
        int res = 0;
        for (int y = 0; y < h; y ++) { 
                stack<Rectangle> st;
                int ma = 0;
                t[y].resize(t.size() + 1);
                t[y][w] = 0;
                for (int x = 0; x <= w; x ++) {
                        Rectangle rect(t[y][x], x);
                        if (st.empty()) {
                                st.push(rect);
                        } else {
                                if (st.top().height < rect.height) {
                                        st.push(rect);
                                } else if (st.top().height > rect.height) {
                                        int target = x;
                                        while (!st.empty() && st.top().height >= rect.height) {
                                                Rectangle prev = st.top(); st.pop();
                                                ma = max(ma, (prev.height + 1) * (x - prev.pos + 1));
                                                target = prev.pos;
                                        }
                                        rect.pos = target;
                                        st.push(rect);
                                }
                        }
                }
                res = max(res, ma);
        }
        return res;
}

int main() {
        int h, w;
        cin >> h >> w;
        vector<vector<int> > a(h, vector<int> (w));
        for (int y = 0; y < h; y ++) {
                string s;
                cin >> s;
                for (int x = 0; x < w; x ++) {
                        a[y][x] = s[x] == '#';
                }
        }
        vector<vector<int> > b(h - 1, vector<int> (w - 1));
        for (int y = 0; y < h - 1; y ++) {
                for (int x = 0; x < w - 1; x ++) {
                        b[y][x] = a[y][x] ^ a[y + 1][x] ^ a[y][x + 1] ^ a[y + 1][x + 1];
                }
        }
        cout << max(max(h, w), LargestRectangle(b, h - 1, w - 1)) << endl;
        return 0;
}



Measured memory_bytes: 59136
# import numpy as np
# import queue
# import heapq


def main():
    print(resolve())


def resolve():
    X = int(input())

    c = 100
    for year in range(1, 10**9):
        c = c * 101 // 100
        if c >= X:
            return year


if __name__ == "__main__":
    main()


Measured memory_bytes: 9164
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }


/*
--------------------------------------------

	type

--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

/*
--------------------------------------------

	container

--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

/*
--------------------------------------------

	repetition

--------------------------------------------
*/
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPinit(a,n) for(int i=a; i<n; i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

/*
--------------------------------------------

	constant

--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

/*
--------------------------------------------

	Optimizer

--------------------------------------------
*/
//#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/*
--------------------------------------------
 
	Utility Algorithm

-------------------------------------------- 
*/

template <typename T>
void swapAlgorithm(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}
 
template <typename T1>
T1 euclideanAlgorithm(T1 a, T1 b) {
    T1 a_tmp = a;
    T1 b_tmp = b;
 
    if (a_tmp > b_tmp) {
        swapAlgorithm<T1>(a_tmp, b_tmp);
    }
 
    T1 r = a_tmp % b_tmp;
    while (r != 0) {
        a_tmp = b_tmp;
        b_tmp = r;
        r = a_tmp % b_tmp;
    }
    return b_tmp;    
}

template <typename T2>
T2 getLCM(T2 a, T2 b) {
    return (a * b)/(euclideanAlgorithm(a, b));
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    cout << count(ALL(s), '1') << endl;
    return 0;
}


Measured memory_bytes: 256