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

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

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

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

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

struct camel { 
  ll k, d; 
  bool operator< (const camel &x) const { return k<x.k||(k==x.k&&d<x.d); };
  bool operator> (const camel &x) const { return k>x.k||(k==x.k&&d>x.d); };
};

int main() {
  ll T; cin >> T;
  rep(_,T) {
    ll N; cin >> N;
    vector<camel> pc, mc;
    ll result = 0;
    rep(i,N) {
      ll K, L, R; cin >> K >> L >> R;
      if (L>=R) { pc.push_back({K-1, L-R}); result += R; }
      else { mc.push_back({K, R-L}); result += L; }
    }
    sort(all(pc)); sort(all(mc));
    // for (auto x: pc) cout << x.k << "->" << x.d << endl;
    // cout << "~~~~~~~~~~~" << endl;
    // for (auto x: mc) cout << x.k << "->" << x.d << endl;

    priority_queue<ll> pqp; ll np = pc.size()-1;
    per(i,N) {
      while (np>=0&&pc[np].k==i) { pqp.push(pc[np].d); np--; }
      if (pqp.size()) { result += pqp.top(); pqp.pop(); }
    }

    priority_queue<ll> pqm; np = 0;
    rep(i,N) {
      while (np<mc.size()&&mc[np].k==i) { pqm.push(mc[np].d); np++; }
      if (pqm.size()) { result += pqm.top(); pqm.pop(); }
    }

    cout << result << endl;
    // cout << "-------------" << endl;
  }
  return 0;
}

