akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int calc(int x)
{
    int ret = 0;
    while(x % 100 == 0)
    {
        x /= 100;
        ret++;
    }
    return ret;
}

int main(void)
{
    int d,n,ans = 0,count = 0;
    cin >> d >> n;
    while(count < n)
    {
        ans++;
        if(calc(ans) == d){count++;}
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int n;
  cin >>n;
  vector<int>a(n);
  vector<int>hantei(n,-1);
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++)--a[i];
  int num=0;
  int count =0;
  for(int i=0;i<n;i++){
    count++;
    if(a[num]==1){
      cout<<count<<endl;
      return 0;
    }
    num=a[num];
  }
  cout<<-1<<endl;
  return 0;
}

Measured memory_bytes: 1024
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
counts = {}
for a_ in A:
  for a in a_:
    if not a in counts:
      counts[a] = 1
    else:
      counts[a] += 1
ans = "Yes"
oe = H%2+W%2
mod1 = 1 if oe == 2 else 0
mod2 = (H//2)*(W%2)+(W//2)*(H%2)
mod4 = (H//2)*(W//2)
for _ in range(mod1):
  for c in counts.keys():
    if counts[c] % 4 == 1:
      counts[c] -= 1
      break
for _ in range(mod2):
  for c in counts.keys():
    if counts[c] % 4 == 2:
      counts[c] -= 2
      mod2 -= 1
      break
if mod2 % 2 == 0:
  mod4 += mod2//2
  for _ in range(mod4):
    for c in counts.keys():
      if counts[c] % 4 == 0 and counts[c] > 0:
      	counts[c] -= 4
      	break
  for n in counts.values():
    if n > 0:
      ans = "No"
      break
else:
  ans = "No"
print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

bool isloop(string t) {
    int n = t.length();
    FOR(i, 0, n) {
        if (t[i] != t[n - i - 1]) {
            return false;
        }
    }
    return true;
}
int main() {
    init();

    string s; cin >> s;
    int n = s.length();
    if (!isloop(s)) {
        cout << "No\n";
        return 0;
    }
    if (!isloop(s.substr(0, (n - 1) / 2))) {
        cout << "No\n";
        return 0;
    }

    if (!isloop(s.substr((n + 3) / 2 - 1))) {
        cout << "No\n";
        return 0;
    }

    cout << "Yes\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int nax = 505;
int dist[nax][nax];

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

bool killed[nax][nax];

vector<pair<int,int>> nei[nax][nax];

int main() {
	int n;
	scanf("%d", &n);
	for(int row = 0; row < n; ++row) {
		for(int col = 0; col < n; ++col) {
			for(int dir = 0; dir < 4; ++dir) {
				int r2 = row + dx[dir];
				int c2 = col + dy[dir];
				if(0 <= r2 && 0 <= c2 && r2 < n && c2 < n) {
					nei[row][col].emplace_back(r2, c2);
				}
			}
		}
	}
	for(int row = 0; row < n; ++row) {
		for(int col = 0; col < n; ++col) {
			dist[row][col] = 1 + min({row, n - 1 - row, col, n - 1 - col});
		}
	}
	long long answer = 0;
	for(int turn = 1; turn <= n * n; ++turn) {
		int who;
		scanf("%d", &who);
		who--;
		int row = who / n;
		int col = who % n;
		answer += dist[row][col] - 1;
		dist[row][col]--;
		killed[row][col] = true;
		vector<pair<int,int>> q;
		q.emplace_back(row, col);
		for(int i = 0; i < (int) q.size(); ++i) {
			pair<int,int> a = q[i];
			for(const pair<int,int>& b : nei[a.first][a.second]) {
				int maybe = dist[a.first][a.second];
				if(!killed[b.first][b.second]) {
					maybe++;
				}
				if(dist[b.first][b.second] > maybe) {
					dist[b.first][b.second] = maybe;
					q.push_back(b);
				}
			}
		}
	}
	printf("%lld\n", answer);
}


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

#define EPS 1e-10

class point {
public:
	double x, y;
	point() {}
	point( double x_, double y_ ) : x(x_), y(y_) {}
	point operator -( point p ) { return point( x - p.x, y - p.y ); }
	point operator +( point p ) { return point( x + p.x, y + p.y ); }
	point operator *( int a ) { return point( x * a, y * a ); }
};

class segment {
public:
	point p1, p2;
	segment() {}
};

double dot( point a, point b ) { return a.x * b.x + a.y * b.y; }
double cross( point a, point b ) { return a.x * b.y - a.y * b.x; }
double norm( point a ) { return a.x * a.x + a.y * a.y; }

double distance( segment s, point p )
{
	if( dot( s.p2 - s.p1, p - s.p1 ) < 0 ) return sqrt( norm( p - s.p1 ) );
	if( dot( s.p1 - s.p2, p - s.p2 ) < 0 ) return sqrt( norm( p - s.p2 ) );;
	return fabs( cross( s.p2 - s.p1, p - s.p1 ) / sqrt( norm( s.p2 - s.p1 ) ) );
}

int ccw( point p0, point p1, point p2 )
{
	point v1 = p1 - p0;
	point v2 = p2 - p0;
	if( cross( v1, v2 ) > EPS ) return 1;
	if( cross( v1, v2 ) < -EPS ) return -1;
	if( dot( v1, v2 ) < -EPS ) return 2;
	if( norm( v1 ) < norm( v2 ) ) return -2;
	return 0;
}

bool intersect( segment s1, segment s2 )
{
	return ccw( s1.p1, s1.p2, s2.p1 ) * ccw( s1.p1, s1.p2, s2.p2 ) <= 0 &&
			ccw( s2.p1, s2.p2, s1.p1 ) * ccw( s2.p1, s2.p2, s1.p2 ) <= 0;
}

double distance( segment s1, segment s2 )
{
	if( intersect( s1, s2 ) ) return 0;
	return min( { distance( s1, s2.p1 ), distance( s1, s2.p2 ),
					distance( s2, s1.p1 ), distance( s2, s1.p2 ) } );
}

int main()
{
	segment s;
	cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;
	int q;
	cin >> q;
	for( int i = 0; i < q; i++ ) {
		point p;
		cin >> p.x >> p.y;
		int ret = ccw( s.p1, s.p2, p );
		string ans = "ON_SEGMENT";
		if( ret == 1 ) ans = "COUNTER_CLOCKWISE";
		if( ret == -1 ) ans = "CLOCKWISE";
		if( ret == 2 ) ans = "ONLINE_BACK";
		if( ret == -2 ) ans = "ONLINE_FRONT";

		cout << ans << endl;
	}
}



Measured memory_bytes: 3288
def rec(r, b, c, a0, n, mod):
    # a_n = r * a_{n-1} + b * n + c
    a = a0
    n_ = 0
    c += b
    diff = 1
    while n:
        n, m = divmod(n, 2)
        if m:
            a = (a * r + b * n_ + c) % mod
            n_ += diff
        r, b, c = r*r%mod, (r*b+b)%mod, (r*c+b*diff+c)%mod
        diff <<= 1
    return a

def main():
    L, A, B, M = map(int, input().split())

    def bis(d):
        # d 桁以上になる最小の項
        n = 10**(d-1)
        ng = -1
        ok = L
        while ng + 1 < ok:
            c = ok+ng >> 1
            s_c = A + B * c
            if s_c >= n:
                ok = c
            else:
                ng = c
        return ok
    Idxs = [0]
    for d in range(1, 19):
        Idxs.append(bis(d))
    Idxs.append(L)

    ans = 0
    for d, (l, r) in enumerate(zip(Idxs, Idxs[1:])):
        if r - l == 0:
            continue
        s_l = A + B * l
        n = r - l
        ratio = 10**d
        a = rec(ratio, B, s_l, s_l, n-1, M)
        #print(d, a)
        ans = (ans * pow(10, d*n, M) + a) % M
    print(ans)

main()


Measured memory_bytes: 9184
#include <iostream>
#include <vector>
#include <set>
#include <functional>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

void solve() {
    int n;
    std::cin >> n;

    Graph<> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        graph[u].emplace_back(u, v);
        graph[v].emplace_back(v, u);
    }

    std::vector<std::vector<int>> gs(2);
    std::function<void(int, int, int)> dfs =
        [&](int v, int p, int d) {
            gs[d].push_back(v);
            for (auto e : graph[v]) {
                if (e.dst == p) continue;
                dfs(e.dst, v, 1 - d);
            }
        };
    dfs(0, -1, 0);

    int id = 0;
    for (id = 0; id < 2; ++id) {
        if ((int)gs[id].size() <= n / 3) break;
    }

    std::vector<int> ans(n);
    if (id < 2) {
        std::set<int> ss;
        for (int i = 1; i <= n; ++i) ss.insert(i);

        int num = 3;
        for (auto v : gs[id]) {
            ans[v] = num;
            ss.erase(num);
            num += 3;
        }
        for (auto v : gs[1 - id]) {
            ans[v] = *ss.begin();
            ss.erase(ss.begin());
        }
    } else {
        int one = 1, three = 3;
        for (auto v : gs[0]) {
            if (one <= n) {
                ans[v] = one;
                one += 3;
            } else {
                ans[v] = three;
                three += 3;
            }
        }

        int two = 2;
        for (auto v : gs[1]) {
            if (two <= n) {
                ans[v] = two;
                two += 3;
            } else {
                ans[v] = three;
                three += 3;
            }
        }
    }

    for (auto a : ans) std::cout << a << " ";
    std::cout << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}


Measured memory_bytes: 22900
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pll;
typedef vector<ll>vll;
const int N = 1e5 + 5;
const int M = 1e9 + 7;
ll dp[N];
ll zabat(ll a)
{
    return ((a % M) + M) % M;
}
ll mul(ll a, ll b)
{
    return zabat(zabat(a) * zabat(b));
}
ll sub(ll a, ll b)
{
    return zabat(zabat(a) - zabat(b));
}
ll add(ll a, ll b)
{
    return zabat(zabat(a) + zabat(b));
}
ll fp(ll b, ll p)
{
    if(!p)      return 1;
    ll res = fp(b, p >> 1);
    res = mul(res, res);
    if(p & 1)   res = mul(res, b);
    return res;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, k, ans = 0;
    cin >> n >> k;
    for(ll i = k;i > 0;--i)
    {
        dp[i] = fp(k / i, n);
        for(ll j = i + i;j <= k;j+=i)
            dp[i] = sub(dp[i], dp[j]);
    }
    for(int i = 1;i <= k;++i)
        ans = add(ans, mul(i, dp[i]));
    cout << ans;
    return 0;
}



Measured memory_bytes: 4428
N,Y = map(int,input().split())
array = []
for i in range(N+1):
    for j in range(N+1-i):
        mon = 10000*i+5000*j+1000*(N-i-j)
        if mon == Y:
            print(i,j,N-i-j)
            exit()
print('-1 -1 -1')

Measured memory_bytes: 9176
use std::collections::HashSet;
use std::vec::Vec;

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

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

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    assert_eq!(v.len(), 2);
    (v[0], v[1])
}

fn main() {
    let (n, k) = read_touple::<usize>();
    let mut a: Vec<usize> = read_vec();
    for i in 0..n {
        a[i] -= 1;
    }

    // init
    let mut visit = HashSet::new();
    visit.insert(0);
    let mut route1 = vec![];
    let mut route2 = vec![];

    // 同じ数字が二度現れるまで繰り返す
    // それまでの経路長を記録しておく
    let mut l: usize = 0;
    let mut now = 0;
    let mut next = a[0];
    route1.push(now);
    for _ in 0..n {
        now = next;
        next = a[now];
        l += 1;
        if visit.contains(&now) {
            break;
        } else {
            visit.insert(now);
        }
        route1.push(now);
    }

    let r = calc(&a, now, &mut route2);

    let mut ans = 0;
    // 循環部分に入らない
    if k < l - r {
        ans = route1[k];
    } else {
        let idx = (k - l + r) % r;
        ans = route2[idx];
    }
    //dbg!(route1);
    //dbg!(route2);
    println!("{}", ans + 1);
}

// 循環部分の長さを求める関数
fn calc(a: &Vec<usize>, start: usize, route: &mut Vec<usize>) -> usize {
    let mut visit = HashSet::new();
    let mut l: usize = 0;
    let mut now = start;
    let mut next = a[now];
    visit.insert(now);
    route.push(now);
    for _ in 0..a.len() {
        now = next;
        next = a[now];
        l += 1;
        if visit.contains(&now) {
            break;
        } else {
            visit.insert(now);
        }
        route.push(now);
    }

    l
}


Measured memory_bytes: 12544
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

fn main() {
    let mut scan = Scan::new();

    let N = scan.word::<usize>();
    let A = scan.list::<i64>(N);

    let mut total = 0_i64;
    let mut freq = HashMap::new();

    for i in 0..N {
        if let Some(&f) = freq.get(&((i + 1) as i64 - A[i])) {
            total += f;
        }

        *freq.entry(A[i] + (i + 1) as i64).or_insert(0) += 1;
    }

    println!("{}", total);
}


Measured memory_bytes: 13316
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define rep(i, s, n) for (int i = s; i < (int)(n); i++)

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

int main()
{
    string s;
    cin >> s;
    ll k;
    cin >> k;
    ll cnt = 1;
    vector<int> v;
    for (int i = 0; i < s.length() - 1; i++)
    {
        if (s[i + 1] == s[i])
        {
            cnt++;
        }
        if (s[i + 1] != s[i])
        {
            v.push_back(cnt);
            cnt = 1;
        }
    }
    v.push_back(cnt);
    cnt = 0;
    if (v.size() == 1)
    {
        cout << v[0] * k / 2 << endl;
        return 0;
    }
    for (int i = 1; i < v.size() - 1; i++)
    {
        cnt += v[i] / 2;
    }
    ll ans = cnt * k;
    if (s[0] == s.back())
    {
        ans += (k - 1) * ((v[0] + v.back()) / 2);
        ans += v[0] / 2 + v.back() / 2;
    }
    else
    {
        ans += (v[0] / 2 + v.back() / 2) * k;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);

int main() {
  vi len(3);
  for (int i = 0; i < 3; i++) {
    cin >> len[i];
  }
  sort(len.begin(), len.end());
  cout << len[0]*len[1]/2 << endl;

  return 0;
}


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

namespace Contest
{
    partial class Program
    {
        static void Main(string[] args)
        {
            ABC152_C();
        }
        #region ABC152
        static void ABC152_A()
        {
            var nm = ReadIntN();
            Console.WriteLine(nm[0] == nm[1] ? "Yes" : "No");
        }
        static void ABC152_B()
        {
            var ab = ReadIntN();
            var A = ab[0];
            var B = ab[1];
            Console.WriteLine(A < B ? String.Join("", Enumerable.Repeat(A, B)) : String.Join("", Enumerable.Repeat(B, A)));
        }
        static void ABC152_C()
        {
            var N = ReadInt();
            var P = ReadIntN();
            int min = P[0];
            int count = 0;
            for (int i = 0; i < N; ++i)
            {
                if (min >= P[i])
                {
                    count += 1;
                    min = P[i];
                }
            }
            Console.WriteLine(count);
        }
        static void ABC152_D()
        {
            var N = ReadInt();
            long[,] count = new long[10, 10];
            for (int i = 1; i <= N; ++i)
            {
                var A1 = i;
                while (A1 > 9) { A1 /= 10; }
                var A0 = i % 10;
                count[A1, A0]++;
            }
            Console.WriteLine(Enumerable.Range(1, 9).Select(i => Enumerable.Range(1, 9).Select(j => count[i, j] * count[j, i]).Sum()).Sum());
        }
        static void ABC152_E()
        {
            var N = ReadInt();
            var A = ReadIntN();
        }
        #endregion


        static string ReadStr()
        {
            return Console.ReadLine();
        }
        static string[] ReadStrN()
        {
            return Console.ReadLine().Split(' ');
        }
        static int ReadInt()
        {
            return Convert.ToInt32(Console.ReadLine());
        }
        static int[] ReadIntN()
        {
            return Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
        }
        static long ReadLong()
        {
            return Convert.ToInt64(Console.ReadLine());
        }
        static long[] ReadLongN()
        {
            return Console.ReadLine().Split(' ').Select(s => Convert.ToInt64(s)).ToArray();
        }
        static Tuple<long, long>[]  ReadTupleLong(int n)
        {
            List<Tuple<long, long>> list = new List<Tuple<long, long>>();
            for (int i = 0; i < n; ++i)
            {
                var ab = ReadLongN();
                list.Add(new Tuple<long, long>(ab[0], ab[1]));
            }
            return list.ToArray();
        }
    }
}


Measured memory_bytes: 32092
// Problem : A - ∴ (Therefore)
// Contest : AtCoder - AtCoder Beginner Contest 168
// URL : https://atcoder.jp/contests/abc168/tasks/abc168_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

string ans[] = {"hon", "pon", "bon"};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int a[] = { 1, 1, 0, 2, 0, 0, 1, 0, 1, 0};
	
	int n;
	cin >> n;
	
	int dig = n%10;
	cout << ans[a[dig]] << endl;
	
	return 0;
}


Measured memory_bytes: 3616
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ

int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		if(a==1){
			printf("%d\n",min(p,q));continue;
		}
		// p++;q++;
		if(p>q)swap(p,q);
		while(p!=q){

			q=(q+a-2)/a;
			if(p>q)swap(p,q);
		}
		printf("%d\n",p);
	}
}

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

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

    vector<int> P(N);
    for (int i = 0; i < N; i++)
    {
        cin >> P.at(i);
    }

    int counter = 0;

    int min = P.at(0);

    for (int i = 0; i < N; i++) 
    {
        if (min >= P.at(i))
        {
            min = P.at(i);
            counter++;
        }
    }

    cout << counter << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=1e9;
