akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>

#define for0(i, N)    for (int i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (int i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (int i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (int i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (int i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (int i = (x), a = 0; a < (N);  \
                              i = (i + 1) % (N), ++a)

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;


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



    vll p(n + 1);
    vll m(n + 1);

    m[0] = 1e6;

    for1n(i, n){
        cin >> p[i];
        m[i] = min(m[i - 1], p[i]);
    }

    int result = 0;

    for1n(i, n){
        if (p[i] < m[i - 1]) {
            // cout << i << ";\n";
            ++result;
        }
    }

    cout << result;


    return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>

#define DICE  6
#define MAX 100

typedef struct Dice {
  int num[DICE];
}Dice;

int main(void) {
  int i, j = 0;
  int tmp;
  char op[MAX];
  Dice dice;

  for(i=0; i<DICE; ++i) {
    scanf("%d", &dice.num[i]);
  }

  scanf("%s", op);

  while(op[j] != '\0') {

    switch(op[j++]) {
      case 'S' : {
        tmp = dice.num[0];
        dice.num[0] = dice.num[4];
        dice.num[4] = dice.num[5];
        dice.num[5] = dice.num[1];
        dice.num[1] = tmp;
        break;
      }
      case 'W' : {
        tmp = dice.num[0];
        dice.num[0] = dice.num[2];
        dice.num[2] = dice.num[5];
        dice.num[5] = dice.num[3];
        dice.num[3] = tmp;
        break;
      }
      case 'N' : {
        tmp = dice.num[0];
        dice.num[0] = dice.num[1];
        dice.num[1] = dice.num[5];
        dice.num[5] = dice.num[4];
        dice.num[4] = tmp;
        break;
      }
      case 'E' : {
        tmp = dice.num[0];
        dice.num[0] = dice.num[3];
        dice.num[3] = dice.num[5];
        dice.num[5] = dice.num[2];
        dice.num[2] = tmp;
        break;
      }
    }
  }

  printf("%d\n", dice.num[0]);

  return 0;
}



Measured memory_bytes: 2128
from collections import defaultdict
from itertools import accumulate
 
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
cnt=list(accumulate(A))
 
ans=0

res=defaultdict(int)
for a in cnt:
  res[a%M] += 1
for a,b in res.items():
  ans += b*(b-1)//2

ans+= res[0]

print(ans)

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	int sum = 0;
	rep(i, n) sum += a[i];
	int cnt = 0;
	rep(i, n) {
		if (a[i] * 4 * m >= sum) cnt++;
	}
	puts(cnt >= m ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>


int main()
{
    int a,b;
    std::cin >> a >> b;
    if (a>b){
        std::cout << "a" << " > " << "b" << std::endl;
    }else if (a<b){
        std::cout << "a" << " < " << "b" << std::endl;
    }else{
        std::cout << "a" << " == " << "b" << std::endl;
    }
    return 0;
}

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

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

    if(a+b+c >= 22){
    	cout<<"bust"<<endl;
    }else{
    	cout<<"win"<<endl;
    }	
 
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
typedef long long ll;
using namespace std;
int n,d,a[200009],max1,max2;
int main()
{
  scanf("%d",&n);
  max1=0;max2=0;
  for (int i=1;i<=n;i++) 
  {
   scanf("%d",&a[i]);
   if (a[i]>=max1) max2=max1,max1=a[i];
   else if (a[i]>=max2) max2=a[i];
  }
  for (int i=1;i<=n;i++)
  if (a[i]==max1) printf("%d\n",max2);
  else printf("%d\n",max1);
  return 0;
} 

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define rep1(i, n) for(ll i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  ll n,m,k;
  cin >> n >> m >> k;
  vector<ll> a(n+1);
  rep1(i,n){
    if(i == 1) cin >> a[i];
    else{
      cin >> a[i];
      a[i] += a[i-1];
    }
  }
  vector<ll> b(m+1);
  rep1(i,m){
    if(i == 1) cin >> b[i];
    else{
      cin >> b[i];
      b[i] += b[i-1];
    }
  }
  ll ans = 0;
  rep(i,n+1){//aのサーチ
    ll target = k - a[i];
    //cout << i << " " << target << " ";
    //for(auto p : b) cout << p << ",";
    ll b_num = upper_bound(all(b),target) - begin(b) - 1;
    ll tmp = i + b_num;
    ll val = a[i] + *(upper_bound(all(b),target) - 1);
    //cout << " " << tmp << " " << val;
    //cout << endl;
    if(val <= k) ans = max(ans,tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 6404
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		var s = new int[h[1]].Select(_ => Console.ReadLine().Split()).ToArray();

		var qs = s.GroupBy(x => x[0], x => x[1]).Where(g => g.Contains("AC")).Select(g => g.TakeWhile(x => x == "WA").Count()).ToArray();
		Console.WriteLine($"{qs.Length} {qs.Sum()}");
	}
}


Measured memory_bytes: 42772
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  int a,b,h,m;
  cin >> a >> b >> h >> m;
  double d;
  d=abs(5.5*m-30.0*h);
  if(d>180) d=360-d;
  double ans=sqrt(1.0*a*a+1.0*b*b-2.0*a*b*cos(d*M_PI/180));
  cout << fixed << setprecision(11) << ans << endl;
  return 0;
}


Measured memory_bytes: 4036
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 2147483647;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 2000005;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[SIZE], finv[SIZE], inv[SIZE];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;
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; }

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

