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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 2e9;
const ld EPS = 1e-8;

typedef ll Weight;
typedef int Flow;

struct Edge {
  int src, dest, rev;
  Flow cap;
  Weight cost;
  bool operator < (const Edge &rhs) const {
    return cost > rhs.cost;
  }
  Edge(int s, int d) : src(s), dest(d) { ; }
  Edge(int s, int d, int c) : src(s), dest(d), cost(c) { ; }
  Edge(int s, int d, int r, Flow cp, Weight cst) : src(s), dest(d), rev(r), cap(cp), cost(cst) { ; }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

bool comp(const Edge &e1, const Edge &e2){
  return e1.cost < e2.cost;
}

pair<Weight, Edges> kruskal(Edges &es, int v){
  sort(ALL(es), comp);
  UnionFind uni(v);
  Edges mst;
  Weight res = 0;
  for(Edge e: es){
    if(!uni.findSet(e.src, e.dest)){
      uni.unionSet(e.src, e.dest);
      mst.push_back(e);
      res += e.cost;
    }
  }
  return make_pair(res, mst);
}

int main(){
  int N, M;
  cin >> N >> M;
  Edges es;
  REP(i,M) {
    int a, b, c;
    cin >> a >> b >> c; --a; --b;
    es.push_back(Edge(a, b, c));
    es.push_back(Edge(b, a, c));
  }

  pair<Weight, Edges> mst = kruskal(es, N);
  Graph g(N);
  for(Edge e: mst.second) {
    g[e.src].push_back(e);
    g[e.dest].push_back(Edge(e.dest, e.src, e.cost));
  }
  /*
  REP(i,N) {
    for(Edge e: g[i]) {
      cout << e.dest << " ";
    }
    cout << endl;
  }
  */

  vector<vector<int>> d(N, vector<int> (N, 0));
  REP(i,N) {
    queue<tuple<int,int,ll>> que;
    que.push(make_tuple(i, -1, 0));
    while(!que.empty()) {
      int curr, prev, cst;
      tie(curr, prev, cst) = que.front(); que.pop();
      d[i][curr] = max(d[i][curr], cst);
      for(Edge e: g[curr]) {
        if(e.dest == prev) continue;
        que.push(make_tuple(e.dest, curr, max((ll)cst, e.cost)));
      }
    }
  }
  /*
  REP(i,N){
    REP(j,N) cout << " " << d[i][j];
    cout << endl;
  }
  */

  int Q;
  cin >> Q;
  REP(q, Q) {
    int S, T;
    cin >> S >> T; --S; --T;
    ll res = mst.first - d[S][T];
    cout << res << endl;
  }
  return 0;
}



Measured memory_bytes: 83300
S = list(input())
cnt = 0
if S[0] == "A":
  cnt += 1
  del S[0]
if  "C" in S[1:-1]:
  cnt += 1
  S.remove("C")
if  "C" in S[1:-1]:
  cnt -= 1
  S.remove("C")
if ("".join(S)).islower():
  cnt += 1
if cnt == 3:
  print("AC")
else:
  print("WA")

Measured memory_bytes: 3064
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize,
        s: chars,
    }
    let mut tot: i64 = 0;
    for i in 0..n {
        for j in 1..min(i + 1, n - i) {
            if s[i] != s[i - j] && s[i] != s[i + j] && s[i - j] != s[i + j] {
                tot -= 1;
            }
        }
    }
    let mut r: i64 = 0;
    let mut g: i64 = 0;
    let mut b: i64 = 0;
    for i in 0..n {
        match s[i] {
            'R' => r += 1,
            'G' => g += 1,
            'B' => b += 1,
            _ => panic!(),
        }
    }
    puts!("{}\n", r * g * b + tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 2308
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd
readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]



def solve(S, T):
    res = []
    for i in range(len(S) - len(T) + 1):
        cc = S[:i] + T + S[i+len(T):]
        q = set([s for s,c in zip(S, cc) if s != c])
        if q == set(['?']) or q == set():
            res.append(cc.replace('?', 'a'))

    res.sort()
    if 0 < len(res):
        return res[0]

    return 'UNRESTORABLE'


