akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef int Int;
typedef pair<Int, Int> pii;
typedef pair<Int, double> pid;
typedef pair<double, double> pdd;
typedef pair<Int, pii> pip;
typedef pair<pii, Int> ppi;
typedef pair<double, Int> pdp;
typedef vector<Int> veci;
typedef vector<double> vecd;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<pii> vecpii;
typedef vector<ppi> vecppi;
typedef vector<veci> mati;
typedef vector<vecll> matll;
typedef vector<vecd> matd;
#define PB(x) push_back(x)
#define EB(x) emplace_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define REP(i, a, b) for(int i = (a);i <= (b);i++)
#define FORO(i, n) REP(i,0,(int)n-1)
#define FORI(i, n) REP(i,1,(int)n)
#define FORIT(i, t) for(auto i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a, _b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
#define DEBUG 1
#if DEBUG
#define DUMP(a) do { std::cout << #a " = " << (a) << ", "; } while(false)
#define DUMPLN(a) do { std::cout << #a " = " << (a) << std::endl; } while(false)
#else
#define DUMP(a)
#define DUMPLN(a)
#endif
template<typename T, typename U>
inline void getMin(T &a, U b) { if (a > b) a = b; }
template<typename T, typename U>
inline void getMax(T &a, U b) { if (a < b) a = b; }
template<typename T>
vector<T> getVector(const int n) { return vector<T>(n); }
template<typename T>
vector<T> getVector(const int n, const T a) { return vector<T>(n, a); }
template<typename T>
vector<T> getEmptyVector() { return vector<T>(); }
template<typename T>
void appendAll(vector<T> &a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); }
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
// #define X first
// #define Y second
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const ll MOD = 1000000007;
const int MAXN = 1 << 17;
const int inf = 1 << 27;
const ll llinf = 1LL << 50;
const int NIL = -inf;
int popcount(int x) { return __builtin_popcount(x); }


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

    int x; cin >> x; cout << !x << endl;

    return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		
		for (int i=a;;i++){
			String s = String.valueOf(i);
			char c1 = s.charAt(0);
			char c2 = s.charAt(1);
			char c3 = s.charAt(2);
			
			if ((c1 == c2) && (c1 == c3)){
				System.out.println(i);
				break;
			}
		}
		
		
		
	}

}


Measured memory_bytes: 21076
$MOD = 10 ** 9 + 7

def modpow(_n, _pp)
    r = 1
    n = _n
    pp = _pp
    while pp > 0
        r = (r*n) % $MOD if pp&1 == 1
        n = (n*n) % $MOD
        pp = pp >> 1
    end
    return r
end

def fermatComb(n, k)
    fermatComb(n, n - k) if k > n - k
    denominator = 1 # 分母
    numerator = 1 # 分子
    k.times do |i|
        denominator *= (n - i)
        denominator %= $MOD
        numerator *= (i + 1)
        numerator %= $MOD
    end

    return denominator * modpow(numerator, $MOD - 2) % $MOD
end

n, a, b = gets.chomp.split.map(&:to_i)
ans = modpow(2, n) - 1
ans -= (fermatComb(n, a) + fermatComb(n, b)) % $MOD

puts ans % $MOD

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

mt19937_64 llrand(random_device{}());

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define cl(x, v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<
#define gcd(x, y) __gcd((x), (y))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector<vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f, LMOD = 1011112131415161719ll;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int K = 1e5+5;
const int N = 1e2+5;

ll n, k, a[N], dp[N][K];

int main () {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    for (int k = 0; k < K; k++) dp[0][k] = 1;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < K; k++) {
            dp[i][k] = dp[i-1][k];
            if (k-a[i]-1 >= 0) dp[i][k] -= dp[i-1][k-a[i]-1];
            dp[i][k] = ((dp[i][k]%MOD)+MOD)%MOD;
            if (k > 0) {
                dp[i][k] += dp[i][k-1];
                dp[i][k] %= MOD;
            }
        }
    }

    ll ans = dp[n][k];
    if (k > 0) ans -= dp[n][k-1];
    ans = ((ans%MOD)+MOD)%MOD;
    printf("%lld\n", ans);

    return 0;
}


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

const int M = 1 << 20, N = 2*M, INF = 1e18;

struct Tree {
    int a[N], b[N], d[N], f[N];
    
    void init() {
        for(int i = M; i < N; i++)
            f[i] = 1 + (d[i] = i - M);
        for(int i = M-1; i > -1; i--) {
            d[i] = d[i*2];
            f[i] = f[i*2+1];
        }
        for(int i = 0; i < N; i++) {
            a[i] = 0;
            b[i] = INF;
        }
    }
    
    void insert(int i, int A, int B) {
        if(i >= N)
            return;
        int deb[] = {d[i] * A + B, d[i] * a[i] + b[i]},
            fin[] = {f[i] * A + B, f[i] * a[i] + b[i]};
        //cout << A << ' ' << B << ' ' << d[i] << ' ' << f[i] << ' ' << deb[0] << ' ' << deb[1] << ' ' << fin[0] << ' ' << fin[1] << '\n';
        if(deb[0] <= deb[1] && fin[0] <= fin[1]) {
            a[i] = A;
            b[i] = B;
        } else if(!(deb[1] <= deb[0] && fin[1] <= fin[0])) {
            int m = (d[i] + f[i]) / 2,
                med[] = {m * A + B, m * a[i] + b[i]};
            if(med[0] < med[1]) {
                swap(A, a[i]);
                swap(B, b[i]);
                swap(deb[0], deb[1]);
            }
            if(deb[0] < deb[1])
                insert(i*2, A, B);
            else
                insert(i*2+1, A, B);
        }
    }
    