Measured memory_bytes: 6856
import sys
sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for a, b, c in ABC:
        D[a-1][b-1] = c
        D[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    ans = M - sum(any(D[i][a-1] + c == D[i][b-1] for i in range(N)) for a, b, c in ABC)
    print(ans)


if __name__ == "__main__":
    main()

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

int n,w,t,e;
int main(){
	string s;
	cin >> s;
	rep(i,s.size()){
		if(s[i] == 'N') n++;
		if(s[i] == 'W') w++;
		if(s[i] == 'S') t++;
		if(s[i] == 'E') e++;
	}
	if((n != 0 && t == 0) || (n == 0 && t != 0) || (w != 0 && e == 0) || (w == 0 && e != 0)){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
    return 0;
}



Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define pb push_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define chmin(x,y) if(x>y)x=y
#define chmax(x,y) if(x<y)x=y
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll,vector<ll>,greater<ll>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
const ll inf=1001001001001001;
const int Inf=1001001001;
const int mod=1000000007;
int main(){
    int n,k;cin>>n>>k;
    string s;cin>>s;
    ll ans=0;
    vi sum(n);
    rep(i,n-1){
        if(s[i]=='A'&&s[i+1]=='C'){
            sum[i]=1;
        }
    }
    REP(i,1,n)sum[i]+=sum[i-1];
    rep(i,k){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a==0)cout<<sum[b-1]<<endl;
        else cout<<sum[b-1]-sum[a-1]<<endl;
    }
}

Measured memory_bytes: 1792
#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__) << "] "

using ll = long long;

const int mod = 1e9 + 7;

// O(N * K^2)

void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}
void sub_self(int& a, int b) {
    a -= b;
    if(a < 0) {
        a += mod;
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> dp(k + 1);
    // dp[i] - the number of ways such that we used i candies so far
    dp[0] = 1;
    for(int child = 0; child < n; ++child) {
        int up_to;
        scanf("%d", &up_to);
        vector<int> fake(k + 1); // combinatorics used to fast the process
        for(int used = k; used >= 0; --used) {
            int tmp = dp[used];
            int L = used + 1;
            int R = used + min(up_to, k - used);
            if(L <= R) {
                add_self(fake[L], tmp);
                if(R + 1 <= k) {
                    sub_self(fake[R+1], tmp);
                }
            }
            //~ for(int i = L; i <= R; ++i) {
                //~ add_self(dp[i], tmp);
            //~ }
        }
        int prefix_sum = 0;
        for(int i = 0; i <= k; ++i) {
            add_self(prefix_sum, fake[i]);
            add_self(dp[i], prefix_sum);
        }
    }
    printf("%d\n", dp[k]);
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {
    char s[4], t[4];
    int count = 0;
    scanf("%s", s);
    scanf("%s", t);
    for(int i = 0; i < 3; i++) {
        if(s[i] == t[i]) count++;
    }
    printf("%d\n", count);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
 
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
 
    vector<pair<int, int>> ud(n), du(n);
    ud[0] = make_pair(1, 0);
    du[0] = make_pair(-1, 0);
    for (int i = 1; i < n; ++i) {
        if (i % 2 == 0) {
            ud[i] = make_pair((i == n - 1 ? 1 : 2), i);   // up
            du[i] = make_pair((i == n - 1 ? -1 : -2), i); // down
        }
        else {
            ud[i] = make_pair((i == n - 1 ? -1 : -2), i); // down
            du[i] = make_pair((i == n - 1 ? 1 : 2), i);   // up
        }
    }
    sort(ud.begin(), ud.end());
    sort(du.begin(), du.end());
 
    ll sum_ud = 0, sum_du = 0;
    for (int i = 0; i < n; ++i) {
        sum_ud += ud[i].first * a[i];
        sum_du += du[i].first * a[i];
    }
 
    cout << max(sum_ud, sum_du) << endl;
 
    return 0;
}

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

ll vis[100001];
void dfs(vector<ll> v[],int e)
{
	vis[e]=1;
	for(auto itr: v[e])
	{
		if(!vis[itr])
		{
			dfs(v,itr);
		}
	}
}


int main()
{
	ll n;
	cin>>n;
	set<ll> s;
	for(ll i=0;i<n;i++)
	{
		ll p;
		cin>>p;
		s.insert(p);
	}
	if(s.size()==n)
		cout<<"YES";
	else
		cout<<"NO";
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
bool a[11];
vector <int> bulb[11];
int p[11];
void input()
{
    int k;
    for (int i = 1; i <= m; i++)
    {
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int s;
            cin >> s;
            bulb[i].push_back(s);
        }
    }
    for (int i=1; i<=m; i++)cin >> p[i];
}
bool check()
{
    for (int i=1;i<=m;i++)
    {
        int cnt=0;
        for (int j:bulb[i])
            if (a[j-1])cnt++;
        if (cnt%2!=p[i])return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    input();
    for(int i=0;i<(1<<n);i++)
    {
        for (int j=0;j<n;j++)a[j]=false;
        for(int j=0;j<n;j++)
            if(i&(1<<j)) a[j] = true;
        if (check())ans++;
    }
    cout<<ans <<endl;
}


Measured memory_bytes: 256
<?php
define('MOD', 10 ** 9 + 7);
list($n, $a, $b, $c) = ints();
init(2 * $n - 2);
$a = modDiv($a, 100 - $c); // 引き分けがない場合の高橋君が勝つ確率
$b = modDiv($b, 100 - $c); // 引き分けがない場合の青木君が勝つ確率
$c = modDiv($c, 100); // 引き分けになる確率
$ans = 0;
// 引き分けを含まずに回数の期待値を計算
for ($i = $n; $i <= 2 * $n - 1; ++$i) {
    $pa = modMul(modPow($a, $n), modPow($b, $i - $n));
    $pb = modMul(modPow($b, $n), modPow($a, $i - $n));
    $p = modMul($i, modMul(nCr2($i - 1, $n - 1), modAdd($pa, $pb)));
    $ans = modAdd($ans, $p);
}
// 引き分けも含んだ回数の期待値に修正
if ($c > 0) $ans = modDiv($ans, modSub(1, $c));
echo $ans;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}
// 足し算
function modAdd($x, $y)
{
    return ($x + $y) % MOD;
}

// 引き算
function modSub($x, $y)
{
    return ($x + MOD - $y) % MOD;
}

// 掛け算
function modMul($x, $y)
{
    return ($x * $y) % MOD;
}

// 割り算
function modDiv($x, $y)
{
    return modMul($x, modPow($y, MOD - 2));
}

// 累乗（繰り返し二乗法）
function modPow($n, $x)
{
    if ($x === 0) return 1;
    $res = (modPow($n, $x >> 1) ** 2) % MOD;
    if ($x % 2 === 1) $res = modMul($res, $n);
    return $res;
}

// 階乗
function modFac($n)
{
    if ($n === 0) return 1;
    return modMul($n, modFac($n - 1));
}

// 順列
function nPr($n, $r)
{
    if ($r === 0) return 1;
    return modMul(nPr($n, $r - 1), $n - $r + 1);
}

// 組み合わせ
function nCr($n, $r)
{
    $r = min($r, $n - $r);
    if ($r === 0) return 1;
    return modDiv(nPr($n, $r), modFac($r));
}

// 階乗、逆元を前処理
function init($n)
{
    global $fact, $ifact;
    $fact[0] = 1;
    for ($i = 1; $i <= $n; ++$i) $fact[$i] = modMul($fact[$i - 1], $i);
    $ifact[$n] = modDiv(1, $fact[$n]);
    for ($i = $n; $i >= 1; --$i)
        $ifact[$i - 1] = modMul($ifact[$i], $i);
}

// 順列（前処理）
function nPr2($n, $r)
{
    global $fact, $ifact;
    return modMul($fact[$n], $ifact[$n - $r]);
}

// 組み合わせ（前処理）
function nCr2($n, $r)
{
    global $fact, $ifact;
    return modMul(modMul($fact[$n], $ifact[$r]), $ifact[$n - $r]);
}


Measured memory_bytes: 34080
// package div2658.dpatcoder;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }

        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        }

        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 

    }

    public static void main(String[] args) {
        FastReader fs = new FastReader();
        int n = fs.nextInt();
        int[] h = new int[n];
        
        for (int i = 0; i < n; i++) {
            h[i] = fs.nextInt();
        }

        int[] dp = new int[n];

        dp[n-1] = 0;

        for (int i = n-2; i >= 0; i--) {
            int curr = Integer.MAX_VALUE;
            for (int k = 1; k <= 2; k++) {
                if (i+k < dp.length) {
                    curr = Math.min(curr, Math.abs(h[i] - h[i+k]) + dp[i+k]);
                }
            }
            dp[i] = curr;
        }

        System.out.println(dp[0]);

    }

}