double len(int a, int b, int c, int d) {
	return (double)sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

long long  gcd(long long  a, long long  b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

long long lcm(long long a, long long b) {
	long long  g = gcd(a, b);
	return a / g * b;
}

int main() {
	int a, b;
	cin >> a >> b;
	if (a != 1 && b != 1) { cout << 1 << endl; }
	else if (a != 2 && b != 2) { cout << 2 << endl; }
	else { cout << 3 << endl; }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int[] l = new int[n];

		for (int i = 0; i < n; i++) {
			l[i] = sc.nextInt();
		}

		int minmp = Integer.MAX_VALUE;
		int count = 0;

		int[] order = new int[n + 1];
		order[0] = 1;

		for (int i = 0; i < n; i++) {
			order[i + 1] = order[i] * 4;
		}

		while (count < Math.pow(4, n)) {
			int a = 0;
			int b = 0;
			int c = 0;
			int mp = 0;
			for (int i = 0; i < n; i++) {
				int mod = (count % order[i + 1]) / order[i];

				switch (mod) {
				case 0: {
					if (a != 0) {
						mp += 10;
					}
					a += l[i];
					break;
				}
				case 1: {
					if (b != 0) {
						mp += 10;
					}
					b += l[i];
					break;
				}
				case 2: {
					if (c != 0) {
						mp += 10;
					}
					c += l[i];
					break;
				}
				case 3: {
					break;
				}
				}
			}
			//			System.out.println("count:" + count + ", a:" + a + ", b:" + b + ", c:" + c);
			count++;
			if (a == 0 || b == 0 || c == 0) {
				continue;
			} else {
				mp += Math.abs(A - a) + Math.abs(B - b) + Math.abs(C - c);
				//				System.out.println("mp:" + mp + ", A-a:" + Math.abs(A - a) + ", B-b:" + Math.abs(B - b) + ", C-c:"
				//						+ Math.abs(C - c));
				//				System.out.println();
				if (mp < minmp) {
					minmp = mp;
				}
			}
		}

		System.out.println(minmp);
		sc.close();
	}
}

Measured memory_bytes: 22356
#include <algorithm>
#include <iostream>
using namespace std;
int       a[200005], t[200005];
long long ans = 0;
void      merge(int l, int r) {
    if (l == r) return;
    int m = (l + r) / 2;
    merge(l, m);
    merge(m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m || j <= r) {
        if (j > r || (i <= m && a[i] < a[j]))
            t[k++] = a[i++];
        else {
            t[k++] = a[j++];
            ans += m - i + 1;
        }
    }
    for (int i = l; i <= r; i++) a[i] = t[i];
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    merge(1, n);
    printf("%lld\n", ans);
    return 0;
}



Measured memory_bytes: 4736
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);++i)
#define rrep(i,n) for(int (i)=(n)-1;(i)>=0;--i)
#define rep1(i,n) for(int (i)=1;(i)<=(n);++i)
#define rrep1(i,n) for(int (i)=(n);(i)>=1;--i)
#define pb push_back
#define fr first
#define sc second
typedef long long ll;
typedef pair<int,int> P;
typedef pair<long long,long long> LP;
typedef double db;
using namespace std;

ll N,K;

int main()
{
  cin>>N>>K;
  ll ans = (N/K)*(N/K)*(N/K);
  rep1(i,K-1){
    if((i*2)%K == 0){
      ll x = (N + (K-i) )/K;
      ans += x*x*x;
    }
  }
  cout<<ans<<endl;
}


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

using namespace std;
typedef long long ll;
ll ans = -1e10;
int N;
int a[10];
int F[100][10];
ll P[100][11];

void dfs(int i) {
  if (i == 10) {
    ll score = 0;
    int sums = 0;
    for (int j = 0; j < N; ++j) {
      int sum = 0;
      for (int k = 0; k < 10; ++k) {
	if (F[j][k] == 1 && a[k] == 1) {
	  sum++;
	  sums++;
	}
      }
      score += P[j][sum];
    }

    if (sums > 0) {
      ans = max(ans, score);
    }
    return;
  }
  a[i] = 0;
  dfs(i + 1);
  a[i] = 1;
  dfs(i + 1);
}

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 10; ++j) {
      cin >> F[i][j];
    }
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= 10; ++j) {
      cin >> P[i][j];
    }
  }
  dfs(0);
  cout << ans << endl;
  return 0;
}



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

int main() {

	int n,k;
	cin >> n >> k;
	int a[n];
	for(int i=0; i<n; i++) cin >> a[i];
	sort(a,a+n);long long sum=0;
	for(int i=0; i<k; i++)
    {
       sum+=a[i];
    }
    cout << sum << endl;
}