    int getMin(int i, int x) {
        if(i == 0)
            return INF;
        return min(getMin(i/2, x), a[i]*x + b[i]);
    }
};

int n, c, h[M], cost[M];

signed main() {
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    Tree tree;
    tree.init();
    cin >> n >> c;
    for(int i = 0; i < n; i++)
        cin >> h[i];
    
    for(int i = 0, j = 1; j < n; i++, j++) {
        tree.insert(1, -(h[i]*2), c + cost[i] + h[i] * h[i]);
        //cout << -(h[i]*2) << ' ' << c + cost[i] + h[i] * h[i] << ' ' << cost[i] << '\n';
        cost[j] = tree.getMin(h[j] + M, h[j]) + h[j] * h[j];
        //cout << h[j] << ' ' << tree.getMin(h[j] + M, h[j]) << ' ' << cost[j] << '\n' << '\n';
    }
    cout << cost[n-1] << '\n';
}


Measured memory_bytes: 69504
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main() {
    int A, B;
    cin >> A >> B;

    cout << A * B - A - B + 1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
const int MAXN = 2e5 + 5, MAXM = 3e5 + 5, BOUND = 1e7, MOD = 1073741824, INF = 0x3f3f3f3f, base = 10000;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-9;
#define mid l + ((r-l)>>1)
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define lc(x) ch[x][0]
#define pii pair<int,int>
#define vi vector<int>
#define RR register int
#define rc(x) ch[x][1]
#define rep(i,a,b) for(RR i=(a);i<=(b);++i)
#define random(a,b) ((a)+rand()%((b)-(a)+1))

int n;
int a[MAXN], l[MAXN], r[MAXN];
int sum;
int gcd(int a, int b) {
	return !b ? a : gcd(b, a%b);
}
int main() {
	cin >> n;
	rep(i, 1, n)cin >> a[i];
	rep(i, 1, n)l[i] = gcd(l[i - 1], a[i]);
	for (int i = n; i >= 1; i--)r[i] = gcd(r[i + 1], a[i]);
	rep(i, 1, n) {
		sum = max(sum, gcd(l[i - 1], r[i + 1]));
	}
	cout << sum << '\n';
	return 0;
}

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

#define ll long long
#define mod 1000000007

int main(void){
	int H, W;
	cin >> H >> W;
	vector<vector<char> > grid(H, vector<char>(W));
	for(int row = 0;row < H;row++){
		for(int col = 0;col < W;col++){
			cin >> grid[row][col];
		}
	}
	vector<vector<ll> > dp(H, vector<ll>(W, 0));
	dp[0][0] = 1;
	for(int i = 1;i < H;i++)
		dp[i][0] = grid[i][0] == '.' && dp[i-1][0] == 1 ? 1 : 0;
	for(int i = 1;i < W;i++)
		dp[0][i] = grid[0][i] == '.' && dp[0][i-1] == 1 ? 1 : 0;
	for(int row = 1;row < H;row++){
		for(int col = 1; col < W;col++){
			dp[row][col] = (grid[row][col] == '.' ? dp[row-1][col] + dp[row][col-1] : 0)%mod;
		}
	}
	cout << dp[H-1][W-1]%mod << endl;
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    vppil l(n);
    rep(i,n){
        int a;
        cin>>a;
        rep(j,a){
            pint xy;
            cin>>xy.first>>xy.second;
            xy.first--;
            l.at(i).push_back(xy);
        }
    }
    //end input
    //binary search
    int ans=0;
    rep(bit,1<<n){
        bool flag=true;
        rep(i,n){
            if(bit&(1<<i)){//is bit true
                //get items from l;
                for(pint xy:l.at(i)){
                    if((bit&(1<<xy.first))>>xy.first!=xy.second){
                        flag=false;
                        i+=n;
                        break;//=>gotonext
                    }
                }
            }
        }
        //gotonext
        if(flag){ans=max(__builtin_popcount(bit),ans);}
    }
    cout<<ans<<endl;
}

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

public class Main {

	static int n;
	static long m;
	static int r;
	static ArrayList<Integer> route = new ArrayList<Integer>();
	static int[][] map;
	static int[][] dis;

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			n = sc.nextInt();
			m = sc.nextLong();
			r = sc.nextInt();

			for (int i = 0; i < r; i++) {
				route.add(sc.nextInt() - 1);
			}

			map = new int[n][n];
			for (int i = 0; i < m; i++) {
				int a = sc.nextInt() - 1;
				int b = sc.nextInt() - 1;
				map[a][b] = map[b][a] = sc.nextInt();
			}

			// 各最短ルート作成
			dis = new int[n][n];
			for (int i = 0; i < r; i++) {
				dijkstra(route.get(i), dis[route.get(i)]);
			}

			System.out.println(calc(new ArrayList<Integer>(), (ArrayList<Integer>)route.clone(), Long.MAX_VALUE));

		}
	}

	static long calc(ArrayList<Integer> a, ArrayList<Integer> b, long result) {
		if (b.size() == 0) {
			long tmp = 0;
			for (int i = 0; i < a.size() - 1; i++) {
				tmp += dis[a.get(i)][a.get(i + 1)];
			}
			if (tmp < result) {
				return tmp;
			} else {
				return result;
			}
		} else {
			for (int i = 0; i < b.size(); i++) {
				ArrayList<Integer> newA = (ArrayList<Integer>)a.clone();
				ArrayList<Integer> newB = (ArrayList<Integer>)b.clone();
				newA.add(b.get(i));
				newB.remove(i);
				long tmp = calc(newA, newB, result);
				if (tmp < result) {
					result = tmp;
				}
			}

		}

		return result;
	}

	public static void dijkstra(int src, int[] distance) {
		int nTown = distance.length;
		boolean[] fixed = new boolean[nTown]; // 最短距離が確定したかどうか
		for (int i = 0; i < nTown; i++) { // 各都市について初期化する
			distance[i] = Integer.MAX_VALUE; // 最短距離の初期値は無限遠
			fixed[i] = false; // 最短距離はまだ確定していない
		}
		distance[src] = 0; // 出発地点までの距離を0とする
		while (true) {
			// 未確定の中で最も近い都市を求める
			int marked = minIndex(distance, fixed);
			if (marked < 0)
				return; // 全都市が確定した場合
			if (distance[marked] == Integer.MAX_VALUE)
				return; // 非連結グラフ
			fixed[marked] = true; // その都市までの最短距離は確定となる
			for (int j = 0; j < nTown; j++) { // 隣の都市(i)について
				if (map[marked][j] > 0 && !fixed[j]) { // 未確定ならば
					// 旗の都市を経由した距離を求める
					int newDistance = distance[marked] + map[marked][j];
					// 今までの距離よりも小さければ、それを覚える
					if (newDistance < distance[j])
						distance[j] = newDistance;
				}
			}
		}
	}

	// まだ距離が確定していない都市の中で、もっとも近いものを探す
	static int minIndex(int[] distance, boolean[] fixed) {
		int idx = 0;
		for (; idx < fixed.length; idx++) // 未確定の都市をどれか一つ探す
			if (!fixed[idx])
				break;
		if (idx == fixed.length)
			return -1; // 未確定の都市が存在しなければ-1
		for (int i = idx + 1; i < fixed.length; i++) // 距離が小さいものを探す
			if (!fixed[i] && distance[i] < distance[idx])
				idx = i;
		return idx;
	}
}


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