def main():
    S = input()
    T = input()
    result = solve(S, T)
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main(){
    int n; cin >> n;
    int l[2*n];
    for(int i = 0; i < 2*n; i++){
        cin >> l[i];
    }
    sort(l,l+2*n);
    int ans = 0;
    for(int i = 0; i < 2*n-1; i+=2){
        ans += min(l[i], l[i+1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define u128 __int128
#define pb push_back

#define N 200010
#define MOD 1000000007


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
   cout.precision(10);

   ll n, k;
   cin >> n >> k;
   ll a[n];
   for (ll i = 0; i < n; ++i)
   {
      cin >> a[i];
   }

   ll b[n] = {}, c1[n] = {};
   for (ll i = 0; i < n; ++i)
   {
      ll c = 0;
      for(ll j = 0; j < n; ++j)
      {
         if(a[j] < a[i])
            c++;
      }
      b[i] = c;
      c = 0;
      for (ll j = i + 1; j < n; ++j)
      {
         if(a[j] < a[i])
            c++;
      }
      c1[i] = c;
   }

   ll sum = 0, p = 0;
   p = ((k * (k - 1) % MOD) * (MOD + 1) / 2) % MOD;
   for (ll i = 0; i < n; ++i)
   {
      sum = (p * b[i] % MOD + sum + k * c1[i] % MOD) % MOD;
   }
   cout << sum << "\n";
   return 0;	 
}

      // while(b)
      // {
      //    if(b & 1)
      //    {
      //       an = (an * a);
            
      //       if(an > 1e18) 
      //          an /= 1e18;
      //    }
      //    a = (a * a);
      //    if(a > 1e18)
      //       a /= 1e18;
      //    b >>= 1;
      // }


Measured memory_bytes: 256
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最小重量 """
    V = sum(price_list)
    dp_max = W+1
    dp = [dp_max] * (V + 1)
    dp[0] = 0   # 境界条件：　価値0 の時は重さは0

    for item in range(N):
        if single:
            S = reversed(range(price_list[item], V + 1))
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = min2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return max(price for price in range(V+1) if dp[price] <= W)


#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

print(knapsack_price(single=True))

Measured memory_bytes: 74368
import math

N, M = input().split()
N = int(N)
M = int(M)


def combinations_count(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))


if N <= 1 and M <= 1:
    print(0)
elif N <= 1:
    print(combinations_count(M))
elif M <= 1:
    print(combinations_count(N))
else:
    print(combinations_count(N) + combinations_count(M))


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

using namespace std;


     
#define ll long long int
#define ld long double


#define fr first
#define se second



#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) (int)v.size()
#define sunq(v) sort(all(v));v.resize(distance(v.begin(),unique(all(v))))


#define pb push_back
#define mp make_pair

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define emla(a, val) memset(a, val, sizeof(a))

#define easm(a, b) (a + b - 1)/b 


#define PI 3.141592653589793238
#define E  2.718281828459045235


ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a*b/gcd(a,b);}


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

const int N = 1e3 + 10, M = 1e9 + 7;

int n, m, dp[N][N];
char g[N][N];


bool valid(int x, int y){return x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.';}

int solve(int i, int j){
  if(!valid(i, j))return 0;
  if(i == n-1 && j == m-1)return 1;
  int &re = dp[i][j];
  if(re != -1)return re;
  int mx = 0;
  mx = (mx%M + solve(i + 1, j)%M)%M;
  mx = (mx%M + solve(i, j + 1)%M)%M;
  return re = mx;
}


int main(){
  //freopen("input.in", "r", stdin);
  //freopen("output.txt", "w", stdout);
  clock_t z = clock();
  scanf("%d%d", &n, &m);
  emla(dp, -1);
  for(int i = 0; i < n; i++)
    scanf("%s", g[i]);
  int d = solve(0, 0);
  printf("%d\n", d);
  debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
  /*
  *try tricky test cases:
    -bounds
    -integer overflow
    -small input (0, 1)
    -big input
    -random tests
  */
  return 0;
}

Measured memory_bytes: 5248
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>

using namespace std;

vector<pair<double, double> >  kochPoint(vector<pair<double, double> > points, int n){
    vector<pair<double, double> > newpoints;
    int points_n = points.size();
    for(int i=0; i<points_n-1; i++){
        pair<double, double> tmp1 = points[i];
        pair<double, double> tmp2 = points[i+1];
        double startx = (tmp2.first - tmp1.first)/3 + tmp1.first;
        double endx = 2*(tmp2.first - tmp1.first)/3 + tmp1.first;
        double starty = (tmp2.second - tmp1.second)/3 + tmp1.second;
        double endy = 2*(tmp2.second - tmp1.second)/3 + tmp1.second;
        double newx = cos(M_PI/3)*(endx - startx) - sin(M_PI/3)*(endy - starty) + startx;
        double newy = sin(M_PI/3)*(endx - startx) + cos(M_PI/3)*(endy - starty) + starty;
        newpoints.push_back(tmp1); 
        newpoints.push_back(make_pair(startx, starty));
        newpoints.push_back(make_pair(newx, newy));
        newpoints.push_back(make_pair(endx, endy));
        if(i==points_n-2) newpoints.push_back(tmp2);
    }
    
    return newpoints;
}


int main(){
    double p1, p2;
    int n;
    vector<pair<double, double> > points;

    points.push_back(make_pair(0, 0));
    points.push_back(make_pair(100, 0));

    cin >> n;

    for(int j=0; j<n; j++){
        points = kochPoint(points, n);
    }
    for(int i=0; i<points.size(); i++){
        pair<double, double> tmp = points[i];
        cout << fixed << tmp.first << setprecision(9) << " " << fixed << tmp.second << setprecision(9) <<  endl;
    }

}

Measured memory_bytes: 3300
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;

int n;
vll a,b,c;

ll bsearch1(int k){
    // 条件を満たす最大値を求める
    ll ok = 0;  //解が存在する値
    ll ng = n+1;//解が存在しない値

    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        if(a[mid] < k){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}

ll bsearch2(int k){

    // 条件を満たす最小を求める
    ll ok = n;  //解が存在する値
    ll ng = -1;  //解が存在しない値 

    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        if(k < c[mid]){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return n-ok;
}

/*----------------------------------------------------------------*/
signed main(){

    cin >> n;
    int v;
    rep(i,n){cin >> v;a.pb(v);}
    rep(i,n){cin >> v;b.pb(v);}
    rep(i,n){cin >> v;c.pb(v);}
    a.pb(-1);
    c.pb(INF);
    SORT(a);
    SORT(c);

    int ans = 0;
    rep(i,n){
        ans += bsearch1(b[i])*bsearch2(b[i]);
    }
    cout << ans << endl;
    

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://pakencamp-2019-day3.contest.atcoder.jp/tasks/pakencamp_2019_day3_c
// rm -r -f test;oj dl https://abc077.contest.atcoder.jp/tasks/arc084_a

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pr pair<int,int>
#define mod 1000000007
#define endl "\n"

int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}
int modinv(int a,int m=mod){ return power(a,m-2,m);}
int add(int a,int b,int m=mod){	int c=(a%m+b%m);	if(c>=m)	c-=m;	return c;}
int sub(int a,int b,int m=mod){	int c=(a%m-b%m);	if(c<0)		c+=m;	return c;}
int mul(int a,int b,int m=mod){	return (a*b)%m;}
//	x<<1 => x*2		x>>1 => x/2;	cout<<flush;
//	cout<<fixed<<setprecision(10)<<ans<<endl;


void solve()
{
	string s;
	cin>>s;
	s=s.substr(0,3);
	cout<<s<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int t=1;//cin>>t;
	for(int i=1;i<=t;i++){	solve();}
	return 0;
}

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

using ll = long long;

#define dbg(x) cerr << #x << " : " << x << "\n";

const int mod = (int)1e9+7;

ll modInverse(int a)
{
    ll f = 1;
    for(int i = 1; i <= a; i++) {
        f *= i;
        f %= mod;
    }
    int N = mod-2;
    ll res = 1, p = f;
    while(N) {
        if(N & 1) {
            res = res * p;
            res %= mod;
        }
        p = p * p;
        p %= mod;
        N /= 2;
    }
    return res % mod;
}

int main()
{
    int n, a, b;
    scanf("%d %d %d", &n, &a, &b);
    int N = n;
    ll res = 1, p = 2;
    while(N) {
        if(N & 1) {
            res = res * p;
            res %= mod;
        }
        p = p * p;
        p %= mod;
        N /= 2;
    }
    ll tmp = 1;
    for(int i = n; i > n - a; i--){
        tmp = tmp * i;
        tmp %= mod;
    }
    res -= (tmp*modInverse(a))%mod;
    res = (res + mod) % mod;
    tmp = 1;
    for(int i = n; i > n - b; i--) {
        tmp = tmp * i;
        tmp %= mod;
    }
    res -= (tmp*modInverse(b))%mod;
    res--;
    res = (res + mod) % mod;
    printf("%lld\n", res);
}


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please



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


	string S;
	cin >> S;

	if (stoi(S.substr(0, 4)) > 2019) co("TBD");
	else if (stoi(S.substr(5, 2)) > 4) co("TBD");
	else co("Heisei");

	Would you please return 0;
}

Measured memory_bytes: 256
//**PEACE BE UPON YOU**
// AZMAYEN FAYEK SABIL
// IUT CSE SWE-19

#include <iostream>
#include <bits/stdc++.h>

#include <cmath>
#include <string>
#include <algorithm>
using namespace std;


int main()

{
    int n,p;
    cin>>n>>p;

    for(int i=p;i>1;i--)
    {
        n--;
    }

    cout<<n;

    return 0;
}


Measured memory_bytes: 256
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
#include <cmath>
#include <math.h>
#include <array>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
#define DEBUG_VIS(x) cerr<<"vis "<<x<<endl;
#define DEBUG_REACH cerr<<"reach here"<<endl;
#define DEBUG_SEQ(x) cerr<<x<<" ";
#define SET_ZERO(x) memset(x,0,sizeof(x));
#define SET_NEGONE(x) memset(x,-1,sizeof(x));
#define SET_INF(x) memset(x,127,sizeof(x));
#define SET_NEGINF(x) memset(x,128,sizeof(x));
#define IS_INF(x) x < 2100000000
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
const int maxn = 1e6 + 10;
template <class T> T mymin(const T a,const T b){return a < b ? a : b;}
template <class T> T mymax(const T a,const T b){return a > b ? a : b;}
ll N,C;
ll dis[maxn],val[maxn],f[maxn],g[maxn],f1[maxn],g1[maxn];
ll sum1[maxn],sum2[maxn];

int main(){
    FAST_IO
    cin>>N>>C;
    ll ans = 0;
    for(int i = 1; i <= N; i++) cin>>dis[i]>>val[i];
    for(int i = 1; i <= N; i++) {
        sum1[i] = sum1[i - 1] + val[i];
        f[i] = sum1[i] - dis[i];
        f1[i] = max(f[i],f1[i - 1]);
        ans = max(ans,f[i]);
    }
    for(int i = N; i >= 1; i--) {
        sum2[i] = sum2[i + 1] + val[i];
        g[i] = sum2[i] - (C - dis[i]);
        g1[i] = max(g1[i + 1],g[i]);
        ans = max(ans,g[i]);
    }
    for(int i = 1; i <= N; i++) ans = max(ans,g1[i + 1] + f[i] - dis[i]);
    for(int i = 1; i <= N; i++) ans = max(ans,f1[i - 1] + g[i] - (C - dis[i]));
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 23552
// {{{ by unolight
#include <bits/stdc++.h>
#include <unistd.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define RALL(x) rbegin(x),rend(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

namespace { namespace unolight {
// Read Input
template<class T> void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( int64_t &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<class T, class... U> void R( T& head, U&... tail ) { _R(head); R(tail...); }
// Write Output
template<class T> void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
void _W( const int64_t &x ) { printf("%" PRId64,x); }
void _W( const double &x ) { printf("%.16f\n",x); }
void _W( const char &x ) { putchar(x); }
void _W( const char *x ) { printf("%s",x); }
template<class T> void _W( const vector<T> &x ) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W( const T& head, const U&... tail ) { _W(head); putchar(sizeof...(tail)?' ':'\n'); W(tail...); }

#ifdef UNOLIGHT
#include "dump.hpp"
#else
#define dump(...)
#endif

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}
// }}}


void main() {
    string s;
    cin >> s;
    int n=SZ(s);
    int ans=0; 
    int p=0,r=0;
    REP(i,n) {
      if ( p<r ) {
         p++;
         if ( s[i]=='g' ) ans++;
      } else {
         r++;
         if ( s[i]=='p' ) ans--;
      }
    }
    W(ans);
}

}} // {{{ main
int main() { unolight::main(); return 0; }
// }}}

Measured memory_bytes: 3860
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         int T = Integer.parseInt(infile.readLine());
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         for(int i=N; i <= M; i++)
            if(i%T == 0)
            {
               System.out.println("OK");
               return;
            }
         System.out.println("NG");
      }
   }

Measured memory_bytes: 32584
#include<iostream>
#include<iomanip>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <numeric>
typedef long long int ll;
using namespace std;

int main(){
	ll N,a,count,b;
	vector<ll> A;
	cin>>N;
	vector<ll> B(N+1,0);
	for(int i=0;i<N;i++){
		cin>>a;
		A.push_back(a);
		B[a]++;
	}
	b=*max_element(A.begin(),A.end());
	count=0;
	for(ll i=1;i<=b;i++){
		if(B[i]>1){
			count=count+B[i]*(B[i]-1)/2;
		}
	}
	for(ll i=0;i<A.size();i++){
		if(B[A[i]]>=2){
			cout<<count-(2*B[A[i]]-2)/2<<endl;
		}else{
			cout<<count<<endl;
		}
	}				
	return 0;
}

Measured memory_bytes: 5872
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    long long int n, t;
    long long int ti[200001];
    long long int ans = 0;
    cin >> n >> t;
    for (int i = 0; i < n; i++)
    {
        cin >> ti[i];
        if (0 < i)
        {
            if (ti[i] - ti[i - 1] < t)
                ans += ti[i] - ti[i - 1];
            else
                ans += t;
        }
    }
    ans += t;
    cout << ans << endl;
    return 0;
}

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

#define MAX 500000
#define INF INT_MAX

int A[MAX+1], L[MAX/2+1], R[MAX/2+1];
int cnt;

void merge(int n, int left, int mid, int right){
  int n1=mid-left;
  int n2=right-mid;

  for(int i=0; i<n1; i++) L[i]=A[left+i];
  for(int i=0; i<n2; i++) R[i]=A[mid+i];

  L[n1]=INF;
  R[n2]=INF;

  for(int i=0, j=0, k=left; k<right; k++){
    cnt++;
    
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
  }
}

void merge_sort(int n, int left, int right){
  int mid;
  
  if(left+1<right){
    mid=(left+right)/2;
    merge_sort(n, left, mid);
    merge_sort(n, mid, right);
    merge(n, left, mid, right);
  }
}

int main(void){
  int n;
  scanf("%d", &n);

  for(int i=0; i<n; i++) scanf("%d", &A[i]);
  merge_sort(n, 0, n);

  for(int i=0; i<n; i++){
    if(i) printf(" %d", A[i]);
    else printf("%d", A[i]);
  }
  printf("\n%d\n", cnt);
  
  return 0;
}



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

using namespace std;

template <class T>inline T updmax(T &a, T b) { return a = max(a, b); }
template <class T>inline T updmin(T &a, T b) { return a = min(a, b); }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int r;
	cin >> r;
	cout << 3*r*r << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  const double PI=3.14159265358979323846;
  //整数の時はint
  int a,b,m;
  double c;
  //文字の時はstring
  string s,t;
 
  cin>>s;
  cin>>t;
  int ans=0;
  for(int i=0;i<s.length();i++){
    if(s[i]!=t[i])ans=1;
  }
  if(ans==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl; 

 
  return 0;
}



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

int N, K;
long dp[100020];
vector<int> pillar;

long jump(int now){
    if(dp[now] != -1){
        return dp[now];
    }else if(now == N - 1){
        return 0;
    }
    long ans = 1e9;
    for(int i = now + 1; i <= now + K && i < N; i++){
        ans = min(ans, jump(i) + abs(pillar[i] - pillar[now]));
    }
    return dp[now] = ans;
}

int main(){
    cin >> N >> K;
    pillar.resize(N);
    for(int i = 0; i < N; i++){
        cin >> pillar[i];
    }
    for(int i = 0; i < 100020; i++){
        dp[i] = -1;
    }
    cout << jump(0) << endl;
}


Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  int minv;
  int maxv = -999999999;

  for(int i=0; i<n; i++){
    int r;cin>>r;
    if(i==0){
      minv=r;
      continue;
    }
    maxv = max(maxv,r-minv);
    minv = min(minv,r);
  }
  cout<<maxv<<endl;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
typedef long long ll;
typedef long double ld;
#define trace(x)  cerr << #x << ": " << x << endl;
const ll N=1e6+5;ll mod=998244353;
const ll NN=1e6+5; 

ll spf[N];ll ans[NN]={0};ll h[N]={0};

void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<N; i++) 
        {spf[i] = i;ans[i]=h[i];}
    for (ll i=4; i<N; i+=2) 
        {spf[i] = 2;ans[2]+=h[i];} 

    for (ll i=3; i<N; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (ll j=2*i; j<N; j+=i){ 
                if (spf[j]==j) 
                    {spf[j] = i;}ans[i]+=h[j];}
        } 
    }
    //for(ll i=0;i<N;i++)trace(spf[i]);
    return;
} 
int main()
{
	fast;
	ll n;cin>>n;ll g=0;std::vector<ll> a(n);
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];g=__gcd(a[i],g);h[a[i]]++;
	}
	if(g!=1)
	{
		cout<<"not coprime";return 0;
	}
	sieve();//cout<<"returned";
	ll f=1;
	for(ll i=2;i<NN;i++)if(ans[i]>1){f=0;break;}
	//trace(k);
	if(f)cout<<"pairwise coprime";
	else cout<<"setwise coprime";

}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010

ll N;

ll func(ll a, ll b) { return max(to_string(a).length(), to_string(b).length()); }

signed main()
{
    cin >> N;

    ll ans = to_string(N).length();
    for(ll i = 1; i <= 100010; ++i) {
        if(N % i == 0) { ans = min(ans, func(i, N / i)); }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
# Starting here
#define Pi 3.14159265
import math

def Sin(n):
    return math.sin(n*math.pi/180)

def Cos(n):
    return math.cos(n*math.pi/180)

a,b,ang=map(float,raw_input().split())
A=a*a
B=b*b
area=(0.5*a*b*Sin(ang))
C=A+B-(2*a*b*(Cos(ang)))
c=float(math.sqrt(C))
s=a+b+c
print round(area,5)
print round(s,5)
print round((area*2)/a,5)




Measured memory_bytes: 4808
#include <vector>
#include <iostream>
using namespace std; typedef long long int lint; typedef pair<lint, lint> plint; typedef pair<double long, double long> pld; typedef unsigned long long ulong;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
const lint mod = 1e9 + 7, INF = 1e18;
lint dx[8] = { 0, -1, 1, 0, 1, -1, 1, -1 }, dy[8] = { 1, 0, 0, -1, -1, -1, 1, 1 };

struct RollingHash {
	const ulong MASK30 = (1ULL << 30) - 1;
	const ulong MASK31 = (1ULL << 31) - 1;
	const ulong MOD = (1ULL << 61) - 1;
	const ulong MASK61 = MOD;

	vector<ulong> hashed, power;

	RollingHash(const string& s, ulong base) {
		int sz = SZ(s);
		hashed.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for (int i = 0; i < sz; i++) {
			power[i + 1] = mul(power[i], base);
			hashed[i + 1] = mul(hashed[i], base) + s[i];
			if (hashed[i + 1] >= MOD) hashed[i + 1] -= MOD;
		}
	}

	//乱数生成、main関数にコピペする
	void generate_base() {
		/*
		ulong base;
		{
			//乱数生成
			random_device seed_gen;
			mt19937 engine(seed_gen());
			uniform_real_distribution<> dist1(129, INT_MAX);
			base = dist1(engine);
		}*/
	}

	ulong get(int l, int r) const {
		ulong ret = hashed[r] + MOD - mul(hashed[l], power[r - l]);
		if (ret >= MOD) ret -= MOD;
		return ret;
	}

	//a*b mod 2^61-1を返す関数
	inline ulong mul(ulong a, ulong b) const {
		ulong u_a = a >> 31;//aの31bit以降
		ulong d_a = a & MASK31;//aの31bit未満
		ulong u_b = b >> 31;
		ulong d_b = b & MASK31;

		ulong mid = d_a * u_b + u_a * d_b;
		ulong u_mid = mid >> 30;
		ulong d_mid = mid & MASK30;
		return CalcMod(u_a * u_b * 2 + u_mid + (d_mid << 31) + d_a * d_b);
	}

	//mod 2^61-1を返す関数
	inline ulong CalcMod(ulong x) const {
		ulong u_x = x >> 61;
		ulong d_x = x & MASK61;
		ulong res = u_x + d_x;
		if (res >= MOD) res -= MOD;
		return res;
	}
};

string s, t;
int main() {
	cin >> s >> t;
	/*
	ulong base;
	{
		//乱数生成
		random_device seed_gen;
		mt19937 engine(seed_gen());
		uniform_real_distribution<> dist1(129, INT_MAX);
		base = dist1(engine);
	}*/
	RollingHash rh1(s, 10007), rh2(t, 10007);
	for (int i = 0; i + SZ(t) <= SZ(s); i++) {
		if (rh1.get(i, i + SZ(t)) == rh2.get(0, SZ(t))) {
			cout << i << endk;
		}
	}
}


Measured memory_bytes: 19816
n = int(input())
l = list(map(int,input().split()))

# print(l)

max_n = 0
i = 1
for s in l:
	if s <= max_n-2:
		print('No')
		break
	if s > max_n:
		max_n = s
	if i==n:
		print('Yes')
	i+=1

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

int main() {
    char c;
    cin >> c;

    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

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

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

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

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

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int DX[] = {0, 1, 0, -1};
const int DY[] = {-1, 0, 1, 0};


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

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


int sum(int n, int s, int i) {
	if (i == 10) {
		if (n == 0 && s == 0)
			return 1;
		else if (n != 0 || s != 0)
			return 0;
	} else {
		return sum(n, s, i + 1) + sum(n - 1, s - i, i + 1);
	}
}

int main(int argc, char const *argv[])
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, s;
	while(cin >> n >> s, n || s){
		cout << sum(n, s, 0) << endl;
	}

	return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define ll          long long int
#define ull         unsigned long long int
#define pb          push_back
#define pii         pair<int,int>
#define F           first
#define S           second
#define vi          vector<int>
#define vli          vector<ll>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define M_PI        3.14159265358979323846
#define mp          make_pair
#define sz(x)       (int)x.size()
#define matrix      vector<vector<ll>>
#define forn(i,a,b)  for(int i=a;i<b;i++)
#define eps 0.0000000001
#define all(a)      (a).begin(),(a).end()
#define ordered_set     tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 

const long long INF = (long long) 1e11+1;
const long long mod = (long long) 998244353 ;
const long long hell = (long long) 1000000007;


ll power(ll x,ll y)
{
  ll res=1;
  while(y>0){
    if(y%2) res=(x*res);
    x=(x*x);    
    y=y/2;
  }
  return res;
}

ll modinv(ll x){
  return power(x,hell-2);
}


void fastIO() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

ll gcd(ll a,ll b)
{
    while( b != 0)
	{
		ll  t = b;
		b= a %t;
		a = t;
	}
	return a;
}

bool chk(ll x,ll& ans){
    int sign=x<0?1:0;
    x=abs(x);
    
    for(ll i=0;i<=5000;i++){
        ll cur=i*i*i*i*i;
        if(cur>x)
        break;
        if(cur==x){
            ans=i;
            if(sign)
            ans*=-1;
            return true;
        }
    }
    return false;
}

void solve(){  
    ll x;
    cin>>x;
    
    for(ll i=0;i<=5000;i++){
        ll a=(i*i*i*i*i);
        ll b=a-x;
        ll ans;
        if(chk(b,ans)){
            cout<<i<<" "<<ans;
            return;
        }
    }
}

int main(){
   fastIO();
   int test;
   //cin>>test;
   test=1;    
   
   while(test--)
   solve();
}

///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1

/*
  For freq or prime factors

for(auto pri:prime){
  while(k%pri==0){
    pcnt[pri]++;
    k/=pri;
  }
}*/

// gcd of strings
/*
string getgcd(string s1,string s2){
    
    while(true){
        if(s1.length()<s2.length()){
            swap(s1,s2);
            continue;
        }
        if(s2.empty())
        return s1;
        
        if(s1.substr(0,s2.length())!=s2)
        return "";
        
        s1=s1.substr(s2.length());
    }
}
*/
/*
// for user defined DS hashmap and set
 
struct hash_pair{
      size_t operator()(const pair<int,pair<int,int>>& p) const{
          auto hash1=hash<int>()(p.F) ;
          auto hash2=hash<int>()(p.S.F) ;
          auto hash3=hash<int>()(p.S.S) ;
          return (hash1^hash2)^hash3;
      }  
};
struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator () (std::pair<T1, T2> const &pair) const
	{
		std::size_t h1 = std::hash<T1>()(pair.first);
		std::size_t h2 = std::hash<T2>()(pair.second);

		return h1 ^ h2;
	}
};
*/



Measured memory_bytes: 3608
N = int(input())
A = list(map(int,input().split()))
Ac = [0]*(N+2)
for i in range(N+1):
    Ac[i] = Ac[i-1]+A[i]

n = [0]*(N+1)
n[0] = 1
for d in range(1,N+1):
    n[d] = min(Ac[N]-Ac[d-1],2*(n[d-1]-A[d-1]))
if n[N]!=A[N]:
    ans = -1
else:
    ans = sum(n)
print(ans)

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

#define endl '\n'
#define rep(i,s,n)      for (int i = s ; i < n ; i++)
#define repp(i,s,n)    for (int i = s ; i <= n ;i++)
#define all(a)      a.begin(),a.end()
#define sz(v)    (int)v.size()
#define NumofDigits(n)    ((long long)log10(n)+1)
#define Unique(n)         (n).erase(unique(all(n)), (n).end())
#define test    int s ; cin >> s; while (s--)
#define readArr    int n ; cin >> n ; int arr[n]; rep(i,0,n)cin>>arr[i]
#define isvowel(a)   (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fast     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll ;

void readFromText ()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif // ONLINE_JUDGE
}

const double Pi = acos(-1.0);

bool countIF (int a){
    return a%4==0;
}

bool myFun (int i , int j ) {

}

const int MAX = 2e5 ;
int sum [MAX+1];
int freq [MAX+1];

int main()
{
    fast;
//    readFromText();
    int n , k ; cin >> n >> k; int arr[n]; rep(i,0,n)cin>>arr[i];
    sort(arr,arr+n);
    long long sum = 0 ;
    rep(i,0,k)sum+=arr[i];
    cout << sum << endl ;
    return 0;
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);

int main() {
    class BIT{
            ll n;
      		vector<ll> bitree;
        public:
        	BIT(unsigned long _n) : bitree(_n + 1, 0){
              n = _n;
            }
        	void add(ll id, ll x){
              while(id <= n){
                bitree[id] += x;
                id += id & -id;
              }
              return;
            }
        	ll sum(ll id){
              ll temp = 0;
              while(id > 0){
                temp += bitree[id];
                id -= id & -id;
              }
              return temp;
            }
      };
    cin>>N>>Q;
    vec c(N), l(Q), r(Q), ord(Q + 1), ans(Q);
    rep(i,N) {
        cin>>c[i];
        --c[i];
    }
    rep(i,Q){
        cin>>l[i]>>r[i];
        --l[i];
        ord[i] = i;
    }
    ord[Q] = Q;
    l.push_back(-1);
    r.push_back(-1);
    sort(ALL(ord), [&](int x, int y){
        return l[x] > l[y];
    });
    vector<set<ll>> col(N);
    BIT bit(N + 10);
    ll i = 0;
    Rrep(L, N){
        if(!col[c[L]].empty()){
            bit.add(*col[c[L]].begin(), 1);
        }
        col[c[L]].insert(L);
        while(l[ord[i]] == L){
            ll id = ord[i];
            ans[id] = r[id] - l[id] - bit.sum(r[id] - 1);
            ++i;
        }
    }
    rep(j,Q){
        cout<<ans[j]<<endl;
    }
}


Measured memory_bytes: 74156
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(snip_i, n) cin >> a.at(snip_i);
  vector<int> b(n);
  rep(snip_i, n) cin >> b.at(snip_i);
  ll pl2 = 0, mi = 0;
  rep(i, n){
    int diff = b.at(i) - a.at(i);
    if(diff < 0) mi += diff;
    if(diff >= 2) pl2 += diff/2;
  }
  if(pl2 + mi >= 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 384
N, K = map(int, input().split())

p = 0
for i in range(1, N+1):
    cnt = 0
    x = i
    while True:
        x *= 2
        cnt += 1
        if x >= K:
            break
    if i <= K-1:
        p += (1/N)*(1/2)**(cnt)
    else:
        p += 1/N

print(p)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define ll long long;
#define ld long double
#define pb push_back
const int mod=1e9+7;
const int mxN=2e6+3;

int main(){
    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    long long tmp1=a*c,tmp2=a*d,tmp3=b*c,tmp4=b*d;
    cout<<max(max(tmp1,tmp2),max(tmp3,tmp4))<<endl;
    return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>

int main(void)
{
	int a, b;
	int n;
	int i;
	int ca, cb;
	
	while (1){
		scanf("%d", &n);
		if (n == 0){
			break;
		}
		
		a = 0;
		b = 0;
		for (i = 0; i < n; i++){
			scanf("%d %d", &ca, &cb);
			
			if (ca > cb){
				a += ca + cb;
			}
			else if (ca < cb){
				b += ca + cb;
			}
			else {
				a += ca;
				b += cb;
			}
		}
		
		printf("%d %d\n", a, b);
	}
	
	return (0);
}

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

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine();
        var N = int.Parse(input);
        var S = Console.ReadLine().ToCharArray();
        
        var red = 0;
        var blue = 0;
        for (var i = 0; i < N; i++) {
            if (S[i] == 'R') {
                red++;
            } else {
                blue++;  
            }
        }
        
        if (red > blue) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }        
    }
}


Measured memory_bytes: 13140
#include<stdio.h>
#define min(x,y)(x>y?y:x)
int main(){
    int A,B,M;scanf("%d %d %d",&A,&B,&M);
    int a[100000];for(int i=0;i<A;i++)scanf("%d",&a[i]);
    int b[100000];for(int i=0;i<B;i++)scanf("%d",&b[i]);
    int x[100000],y[100000],c[100000];
    for(int i=0;i<M;i++)scanf("%d %d %d",&x[i],&y[i],&c[i]);

    int mina=999999,minb=999999;
    for(int i=0;i<A;i++){
        mina=min(mina,a[i]);
    }
    for(int i=0;i<B;i++){
        minb=min(minb,b[i]);
    }
    int ans=999999;
    ans=min(ans,mina+minb);
    for(int i=0;i<M;i++){
        ans=min(ans,a[x[i]-1]+b[y[i]-1]-c[i]);
    }
    printf("%d\n",ans);
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, Q;
  cin >> N >> Q;
  vector<vector<int>> G(N);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }

  vector<int> counter(N, 0);
  for (int i = 0; i < Q; i++) {
    int p, x;
    cin >> p >> x;
    counter[p - 1] += x;
  }

  queue<int> que;
  que.push(0);
  vector<bool> used(N, false);
  used[0] = true;
  while (!que.empty()) {
    int u = que.front();
    que.pop();

    for (int v : G[u]) {
      if (used[v]) continue;
      counter[v] += counter[u];
      que.push(v);
      used[v] = true;
    }
  }

  for (int i = 0; i < N; i++) {
    cout << counter[i] << (i == N - 1 ? '\n' : ' ');
  }
  return 0;
}


Measured memory_bytes: 15604
from collections import Counter

M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Measured memory_bytes: 22636
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MAX=100010;
const ll MOD=1e+9+7;
void add(ll &a,ll b){
  a+=b;
  if(a>=MOD){
    a-=MOD;
  }
}
int main(){
  string s;
  cin>>s;
  vector<vector<ll>>dp(MAX,vector<ll>(13,0));
  dp[0][0]=1;
  for(ll i=0;i<s.size();i++){
    for(ll j=0;j<13;j++){
      if(s.at(i)=='?'){
        for(ll k=0;k<10;k++){
          add(dp[i+1][(j*10+k)%13],dp[i][j]);
        }
      }else{
        ll k=s.at(i)-48;
        add(dp[i+1][(j*10+k)%13],dp[i][j]);
      }
    }
  }
  cout<<dp[s.size()][5]<<endl;

}

Measured memory_bytes: 16720
import java.util.*;
    public class Main{
    	public static void main(String[] args){
        	Scanner s  = new Scanner(System.in);
          	int n = s.nextInt();
          	int max = 0;
          	int[] Xs = new int[n];
          	int[] Ys = new int[n];
          	int[] sums = new int[n];
          	int[] diffs = new int[n];
          	for(int i = 0;i<n;i++){
            	Xs[i] = s.nextInt();
              	Ys[i] = s.nextInt();
              	sums[i] = Xs[i]+Ys[i];
              	diffs[i] = Xs[i]-Ys[i];
            }
          Arrays.sort(sums);
          Arrays.sort(diffs);
          int res1 = sums[n-1]-sums[0];
          int res2 = diffs[n-1] - diffs[0];
          System.out.println(Math.max(res1,res2));
        }
    }

Measured memory_bytes: 64336