Measured memory_bytes: 3628
n = int(input())
a = list(map(int, input().split()))
i = 0
Alice = []
Bob = []
while i < n:
    if a == []:
        break
    else:
        Alice.append(max(a))
        a.remove(max(a))
    if a == []:
        break
    else:
        Bob.append(max(a))
        a.remove(max(a))
    i += 1
print(abs(sum(Alice) - sum(Bob)))

Measured memory_bytes: 3064
import java.io.*;

/**
 * Created by Ayushi on 07/07/2019.
 */

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = r.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int d = Integer.parseInt(temp[1]);
        int[][] p = new int[n][d];
        for (int i = 0; i < n; i++) {
            temp = r.readLine().split(" ");
            for (int j = 0; j < d; j++) {
                p[i][j] = Integer.parseInt(temp[j]);
            }
        }
        r.close();

        double x, y, z;
        int ans = 0;
        for (int k = 0; k < n; k++) {
            for (int l = k+1; l < n; l++) {
                y = 0;
                for (int m = 0; m < d; m++) {
                    x = p[k][m] - p[l][m];
                    y += x*x;
                }
                z = Math.sqrt(y);
                if (z % 1 == 0) ans++;
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 21460
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        x: i64,
    }
    match x % 10 {
        2 | 4 | 5 | 7 | 9 => println!("hon"),
        0 | 1 | 6 | 8 => println!("pon"),
        _ => println!("bon"),
    }
}


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

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100010 ;
const int MOD = 1000000007;
const int LOG = 20;

int n, h[N], par[N], act[N];
vi G[N];

void DFS(int v, int p = 0){
	for (auto u:G[v]){
		if (u == p) continue;
		h[u] = h[v] + 1;
		par[u] = v;
		act[v] ++;
		DFS(u, v);
	}
}


int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		G[v].pb(u);
		G[u].pb(v);
	}
	if (n == 2) return cout << "Second", 0;
	if (n % 2 == 1){
		cout << "First";
		return 0;
	}
	for (int i = 1; i <= n; i++){
		if (G[i].size() == 1){
			DFS(i);
			break;
		}
	}
	set<pii> st;
	for (int i = 1; i <= n; i++){
		st.insert({-h[i], i});
	}
	while (st.size()){
		int fr = st.begin()->S;
		int v = par[fr];
		if (act[v] > 1) return cout << "First", 0;
		act[par[v]] --;
		st.erase({-h[v], v});
		st.erase({-h[fr], fr});
	}
	cout << "Second";
	return 0;
}


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

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

string str[n];
int co[4]; // AC, WA, TLE, RE

for (int i = 0; i<4; i++){
	co[i] = 0;
}

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

for (int i = 0; i<n; i++){
	if (str[i] == "AC") {
		co[0] += 1;
	} else if (str[i] == "WA") {
		co[1] +=1 ;
	} else if (str[i] == "TLE") {
		co[2] +=1 ;
	} else {
		co[3] += 1;
	}
}
/*
	switch(str[i]) {
		case "AC":
		co[0] += 1;
		break;

		case "WA":
		co[1] += 1;
		break;

		case "TLE":
		co[2] += 1;
		break;

		case "RE":
		co[3] += 1;
		break;	
	}
	*/
	
	cout << "AC x " << co[0] << endl;
	cout << "WA x " << co[1] << endl;
	cout << "TLE x " << co[2] << endl;
	cout << "RE x " << co[3] << endl;
	
//cout << a << endl;
return 0;
}


Measured memory_bytes: 6748
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