int main() {
  int A, B;
  cin >> A >> B;

  if (A >= 13){
    cout << B << endl;
  }
  
  else if (A <= 5){
  cout << 0 << endl;
  }
  
  else {
  cout << B/2 << endl;
  }

}


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

int main()
{
    int k, a, b;
    bool can = false;
    cin >> k;
    cin >> a >> b;
    for (int i = 0; i <= b; i += k) {
        if (i >= a && i <= b) can = true;
    }
    cout << (can ? "OK" : "NG") << endl;
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
int main()
{
	//// 整数の入力
	//int a;
	//cin >> a;
	//// スペース区切りの整数の入力
	//int b, c;
	//cin >> b >> c;
	//// 文字列の入力
	//string s;
	//cin >> s;
	//// 出力
	//cout << (a + b + c) << " " << s << endl;


	// 1
	//int N;
	//cin >> N;
	//cout << (800 * N) - N / 15 * 200;

	//2
	/*int N;
	cin >> N;
	long long int p = 1;
	for (int i = 1; i <= N; i++)
	{
		p *= i;
		p %= 1000000007;
	}
	cout << p;
*/

	//3
	long long int N, M;
	cin >> N >> M;


	long long int n = std::min(N, M/2);
	long long int num = n + (M - 2 * n) / 4;
	cout << num;

	//cin >> n;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;

int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	ll n;
 	cin>>n;
 	ll a[n];
 	for(ll i=0;i<n;i++)
 	{
 		cin>>a[i];
 	}
 	unordered_map<ll,ll>mp;
 	ll ans=0;
 	for(ll i=0;i<n;i++)
 	{
 		ll val = i-a[i];
 		ans+=mp[val];	
 		mp[i+a[i]]++;
 	}
 	cout<<ans<<endl;
    return 0;
}

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

int main()
{
    string n;
    cin>>n;
    int i, count=0;

    for(i=0; i<4; i++)
    {
        if(n[i] == n[i+1])
        {
            count++;
            break;
        }
    }
    if(count ==0)
        cout<<"Good";
    else
        cout<<"Bad";
}


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


def solve(x: "List[int]", y: "List[int]"):
    dx = x[1] - x[0]
    dy = y[1] - y[0]

    x3 = x[1] - dy
    y3 = y[1] + dx
    x4 = x[0] - dy
    y4 = y[0] + dx

    print(x3,y3,x4,y4)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x = [int()] * (2)  # type: "List[int]" 
    y = [int()] * (2)  # type: "List[int]" 
    for i in range(2):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(x, y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	ans := 0
	for i := 1; i*i < n; i++ {
		if x := n % i; x == 0 {
			if y := (n / i) - 1; y > i {
				ans += y
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1788
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
# include <climits>
#define ll long long int
#define rep(i,rept) for (ll i = 0; i < rept; i++)
#define yes(b) std::cout<< (b ? "Yes" : "No")
#define YES(b) std::cout<< (b ? "YES" : "NO")
using namespace std;
/*int ketawa(ll num) {
	int dig, sum = 0;
	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}
*/
bool keta(ll num, vector<int> v) {
	int dig;
	while (num) {
		dig = num % 10;
		for (auto& i : v) {
			if (dig == i) {
				return false;
			}
		}
		num = num / 10;
	}
	return true;
}

ll func(ll a, ll b, ll c, ll d,int n) {
	return ((c / (d - b) + n)*(d - b)) + (a % (d - b));
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,k;
	vector<int> v;
	cin >> n>>m;
	for (int i = 0; i < m; ++i) {
		cin >> k;
		v.push_back(k);
	}
	while (true) {
		if (keta(n, v)) {
			break;
		}
		++n;
	}
	cout << n;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int A, B, H, M;
long double ans;
int main()
{
	cin >> A >> B >> H >> M;
	int t = abs(60 * H - 11 * M);
	if (t > 360)
	{
		t = 720 - t;
	}
	if (t == 360)
	{
		ans = A + B;
	}
	else if (t == 0)
	{
		ans = abs(A - B);
	}
	else
	{
		ans = sqrt(A * A + B * B - 2 * A * B * cos((long double)t / 2.0 * (acos(-1.0) / 180.0)));
	}
	printf("%.20Lf\n", ans);
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll n; cin >> n;
  ll r[2*n] = {}; rep(i,n) r[i] = 1;
  ll tsum = n-1;
  rep(i,n) {
    if (i==0) { r[i+n] = n; continue; }
    r[i+n] += (n-1)*(n-1) + r[i+n-1] + tsum; r[i+n] %= MOD;
    tsum += r[i+n-2] - r[i-1]; tsum = (tsum%MOD+MOD)%MOD;
  }
  // debug(r,r+2*n);
  ll result = r[2*n-1];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int l,r;
    scanf("%d%d",&l,&r);
    if(r-l+1>=2020)
        printf("0");
    else
    {
        int ans=2019;
        for(int i=l; i<=r; i++)
            for(int j=i+1; j<=r; j++)
                if(((i%2019)*(j%2019))%2019<ans)
                    ans=((i%2019)*(j%2019))%2019;
        printf("%d",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;

vector<long> ans;

bool solve( long n, const long* a, long offset )
{
    if(n<1) return true;

    long aa = a[0] - offset;
    if(aa<1 || aa>n) return false;

    ans.push_back(1);
    if (!solve( aa-1, &(a[1]), offset )) {
        return false;
    }
    ans.push_back(0);

    solve( n-aa, &(a[aa]), offset+aa );

    return true;
}

int main(int argc, char* argv[])
{
    long n;
    scanf("%ld", &n);

    vector<long> a(n);
    long i;
    for(i=0; i<n; i++) {
        long tmp;
        scanf("%ld", &tmp);
        a[tmp-1] = i+1;
    }

    if( solve( n, &(a[0]), 0 ) ) {    
        for(i=0; i<(long)ans.size(); i++) {
            if(ans[i]) printf("(");
            else       printf(")");
        }
        printf("\n");
    }
    else {
        printf(":(\n");
    }

    return 0;
}




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

int a[200010];

signed main()
{
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int sum=0ll,maxv=0ll;
	for(int i=1;i<k;i++) sum+=a[i];
	for(int i=k;i<=n;i++){
		sum+=a[i];
		sum-=a[i-k];
		if(sum>maxv) maxv=sum;
	}
	double ans=(double)(maxv+k)*1.0/2;
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 100009 /// I wanna be the wind
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define per(i, b, a) for(ll i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
using namespace std;
const ll INF = 1e17 + 9;
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll fastpow(ll a, ll b){
    ll calc=1;
    for(;b>=1LL;b/=2LL){
        if((b&1LL))calc=mult(calc,a);
        a=mult(a,a);
    }
    return calc;
}
ll soma(ll a,ll b){
    if(a+b>MOD)return a+b-MOD;
    else return a+b;
}
ll subt(ll a,ll b){
    if(a-b<0)return a-b+MOD;
    else return a-b;
}
vector<int> adj[maxn];
pii dfs(int v, int p){
    ll allwhite = 1;
    ll stblack = 0;
    for(auto e: adj[v]){
        if(e==p){
            continue;
        }
        pii res = dfs(e,v);
        ll antwhite = allwhite;
        allwhite = mult(allwhite,res.second);
        stblack = soma(mult(stblack, soma(res.first, res.second)), mult(antwhite, res.first));
    }
    return {allwhite,soma(allwhite, stblack)};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    ll m = n-1;
    while(m--){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    pii ans = dfs(1,-1);
    ll ansf = soma(ans.F,ans.S);
    cout<<ansf<<"\n";
    return 0;  
}

Measured memory_bytes: 16000
#include <stdio.h>
 
int main(){
    int i, j, k, x[10], tmp;
 
    for(i = 0; i < 10; i++) scanf("%d", &x[i]);
 
    for(i = 0; i < 10; i++)
        for(j = 9; j > i; j--)
            if(x[j - 1] < x[j]){
                tmp  = x[j];
                x[j] = x[j - 1];
                x[j - 1] = tmp;
            }
 
    for(i = 0, k = 0; i < 10 && k < 3; i++, k++)
        printf("%d\n", x[i]);
 
    return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int M,K;
  cin>>M>>K;

  int N=pow(2,M+1);
  if(K==0){
      for(int i=0;i<N/2;i++) cout<<i<<" "<<i<<" ";
      cout<<endl;
      return 0;
  }

  if(N/2<=K||M<=1){
      cout<<-1<<endl;
      return 0;
  }

  vector<int> v;
  vector<bool> used(N/2,0);
  used[K]=1;
  for(int i=1;i<N/2;i++){
      if(used[i]) continue;

      v.push_back(i);
      v.push_back(K^i);
      used[i]=1;
      used[K^i]=1;
  }
  
  cout<<0<<" ";
  for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
  cout<<0<<" ";
  cout<<K<<" ";
  for(int i=v.size()-1;i>=0;i--) cout<<v[i]<<" ";
  cout<<K<<endl;




  return 0;
}


Measured memory_bytes: 2428
from math import factorial
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
a.sort()
x=(factorial(n-1)*pow(factorial(k-1),mod-2,mod)*pow(factorial(n-k),mod-2,mod))%mod
y=1
for i in range(n-k+1):
  ans-=a[i]*x
  ans%=mod
  x=(x*(n-k-i)*pow(n-i-1,mod-2,mod))%mod
for i in range(k-1,n):
  ans+=a[i]*y
  ans%=mod
  y=(y*(i+1)*pow(i-k+2,mod-2,mod))%mod
print(ans)

Measured memory_bytes: 64420
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int INF = 1001001001;
int main(){
  int N,M;
  cin>>N>>M;
  vector<int>a(N);
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>a.at(i);
    sum+=a.at(i);
  }

   sort(a.begin(),a.end());
   reverse(a.begin(),a.end());
 
  for(int i=0;i<M;i++){
  if(4*M*a[i]<sum){cout<<"No"<<endl;return 0;}
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int st,e;
    string s;
    cin>>s;
    int l=s.length();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='A')
        {
            st=i+1;
            break;
        }
    }
    for(int i=0;i<l;i++)
    {
        if(s[i]=='Z')
        {
            e=i+1;
        }
    }
    cout<<e-st+1<<endl;
    return 0;
}


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

int n, m;
const int N = 5e4 + 10;
string s[2][N];
int bs1(string w, int r){
  int ok = n-1, ng = -1;
  while(ok - ng > 1) {
    int mid = (ok + ng) >> 1;
    if(s[r][mid] >= w) ok = mid;
    else ng = mid;
  }
  return ok;
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> m;
  set<string> st[2];
  for(int i = 0; i < n; i++ ){
    cin >> s[0][i];
    s[1][i] = s[0][i];
    reverse(begin(s[1][i]), end(s[1][i]));
    st[0].insert(s[0][i]);
    st[1].insert(s[1][i]);
  }
  sort(s[0], s[0] + n);
  sort(s[1], s[1] + n);
  const char C = 'z' + 1;
  s[0][n] = C;
  s[1][n] = C;
  n++;
  // for(int i = 0; i < n; i++) cout << i << "  ] " << s[1][i] << endl;
  for(int i = 0; i < m; i++) {
    string w;
    cin >> w;
    int ans = 0;
    int r = 0;
    if(w.front() == '*') {
      reverse(begin(w), end(w));
      r = 1;
    }
    int u = w.back() == '*';
    if(u) w.pop_back();
    int g = w.find('?');
    // cout << "a" << ("cat" >= "cat") << endl;
    // cout << bs1(w + C, r) << "- " <<  bs1(w, r) << endl;;
    if(g == -1) {
      if(u) {
        ans += bs1(w + C, r) - bs1(w, r);
      } else ans += st[r].count(w);
    }
    else for(int i = 0; i < 26; i++) {
      w[g] = 'a' + i;
      if(u) {
        ans += bs1(w + C, r) - bs1(w, r);
      } else ans += st[r].count(w);
    }
    cout << ans << endl;
  }
  return 0;
}




Measured memory_bytes: 18912
# coding=utf-8
from __future__ import division
from  math import sqrt


def main():
    n = input()
    while n:
        scores = map(int, raw_input().split())
        m = sum(scores) / n
        print sqrt(sum([(x - m) ** 2 for x in scores]) / n)
        n = input()


if __name__ == '__main__':
    main()

Measured memory_bytes: 4476
#include <iostream>
#include <vector>
using namespace std;
long n,m;
vector <long> F[100005];
bool Free[100005];
long G[100005];
long DFS(long u)
    {
        long i,v;
        if (G[u]!=0) return G[u];
        for (i=0;i<F[u].size();++i)
        {
            v=F[u][i];
            if (Free[v]==true)
            {
                Free[v]=false;
                G[u]=max(G[u],DFS(v)+1);
            }
            Free[v]=true;
        }
        return G[u];
    }
int main()
    {
        long i,t1,t2;
        cin>>n>>m;
        for (i=1;i<=m;++i)
        {
            cin>>t1>>t2;
            F[t1].push_back(t2);
        }
        for (i=1;i<=n;++i) F[0].push_back(i);
        fill(Free+1,Free+1+n,true);
        cout<<DFS(0)-1;
        return 0;
    }


Measured memory_bytes: 12116
n, m = map(int, input().split())
x = list(map(int, input().split()))

if n >= m:
    print(0)
    exit()

x.sort()
d = [0] * (m - 1)

for i in range(m - 1):
    d[i] = x[i + 1] - x[i]

d.sort()
print(sum(d[0:m - n]))

Measured memory_bytes: 52904
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int a[1000005];
int main()
{
    double x;
    while(cin >> x)
    {
        if(x<=48.00) cout << "light fly" << endl;
        else if(x<=51.00) cout << "fly" << endl;
        else if(x<=54.00) cout << "bantam" << endl;
        else if(x<=57.00) cout << "feather" << endl;
        else if(x<=60.00) cout << "light" << endl;
        else if(x<=64.00) cout << "light welter" << endl;
        else if(x<=69.00) cout << "welter" << endl;
        else if(x<=75.00) cout << "light middle" << endl;
        else if(x<=81.00) cout << "middle" << endl;
        else if(x<=91.00) cout << "light heavy" << endl;
        else  cout << "heavy" << endl;
    }
    return 0;
}



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

using namespace std;

int main(){
	int a, b;
	string s;
	
	cin >> a >> b;
	cin >> s;
	
	for(int i=0; i < s.size(); i++){
		if(s[i] == '-' && i!=a){
			cout << "No";
			return 0;
		}
		if(s[a] != '-'){
			cout << "No";
			return 0;
		}
	}
	
	cout << "Yes";
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t[]={"dreamer","dream","eraser","erase"};
  bool ans=1;
  cin>>s;
  for(int i=0;i<s.size();i++){
    bool f=0;
    for(int j=0;j<4;j++)
      if(!f)
	for(int k=0;k<t[j].size()&&i+k<s.size();k++){
	  if(t[j][k]!=s[i+k])break;
	  if(k==t[j].size()-1){
	    if(j==0&&i+k+1<s.size()&&s[i+k+1]=='a')break;
	    f=1,i+=k;

	  }
	}
    if(!f){ans=0;break;}
  }

  if(ans)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}


Measured memory_bytes: 512
//Author: AnandRaj doubleux
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define all(v) v.begin(),v.end()
#define prinp(p) cout<<p.first<<" "<<p.second<<endl
#define prinv(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int in=f;in<f+n;in++) cin>>V[in]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7,MAX = 1e6+5;
const ll INF = 1e18+5;

int main()
{
	int s;
	cin>>s;
	vi dp(s+1);
	dp[3]=1;
	for(int i=4;i<=s;i++)
	{
		dp[i]=1;
		for(int j=3;j<=i;j++)
		{
			dp[i] += dp[i-j];
			dp[i]%=MOD;
		}
	}
	cout<<dp[s]<<endl;
}

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

using namespace std;

int dp[(int)1e5+10][3];
string t;
int k, r, s, p;

int solve(int n, int c){
    if(n < 0) return 0;
    if(dp[n][c] != -1) return dp[n][c];

    int sol = 0;

    if(t[n] == 'r'){
        if(c == 1)
            sol = max(solve(n-k, 0), solve(n-k, 2));
        if(c == 0)
            sol = max(solve(n-k, 1), solve(n-k, 2));
        if(c == 2)
            sol = max(solve(n-k, 1), solve(n-k, 0)) + p;
    }
    else if(t[n] == 's'){
        if(c == 1)
            sol = max(solve(n-k, 0), solve(n-k, 2)) + r;
        if(c == 0)
            sol = max(solve(n-k, 1), solve(n-k, 2));
        if(c == 2)
            sol = max(solve(n-k, 1), solve(n-k, 0));
    }
    else{
        if(c == 1)
            sol = max(solve(n-k, 0), solve(n-k, 2));
        if(c == 0)
            sol = max(solve(n-k, 1), solve(n-k, 2)) + s;
        if(c == 2)
            sol = max(solve(n-k, 1), solve(n-k, 0));
    }
    
    return dp[n][c] = sol;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;

    cin >> n >> k >> r >> s >> p >> t;

    memset(dp, -1, sizeof(dp));

    int sol = 0;
    for(int i=0;i<k;++i){
        int t1 = solve(n-1-i, 0);
        int t2 = solve(n-1-i, 1);
        int t3 = solve(n-1-i, 2);
        sol += max(t1, max(t2, t3));
    }

    cout << sol << '\n';

    return 0;
}

Measured memory_bytes: 6252
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
print(N * 800 - 200 * (N // 15))


Measured memory_bytes: 27172
#include <iostream>
#include <math.h>
#define MAX 80000
using namespace std;

int main(){
	static int n;
	static int prime[MAX],i,j;
	static int count;
	static bool flag;

	while((cin >> n)!= NULL){
		count = 0;
		for(i = 3; i <= n; i+=2){
			flag = true;
			for(j = 0; j < count; j++){
				if(i % prime[j] == 0){
					flag = false;
					break;
				}
				if(prime[j] * prime[j] > i) break;
			}
			if(flag == true){
				prime[count++] = i;
			//	cout << count << endl;
			}
		}
		if(n > 1)	count++; //2
		cout << count << endl;
		//delete[] prime;
	}
	return 0;
}

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

bool isPrime(int n){
	if( n < 2 )return false;

	for(int i=2;i*i<=n;i++)
		if( n%i== 0 )
			return false;

	return true;
}

int main(){
  while(1){
  int n,count=0,s;
  cin >> n;
  if(n==0) break;
  for(int i=n+1; i<=2*n; i++){
	s=0;
/*
	for(int j=1; j<=2*n; j++){
          if(i%j==0){
	    s++;
 	  }
	  if(i<j) break;
	}
	if(s==2) count++;
*/
	if( isPrime( i ) ) count++;
	//cout << a[i][j];
  }
  //cout << s << endl;
  //cout << endl;
  cout << count << endl;
  }
 return 0;
}



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

int main() {
  int N, M=0;
  cin >> N;
  vector<int> V(N);
  for (int i=0; i<N; i++) {
    cin >> V[i];
  }
  
  int C=0;
  for (int i=0; i<N; i++) {
    if (M<=V[i]) {
      C++;
      M=V[i];
    }
  }
  cout << C << endl;
  
}


Measured memory_bytes: 3652
# -*- coding:utf-8 -*-
from collections import deque
"""解説
全探索

左からL個、右からR個宝石を取り、K-(L+R)個の宝石を筒に詰めるとき方針として、

・筒に詰める宝石は絶対値の大きい負の値のもの

あとは全探索
"""

def solve():
    N, K = list(map(int, input().split()))
    V = list(map(int, input().split()))

    ans = 0
    r = min(N, K)
    for a in range(r+1):  # 左から取る個数
        for b in range(r+1):  # 右から取る個数
            if r < a+b: continue

            t = V[:a] + V[::-1][:b]  # 左からa個、右からb個とった宝石を「持っているリストt」にぶちこむ
            t.sort(reverse=True)

            for _ in range(K-a-b):
                if len(t) > 0 and t[-1] < 0:
                    t.pop()
                    continue
                break
            ans = max(ans, sum(t))

    print(ans)



if __name__ == "__main__":
    solve()


Measured memory_bytes: 3316
#include <iostream>
#include <tuple>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main() {
  int n;
  cin >> n;
  tuple<string, int, int> a[n];
  rep(i,n) {
    string s;
    int p;
    cin >> s >> p;
    a[i] = tuple<string, int, int>(s, -p, i + 1);
  }
  sort(a, a + n);
  rep(i,n) cout << get<2>(a[i]) << endl;
  return 0;
}

Measured memory_bytes: 256
import math

a,b,x = map(int,input().split())

if a**2*b == x:
    print(0)
elif a**2 * b < 2*x:
    print(90-math.degrees(math.atan((1/2*a**3)/(a**2*b-x))))
else:
    print(math.degrees(math.atan((1/2*a*b**2)/(x))))

Measured memory_bytes: 3060
// Aizu 1140: Cleaning Robot
// 2017.9.14 bal4u@uu

#include <stdio.h>
#include <string.h>

typedef struct { int r, c, d; } Q;
Q que[1003]; int top, end;

typedef struct { int r, c; } PP;
PP pp[12]; int n;
char map[22][22], mk[22][22]; int w, h;
int dist[12][12];
int m[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} }; 
char f[12];
int ans;

int distance()
{
	int i, j, k, d, r, c, r2, c2;

	for (i = 0; i < n; i++) for (j = i+1; j < n; j++) {
		memset(mk, 0, sizeof(mk));
		que[0].r = pp[i].r, que[0].c = pp[i].c, que[0].d = 0, top = 0, end = 1;
		while (1) {
			if (top >= end) return 0;
			r = que[top].r, c = que[top].c, d = que[top++].d;
			if (r == pp[j].r && c == pp[j].c) {	dist[i][j] = dist[j][i] = d; break; }
			for (k = 0; k < 4; k++) {
				r2 = r + m[k][0], c2 = c + m[k][1];
				if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w || map[r2][c2] == 'x') continue;
				if (mk[r2][c2]) continue;
				mk[r2][c2] = 1;
				que[end].r = r2, que[end].c = c2, que[end++].d = d+1;
			}
		}
	}
	return 1;
}

void combi(int k, int a, int w)
{
	int b;

	if (k == n) { if (w < ans) ans = w; return; }
	for (b = 1; b < n; b++) {
		if (f[b]) continue;
		if (w + dist[a][b] < ans) f[b] = 1, combi(k+1, b, w+dist[a][b]), f[b] = 0;
	}
}

int main()
{
	int i, r, c;

	while(scanf("%d%d", &w, &h) && w) {
		for (n = 1, r = 0; r < h; r++) {
			scanf("%s", map[r]);
			for (c = 0; c < w; c++) {
				if      (map[r][c] == 'o') pp[0].r = r, pp[0].c = c;
				else if (map[r][c] == '*') pp[n].r = r, pp[n++].c = c;
			}
		}
		if (n <= 1) { puts("0"); continue; }
		if (!distance()) { puts("-1"); continue; }
		memset(f, 0, sizeof(f)), ans = 1000;
		for (i = 1; i < n; i++) f[i] = 1, combi(2, i, dist[0][i]), f[i] = 0;
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1720
#include "bits/stdc++.h"
#define _USE_MATH_DEFINES
#include <math.h>
 
using namespace std;
 
using LL = long long;
using VLL = std::vector<LL>;
using VVLL = std::vector<VLL>;
using VVVLL = std::vector<VVLL>;
using LD = long double;
using VLD = std::vector<LD>;
using VVLD = std::vector<VLD>;
using VVVLD = std::vector<VVLD>;
 
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }

#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) {LL i=0; for(auto (a): v ){   cerr <<i << " : "<<  a << endl; i++;}}
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl
#define cmax(a,b) {if(a<b){a=b;}}
#define cmin(a,b) {if(a>b){a=b;}}
//#define cmax(a,b) a = (a>b ? a:b)
//#define cmin(a,b) a = (a<b ? a:b) 

void func() {
  LL D,G;
  cin >>D>>G;
  VLL P(D);
  VLL C(D);
  REP(i,D){
    cin >> P[i];
    cin >> C[i];
  }  

  LL num_min = 1e9;
  LL N = D;
  for (LL bit = 0; bit < (1 << N); ++bit) {
    //cout << std::bitset<10>(bit)<<endl;
    LL score = 0;
    LL num   = 0;
    for (LL i = 0; i < N; ++i) {
      if (bit & (1 << i)) {
        score += (i+1)*100*P[i]+C[i];
        num += P[i];
      }
      else{

      }
    }
    if(score>=G){
      chmin(num_min,num);
      continue;
    }

    for (LL i = N-1; i >=0 ; --i) {
      if (bit & (1 << i)) {
      }
      else{
        LL sabun = G-score;
        LL nokori = min((LL)(sabun/((i+1)*100)),P[i]);
        for(LL j=1;j<=P[i];++j){
          score += (i+1)*100;
          num += 1;
          if(score>=G){
            chmin(num_min,num);
            break;
          }
        }
        break;
      }
    }
    //cerr << num << " " << score << endl;
    if(score>=G){
      chmin(num_min,num);
    }

  }
  cout << num_min;
  return;
}

 
int main()
{
  func();
  return 0;
}
 

Measured memory_bytes: 256
//Catchharsh
    #include<bits/stdc++.h>
    #define ll long long int 
    #define ld long double
    #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    #define F first
    #define S second
    #define pb push_back
    #define endl '\n'
    #define see(x) cout<<#x<<" = "<<x<<endl
    const ll MOD = 1e9+7;
    const ll INF = 1011111111;
    const ll LLINF = 1000111000111000111LL;
    const ld EPS = 1e-10;
    const ld PI = 3.14159265358979323;
    using namespace std;
    ll power (ll x,ll n)
    {
        if(n==0)
        return 1;
        else if(n%2==0)
        return power((x*x),n/2);
        else
        return x*power((x*x),(n-1)/2); 
    }
    vector<ll> g[100005];
    ll deg[100005];
    ll nc[100005];
    map<pair<ll,ll>,ll> edge;
    vector<pair<ll,ll>> v;
    bool visit[100005];
    void dfs(ll node,ll col)
    {
       visit[node]=true;
       ll st=1;
       for(auto to:g[node])
       {
          if(!visit[to])
          {
             if(st==col) st++;
             nc[to]=st;
             edge[{node,to}]=st;
             edge[{to,node}]=st;
             st++;
          }
       }
       for(auto to:g[node])
       {
          if(!visit[to])
          {
             dfs(to,nc[to]);
          }
       }
    }

    int main()
    {   
         IOS;
         ll n,m,i,j,k;
         cin>>n;
         for(i=0;i<n-1;i++)
         {
           ll uu,vv;
           cin>>uu>>vv;
           v.pb({uu,vv});
           g[uu].pb(vv);
           g[vv].pb(uu);
           deg[uu]++;
           deg[vv]++;
         }
         ll ans=-1;
         for(i=1;i<=n;i++)
         {
           if(deg[i]>ans)
           {ans=max(ans,deg[i]);k=i;}
         }
         cout<<ans<<endl;
         dfs(1,0);
         for(i=0;i<n-1;i++)
         {
           int uu,vv;
           uu=v[i].F;
           vv=v[i].S;
           cout<<edge[{uu,vv}]<<endl;
         }
         

         cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';             
    }

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

int N, M;
vector<vector<bool>> G(8, vector<bool>(8));
vector<bool> seen(N, false);
int Vis = 0;
int ans = 0;

void dfs(int now){
    seen[now] = true;
    Vis++;
    if(Vis == N){
        ans++;
        Vis--;
        seen[now] = false;
        return;
    }
    
    
    for(int next = 0; next < 8; next++){
        if(!seen[next] && G[now][next])dfs(next);
    }
    
    seen[now] = false;
    Vis--;
    return;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a][b] = true;
        G[b][a] = true;
    }
    dfs(0);
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define F first
#define S second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;

const db eps = (db)1e-9;
const db pi = acos(-1.0);

const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int N = 100500;

int n, a[N];
ll dp[N][3];

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

	//srand(time(NULL));

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;
	
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i][0] = dp[i][1] = dp[i][2] = -inf;
	}

	dp[1][0] = a[1] / 2;
	if (a[1]) dp[1][1] = (a[1] - 1) / 2;
	if (a[1] >= 2) dp[1][2] = (a[1] - 2) / 2;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 2; j++) {
			for (int k = 0; k <= 2; k++) {
				for (int x = 0; x <= 2; x++) {
					if (k + x <= a[i] && !((a[i] - k - x) & 1))
						dp[i][k] = max(dp[i][k], dp[i - 1][j] + (a[i] - k - x) / 2 + min(j, x));
				}
			}
		}
	}

	cout << max({dp[n][0], dp[n][1], dp[n][2]});
	
	//cerr << (clock() + 0.0) / CLOCKS_PER_SEC;

	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;

LL k, a, b;

void solve() {
    if (k + 1 < a) {
        cout << k + 1 << endl;
    } else {
        LL ans = a;
        k -= a - 1;
        if (k & 1) {
            --k;
            ++ans;
        }
        cout << max(ans + k, ans + (b - a) * k / 2) << endl;
    }
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN

    while (cin >> k >> a >> b) {
        solve();
    }
    return 0;
}

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

class Main {
	
	public static void main(String[] args) {
        FastScanner in = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt(), x = in.nextInt(), t = in.nextInt();
        long ans = 0;
        int y = n/x;
        if(n%x!=0) y++;
        ans = y*t;
        out.println(ans);
        
        out.flush();
	}
	
	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		
		String next() {
			while(!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				}catch(IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int[] readArray(int n) {
			int a[] = new int[n];
			for(int i=0;i<n;i++) a[i] = nextInt();
			return a;
		}
		
		long[] readArray(int n,long x) {
			long a[] = new long[n];
			for(int i=0;i<n;i++) a[i] = nextLong();
			return a;
		}
		
	}
}











Measured memory_bytes: 25388