const int maxn=200100;
char str[maxn];
int dp[1<<26];
int zt[1<<26];
int n;
int main(){
//	freopen("D.in","r",stdin);
	scanf("%s",str+1);
	n=strlen(str+1);
	zt[0]=0;
	for(int i=1;i<=n;i++)
		zt[i]=zt[i-1]^(1<<(str[i]-'a'));
	for(int i=0;i<(1<<26);i++)
		dp[i]=INF;
	for(int i=0;i<26;i++)
		dp[1<<i]=0;
	dp[0]=0;
	int st;
	for(int i=1;i<=n;i++){
		st=dp[zt[i]]+1;
		for(int j=0;j<26;j++)
			if(st<dp[zt[i]^(1<<j)])
				dp[zt[i]^(1<<j)]=st;
		if(i==n) printf("%d\n",st);
	}
	return 0;
}


Measured memory_bytes: 263424
r, c = map(int, input().split())
a = [0 for i in range(r)]
for i in range(r):
  a[i] = list(map(int, input().split()))
sumA = 0
sumB = 0
sumC = 0

for i in range(r):
  for j in range(c):
    print(a[i][j], "", end="")
    sumA = sumA + a[i][j]
    if j == (c-1):
      print(sumA)
      sumA = 0

for i in range(c):
  for j in range(r):
    sumB = sumB + a[j][i]
    if j == (r-1):
      print(sumB, "", end="")
      sumC = sumC + sumB
      sumB = 0
  if i == (c-1):
    print(sumC)