Measured memory_bytes: 42632
N, K = map(int, input().split())
xs = list(map(int, input().split()))

cost = 10**9
for i in range(N-K+1):
    d1 = abs(xs[i])
    d2 = abs(xs[i+K-1])
    if xs[i] * xs[i+K-1] <= 0:
        cost = min(cost, 2 * min(d1, d2) + max(d1, d2))
    else:
        cost = min(cost, max(d1, d2))

print(cost)

Measured memory_bytes: 14532
a,b,c,d,e,f = map(int,input().split())

water = set()
for i in range(f//(100*a)+1):
    for j in range(f//(100*b)+1):
        g = 100*a*i+100*b*j
        if g <= f and g != 0:
            water.add(g)

max_con = 0
max_water = min(100*a,100*b)
max_suger = 0

for w in water:
    suger = set()
    for i in range((f-w)//c+1):
        for j in range((f-w)//d+1):
            if i*c+j*d <= f-w:
                suger.add(i*c+j*d)
    for s in suger:
        if w//100*e >= s:
            con = 100*s/(w+s)
            if con > max_con:
                max_con = con
                max_water = w
                max_suger = s

print(max_water+max_suger,max_suger)

Measured memory_bytes: 3232
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>


using namespace std;



int main(){
    int a,b,x;
    static double conv = 180.0000/3.14159265358979; // (double)
    cin >> a >> b >> x;
    if(2*x > a*a*b){
        double p=(double)(2*(a*a*b-x));
        printf("%.10lf",atan2(p, (double)a*a*a) * conv);
    }else{
        printf("%.10lf",atan2((double)(a*b*b), (double)(2*x)) * conv);
    }
    return 0;
}


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

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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    map<int, int, greater<int>> mp;
    rep(i, M){
        int b, c;
        cin >> b >> c;
        mp[c] += b;
    }
    priority_queue<int> p_que;
    for(auto p : mp){
        while(p.second != 0 && p_que.size() < N){
            p_que.push(p.first);
            p.second--;
        }
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    rep(i, N){
        if(a[i] < p_que.top() && !p_que.empty()){
            ans += p_que.top();
            p_que.pop();
        }else{
            ans += a[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8956
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;
    cin >> n;
    vector <long long> qw (n);
    for (int i=0; i<n; ++i)
        cin >> qw[i];
    long long t=0;
    for (int i=1; i<n; ++i)
    {
        if (qw[i-1]>qw[i])
        {
            t+=qw[i-1]-qw[i];
            qw[i]=qw[i-1];
        }
    }
    cout << t << endl;
}


Measured memory_bytes: 4748
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
     
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        while(true){
            try{
                StringTokenizer st=new StringTokenizer(str," ");
                int sum=Integer.parseInt(st.nextToken())+Integer.parseInt(st.nextToken());
                System.out.println(String.valueOf(sum).length());
                str=br.readLine();
            }catch(Exception e){System.exit(0);}
        }
    }
     
}

Measured memory_bytes: 24552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
const ll INF = 1ll << 60;
int a, b, q;
ll s[maxx], t[maxx], dd;

/*int solve1(ll x) {
	ll y = s[a];
	int n = a;
	int l = 1, r = n, ans1 = n + 1, ans2 = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(x <= s[mid]) r = mid - 1, ans1 = mid;
		else l = mid + 1;
	}
	l = 1, r = n;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(y >= s[mid]) l = mid + 1, ans2 = mid;
		else r = mid - 1;
	}
	return ans2 - ans1 + 1;
}

int solve2(ll x) {
	ll y = t[b];
	int n = b;
	int l = 1, r = n, ans1 = n + 1, ans2 = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(x <= t[mid]) r = mid - 1, ans1 = mid;
		else l = mid + 1;
	}
	l = 1, r = n;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(y >= t[mid]) l = mid + 1, ans2 = mid;
		else r = mid - 1;
	}
	return ans2 - ans1 + 1;
}*/

int main() {
	scanf("%d %d %d", &a, &b, &q);
	for(int i = 1; i <= a; i++) scanf("%lld", &s[i]);
	for(int i = 1; i <= b; i++) scanf("%lld", &t[i]);
	s[0] = s[1], t[0] = t[1];
	s[a + 1] = s[a], t[b + 1] = t[b];
	while(q--) {
		scanf("%lld", &dd);
		//int cnt1 = solve1(dd); //s中有pos1个比dd大的
		//int cnt2 = solve2(dd); //t中有pos2个比dd大的
		int cnt1 = lower_bound(s + 1, s + a + 1, dd) - s;
		cnt1 = a - cnt1 + 1;
		int cnt2 = lower_bound(t + 1, t + b + 1, dd) - t;
		cnt2 = b - cnt2 + 1;
		ll res = 0;
		ll ans1 = abs(dd - s[a - cnt1]);
		ll ans2 = abs(dd - s[a - cnt1 + 1]);
		ll res1 = abs(s[a - cnt1] - t[b - cnt2]);
		ll res2 = abs(s[a - cnt1 + 1] - t[b - cnt2]);
		res = min(ans1 + res1, ans2 + res2);
		ans1 = abs(dd - s[a - cnt1]);
		ans2 = abs(dd - s[a - cnt1 + 1]);
		res1 = abs(s[a - cnt1] - t[b - cnt2 + 1]);
		res2 = abs(s[a - cnt1 + 1] - t[b - cnt2 + 1]);
		ll tmp1 = min(ans1 + res1, ans2 + res2);
		res = min(res, tmp1);
		ans1 = abs(dd - t[b - cnt2]);
		ans2 = abs(dd - t[b - cnt2 + 1]);
		res1 = abs(t[b - cnt2] - s[a - cnt1]);
		res2 = abs(t[b - cnt2 + 1] - s[a - cnt1]);
		ll tmp2 = min(ans1 + res1, ans2 + res2);
		res = min(res, tmp2);
		ans1 = abs(dd - t[b - cnt2]);
		ans2 = abs(dd - t[b - cnt2 + 1]);
		res1 = abs(t[b - cnt2] - s[a - cnt1 + 1]);
		res2 = abs(t[b - cnt2 + 1] - s[a - cnt1 + 1]);
		ll tmp3 = min(ans1 + res1, ans2 + res2);
		res = min(res, tmp3);
		cout << res << endl;
	}
}

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

using namespace std;

const int N = 16;

int n, a[N][N];
long long f[1 << N];
long long val[1 << N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
    memset(f, -0x3f, sizeof(f)); f[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector <int> vec;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) vec.push_back(i);
        }
        
        for (int i = 0; i < vec.size(); i++) {
            for (int j = i + 1; j < vec.size(); j++) {
                val[mask] += a[vec[i]][vec[j]];
            }
        }
    }
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            f[mask] = max(f[mask], f[mask ^ submask] + val[submask]);
        }
    }
    
    cout << f[(1 << n) - 1];
    return 0;
}

Measured memory_bytes: 1280
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define reps(x, c) for (auto x : c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair((a), (b))
#define pl pair<ll, ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cerr << #x "=" << (x) << "\n"
#define dbgv(x) \
    cerr << #x << "\n"; \
    reps(y, x) { cerr << y << " "; } \
    cerr << "\n"

int main() {
    vector<int> a(5);
    rep(i, 5) { cin >> a[i]; }
    int k;
    cin >> k;

    rep(i, 5) {
        FOR(j, i, 5) {
            if (a[j] - a[i] > k) {
                cout << ":(" << endl;
                return 0;
            }
        }
    }

    cout << "Yay!" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll getMaxscoreForPlayerOne(vector<ll> inp,vector<ll> runningSum,int n) {
	ll res=0;
	vector<vector<ll>> dp(n,vector<ll>(n,0));
	for(int i=0;i<n;i++)dp[i][i]=inp[i];
	for(int size=2;size<=n;size++) {
		for(int i=0;i<n-size+1;i++) {
			ll subSequenceSum=runningSum[size+i]-runningSum[i];
          	dp[i][size+i-1]=max(subSequenceSum-dp[i][size+i-2],subSequenceSum-dp[i+1][size+i-1]);
		}
	}
	res=dp[0][n-1];
	return res;
}

ll getScoreDifference(vector<ll> inp,int n) {
	ll res=0;
	vector<ll> runningSum(n+1,0);
	for(int i=1;i<n+1;i++) {
		runningSum[i]=runningSum[i-1]+inp[i-1];
	}
	res=getMaxscoreForPlayerOne(inp,runningSum,n);
	res=res-(runningSum[n]-res);
	return res;
}

int main() {
	int n=0;
	cin>>n;
	vector<ll> inp(n,0);
	for(int i=0;i<n;i++) cin>>inp[i];
	cout<<getScoreDifference(inp,n)<<endl;
	return 0;
}


Measured memory_bytes: 73636
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cmath>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;

int main() {
	long long int n;
	cin >> n;
	vector<long long int> v(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<long long int> res(n, 0);
	long long int s = accumulate(v.begin(), v.end(), (long long int)0);
	long long int base = (1 + n) * n / 2;
	if (s % base != 0) {
		cout << "NO" << endl;
		return 0;
	}
	long long int nn = s / base;
	if (nn - (v[0] - v[n - 1]) < 0 || (nn - (v[0] - v[n - 1])) % n != 0) {
		cout << "NO" << endl;
		return 0;
	}
	res[0] += (nn - (v[0] - v[n - 1])) / n;
	for (int i = 1; i < n; i++) {
		int diff = v[i] - v[i - 1];
		if (nn - diff < 0 || (nn - diff) % n != 0) {
			cout << "NO" << endl;
			return 0;
		}
		res[i] += (nn - diff) / n;
	}
	if (accumulate(res.begin(), res.end(), 0) != nn) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	}
}






Measured memory_bytes: 4844
#include <bits/stdc++.h>
using namespace std;
#define ALL(a)  (a).begin(),(a).end()
int main() {
  long N;
  cin>>N;
  vector<long> a(N);
  for(int i=0;i<N;i++) cin>>a[i];
  vector<long> b(100005);
  for(int i=0;i<N;i++) b[a[i]]++;
  for(int i=0;i<100005;i++){
    if(b[i]%2==1){
      b[i]=1;
    }
    else if(b[i]>0&&b[i]%2==0){
      b[i]=2;
    }
  }
  int one=0,two=0;
  for(int i=0;i<100005;i++){
    if(b[i]==1) one++;
    if(b[i]==2) two++;
  }

  int ans=0;
  if(two%2==0) ans=one+two;
  else ans=one+two-1;
  cout<<ans<<endl;


}


Measured memory_bytes: 1920
from operator import itemgetter
from heapq import heappush, heappop, heapify

N = int(input())
xy = sorted([list(map(int, input().split())) + [i] for i in range(N)])
G = [[] for i in range(N)]
for i in range(N-1):
  a,b = xy[i][2], xy[i+1][2]
  c = xy[i+1][0]-xy[i][0]
  G[a].append((b,c))
  G[b].append((a,c))
xy.sort(key = itemgetter(1))
for i in range(N-1):
  a,b = xy[i][2], xy[i+1][2]
  c = xy[i+1][1]-xy[i][1]
  G[a].append((b,c))
  G[b].append((a,c))

used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Measured memory_bytes: 126808
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    int a,b,d,r;
    double x,y,f;
    cin >> a >> b;
    x = a;
    y = b;
    d = a / b;
    r = a % b;
    f = x / y;
    printf("%d %d %.5f\n",d,r,f);
    return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long qq(long long x,long long y){
    if(y==0){
        return 1;
    }
    else if(y%2==0){
        return qq(x*x%mod,y/2);
    }
    else{
        return x*qq(x,y-1)%mod;
    }
}
int main(){
    long long m,n;
    cin>>m>>n;
    cout<<qq(m,n)<<endl;
    return 0;
}


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



int main()
{
int N;
cin>>N;
vector<int>d(N);
for(int i=0;i<N;i++)
{cin>>d[i];}

sort(d.begin(),d.end());
cout<<d[N/2]-d[N/2-1]<<endl;

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mp make_pair
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1LL << 30;
const ll LINF = 1LL << 60;
const double eps = 1e-9;
const ll MOD = 1000000007LL;
template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
};
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
};
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    vector<string> s(3);
    vector<int> id(3);
    for(int i = 0; i < 3; i++) {
        cin >> s[i];
    }
    int t = 0;
    while(1) {
        if(id[t] >= s[t].length()) {
            if(t == 0) {
                cout << 'A' << endl;
            } else if(t == 1) {
                cout << 'B' << endl;
            } else {
                cout << 'C' << endl;
            }
            break;
        }
        id[t]++;
        if(s[t][id[t] - 1] == 'a') {
            t = 0;
        } else if(s[t][id[t] - 1] == 'b') {
            t = 1;
        } else {
            t = 2;
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int n, m; cin >> n >> m;
    vector<string> lis(n);
    REP(i, 0, n){cin >> lis[i];}
    vector<int> al(26, 0);
    REP(i, 0, n){
        REP(l, 0, m){
            al[(lis[i][l] - 'a')]++;
        }
    }
    int c4 = 0, c2 = 0, c1 = 0;
    c4 = (n - (n % 2)) / 2 * (m-(m%2)) / 2;
    c2 = (n % 2) *  (m-(m%2)) / 2 + (m % 2) *  (n-(n%2)) / 2;
    c1 = (n%2) * (m%2);
    int count4 = 0, count2 = 0;
    REP(i, 0, 26){
        while(al[i] >=4 && c4 > count4){
            al[i] -= 4;
            count4++;
        }
    }
    REP(i, 0, 26){
        while(al[i] >=2 && c2 > count2){
            al[i] -= 2;
            count2++;
        }
    }
    if(c4 == count4 && c2 == count2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main() {
    long long n;
    cin >> n;
    long long ans =0;
    if(n%2==0){
        for(long long i=10; i<=1e18+1; i*=5){
            ans += n/i;
        }
        cout << ans << endl;
    }
    else{
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
int main(void)
{
	char s[101], t[101];
	int n, ls, lt;
	std::cin >> n >> s >> t;
	ls = std::strlen(s);
	lt = std::strlen(t);
	for(int i = std::max(ls - lt, 0); i != ls; i++){
		if(i + lt < n) continue;
		bool flg = true;
		for(int j = i; j != ls; j++){
			if(s[j] != t[j - i]){
				flg = false;
				break;
			}
		}
		if(flg){
			std::cout << i + lt << std::endl;
			return 0;
		}
	}
	std::cout << std::max(ls + lt, n) << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using ll = long long;
int main(){
    char a;
    cin >> a;
    if (isupper(a))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }
}

Measured memory_bytes: 3620
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
	input!{
    	a: i32,
        b: i32,
    };
    if (a * b) % 2 == 0 {
    	println!("Even");
    } else {
    	println!("Odd");
    }
}

Measured memory_bytes: 4352
#include<stdio.h>
#include<string.h>

void judgecount(char large, char small , char s[]);

int main (void)
{
	char s;
	int count[26];
	
	for(int i = 0 ; i < 26 ; i++)
	{
		count[i] = 0 ;
	}
	
	while(scanf("%c",&s)!=EOF)
    {
    	if(s >= 'A' && s <= 'Z')
    	{
    		count[s-'A']++;
    	}
    	else if(s >= 'a' && s <= 'z')
    	{
    		count[s-'a']++;
    	}
    }
	
	for(int i = 0 ; i < 26 ; i++)
	{
		printf("%c : %d\n",'a' + i ,count[i]);
	}
	
	return 0;
}


Measured memory_bytes: 2140
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  vi v(n);
  rep(i, n) cin >> v[i];
  //vi a(100001), b(100001);
  vector<pair<int, int>> a(100001, make_pair(0, 0)), b(100001, make_pair(0, 0));
  rep(i, 100001){
    a[i].second = i;
    b[i].second = i;
  }
  for(int i = 0; i < n; i += 2) a[v[i]].first++;
  for(int i = 1; i < n; i += 2) b[v[i]].first++;
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  sort(b.begin(), b.end());
  reverse(b.begin(), b.end());
  if(a[0].second == b[0].second){
    if(a[1].first > b[1].first){
      cout << n - a[1].first - b[0].first << endl;
    }else{
      cout << n - a[0].first - b[1].first << endl;
    }
  }else{
    cout << n - a[0].first - b[0].first << endl;
  }
}

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

typedef long long LL;
const int MO=1e9+7;

// a+2b=X
// 2a+b=Y
// 2a+4b=2X
// 3b=2X-Y -> b
// a=X-2b

LL qp(LL a,LL n)
{
	LL ans=1;
	while(n)
	{
		if(n&1) ans=ans*a%MO;
		a=a*a%MO;
		n>>=1;
	}
	return ans;
}

// (a+b)!/a!/b!

int main()
{
	LL x,y;
	cin>>x>>y;
	LL b=2*x-y;
	if(b<0||b%3)
	{
		printf("0\n");
		return 0;
	}
	b/=3;
	LL a=x-2*b;
	if(a<0)
	{
		printf("0\n");
		return 0;
	}
	LL ans=1;
	LL tmp=1;
	for(int i=1;i<=(a+b);i++)
		ans=ans*i%MO;
	for(int i=1;i<=a;i++)
		tmp=tmp*i%MO;
	for(int i=1;i<=b;i++)
		tmp=tmp*i%MO;
	cout<< (ans*qp(tmp,MO-2)%MO) <<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;
int main(){
long long int A, B, C, D ,E ,F, N , K;
long long V[10000000] = {};
long long G[10000000] = {};
string S,Sa,Sb,Sc;
bool ans = true;
A = 1;
cin >> N >> K;
for(int i = 0;i < N;i++){
if(A * 2 - A < K)A *= 2;
else A += K;
}
cout << A << endl;
return 0; 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a[250],s=0;
int main(){
	cin>>n;
	for(int i=1;i<=n*2;i++)cin>>a[i];
	sort(a+1,a+1+2*n);
	for(int i=1;i<=n;i++)s+=a[i*2-1];
	cout<<s<<endl;
}

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

int main(void){
  while(1){
    int H,W;
    cin>>H>>W;
    if(H==0&&W==0)break;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(i==0||i==H-1||j==0||j==W-1)cout<<"#";
        else cout<<".";
      }cout<<endl;
    }
    cout<<endl;
  }
}


Measured memory_bytes: 3084
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*n

    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return 

        if self.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def are_same(self,x,y):
        return self.find(x)==self.find(y)

    def element_count(self,x):
        x=self.find(x)
        return -self.parents[x]

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    uf=UnionFind(n)
    for i in range(m):
        x,y,z=map(int,readline().split())
        x-=1
        y-=1
        uf.union(x,y)
    print(uf.group_count())

if __name__=="__main__":
    main()

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

int main()
{
    int n,m;
    ll x,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        q.push(x);
    }
    for(int i=1;i<=m;i++)
    {
        int t=q.top();
        q.pop();
        t/=2;
        q.push(t);
    }
    while(!q.empty())
    {
        sum+=q.top();
        q.pop();
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;
// #define int long long
mt19937 rnd(time(0));
typedef long long ll;
typedef long double ld;

// #define _GLIBCXX_DEBUG
#define f first
#define s second
#define pb push_back
#define pii pair<int, int> 
#define vi vector<int>
#define int ll

void solve(){
	int h, w;
	cin >> h >> w;
	if (h == 1 || w == 1)
		cout << 1 << endl;
	else	
		cout << (h + 1) / 2 * ((w + 1) / 2) + h / 2 * (w / 2) << endl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	while(t--){
		solve();
	}
	
	return 0;
}
	

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  vector<double> Ainv(N);
  rep(i, N) Ainv[i] = 1.0/A[i];
  double sum = 0;
  rep(i, N) sum += Ainv[i];
  cout << fixed << setprecision(5) << 1/sum << endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8

import heapq

def dj(adjm, start):
    n = len(adjm)
    d = [float("inf")] * n
    d[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while(q):
        td, v = heapq.heappop(q)
        for k in adjm[v].keys():
            nd = td + adjm[v][k]
            if d[k] > nd:
                d[k] = nd
                heapq.heappush(q, (nd, k))
    return d


def main():
    n = int(input())
    # 隣接行列
    adjm = [{} for _ in range(n)]
    for i in range(n):
        vdata = list(map(int, input().split()))
        for j in range(vdata[1]):
            v, c = vdata[j * 2 + 2], vdata[j * 2 + 3]
            adjm[i][v] = c
    ans = dj(adjm, 0)
    for i, d in enumerate(ans):
        print(i, d)


if __name__ == "__main__":
    main()



Measured memory_bytes: 49796
#include <stdio.h>


int main(){

  int n, s, z, i, j, max, min;

  while(1){

    scanf("%d", &n);

    if(n == 0)
      break;

    max = 0;
    min = 500;

    for(i = 0;i < n;i++){

      z = 0;

      for(j = 0;j < 5;j++){
	scanf("%d", &s);
	z += s;
      }
      
      if(max < z){
	max = z;
      }

      if(min > z){
	min = z;
      }

    }

    printf("%d %d\n", max, min);
    
  }

  
  return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<math.h>
using namespace std;
int main(void){
    double n, y, b, r, t; 
    for(int x=0;x<100;x++){
    cin >> n;if(n==0){return 0;}
    cin >> y;double sum = 0,ans = 0;
    for(int h = 0; h < n; h++){
        cin >> b >> r >> t;
        if(t == 1){
          if(sum < 1 + y * r / 100){
             ans = b;
             sum = 1 + y * r / 100;
          }
        }
        if(t == 2){
          if(sum < pow((1 + r / 100), y)){
             ans = b;
             sum = pow((1 + r / 100), y);
          }
        }
    }
  cout << ans << endl;
    }
}



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

using E = System.Linq.Enumerable;

public class Program
{
    const long Mod = (long)1e9 + 7;

    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());

        var dp = new (long Both, long One, long None)[n + 2];
        dp[0] = (0, 0, 1);
        for (int i = 1; i < dp.Length; ++i)
        {
            var x = dp[i - 1];
            x.Both *= 10; x.Both %= Mod;
            x.Both += x.One; x.Both %= Mod;
            x.One *= 9; x.One %= Mod;
            x.One += x.None * 2 % Mod; x.One %= Mod;
            x.None *= 8; x.None %= Mod;
            dp[i] = x;
        }

        Console.WriteLine(dp[n].Both);
    }
}


Measured memory_bytes: 50672
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

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

    ll X, Y;
    while (cin >> X >> Y) {
        int ans = 1;
        while (X*2 <= Y) {
            X *= 2;
            ans++;
        }
        cout << ans << endl;
    }
}


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

int main() {
    long W,H,x,y;
    cin>>W>>H>>x>>y;

    cout<<double(W)*double(H)/2<<" "<<(x+x==W&&y+y==H)<<endl;
    //printf("%lf %d\n", double(W)*double(H) / 2, x + x == W&&y + y == H);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	string S;

	cin >> S;

	int ans[2]={};
	char c[2]={'0','1'};
	for(int i=0;i<S.size();i++)
	{
		if(S[i]!=c[i%2])ans[0]++;
		if(S[i]!=c[1-(i%2)])ans[1]++;
	}

	cout << min(ans[0],ans[1]) << endl;

	return 0;
}



Measured memory_bytes: 512
#include <stdio.h>

long long max(long long a,long long b){
  if(a > b){
    return a;
  }
  return b;
}

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

  long long w[N], v[N];
  for (int i = 0; i < N; i++) {
    scanf("%lld%lld", &w[i], &v[i]);
  }

  long long dp[W+1];
  for (int i = 0; i <= W; i++) {
    dp[i] = 0;
  }

  for (int i = 0; i < N; i++) {
    for (int j = W; j >= w[i]; j--) {
      dp[j] = max(dp[j-1], dp[j-w[i]]+v[i]);
    }
  }

  printf("%lld\n", dp[W]);

  return 0;
}

Measured memory_bytes: 896
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    s = S()
    li = ['x' for x in range(len(s))]
    ans = ''

    for i in li:
        ans += i

    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

const int MAXN = 300;
const int INF = 1000<<20;

int mat[MAXN][MAXN];
int edges[MAXN][MAXN];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, i, j, d;
	vector<pair<int, pair<int, int>>> vec;
	long long sol = 0;
	
	cin>>n;
	
	for (i = 0; i < n; ++i) for (j = 0; j < n; ++j)
	{
		edges[i][j] = INF;
		
		cin>>mat[i][j];
		vec.push_back({mat[i][j], {i, j}});
	}
	
	sort(vec.begin(), vec.end());
	
	for (const auto& x: vec)
	{
		d = x.first;
		tie(i, j) = x.second;
		
		int mn = INF;
		for (int k = 0; k < n; ++k) if (k != j)
			mn = min(mn, mat[i][k] + edges[k][j]);
		
		if (mn < d)
		{
			cout<<"-1\n";
			return 0;
		}
		if (mn > d)
			sol += (edges[i][j] = edges[j][i] = d);
	}
	
	cout<<sol<<'\n';
}


Measured memory_bytes: 2424
#include "bits/stdc++.h"
    using namespace std;
    //#define MOD 1000000007
    //#define MOD 998244353
    #define MOD 2019
    const double EPS = 1e-9;
    #define INF (1LL<<60)
    #define D double
    #define fs first
    #define sc second
    #define int long long
    #define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
    #define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
    #define REP(i,n)  FOR(i,0,(n))
    #define RREP(i,n) RFOR(i,0,(n))
    #define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
    #define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
    #define range(i,a,b) ((a)<=(i) && (i)<(b))
    #define debug(x)  cout << #x << " = " << (x) << endl;
    #define SP << " " << 
    typedef pair<int,int> P;
    typedef vector<int> vec;
    typedef vector<vector<int>> mat;
     
    signed main(){
      ios::sync_with_stdio(false);
      cin.tie(0);
      cout.precision(20);
     
      int n;
      cin >> n;

      mat a(2, vec(n));
      REP(i, 2) REP(j, n){
        cin >> a[i][j];
      }

      vec b(n, 0);
      REP(i,n){
        REP(j, i + 1) b[i] += a[0][j];
        REP(j, n - i){
          b[i] += a[1][i + j];
        }
      }

      cout << *max_element(b.begin(), b.end()) << endl;

      return 0;
    }

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P, int> PP;
int H, W;
int cas[1000][1000];
vector<string> vs;
queue<PP> que; // PP(P(y, x),???i??????)?????¢?????\???
int vy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int vx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> H >> W;
  FOR(i,0,H) {
    string s; cin >> s;
    vs.push_back(s);
  }
  FOR(i,0,H) {
    FOR(j,0,W) {
      if(isdigit(vs[i][j])) {
        cas[i][j] = 1e9;
        que.push(PP(P(i, j), 1));
      }
    }
  }
  int ans = 0;
  while(!que.empty()) {
    PP p = que.front(); que.pop();
    int y = p.first.first;
    int x = p.first.second;
    int t = p.second;
    if(cas[y][x] <= t) continue; // ?????§????´?????????????
    int cnt = 0;
    FOR(i,0,8) if(cas[y+vy[i]][x+vx[i]] < t) cnt++;
    // ?´???????
    if(cnt >= vs[y][x] - '0') {
      cas[y][x] = t;
      ans = max(ans, t);
      FOR(i,0,8) {
        if(cas[y+vy[i]][x+vx[i]] > t) {
          que.push(PP(P(y+vy[i], x+vx[i]), t + 1));
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 19796
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
def LI(): return list(map(int, sys.stdin.readline().split()))
n_ = 10**5 + 3

fun = [1 for i in range(n_+1)]
for i in range(1, n_ + 1):
    fun[i] = fun[i-1] * i % mod

rev = [1 for i in range(n_+1)]
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1) % mod

def nCr(n,r):
    if n <= 0 or r < 0 or r> n:return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

N, K = LI()
A = LI()

A.sort()
ma, mi = 0,0
for i, x in enumerate(A):
    ma += nCr(i, K-1)*x
    mi += nCr(N-i-1, K-1)*x
    ma %= mod
    mi %= mod
print((ma-mi)%mod)


Measured memory_bytes: 97904
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
 
const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);
 
using namespace std;

int main(void){
	int N,M;
	cin >> N >> M;
	vector<ll> a(N);
	vector<pair<ll,ll>> x;
	rep(i,N)cin >> a[i];
	//b枚までcにして良い	
	rep(i,M){
		int b,c;
		cin >> b >> c;
		x.emplace_back(-c,b);
	}
	sort(ALL(a));
	sort(ALL(x));
	int cnt = 0;
	int num = 0;
	for(int i=0;i<N;i++){
		if(num==M)break;
		int now = -1*x[num].first;
		if(a[i]<now){
			a[i] = now;
			cnt++;
			if(cnt==x[num].second){
				cnt = 0;
				num++;
			}
		}else break;
	}
	cout << accumulate(ALL(a),0LL) << endl;
}

Measured memory_bytes: 3188