int main()
{
    //変数の宣言
    int a[10];
    int i = 0;
    //入力
    while (scanf("%d", &a[i++]) + 1);
    //降順にsort
    for(int i=0;i<10;i++){
        for(int j=i+1;j<10;j++){
            int temp=0;
            if(a[i]<a[j]){
                //入れ替える(swap)
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    for(int i=0;i<3;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}



Measured memory_bytes: 3184
A,B,C,D,E,F = map(int,input().split())
waterset = set()
for i in range(F//(100*A)+1):
    for j in range(F//(100*B)+1):
        water = (A*i + B *j)*100
        if water < F:
            waterset.add(water)
waterset.remove(0)
sugarset = set()
for i in range(F//C + 1):
    for j in range(F//D + 1):
        sugar = C*i + D*j
        if sugar < F:
            sugarset.add(sugar)
best_conc = -1
best_a = -1
best_b = -1
for a in waterset:
    for b in sugarset:
        if a+b >F:
            continue
        if b > E*a/100:
            continue
        conc = 100*b/(a+b)
        if conc > best_conc:
            best_conc = conc
            best_a = a
            best_b = b
print(best_a+best_b,best_b)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(v)			((v).begin()), ((v).end())
#define SZ(v)			((int)((v).size()))
#define clr(v, d)		memset(v, d, sizeof(v))
#define has(c,i) 		((c).find(i) != end(c))
#define has_str(s, c)	((s).find(c) != string::npos)
typedef long long ll;

int main() {
#ifdef LOCAL
    //freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, w;
    cin >> n >> w;
    ll ans = 0, vt = 0;
    vector<pair<ll,ll>> val;
    for(int i = 0; i < n; ++i) {
        ll weight, value;
        cin >> weight >> value;
        vt += value;
        val.push_back({weight, value});
    }
    vector<ll> dp(vt+1, 1e9+9);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = vt - val[i].second; j >= 0; --j) {
            dp[j + val[i].second] = min(dp[j + val[i].second], dp[j] + val[i].first);
        }
    }
    for(int i = 1; i <= vt; ++i) {
        if(dp[i] <= w)
            ans = max(ans, 1ll*i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
int ara[100009];
int main(){
    int n,m;
    cin>>n>>m;
    int mn=0,mx=1000000;
    bool flag=1;
    for(int i=0;i<m;i++)
    {
        int a,b;cin>>a>>b;
        if(flag)
        {
            if(a>mx||b<mn){
                flag=0;
            }
            else
            {
                if(a>=mn)
                {
                    mn=a;
                }
                if(b<=mx)
                    mx=b;
            }
        }
//        cout<<mx<<"  "<<mn<<endl;
    }
    if(flag)cout<<mx-mn+1<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 256
# Primality test
import numpy as np

n = 100003 # limit

primes = np.ones((n + 1,), dtype=int)
primes[0] = 0
primes[1] = 0
primes[2*2::2] = 0
primes[3*2::3] = 0
m = 5
l = n ** 0.5
while m <= l:
    if primes[m]:
        primes[m * 2::m] = 0
    if m % 6 == 5:
        m += 2
    else:
        m += 4

# solve
X = int(input())

while True:
    if primes[X]:
        print(X)
        break
    X += 1

Measured memory_bytes: 13144
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7
dy = [0,1,0,-1]
dx = [1,0,-1,0]
ddy = [0,1,1,1,0,-1,-1,-1]
ddx = [1,1,0,-1,-1,-1,0,1]

n,x = map(int,input().split())
P = [1]
L = [1]
for i in range(n):
    P.append(P[-1]*2+1)
    L.append(L[-1]*2+3)

def f(N,X):
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= 1 + L[N-1]:
        return f(N-1,X-1)
    else:
        return P[N-1]+1+f(N-1,X-2-L[N-1])

print(f(n,x))

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

void fnInput(string& rsTarget)
{
  cin >> rsTarget;
}

int fnParse(string sTarget)
{
  const vector<string> cnvsWord{"dream", "dreamer", "erase", "eraser"};
  int ixBgn, ixEnd;
  ixBgn = sTarget.size();

  while (ixBgn)
  {
    bool bReslt = false;
    ixEnd = ixBgn;
    for (int i = 0; i < cnvsWord.size(); i++)
    {
      ixBgn = ixEnd - cnvsWord[i].size();
      if (ixBgn < 0)  continue;

      if (sTarget.substr(ixBgn, cnvsWord[i].size()) == cnvsWord[i])
      {
        bReslt = true;
        break;
      }
    }
    if (!bReslt)  return 0;
  }
  return 1;
}

int main()
{
  string sTarget;
  
  fnInput(sTarget);
  if (fnParse(sTarget)) cout << "YES" << endl;
  else                  cout << "NO"  << endl;

  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int ans = 0;
	if (s[0] == 'R' || s[1] == 'R' || s[2] == 'R') {
		ans++;
	}
	if (s[0] == s[1] && s[0] == 'R') {
		ans++;
	}
	if (s[1] == s[2] && s[1] == 'R') {
		ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

string s = "keyence";

int main() {
    string str;
    cin >> str;
    if (str.size() < s.size()) {
        cout << "NO" << endl;
        return 0;
    }
    int cnt = 0;
    rep(i,str.size()) {
        if (str[i] == s[i]) {
            cnt++;
        } else {
            break;
        }
        if (cnt == s.size()) break;
    }
    int j = 0;
    for (int i = str.size()-1; i >= 0; i--) {
        if (cnt == s.size()) break;
        if (str[i] == s[s.size()-1-j]) {
            cnt++;
        } else {
            break;
        }
        j++;
    }
    if (cnt == s.size()) cout << "YES" << endl;
    else cout << "NO" << endl;
}



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

int main() {
  int h, w;
  while (cin >> h >> w, (h || w)) {
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cout << "#";
      }
      cout << "\n";
    }
    cout << endl;
  }
}

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
  int n, k;
  cin >> n >> k;
  long long sumCount = 0;
  for (long long i = k; i <= n + 1; i++) {
    sumCount += ((n - i + 1) * i + 1) % MOD;
    sumCount %= MOD;
  }
  cout << sumCount << endl;
  return 0;
}

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

using namespace std;

#define rep(a,b) for(int (a)=0; (a)<b;(a)++)
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

int main(){
	int n;
	cin>>n;
	int c=0;
	rep(loop,n){
		if(c!=0)cout<<endl;
		c++;
		int data[9][9];
		bool isOK[9][9];
		rep(i,9)rep(j,9)cin>>data[i][j];

		rep(i,9)rep(j,9)isOK[i][j]=true;

		rep(i,9){
			int used[10]={};
			rep(j,9){
				used[ data[i][j] ]++;
			}
			for(int j=1;j<10;j++){
				if( used[j]>=2 ){
					rep(k,9)
						if(data[i][k]==j)
							isOK[i][k]=false;
				}
			}
		}

		rep(j,9){
			int used[10]={};
			rep(i,9){
				used[ data[i][j] ]++;
			}
			for(int i=1;i<10;i++){
				if( used[i]>=2 ){
					rep(k,9)
						if(data[k][j]==i)
							isOK[k][j]=false;
				}
			}
		}

		rep(I,3){
			rep(J,3){
				int used[10]={};
				rep(i,3){
					rep(j,3){
						used[ data[I*3+i][J*3+j] ] ++;
					}
				}
				for(int k=1;k<10;k++){
					if(used[k]>=2){
						rep(i,3){
							rep(j,3){
								if(data[I*3+i][J*3+j]==k)
									isOK[I*3+i][J*3+j]=false;
							}
						}
					}
				}
			}
		}

		rep(i,9){
			rep(j,9){
				if(isOK[i][j]==true)cout<<" ";
				else cout<<"*";
				cout<<data[i][j];
			}
			cout<<endl;
		}
	}
	return 0;
}

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

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

void solve(){
	int k,s,count = 0;
	cin >> k >> s;
	rep(i,s+1){
		REP(j,i,s+1){
			int x,y,z;
			x = i;
			y = j - i;
			z = s - j;
			if(x <= k and y <= k and z <= k)count++;
		}
	}
	P(count);
}

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


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

struct TTree {
  vector<int> t;
  int n;

  TTree (int nn)
  {
      n = nn;
        t.assign (n, 0);
  }

  int sum (int r)
  {
      int result = 0;
        for (; r >= 0; r = (r & (r+1)) - 1)
              result += t[r];
          return result;
  }

  void inc (int i, int delta)
  {
      for (; i < n; i = (i | (i+1)))
            t[i] += delta;
  }

  int sum (int l, int r)
  {
      return sum (r) - sum (l-1);
  }
};

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  int q;
  cin >> q;

  vector<TTree> tree(26, TTree(n));
  for (int i = 0; i < n; ++ i) tree[s[i] -'a'].inc(i, +1);

  for (int i = 0; i < q; ++i) {
    int type;
    cin >> type;
    if (type == 1) {
      int ind;
      char what;
      cin >> ind >> what;
      ind--;
      tree[s[ind] - 'a'].inc(ind, -1);
      s[ind] = what;
      tree[s[ind] - 'a'].inc(ind, +1);
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      r--;
      int result = 0;
      for (int t = 0; t < 26; ++t) result += tree[t].sum(l, r) > 0;
      cout << result << endl;
    }
  }

  return 0;
}


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

int n, m, a[201000], ans;

bool check(int lim) {
  int cur = m + 1;
  for(int i = lim + 1; i <= n << 1; i++) {
    cur = min(cur, a[i] + a[(n << 1) - i + lim + 1]);
  }
  return cur < m ? false : (ans = lim, true);
}

int main(void) {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n << 1; i++) {
    scanf("%d", &a[i]);
  }
  sort(a + 1, a + n + n + 1);
  int l = 0, r = n;
  while(l <= r) {
    int mid = l + r >> 1;
    if(check(mid << 1)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  int realans = 0;
  for(int i = 1; i <= ans; i++) {
    realans = max(realans, a[i] + a[ans - i + 1]);
  }
  for(int i = ans + 1; i <= n << 1; i++) {
    realans = max(realans, a[i] + a[(n << 1) - i + ans + 1] - m);
  }
  cout << realans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <iomanip>
typedef long long int lli;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define JUGAD freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
using namespace std;

int main(){
    FAST;
    int x;
    cin>>x;
    cout<<1-x<<endl;
}



Measured memory_bytes: 3608
# B
x1, y1, x2, y2 = map(int, input().split())
x3 = x2 - (y2-y1)
y3 = y2 + (x2-x1)
x4 = x3 - (y3-y2)
y4 = y3 + (x3-x2)

print("{} {} {} {}".format(x3, y3, x4, y4))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<tuple<int, int, int>> v;
    v.emplace_back(0, 0, 0);
    for (int i = 0; i < n; ++i)
    {
        int t, x, y;
        cin >> t >> x >> y;
        v.emplace_back(t, x, y);
    }
    for (int i = 1; i <= n; ++i)
    {
        int t1, t2, x1, x2, y1, y2;
        tie(t1, x1, y1) = v[i - 1];
        tie(t2, x2, y2) = v[i];
        int d = x2 - x1 + y2 - y1;
        int t = t2 - t1;
        if (t < d || (t + d) % 2)
            return cout << "No", 0;
    }
    cout << "Yes";
}


Measured memory_bytes: 1912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,c,dp[200005],l,r,h[200005];
P deq[200005];
bool check(P a,P b,P c){
    return D(c.S-b.S)/D(b.F-c.F)<=D(b.S-a.S)/D(a.F-b.F);
}
int main(void){
    scanf("%lld%lld",&n,&c);
    for(int i=0;i<n;i++)scanf("%lld",h+i);
    for(int i=1;i<n;i++){
        P x=P(-2*h[i-1],dp[i-1]+h[i-1]*h[i-1]);
        while(l<=r-2&&check(deq[r-2],deq[r-1],x))r--;
        deq[r++]=x;
        while(l+1<r&&deq[l].F*h[i]+deq[l].S>deq[l+1].F*h[i]+deq[l+1].S)l++;
        dp[i]=deq[l].F*h[i]+deq[l].S+c+h[i]*h[i];
    }
    printf("%lld\n",dp[n-1]);
}


Measured memory_bytes: 6528
#include<stdio.h>
#include<limits.h>
int main(){
	int n, m;
	int i, j;
	while(scanf("%d%d", &n, &m), n) {
		int cost[100][100] = {0};
		int determined[100] = {0}, undeterminednodes;
		int mincost[100] = {0};
		int costsum = 0;
		int minnode, minnodecost;

		// initialize cost table
		for(i = 0; i < n; i ++) {
			for(j = 0; j < n; j ++) {
				cost[i][j] = INT_MAX;
			}
		}

		// load
		for(i = 0; i < m; i ++) {
			int a, b, d;
			scanf("%d,%d,%d", &a, &b, &d);
			cost[a][b] = cost[b][a] = d/100-1;
		}

		// node 0 is determined
		determined[0] = 1;
		undeterminednodes = n-1;

		// initialize mincost
		for(i = 0; i < n; i ++) {
			if(!determined[i]) {
				mincost[i] = cost[0][i];
			} else {
				mincost[i] = INT_MAX;
			}
		}

		while(undeterminednodes > 0) {
			// select the nearest undetermined node
			minnodecost = INT_MAX;
			for(i = 0; i < n; i ++) {
				if(mincost[i] < minnodecost) {
					minnode = i;
					minnodecost = mincost[i];
				}
			}

			// the node is determined
			determined[minnode] = 1;
			costsum += minnodecost;
			undeterminednodes --;
			mincost[minnode] = INT_MAX;

			// update mincost
			for(i = 0; i < n; i ++) {
				if(!determined[i]) {
					if(cost[minnode][i] < mincost[i])
						mincost[i] = cost[minnode][i];
				}
			}
		}
		printf("%d\n", costsum);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
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; }
int main(){
    ios::sync_with_stdio(false);
    ll h,w;
    cin >> h >> w;
    ll ans = INT64_MAX;
    if(h%3 == 0) ans = 0;
    if(w%3 == 0) ans = 0;
    chmin(ans,w);
    chmin(ans,h);
    rep(i,3) {
        ll a = h/2;
        ll b = h-a;
        ll c = w/3 + i;
        ll d = w-c;
        ll s = a*d;
        ll t = b*d;
        ll u = h*c;
        if(a == 0 || b == 0 || c == 0 | d == 0) continue;
        ll ma = max(t,u);
        ll mi = min(s,u);
        chmin(ans, ma-mi);
    }
    rep(i,3) {
        ll a = w/2;
        ll b = w-a;
        ll c = h/3 + i;
        ll d = h-c;
        if(a == 0 || b == 0 || c == 0 | d == 0) continue;
        ll s = a*d;
        ll t = b*d;
        ll u = w*c;
        ll ma = max(t,u);
        ll mi = min(s,u);
        chmin(ans, ma-mi);
    }
    cout << ans << endl;
}


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

long long lucas(long long v)
{
  static unordered_map<size_t, long long> cache {};
  
  if (v == 0)
    return 2;
  if (v == 1)
    return 1;
  
  const auto it {cache.find(v)};
  if (it != cache.end()) {
    return it->second;
  } else {
    const auto ans {lucas(v - 1) + lucas(v - 2)};
  	cache.emplace(v, ans);
    return ans;
  }
}

int main()
{
  int input;
  cin >> input;
  cout << lucas(input) << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n,i,x,result;
  scanf("%d",&n);
  int hotel[n];
  for(i=0;i<n;++i){
    scanf("%d",&x);
    hotel[i] = x;
  }
  result = 1;
  x = hotel[0];
  for(i=1;i<n;++i){
    if(x <= hotel[i]){
      ++result;
      x = hotel[i];
    }
  }
  printf("%d\n",result);
  return 0;
}

Measured memory_bytes: 128
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for a in A:
    d[a] += 1
cant_use = [0] * (N+1)
for v in d.values():
    for i in range(v):
        cant_use[i] += v - i


def is_ok(i, k):
    return (N-cant_use[i])/k >= i

def bisect(ng, ok, k):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, k):
            ok = mid
        else:
            ng = mid
    return ok

for k in range(1, N + 1):
    print(bisect(N+1, 0, k))


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

int main() {
  long a,b;
  cin >> a>>b;
  long ans;
  if(a==1||b==1){
    ans=max(1LL,a-2LL)*max(1LL,b-2LL);
  }
  else{
    ans=max(0LL,a-2LL)*max(0LL,b-2LL);
  }
 
  cout<<ans<<endl;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const long long mod = 1e9+7; // CHECK
long long power(long long a, long long b, long long m = mod) {
    if(b < 0) {
        return power(power(a, -b), mod-2);
    }
    long long x = 1;
    while(b) {
        if(b & 1) {
            x = 1ll * x * a % m;
        }
        a = 1ll * a * a % m;
        b /= 2;
    }
    return x;
}
#define ll long long
const int INT_INF = 1e9+9;
const ll LL_INF = 2e18;
const int N = 3e5+9;
void bye() {
	cout << "-1\n";
	exit(0);
}
signed main() {  
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<ll> a(n+1);
    for (int i = 0; i <= n; i++) {
    	cin >> a[i];
    }
    vector<ll> post(n+2);
    for (int i = n; i >= 0; i--) {
    	post[i] = post[i+1] + a[i];
    }
    ll ans = 0, cur = 1;
   	for (int i = 0; i <= n; i++) {
   		ans += cur;
   		cur -= a[i];
   		if (cur < 0) bye();
   		// if (post[i+1] > 2 * cur) bye();
   		cur = min(2 * cur, post[i+1]);

   	}
   	cout << ans << '\n';

    

    return 0;
}



Measured memory_bytes: 5084
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define endl '\n'
#define Endl '\n'
#define fi first
#define ii pair<int,int>
#define iil pair<ll,ll>
#define se second
#define ld long double
#define mod 1000000007
#define popcount __builtin_popcountll
#define x0 zxcxzcsacasd
#define x1 ghfghujfgfg
#define y0 olkjhdnncvcv
#define y1 bhvgrewm345345435
#define debug(x) std::cerr<<#x<<": "<<(x)<<'\n'
#define all(x) x.begin(), x.end()
using namespace std;
ll p(ll a, ll b){
	if(b==0)return 1;
	ll ret=p(a, b/2);
	ret*=ret;
	ret%=mod;
	if(b%2)ret*=a;
	return ret%mod;
}
int main(){
	int n;
	cin>>n;
	ll ans = p(10, n);
	ans-=2*p(9, n);
	ans%=mod;
	if(ans<0)ans+=mod;
	ans+=p(8, n);
	ans%=mod;
	cout<<ans<<endl;
}



Measured memory_bytes: 3596
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
using namespace std;
const ll INF = 1e10;


int n,a[100005],ans,aa[100005];
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    ans+=abs(a[i]-a[i-1]);
  }
  ans+=abs(a[n]);
  for(int i=1;i<=n;i++){
    int b=ans;
    
    b-=abs(a[i]-a[i-1]);
    
    b-=abs(a[i+1]-a[i]);
    b+=abs(a[i+1]-a[i-1]);
    cout<<b<<endl;
  }
  return 0;
}




Measured memory_bytes: 1664
#include <iostream>
#include <map>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<int> mem(n, 0);

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }

    int cur = 0;
    int cnt = 0;
    mem[0] = 1;

    while (true) {
        cnt++;
        cur = a[cur];
        if (cur == 1) {
            std::cout << cnt << std::endl;
            break;
        }
        if (mem[cur] == 1) {
            std::cout << -1 << std::endl;
            break;
        }
        mem[cur] = 1;
    }
    return 0;
}

Measured memory_bytes: 1024
n, s = gets.chomp.split.map(&:to_i)
arr = gets.chomp.split.map(&:to_i)
l = r = sum = 0
li = ri = -1
min = nil
while true
    sum += r
    sum -= l
    if sum >= s
        min = ri - li if min.nil? || min > ri - li
        li += 1
        break if li == ri
        l, r = arr[li], 0
    else
        ri += 1
        break if ri == n
        l, r = 0, arr[ri]
    end
end
puts (min.nil? ? 0 : min)


Measured memory_bytes: 12768
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=61;
ll pw[N];
int32_t main(){
    pw[0]=1;
    for (int i=1;i<N;i++){
        pw[i]=pw[i-1]*2;
    }
    ll a,b;
    cin >> a >> b;
    if (a==b) kill(1);
    ll mx=60;
    while (mx){
        ll p1=0;
        if (a>=pw[mx] && b>=pw[mx]) a-=pw[mx],b-=pw[mx],mx--,p1++;
        if (a<pw[mx] && b<pw[mx]) mx--,p1++;
        if (p1) continue;
        else break;
    }
   // cout << mx << endl;
    ll ans=pw[mx]-a;
    ll mb=0;
    ll z=b-pw[mx];
    for (int i=0;i<N;i++){
        if (pw[i]<=z) mb=i+1;
    }
    //cout << mb << endl;
    if (pw[mb]>=a){
        ans+=pw[mx];
        kill(ans);
    }
    else{
        ans+=(pw[mx]-a)+(pw[mb]);
        kill(ans);
    }
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;


int f(int a, int b){
    int MIN = 1e9;
    // cout << a << " " << b << endl;
    rep(i, 1, a){
        int d[3] = {}, e[3] = {};
        d[0] = i * b;
        d[1] = (a - i) * (b / 2);
        d[2] = (a - i) * ((b + 1) / 2);
        sort(d, d + 3);
        MIN = min(MIN, d[2] - d[0]);
        e[0] = i * b;
        e[1] = (a - i) / 2 * b;
        e[2] = (a - i + 1) / 2 * b;
        sort(e, e + 3);
        MIN = min(MIN, e[2] - e[0]);
        // cout << i << " " << d[2] << " " << d[0] << " " << e[2]  << " "<<  e[0] << endl;
    }
    return MIN;
}

signed main(){
    int a, b;
    cin >> a >> b;
    cout << min(f(a, b), f(b, a)) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

int main() {
  Int n = lin();
  Int m = lin();
  Int d = lin();

  auto f = [=] (Int v) {
    int res = 0;
    if (v >= 1 + d) ++res;
    if (v <= n - d) ++res;
    return d == 0 ? 1 : res;
  };

  vector<Int> K;
  K.push_back(1);
  K.push_back(n + 1);
  for (int p = -1; p <= 1; ++p) {
    Int k = 1 + d + p;
    if (1 <= k && k <= n) K.push_back(k);
    k = n - d + p;
    if (1 <= k && k <= n) K.push_back(k);
  }
  sort(K.begin(), K.end());
  K.erase(unique(K.begin(), K.end()), K.end());

  Int res = 0;
  for (int i = 0; i + 1 < (int)K.size(); ++i) {
    Int e = f(K[i]);
    res += e * (K[i + 1] - K[i]);
  }

  printf("%.9f\n", res / (double)n * (m - 1) / n);

  return 0;
}


Measured memory_bytes: 256
def baseConv(n,ro,ri=10):
    n = int(str(n),base=ri)
    s = ""
    nums = "0123456789abcdefghijklmnopqrstuvwxyz"
    while n:
        s += nums[n%ro]
        n //= ro
    return s[::-1]
  
n,k = map(int,input().split())
print(len(baseConv(n,k)))

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

int gcd(int n, int m) {
  if(n < m) swap(n, m);
  if(m == 1) return 1;
  else if(m == 0) return n;
  else return gcd(m, n%m);
}

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

signed main() {
  int N; cin >> N;
  vector<int> T(N);
  rep(i, N) cin >> T[i];
  
  int ans = T[0];
  rep(i, N-1) {
    //cout << ans << endl;
    ans = lcm(ans, T[i+1]);
  }
  cout << ans << endl;

}

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

//
int main(){
    //定義、入力
    long long int N,M,X;
    cin >> N >> M >> X;
    long long int* C = new long long int[N];
    long long int** A = new long long int*[N];
    for(int i=0;i<N;++i){
        A[i] = new long long int[M];
    }
    for(int i=0;i<N;++i){
        cin >> C[i];
        for(int j=0;j<M;++j){
            cin >> A[i][j];
        }
    }

    //計算
    long long int min_value=100000000;
    long long int* skill = new long long int[M];
    for(int bit=0;bit<(1<<N);++bit){
        //初期化
        long long int value=0;
        for(int j=0;j<M;++j){
            skill[j]=0;
        }
        //アイテムごとに見る
        for(int i=0;i<N;i++){
            //選ばれるとき
            if((1<<i) & bit){
                value=value+C[i];
                for(int j=0;j<M;++j){
                    skill[j]=skill[j]+A[i][j];
                }
            }
        }
        bool skilled=true;
        for(int j=0;j<M;++j){
            if(skill[j]<X){
                skilled=false;
            }
        }
        if(skilled){
            if(value<min_value){
                min_value=value;
            }
        }
    }

    //出力
    if(min_value==100000000){
        cout << -1 << endl;
    } else{
        cout << min_value << endl;
    }

    //事後処理
    delete[] C;
    for(int i=0;i<N;++i){
        delete[] A[i];
    }
    delete[] A;
    delete[] skill;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)

int card[2][105];
void generate(int N)
{
  bool flag[210] = {0};
  int itr = 0;
  Rep(i,N) {
    cin >> card[0][i];
    flag[card[0][i]]++;
  }
  Rep(i,2 * N) {
    if(!flag[i + 1]) {
      card[1][itr] = i + 1;
      itr++;
    }
  }
  sort(card[0],card[0] + N);
}
int main()
{
  int N;
  while(cin >> N,N) {
    
    int cnt[2] = {0};
    bool used[2][105] = {0};
    generate(N);
    int field = 0;
    while(true) {
      Rep(p,2) {
	bool flag = false;
	Rep(i,N) {
	  if(field < card[p][i] && !used[p][i]) {
	    used[p][i] = true;
	    flag = true;
	    field = card[p][i];
	    cnt[p]++;
	    break;
	  }
	}
	if(!flag)field = 0;
	if(cnt[p] >= N)break;
      }
      if(cnt[0] >= N || cnt[1] >= N)break;
    }
    cout << N - cnt[1] << endl << N - cnt[0] << endl;
  }
  return 0;
}

Measured memory_bytes: 3068
#set
a,b = gets.chomp.split(" ").map(&:to_i)
answer_ary = []

#main
answer_ary[0] = a + b
answer_ary[1] = a - b
answer_ary[2] = a * b
answer_ary.sort! {|a , b| b <=> a }

print ("#{answer_ary[0]}\n")

Measured memory_bytes: 1788