Measured memory_bytes: 6744
a,b,c=map(int,input().split())
wa = a + b + c
if (3 * max(a,b,c) - wa) % 2 == 0:
    print((3*max(a,b,c)-wa) // 2)
else:
    print(((3*((max(a,b,c))+1))-wa) // 2)




Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C;
  cin >> A >> B >> C;
  if (A==7&&B==5&&C==5){
    cout << "YES" << endl;
  }
  else if (A==5&&B==7&&C==5){
    cout << "YES" << endl;
  }
  else if (A==5&&B==5&&C==7){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
from fractions import gcd
n, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
x0 = x[0]
d = x[1] - x0
for i in range(2, n+1):
  d = gcd(x[i] - x0, d)
print(d)

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"
#define int ll

struct LzSegT{
  int sz;
  vector<int>v;
  vector<int>lz;
  LzSegT(int n){
    sz=1;while(sz<n)sz*=2;
    v.resize(2*sz-1,0);
    lz.resize(2*sz-1,0);
  }
  void eval(int k,int l,int r){
    if(lz[k]!=0){
      v[k]+=lz[k];
      if(2*k+1<2*sz-1){
        lz[2*k+1]+=lz[k]/2;
        lz[2*k+2]+=lz[k]/2;
      }
      lz[k]=0;
    }
  }
  void add(int a,int b,int x){
    add_(a,b,x,0,0,sz);
  }
  void add_(int a,int b,int x,int k,int l,int r){
    eval(k,l,r);
    if(b<=l||r<=a)return;
    if(a<=l&&r<=b){
      lz[k]+=x*(r-l);
      eval(k,l,r);
    }
    else{
      add_(a,b,x,2*k+1,l,(l+r)/2);
      add_(a,b,x,2*k+2,(l+r)/2,r);
      v[k]=v[2*k+1]+v[2*k+2];
    }
  }
  int sum(int a,int b){
    return sum_(a,b,0,0,sz);
  }
  int sum_(int a,int b,int k,int l,int r){
    eval(k,l,r);
    if(b<=l||r<=a)return 0;
    if(a<=l&&r<=b)return v[k];
    int vl=sum_(a,b,2*k+1,l,(l+r)/2);
    int vr=sum_(a,b,2*k+2,(l+r)/2,r);
    return vl+vr;
  }
};

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

  int n,q;
  cin>>n>>q;
  LzSegT seg(n);
  while(q--){
    int a;
    cin>>a;
    if(a==0){
      int s,t,x;
      cin>>s>>t>>x;
      s--,t--;
      seg.add(s,t+1,x);
    }
    if(a==1){
      int s,t;
      cin>>s>>t;
      s--,t--;
      cout<<seg.sum(s,t+1)<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 7080
n=int(input())
for i in range(int(pow(n,1/5))+100):
	a=i
	b=-1*(n-pow(a,5))

	c=int(pow(abs(b),1/5))
	if b<0:
		c=-c
	if c*c*c*c*c==b:
		print(a,c)
		exit()

Measured memory_bytes: 9440
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer> cities = new ArrayList<>();
	static int N,M,R;
	static int dist[][];
	static boolean used[];
	static int result;
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		N = Integer.parseInt(sc.next());
		M = Integer.parseInt(sc.next());
		R = Integer.parseInt(sc.next());
		dist = new int[N][N];
		used = new boolean[R];
		edge[] e = new edge[M];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(i!=j) dist[i][j] = 100000000;
				else dist[i][j] = 0;
			}
		}
		for (int i = 0; i < R; i++) {
			cities.add(Integer.parseInt(sc.next()));
		}
		for (int i = 0; i < M; i++) {
			int a = Integer.parseInt(sc.next()) - 1;
			int b = Integer.parseInt(sc.next()) - 1;
			int c = Integer.parseInt(sc.next());
			e[i] = new edge(a,b,c);
			dist[a][b] = Math.min(c,dist[a][b]);
			dist[b][a] = Math.min(c,dist[b][a]);
		}

		for(int k=0;k<N;k++){
			for(int i=0;i<N;i++){
				for(int j=0;j<N;j++){
					dist[i][j] = Math.min(dist[i][j],dist[i][k]+dist[k][j]);
				}
			}
		}

		result = Integer.MAX_VALUE;
		dfs(0,-1,0);


		out.println(result);
		out.flush();
	}


	public static void  dfs(int count, int las, int subdist) {
		if(count == R) {
			if(result>subdist) result = subdist;
			return;
		}

		for(int i=0;i<R;i++) {
			if(!used[i]) {
				used[i] = true;
				if(las == -1) {
					dfs(count+1, i, 0);
				}
				else {
					dfs(count+1, i, subdist + dist[cities.get(las)-1][cities.get(i)-1]);
				}
				used[i] = false;
			}
		}
	}
}

class edge {
	int cost;

	public edge(int a, int b, int c) {
		this.cost = c;
	}
}


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

using namespace std;

typedef long long ll;

const int MX = 404;
const ll MOD = 998244353;

template <typename T> void add(T &x, const T &y)
{
	x = (x+y) % MOD;
}

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

ll qpow(ll x, ll t)
{
	ll ans = 1;
	while(t)
	{
		if(t & 1) ans = ans * x % MOD;
		x = x * x % MOD;
		t >>= 1;
	}
	return ans;
}

ll inv(ll x)
{
	return qpow(x, MOD-2);
}

ll fac[MX], faci[MX], ivx[MX];
ll f[MX][MX];
int A[MX], B[MX], sA[MX], sB[MX];
int n;

void init()
{
	fac[0] = 1;
	for(int i=1; i<MX; i++) fac[i] = fac[i-1] * i % MOD;
	faci[MX-1] = inv(fac[MX-1]);
	for(int i=MX-1; i>=1; i--) faci[i-1] = faci[i] * i % MOD;
	for(int i=1; i<MX; i++) ivx[i] = faci[i] * fac[i-1] % MOD;
}

void input()
{
	read(n);
	for(int i=1; i<=n; i++)
	{
		read(A[i]), sA[i] = sA[i-1] + A[i];
		read(B[i]), B[i]--, sB[i] = sB[i-1] + B[i];
	}
}

void print_coef(ll *s)
{
	for(int i=0; i<=4; i++) printf("%lld ", s[i]*fac[i]%MOD);
	putchar('\n');
}

void work()
{
	f[0][0] = MOD-1;
	for(int i=1; i<=n; i++)
	{
		for(int j=sA[i]; j>=A[i]; j--)
		{
			for(int a=sB[i]; a>=0; a--)
			{
				ll tmp = 1;
				for(int b=0; b<=B[i]&&b<=a; b++)
				{
					add(f[j][a], MOD*MOD - f[j-A[i]][a-b]*tmp%MOD*faci[b]);
					tmp = tmp * A[i] % MOD;
				}
			}
		}
	}
	ll ans = 0;
	for(int i=1; i<=sA[n]; i++)
		for(int j=0; j<=sB[n]; j++)
			add(ans, f[i][j] * fac[j] % MOD * qpow(inv(i), j+1) % MOD);
	printf("%lld\n", ans * sA[n] % MOD);
}

int main()
{
	init();
	input();
	work();
	return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

LL dp[210][210];

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

  int N;
  cin >> N;
  dp[0][0] = 1;
  REP(i,N){
	char c;
	cin >> c;
	if(c == 'U'){
	  REP(j,201){
		(dp[i+1][j+1] += dp[i][j]) %= MOD;
		(dp[i+1][j] += dp[i][j] * j % MOD) %= MOD;
	  }
	}
	else if(c == 'D'){
	  REP(j,201){
		if(j>0) (dp[i+1][j-1] += dp[i][j] * j * j % MOD) %= MOD;
		(dp[i+1][j] += dp[i][j] * j % MOD) %= MOD;
	  }
	}
	else{
	  REP(j,210) dp[i+1][j] = dp[i][j];
	}
  }
  cout << dp[N][0] << endl;

  return 0;
}

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

using namespace std;

int main() {
	int N, sum;
	cin >> N;
	sum = 0;
	int a = N;

	while (a > 0) {
		sum += a % 10;
		a /= 10;
	}
	if (N % sum == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <map>
using namespace std;

struct Edge {
  int dst, cost;
  Edge(int d, int c) : dst(d), cost(c) {}
};

int dist[222][222];
vector<Edge> graph[10];

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  int H, W, c, A;
  cin >> H >> W;
  for(int i = 0; i < 10; ++i)
    for(int j = 0; j < 10; ++j) {
      cin >> A;
      graph[i].emplace_back(j, A);
    }
  vector<vector<int>> dist(10, vector<int>(10, 1<<30));
  for(int s = 0; s < 10; ++s) {
    dist[s][s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.emplace(0, s);
    while(!pq.empty()) {
      int c = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      for(Edge e : graph[v]) {
        if(dist[s][e.dst] > dist[s][v] + e.cost) {
          dist[s][e.dst] = dist[s][v] + e.cost;
          pq.emplace(dist[s][e.dst], e.dst);
        }
      }
    }
  }
  
  int ans = 0;
  for(int i = 0; i < H; ++i)
    for(int j = 0; j < W; ++j) {
      cin >> c;
      if(c == -1) continue;
      ans += dist[c][1];
    }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);

int n, m;

void read()
{
	cin >> n >> m;
}

void solve()
{
	int total = 0;
	total += (m * 1900);
	total += (n - m) * 100;

	double prob_succ = 0;
	prob_succ = 1;
	for(int i = 0; i < m; i++)
		prob_succ = prob_succ / 2.0;

	cout << (int)(total / prob_succ) << endl;
}

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

	read();
	solve();
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if (a%b==0)return b;
    else return gcd(b,a%b);
}
int main()
{
    int k;
    cin>>k;
    long long int ans = 0;
    for (int a = 1;a<=k;a++){
        for (int b = 1;b<=k;b++){
            for (int c = 1;c<=k;c++){
                ans+=gcd(a,gcd(b,c));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int d, n, m, l, t, p;
pair<int, int> board[11], faucet[11];
int over[101] = {0};

double solve(int le, int ri, int bf, bool ch);

int main() {
  int i, j;
  cin >> d;
  for(int dd = 0; dd < d; ++dd) {
    cin >> n;
    for(i = 0; i < n; ++i)
      cin >> board[i].first >> board[i].second;

    cin >> m;
    for(i = 0; i < m; ++i)
      cin >> faucet[i].first >> faucet[i].second;
    cin >> l;
    for(i = 0; i < l; ++i) {
      cin >> p >> t;
      // cout << fixed << setprecision(7)
      // if(solve(0, 100, 50, 1) == 22.5)
      // cout << n << " " << board[i].first << " "
      //   << board[i].second << endl;
      cout << solve(0, 100, 50, 1) << endl;
      // for(j = 0; j < 101; ++j) cout << j << over[j] << "
      // ";  cout << endl;
      for(j = 0; j < 101; ++j) over[j] = 0;
    }
  }
  return 0;
}

double solve(int le, int ri, int bf, bool ch) {
  int i, wash = 0, sumover = 0;
  pair<int, int> maxh = make_pair(0, 0);
  //範囲内の一番大きい仕切りを探す
  for(i = 0; i < n; ++i)
    if(maxh.second < board[i].second &&
       le < board[i].first && board[i].first < ri)
      maxh = board[i];
  //範囲内の蛇口の水量の合計を求める
  for(i = 0; i < m; ++i)
    if(faucet[i].first > le && faucet[i].first < ri)
      wash += faucet[i].second;
  //あふれ出たものの合計を求める
  for(i = le; i <= ri; ++i) sumover += over[i];
  // cout << le << " " << ri << " " << bf << " " << sumover
  //    << endl;
  if(ch) {
    //一番高い仕切りを超えるかどうか(超えるならそのまま計算、越えなければ再帰)

    if(30 * (ri - le) * maxh.second <= t * wash + sumover) {
      if((double)(t * wash + sumover) / (30 * (ri - le)) >
         bf)
        return bf;
      return (double)(t * wash + sumover) /
             (30 * (ri - le));
    }
    else {
      if(le <= p && p <= maxh.first) {
        solve(maxh.first, ri, maxh.second, 0);
        return solve(le, maxh.first, maxh.second, 1);
      }
      else {
        solve(le, maxh.first, maxh.second, 0);
        return solve(maxh.first, ri, maxh.second, 1);
      }
    }
  }
  sumover += (double)t * wash - 30 * bf * (ri - le);
  if(sumover < 0) sumover = 0;
  if(le > 1) over[le - 1] += sumover;
  if(ri < 100) over[ri + 1] += sumover;
  return 0;
}


Measured memory_bytes: 3232
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d = map(int, readline().split())

if abs(c - a) <= d:
    bl = True
elif abs(b - a) <= d and abs(c - b) <= d:
    bl = True
else:
    bl = False
print("Yes" if bl else "No")


Measured memory_bytes: 3316
S=input()
T=input()

def match(S,T):
    for i in range(len(T)):
        if S[i]==T[i] or S[i]=='?':
            continue
        else:
            return False
    return True

if len(T)>len(S):
    print('UNRESTORABLE')
    exit()

S=S[::-1]
T=T[::-1]   
p=len(S)-len(T)+1
for i in range(p):
    sub = S[i:i+len(T)]
    if match(sub,T):
        S1=S.replace(sub,T,1).replace('?','a')
        print(S1[::-1])
        exit()
print('UNRESTORABLE')
        




Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main()
{
  int n,y;
  cin>>n>>y;
  int a=y/10000;
  for(int i=a;i>=0;i--){
    for(int j=0;j<=(y-10000*i)/5000;j++){
      int k=(y-10000*i-5000*j)/1000;
      if(k>=0&&i+j+k==n){
        cout<<i<<" "<<j<<" "<<k;
        return 0;
      }
    }
  }
  cout<<"-1 -1 -1";
  return 0;
}

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

#define mod 998244353
long long exp(long long taban, long long us) {
    long long carpan = taban;
    long long temp = us;
    long long res = 1;
    for(int i = 0;;i++){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
        if(temp == 0) break;
    }
    return res;
}
int main(){
	int n; cin>>n;
	ll arr[100005] = {};
	int maks = 0;
	forloop(n){
		int sayi; cin>>sayi;
		if( (i == 0 && sayi != 0) || arr[0] > 1){
			cout<<0;
			return 0;
		}
		arr[sayi]++;
		maks = max(maks, sayi);
	}
	ll res = 1;
	for(int i = 1; i <= maks; i++){
		res = (res * exp(arr[i-1], arr[i])) % mod;
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 1024
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

#include<unistd.h>
struct Buffer{
    enum { chunk = 1 << 16 };
    int idx;
    char buf[chunk];
    Buffer(){ init(); }
    void init(){ idx = 0; read(0, buf, chunk); }
    void check(){ if(idx == chunk){ init(); } }
    int next(){
        static char notDigits[256] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, 0,0,0,0,0,0,0,0,0,0,};
        int ret = 0, sign = 1;
        while(check(), notDigits[(int)buf[idx]]){ idx++; }
        if(check(), buf[idx] == '-'){ sign = -1; idx++; }
        while(check(), !notDigits[(int)buf[idx]]){ ret = ret * 10 + buf[idx++] - '0'; }
        return sign * ret;
    }
};
struct FastInput {
    Buffer buf;
    template <class T>
    FastInput& operator >> (T& num) { num = buf.next(); return *this; }
    void tie(int){ }
    template <class S, class T>
    friend FastInput& operator >> (FastInput& in, pair<S, T>& p){ return in >> p.first >> p.second; }
    template <class T>
    friend FastInput& operator >> (FastInput& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
};
FastInput fin;
#define cin fin

int accs[501][501];
int main(){
    int n, m, q;
    cin >> n >> m >> q;
    // vector<vector<int>> accs(n, vector<int>(n));
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        l--; r--;
        accs[0][r]++;
        accs[l + 1][r]--;
        // for(int i = 0; i <= l; i++){
        //     accs[i][r]++;
        // }
    }
    for(int j = 0; j < n; j++){
        for(int i = 1; i < n; i++){
            accs[i][j] += accs[i - 1][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 1; j < n; j++){
            accs[i][j] += accs[i][j - 1];
        }
    }
    for(int i = 0; i < q; i++){
        int p, q;
        cin >> p >> q;
        p--; q--;
        cout << accs[p][q] << '\n';
    }
}


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

#define fore(i,ii,iii) for(int i=ii;i<iii;i++)

const int N=1e5+15;
int n,dp[N],h[N];

int f(int x){
  if(x==0)return 0;
  if(x==1)return abs(h[1]-h[0]);
  if(dp[x-1]>=0)return dp[x-1];
  dp[x-1]=min(f(x-1)+abs(h[x]-h[x-1]),
              f(x-2)+abs(h[x]-h[x-2]));
  return dp[x-1];
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n; 
  fore(i,0,n){cin>>h[i];}
  memset(dp,-1,sizeof dp);
  cout<<f(n-1)<<endl;
}

Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

int main(){
	ll n,m;
	cin >> n >> m;
	if(n == 1){
		ll ret = 1;
		rep(i,m+1){
			ret *= 2;
			ret %= M;
		}
		cout << ret << endl;
		return 0;
	}
	
	static  ll dp[3002][3002] = {};
	dp[0][0] = 1;
	rep(i,m){
		rep(j,i+1){
			if(j>0)dp[i+1][j-1] += dp[i][j];
			dp[i+1][j] += dp[i][j]*2;
			if(j+1 <= n-2)dp[i+1][j+1] += dp[i][j];
		}
		rep(j,i+2){
			dp[i+1][j] %= M;
		}
	}
	
	static  ll dp2[3002][3002] = {};
	dp2[0][0] = 1;
	rep(i,m){
		rep(j,i+1){
			if(j>0)dp2[i+1][j-1] += dp2[i][j];
			dp2[i+1][j] += dp2[i][j]*2;
			if(j+1 <= n-1)dp2[i+1][j+1] += dp2[i][j];
		}
		rep(j,i+2){
			dp2[i+1][j] %= M;
		}
	}
	
	/*rep(i,m){
		rep(j,m)cout << dp[i][j] << " ";
		cout << endl;
	}*/
	
	//static ll dp2[3002][3002] = {};
	rep(i,3002){
		rep(j,3001){
			dp2[i][j+1] += dp2[i][j];
			dp2[i][j+1] %= M;
		}
	}
	
	ll POW[3002];
	POW[0] = 1;
	rep(i,3000){
		POW[i+1] = POW[i]*4;
		POW[i+1] %= M;
	}
	
	ll ret = 0;
	for(int x = 0 ; x <= m-1 ; x ++){
		for(int y = 2 ; x+y <= m-1 ; y ++){
			ll a = dp2[x][n-1]*dp[y-2][n-2]; a %= M;
			a *= POW[m-1-x-y]; a %= M;
			ret += a;
			//ret += dp2[x][n-1]*dp[y-2][n-2];
			ret %= M;
		}
	}
	ll _ret = 1;
	rep(i,m-1){
		_ret *= 4;
		_ret %= M;
	}
	_ret += 2*(M-ret); _ret %= M;
	cout << (_ret*4)%M << endl;
}

Measured memory_bytes: 141056
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define rf(i,a,b) for(ll i=a; i>=b; i--)
#define pb push_back
#define mp make_pair
#define show(a) for(auto el:a)cout<<el<<" "
#define ff first
#define ss second
#define ppair vector<pair<ll,ll>>
#define vec vector <ll> 
#define all(a) a.begin(),a.end()
#define mo 1000000007

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
     ll n,i,x;
     cin>>n>>x;
     ll c=1,s=0,l;
     fr(i,0,n)
     {
         cin>>l;
         s=s+l;
         if(s<x || s==x)
         {
             c++;
             
         }
         else
         break;
     }
    cout<<c;
     return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

int main(){
    int n;
    scanf("%d", &n);   
    ll T = 0, A = 0;
    for(int i=1;i<=n;i++){
        int t, a;
        scanf("%d%d", &t, &a);
        int g = __gcd(t, a);
        t /= g;
        a /= g;

        if(i == 1) T = t, A = a;
        else{
            ll d = max((T+t-1)/t, (A+a-1)/a);
            T = t*1ll*d;
            A = a*1ll*d;
        }
    }
    printf("%lld\n", A+T);
}

Measured memory_bytes: 3824
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
   int n;
   cin >> n;
   map<string,int> m;
   rep(i,n){
      string s;
      cin >> s;
      m[s]++;
   }
   int kind = 0;
   for (auto w :m){
      kind++;
   }
   cout << kind << endl;

}


Measured memory_bytes: 19236
n,m,q=map(int,input().split())
a=[[0 for _ in range(n+1)]for _ in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  a[r][l]+=1
for i in range(n+1):
  for j in range(n):
    a[i][j+1]+=a[i][j]
for i in range(n):
  for j in range(n+1):
    a[i+1][j]+=a[i][j]
for i in range(q):
  l,r=map(int,input().split())
  print(a[r][r]-a[r][l-1]-a[l-1][r]+a[l-1][l-1])

Measured memory_bytes: 18700
# O (T * log(S))
from bisect import bisect_left

S = list(input())
T = list(input())
# S = 'a' * (10 ** 5) + 'b'
# T = 'b' * (10 ** 5)
#条件を満たせるかを調べる
setS = set(S)
for t in T:
    if t not in setS:
        print (-1)
        exit()

lst = [[] for _ in range(26)]
for index, x in enumerate(S):
    lst[ord(x) - 97].append(index)

tmp = 0 #現在地
roop = 0
for t in T:
    tmp = bisect_left(lst[ord(t) - 97], tmp)
    if tmp == len(lst[ord(t) - 97]):
        roop += 1
        tmp = lst[ord(t) - 97][0] + 1
    else:
        tmp = lst[ord(t) - 97][tmp] + 1

# print (roop)
# print (tmp)
print (roop * len(S) + tmp)

Measured memory_bytes: 9056