akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

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

    // input
    ll N, M;
    cin >> N >> M;

    vector<pair<ll, ll> > A(N);
    FOR(i, 0, N){
        ll a, b;
        cin >> a >> b;
        A[i] = make_pair(a, b);
    }
    sort(ALL(A));

    ll cost = 0;
    FOR(i, 0, N){
        auto p = A[i];
        ll price = p.first;
        ll num = p.second;
        
        if(M>=num){
            M -= num;
            cost += price * num;
        }
        // M < num
        else{
            cost += price * M;
            M = 0;
        }

        if(M==0){
            break;
        }
    }

    p(cost);
    
    return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main () {
  int a, b;
  std::cin >> a >> b;
  std::vector<int> sums(1000, 1);
  for (int i = 2; i < 1000; ++i) {
    sums[i] = sums[i-1] + i;
  }
  std::cout << sums[b - a - 1] - a << std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000000000LL
vector<ll>s;
vector<ll>t;

int main(){
  ll a,b,q;
  cin>>a>>b>>q;

  s.push_back(-INF);
  t.push_back(-INF);
  for(int i=0;i<a;i++){
    ll ns;
    cin>>ns;
    s.push_back(ns);
  }
  for(int i=0;i<b;i++){
    ll nt;
    cin>>nt;
    t.push_back(nt);
  }
  s.push_back(INF);
  t.push_back(INF);

  for(int i=0;i<q;i++){
    ll x;
    cin>>x;
    int p=upper_bound(s.begin(),s.end(),x)-s.begin();
    int q=upper_bound(t.begin(),t.end(),x)-t.begin();

    ll ans=max(s[p]-x,t[q]-x);
    ans=min(ans,max(x-s[p-1],x-t[q-1]));
    ans=min(ans,(s[p]-x)*2+(x-t[q-1]));
    ans=min(ans,(t[q]-x)*2+(x-s[p-1]));
    ans=min(ans,(x-s[p-1])*2+(t[q]-x));
    ans=min(ans,(x-t[q-1])*2+(s[p]-x));

    cout<<ans<<endl;
  }

  return(0);
}


Measured memory_bytes: 3060
#include <iostream>
#include <string>

using namespace std;

int main(void){
  int N;
  string S;
  int r, g, b;
  long long ans;

  r = g = b = 0;
  ans = 1;

  cin >> N;
  cin >> S;

  for(int i=0; i<N; i++){
    if(S[i]=='R') r++;
    if(S[i]=='G') g++;
    if(S[i]=='B') b++;
  }
  ans*=r*g;
  ans*=b;

  for(int k=2; k<N; k++){
    for(int i=0; i<k-1; i++){
      if((i+k)%2==0){
        int j = (i + k) / 2;
        if(S[i]!=S[j] && S[j]!=S[k] && S[i]!=S[k]) ans--;
      }
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    string s; cin>>s;
    int n=s.size();
    int ans=INF;
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            ans=min(ans,max(i+1,n-(i+1)));
        }
    }
    cout<<(ans==INF?n:ans)<<endl;
    return 0;
}


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


ll pow(long long a, long long b, ll mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        ll d = pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*pow(a,b-1,mod)%mod;
}

//関数名：comb
//概要：二項係数
//第一引数n：組み合わせの全体
//第二引数r：何個取り出すか
//第三引数mod：法となる値
//戻り値：nCr(m mod)
ll comb(long long n,long long r,ll mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; --i) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; --i) fact2 = fact2*i%mod;
    return fact1*pow(fact2,mod-2,mod)%mod;
}


int main(){
    ll x, y; cin >> x >> y;
    if((x+y)%3) cout << 0 << endl;
    else{ // x+yが3の倍数
        ll k = (x+y)/3;
        if(x > 2*k || x < k) cout << 0 << endl;
        else{
            cout << comb(k, x-k, MOD) << endl;
        }
    }
}

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

int main() {
	while (1) {
		int all = 0 , rem = 0, count = 0, tmp  = 0;
		cin >> all;
		if (all == 0)
			break;
		rem = 1000 - all;
		if (rem >= 500) {
			count = count + 1;
			rem = rem - 500;
		}
		if (rem >= 100) {
			tmp = rem / 100;
			count = count + tmp;
			rem = rem - (100 * tmp);
		}
		if (rem >= 50) {
			tmp = rem / 50;
			count = count + tmp;
			rem = rem - 50 * tmp;
		}
		if (rem >= 10) {
			tmp = rem / 10;
			count = count + tmp;
			rem = rem - 10 * tmp;
		}
		if (rem >= 5) {
			tmp = rem / 5;
			count = count + tmp;
			rem = rem - 5 * tmp;
		}
		count = count + rem;
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Class13
    {
        static void Main()
        {
            var WHN = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int W = WHN[0], H = WHN[1], N = WHN[2];
            bool[,] map = new bool[W, H];
            for (int i = 0; i < W; i++)
                for (int j = 0; j < H; j++)
                    map[i, j] = true;

            for(int i = 0; i < N; i++)
            {
                var xya = Console.ReadLine().Split().Select(int.Parse).ToArray();
                int x = xya[0], y = xya[1], a = xya[2];

                if (a == 1)
                {
                    for (int j = 0; j < xya[0]; j++)
                        for (int k = 0; k < H; k++)
                            map[j, k] = false;
                }
                else if (a == 2)
                {
                    for (int j = W - 1; j >= xya[0]; j--)
                        for (int k = 0; k < H; k++)
                            map[j, k] = false;
                }
                else if (a == 3)
                {
                    for (int j = 0; j < W; j++)
                        for (int k = 0; k < xya[1]; k++)
                            map[j, k] = false;
                }
                else if (a == 4)
                {
                    for (int j = 0; j < W; j++)
                        for (int k = H - 1; k >= xya[1]; k--)
                            map[j, k] = false;
                }
            }
            int count = 0;
            foreach (bool b in map)
                if (b) count++;

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n, k;
    cin >> n >> k;
    int ans = 1;
    while(1) {
        if ( n < k ) break;
        ++ans;
        n /= k;
    }
    cout << ans << endl;
    return 0;
}


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

const int MOD = 1e9+7;

int n,m;
int f[1005][1005];
bool a[1005][1005];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char ch;
			cin>>ch;
			if(ch=='.')
				a[i][j] = true;
		}
	f[1][1] = 1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!(i==1 && j==1) && a[i][j])
				f[i][j] = (f[i-1][j]+f[i][j-1])%MOD;
	cout<<f[n][m]<<endl;
	
	return 0;
}

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll tmpAll = 0;

    rep(i, N) {
        cin >> A[i];
        A[i] -= (i + 1);
    }
    sort(all(A));
    ll b;
    if (N % 2 == 1) {
        b = A[N / 2];
    } else {
        b = (A[N / 2] + A[(N / 2) - 1]) / 2;
    }

    ll ans = 0;
    rep(i, N) {
        ans += abs(A[i] - b);
    }
    cout << ans << endl;
}

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

int main() {
  int N;
  string C, K;
  
  cin >> N;
    
  for(int i=0;i<N;i++){
    cin >> C;
    if(C=="Y"){
      break;
    }
  }
  
  if(C=="Y"){
    cout << "Four" <<endl;
  }
  else{
    cout << "Three" <<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

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

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
////////////////////////////////////////////////////////////////////
int main()
{
    int len[5],k;
    REP(i,5) cin >> len[i];
    cin >> k;
    
    REP(i,5){
        FOR(j,i,5){
            if(abs(len[i]-len[j])>k){
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    cout << "Yay!" << endl;
    return 0;
}


Measured memory_bytes: 256
N = gets.to_i
xy = []

N.times {
  x, y = gets.split.map(&:to_i)
  xy << [x, y]
}

total = 0.0
pattern = 1
(N-2).times do |i|
  pattern *= i+1
end
pattern *= N-1
# puts "pattern=#{pattern}"

(N-1).times do |i|
  (i+1).upto(N-1) do |j|
    # puts "i=#{i} j=#{j}"
    calc = (xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2
    # puts "inside sqrt=#{calc}"
    dist = Math.sqrt(calc) *2
    total += dist * pattern
    # puts "total = #{total}"
  end
end

puts total/(pattern * N)


Measured memory_bytes: 1788
#include <cstdio>
#include <cstdlib>

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

int main(){
    int i, n, xs, d;
    scanf("%d %d",&n,&xs);
    int *x = (int *)malloc(sizeof(int)*n);
    for(i=0;i<n;i++){
        scanf("%d",x+i);
        x[i] = abs(x[i]-xs);
    }
    for(i=0;i<n;i++){
        if(x[i]>0){
            d = x[i];
            break;
        }
    }
    for(;i<n;i++){
        if(x[i]>0){
            d = gcd(d,x[i]);
        }
    }
    printf("%d\n",d);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n; cin>>n;
  string s; cin>>s;
 
  for(int i=0;i<s.size();i++) {
    int tmp=(int)(s[i]-'A')+n;
    if (tmp>=26) tmp-=26;
    cout<<(char)(tmp+'A');
  }
  cout<<endl;
}

Measured memory_bytes: 256
x = int(input())
numclass= int()

if 400 <= x < 600:
    numclass = 8
elif 600 <= x < 800:
    numclass = 7
elif 800 <= x < 1000:
    numclass = 6
elif 1000 <= x < 1200:
    numclass = 5
elif 1200 <= x < 1400:
    numclass = 4
elif 1400 <= x < 1600:
    numclass = 3
elif 1600 <= x < 1800:
    numclass = 2
elif 1800 <= x < 2000:
    numclass = 1
    
if numclass > 0:
    print(numclass)


Measured memory_bytes: 9128
import Control.Applicative

main = do
  (n:t:_) <- (map read) . words <$> getLine
  ts <- (map read) . words <$> getLine

  print $ f ts t
  where
    f (x:[]) t = t
    f (x:y:xs) t = (if y-x < t then y-x else t) + (f (y:xs) t)


Measured memory_bytes: 70012
n = int(input())
l = list(map(int,input().split()))
dp = [[-float("INF")]*(3) for i in range(n+1)]
dp[0][0] = 0
dp[1][-1] = 0
dp[1][1] = l[0]
for i in range(1,n):  
    dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
    dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
    dp[i+1][1] = dp[i-1][1]+l[i]
    
print(max(dp[-1][0],dp[-1][-1]))



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

int count(int n) {
	int t = 10000, rtn = 0;
	while (n != 0) {
		rtn += (int)n / t;
		n %= t;
		t /= 10;
	}
	return rtn;
}

int main() {
	int n, a, b, ans = 0;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		int cnt = count(i);
		if (a <= cnt && cnt <= b)ans += i;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

ll A[100001];
ll usable_non_leaf_nodes[100001];
ll max_non_leaf_nodes[100001];

int main() {
	int N;
	cin >> N;
	cin >> A[0];

	if (N == 0) {
		if (A[0] == 1) {
			cout << 1 << endl;
		} else {
			cout << -1 << endl;
		}
		return 0;
	} else if (A[0] > 0) {
		cout << -1 << endl;
		return 0;
	}

	usable_non_leaf_nodes[0] = 1;
	for (int i=1; i<N; i++) {
		cin >> A[i];
		usable_non_leaf_nodes[i] = min(usable_non_leaf_nodes[i-1] * 2 - A[i], (ll)1e18);
		if (usable_non_leaf_nodes[i] <= 0) {
			cout << -1 << endl;
			return 0;
		}
	}

	ll usable_N_leaves = usable_non_leaf_nodes[N-1] * 2;

	cin >> A[N];

	if (usable_N_leaves < A[N]) {
		cout << -1 << endl;
		return 0;
	}

	ll ans = A[N];
	max_non_leaf_nodes[N] = 0;
	for (int i=N-1; i>=0; i--) {
		max_non_leaf_nodes[i] = min(usable_non_leaf_nodes[i], max_non_leaf_nodes[i+1] + A[i+1]);
		ans += max_non_leaf_nodes[i] + A[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5980
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main(){
    int x,y,z;
    cin>>x>>y>>z;
    pair<string,int>p("A",x);
    pair<string,int>q("B",y);
    pair<string,int>r("c",z);
    swap(p.second,q.second);
    swap(p.second,r.second);
    cout<<p.second<<" "<<q.second<<" "<<r.second;
    }

Measured memory_bytes: 256
#require 'prime'
require 'openssl'
MOD=10**9+7;  cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.chomp.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def ar2(s1,s2,de=nil) Array.new(s1){Array.new(s2,de)} end
def ar3(s1,s2,s3,de=nil) Array.new(s1){Array.new(s2){Array.new(s3,de)}} end

def desc(ar) ar.sort!{|x,y| y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+).to_i end
def ceil(a,b) (a.to_f/b).ceil end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end
def rui(ar) s=[0]; ar.size.times{|i| s<<s[-1]+ar[i]}; s end
def rev_rui(ar) s=[0]; ar.size.times.reverse_each{|i| s<<s[-1]+ar[i]}; s end

def puts_yesno(b) puts(b ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def pu(h) begin; require './../nemi_lib/debug.rb'; puts_val(h); rescue LoadError; end; end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n,k=gsmi

# 累乗 とても大きい累乗にも対応
def pow(a, b, mod=MOD)
  base = a
  ans=1
  while b>0 do
    ans *= (base**(b%10))
    ans %= mod
    base = (base**10) % mod
    b /= 10
  end
  ans
end

ar=(0..n).to_a
rui=rui ar
r_rui=rev_rui ar
k.upto (n+1) do |i|
  min=rui[i]
  max=r_rui[i]
  cnt+=max-min+1
end

puts (cnt)%MOD

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int a, b, c;

int main() {
	cin >> a >> b >> c;
	if (a<=c && c<=b) cout << "Yes" << ln;
	else cout << "No" << ln;
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "../../library/library/debug_template.cpp"
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else
#define DMP(...) ((void)0)
#endif

#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int x;
	cin >> x;
	cout << !x << "\n";

	return 0;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


set<int> SET;

int main(){

	int N;
	scanf("%d",&N);

	int tmp;
	for(int i = 0; i < N; i++){

		scanf("%d",&tmp);
		SET.insert(tmp);
	}

	int M;
	scanf("%d",&M);

	for(int i = 0; i < M; i++){

		scanf("%d",&tmp);
		if(SET.count(tmp)){

			SET.erase(tmp);
		}
	}

	for(auto at = SET.begin(); at != SET.end(); at++){

		printf("%d\n",*at);
	}

	return 0;
}



Measured memory_bytes: 12588
// Course＞Introduction to Programming I ＞ ITP1_1_B:   X Cubic
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_B&lang=jp

// 以下のソースコードには(複数の？)誤りがあるので、このまま提出しても「誤り」と判定されます。
// ソースコード中の誤りを修正し、「正解」（Accepted）を出してください。

// 適宜、paiza.io (https://paiza.io/ja/projects/new) などのC++実行環境を、確認に用いることを推奨します。

#include <iostream>
using namespace std;

int main(){
	int x;
	cin >> x;
	cout << ( x * x * x ) << endl;
	return 0;
	}


Measured memory_bytes: 3072
A, B = map(int, input().split())
sum = 0
if A < B:
  sum += B
  B = B-1
else:
  sum += A
  A = A-1
 
if A < B:
  sum += B
  B = B-1
else:
  sum += A
  A = A-1
 
print(sum)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
// #define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;



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

    ll n,k;
    ll ans=0;
    cin>>n>>k;
    vi a(n);
    rep(i,n)cin>>a[i];
    vi all(n,0),right(n,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i]>a[j]){
                all[i]++;
                if(i<j)right[i]++;
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     cout<<all[i]<<" ";
    // }
    // cout<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<right[i]<<" ";
    // }
    // cout<<endl;
    ll K=(k*k-k*(k+1)/2)%P;
    for(int i=0;i<n;i++){
        ans+=((all[i]*K)%P+(right[i]*k)%P)%P;
        ans%=P;
    }
    fin(ans);


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
from collections import deque

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [-1] * N
minDist = [10**18] * N
minDist[0] = 0
que = deque([0])

while que:
    now = que.popleft()
    dist = minDist[now] + 1
    for to in edges[now]:
        if minDist[to] > dist:
            minDist[to] = dist
            ans[to] = now
            que.append(to)

print('Yes')
for a in ans[1:]:
    print(a + 1)


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

using namespace std;

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

template <class T>
class SegTree{
    int n;
    vector<T> data;
    T def; //初期値,単位元
    function<T(T, T)> operation; //区間クエリで使う処理
    function<T(T, T)> update; //1点更新で使う処理

    //区間[a,b)の総和
    T _query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return def; //交差しない時
        if(a <= l && r <= b) return data[k]; //[l,r)が完全に含まれるとき
        else{
            T c1 = _query(a, b, (k << 1)+1, l, (l+r)/2);
            T c2 = _query(a, b, (k << 1)+2, (l+r)/2, r);
            return operation(c1, c2);
        }
    }

  public:
    // _n:必要サイズ _def:初期値かつ単位元 _operation:クエリ関数
    // _update:更新関数
    SegTree(size_t _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update){
        n = 1;
        while(n < _n){
            n *= 2;
        }
        data = vector<T>(2*n-1, def);
    }

    //場所i(0-idx)の値をxで更新
    void change(int i, T x){
        i += n-1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i-1)/2;
            data[i] = operation(data[(i<<1) + 1], data[(i<<1) + 2]);
        }
    }

    T query(int a, int b){
        return _query(a, b, 0, 0, n);
    }

    T operator[](int i){
        return data[i+n-1];
    }
};

int main(void){
    int N, Q; cin >> N >> Q;
    SegTree<long long> st(N, (1LL << 31)-1,
                        [](long long a, long long b){return min(a, b);},
                        [](long long a, long long b){return b;});
    
    rep(q, Q){
        int c, x, y; cin >> c >> x >> y;
        if(c == 0){
            st.change(x, y);
        }
        else{
            cout << st.query(x, y+1) << endl;
        }
    }

    return 0;
}


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

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

using namespace std;

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

const int M = 100010;
long long h[M];

long long dp[M];

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

    rep(i, N) cin >> h[i];
    rep(i, M) dp[i] = INF;

    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
    }

    cout << dp[N - 1] << endl;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;

class DivideTheProblems
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine();
        string answer = "";
        char[] array = new char[input.Length];

        for (int i = 0; i < input.Length; i++)
        {
            array[i] = input[i];
        }

        Array.Sort(array);

        if (array[0].Equals(array[1]) && array[2].Equals(array[3]))
        {
            answer = "Yes";
            if (array[0].Equals(array[1]) && array[1].Equals(array[2]) && array[2].Equals(array[3]))
            {
                answer = "No";
            }
        }
        else
        {
            answer = "No";
        }
        Console.WriteLine(answer);
    }
}



Measured memory_bytes: 11348
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define DL double
#define MLL map<LL,LL>::iterator
#define MSL map<string,L>::iterator
#define MLS map<LL,string>::iterator
#define MSS map<string,string>::iterator
#define MCL map<char,LL>::iterator
#define SL set<LL>::iterator
#define SS set<string>::iterator sl
#define G getline
#define SZ size()
#define IN insert
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
map<LL,LL>v;
int main()
{
    FAST;
    LL n,m,i,j,k,p,q,o,l,s,t,z;
    string a;
    cin>>n;
    for(i=0,k=0; i<n; i++)
    {
        cin>>o;
        v[o]++;
        v[o-1]++;
        v[o+1]++;
        k=max(k,max(max(v[o],v[o-1]),v[o+1]));

    }
  cout<<k<<endl;
    return 0;

}


Measured memory_bytes: 6144
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int s, g;
	int n;

	void run(){
		n=sc.nextInt();
		for(int i=0; i<n; i++){
			s=sc.nextInt();
			g=sc.nextInt();
			solve();
		}
	}

	void solve(){
		// s<g
		LinkedList<Integer> list=new LinkedList<Integer>();
		if(s<g){
			for(int i=s; i<=g; i++){
				list.add(i);
			}
		}else{
			if(s<=5){
				for(int i=s; i>=g; i--){
					list.add(i);
				}
			}else{
				// s>5
				int i=s;
				boolean f=false;
				for(; i<=9; i++){
					list.add(i);
					if(i==g){
						f=true;
						break;
					}
				}
				if(!f){
					for(i=5; i>=0; i--){
						list.add(i);
						if(i==g){
							f=true;
							break;
						}
					}
				}
				if(!f){
					for(i=1; i<=g; i++){
						list.add(i);
						if(i==g){
							f=true;
							break;
						}
					}
				}
			}
		}
		for(int i=0; i<list.size(); i++){
			print(list.get(i)+(i==list.size()-1?"\n":" "));
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

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

int main() {
  string a;
  cin>>a;
  char b;
  b=a.at(a.size()-1);
  if(b=='3'){
    cout<<"bon"<<endl;
  }
  else if(b=='0'||b=='1'||b=='6'||b=='8'){
    cout<<"pon"<<endl;
  }
  else{
    cout<<"hon"<<endl;
  }
}

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

int main()
{
	int n;
	cin>>n;
	if(n%10==7){
		cout<<"Yes"<<endl;
	}
	else {
		n/=10;
		if(n%10==7){
			cout<<"Yes"<<endl;
		}
		else {
			n/=10;
			if(n==7){
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
		}
	}
	return 0;
}

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

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
#define rep2(i,a,b,c) for(i=a;i<=b;i+=c)

int main(){
	int X,A,B;
	cin>>X>>A>>B;
	if(B<=A){
		cout<<"delicious\n";
	}
	else if(B-A <= X){
		cout<<"safe\n";
	}
	else{
		cout<<"dangerous\n";
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
#include<string>
#include<stack>
#include<map>
#include<cmath>
#include<queue>
#include<set>
#include<string>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+7;
const LL LL_MAX=9223372036854775807;
const LL maxn=4e5+10;
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int read1()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    LL h,w;
    cin>>h>>w;
    LL res=0;
    res=h*w;
    if(h==1||w==1){
        printf("1\n");
        return 0;
    }
    else{
    if(res%2){
        res=res/2+1;
    }
    else{
        res/=2;
    }
    printf("%lld\n",res);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;


int dp[11][100100];

int main()
{
    string s;
    cin >> s;
    bool ans = true;
    int n = s.size();
    if(n%2!=0){
        ans = false;
    }else{
        for(int i = 0; i < n-1; i+=2){
            if(s[i] != 'h' || s[i+1] != 'i') ans = false;
        }
    }
    if(ans){
        cout << "Yes";
    }else{
        cout << "No";
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
char s[N];
vector<pair<int, int>> pa, pb;
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s", s);
        int a = 0, b = 0;
        for(int j = 0; s[j]; j++) {
            if(s[j] == '(') a++;
            else if(a) a--;
            else b++;
        }
        if(a <= b) pa.push_back({a, b});
        else pb.push_back({a, b}); 
    }
    sort(pa.begin(), pa.end());
    sort(pb.begin(), pb.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    });
    int sum = 0;
    bool flag = true;
    for(int i = 0; i < pa.size(); i++) {
        sum -= pa[i].first;
        if(sum < 0) flag = false;
        sum += pa[i].second;
    }
    for(int i = 0; i < pb.size(); i++) {
        sum -= pb[i].first;
        if(sum < 0) flag = false;
        sum += pb[i].second;
    }
    if(sum) flag = false;
    printf("%s\n", flag ? "Yes" : "No");
    return 0;
}



Measured memory_bytes: 11372
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N = int(input())
A = []
B = []
C = []
for i in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)

dp = [ [0 for _ in range(3)] for _ in range(N+1) ]

for i in range(1, N+1):
    dp[i][0] = max(dp[i-1][1]+B[i-1], dp[i-1][2]+C[i-1])
    dp[i][1] = max(dp[i-1][0]+A[i-1], dp[i-1][2]+C[i-1])
    dp[i][2] = max(dp[i-1][0]+A[i-1], dp[i-1][1]+B[i-1])

print(max(dp[N]))


Measured memory_bytes: 36168
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n = int(input())
    Vs = list(map(int, input().split()))
    Vs.sort()
    
    while len(Vs) > 1:

        Vs[0] = (Vs[0] + Vs[1]) / 2
        Vs[1:] = Vs[2:]
    print(Vs[0])

    return

if __name__ == '__main__':
    main()

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

#define int long long
#define debug(x) cout<<#x<<" "<<x<<endl;

const int N=1e6+5;
const double eps=1e-9;
const int INF=1e18;

int w[N],v[N];
int dp[N];

signed main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int m,n;cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=100000;i++) dp[i]=1e10;
    for(int i=1;i<=n;i++){
        for(int j=w[i];j<=50000;j++)
            dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
    }
    int ans=1e9+7;
    for(int i=m;i<=50000;i++) if(dp[i]!=0) ans=min(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}

//Created Time  :2020/1/26 20:09:32


Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define dcout cout<<fixed<<setprecision(20)
#define Accepted_MAGIC cin.tie(0);ios::sync_with_stdio(false);cerr << "compiled" << endl

// typedef long long ll;
using Real = long double;
#define int long long

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;
constexpr Real eps = 1e-9, pi = acos(-1);

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

int N, M;
vector<INTV> Graph;
INTV topo;
vector<bool> visit;

void dfs(int pos){
  if(visit[pos]) return;
  for(auto nxt : Graph[pos]) dfs(nxt);
  visit[pos] = 1;
  topo.eb(pos);
  return;
}

signed main(void){
  Accepted_MAGIC;
  
  cin >> N >> M;
  Graph.resize(N);
  visit.resize(N, 0);
  REP(i, N+M-1){
    int a, b; cin >> a >> b; --a; --b;
    Graph[a].eb(b);
  }
  REP(i, N){
    dfs(i);
  }
  reverse(ALL(topo));
  // cerr << topo.size() << endl;
  INTV idx(N);
  REP(i, N) {
    // cerr << topo[i] << endl;
    idx[topo[i]] = i;
  }
  INTV par(N, -1);
  REP(from, N){
    for(auto to : Graph[from]){
      chmax(par[to], idx[from]);
    }
  }
  REP(i, N){
    if(par[i] == -1) cout << 0 << endl;
    else cout << topo[par[i]]+1 << endl;
  }
}

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

using namespace std;
#define int long long int
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define vi vector <int>
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define piii pair< int,pair<int,int> >
#define tiii tuple <int,int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(v) v.rbegin(),v.rend()
#define endl '\n'
#define matrix vector <vector <int> >
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define NAYAN freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define N 500006
#define mod 1000000007
#define mod2 998244353
#define inf 1e17

int dp[101][100001];
int w[101],v[101];
int n,W;

int solve(int i,int j)
{
    if(j<0)
        return -inf;
    if(j==0 || i<0)
        return 0;
    
    int &ans=dp[i][j];
    if(ans!=-1)
        return ans;
    //ans=0;
    ans=max(solve(i-1,j),v[i]+solve(i-1,j-w[i]));
    return ans;


}


int32_t main()  
{
    boost
    // #ifndef ONLINE_JUDGE 
    // NAYAN
    // #endif
    
    

    cin >> n >> W;

    
    memset(dp,-1,sizeof dp);
    int i,j;
    
    for(i=0;i<n;i++)
    {
        cin >> w[i] >> v[i];
    }

    

    int ans=solve(n-1,W);

    cout << ans << endl;


}

Measured memory_bytes: 79232
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;


int main() {
  int a,b; cin >> a >> b;
  string s; cin >> s;
  bool ans = true;
  rep(i,s.size()){
    if (i < a && s[i] == '-')ans = false;
    if (i == a && s[i] != '-') ans = false;
    if (i > a && s[i] == '-') ans = false;
  }

  cout << (ans ? "Yes" : "No") << endl;
	return 0;
}



Measured memory_bytes: 3600
def resolve():
    n, x = map(int, input().split())
    a = [int(i) for i in input().split()]
    a = sorted(a)

    ans = 0
    for _a in a[:-1]:
        x = x - _a
        if x >= 0:
            ans += 1
    if x == a[-1]:
        ans += 1
    print(ans)


resolve()


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const int inf=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;


int main(){
  ll n;cin>>n;
  vll a(n);
  set<ll> s;
  rep(i,0,n){
    cin>>a[i];
    s.insert(a[i]);
  }
  if(s.size()>3){
    cout<<"No"<<endl;return 0;
  }
  if(s.size()==3){
    vll b(3);
    auto it=s.begin();
    rep(i,0,3){
      b[i]=*it;
      it++;
    }
    ll x=b[0]^b[1]^b[2];
    if(x!=0){
      cout<<"No"<<endl;return 0;
    }
    vll c(3,0);
    rep(i,0,n){
      rep(j,0,3){
        if(a[i]==b[j])c[j]++;
      }
    }
    if(!(c[0]==c[1]&&c[1]==c[2])){
      cout<<"No"<<endl;return 0;
    }
  }
  else if(s.size()==2){
    auto it=s.begin();
    if(*it!=0){
      cout<<"No"<<endl;return 0;
    }
    ll x=0;
    rep(i,0,n){
      if(a[i]==0)x++;
    }
    if(x!=n/3||n%3){
      cout<<"No"<<endl;return 0;
    }
  }
  else{
    
    if(*(s.begin())!=0){
      cout<<"No"<<endl;return 0;
    }
  }
  cout<<"Yes"<<endl;
  
}




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

ll mod(ll val, ll m) {
  ll res = val % m;
  if (res < 0) res += m;
  return res;
}
    ll pow_kai(int a, int n)
{ //aのn乗を計算します。
    ll x = 1;
    rep(i, n)
    {
        x *= a;
        x %= MOD;
    }
    return x;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;

    ll Ans = pow_kai(10, N);
    ll temp = pow_kai(9, N);
    Ans -= (temp * 2);

    Ans += pow_kai(8, N);
    Ans = mod(Ans, MOD);
    cout << Ans << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

struct union_find{
    vector<ll> parent;
    vector<ll> nums;
    union_find(ll n){
        parent.resize(n);
        nums.resize(n, 1LL);
        rep(i, 0, n) parent[i] = i;
    }

    ll root(ll x){
        if(parent[x] == x) return x;
        parent[x] = root(parent[x]);
        return parent[x];
    }

    void unite(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        if(rx != ry){
            parent[rx] = ry;
            nums[ry] += nums[rx];
        }
    }

    bool same(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        if(rx == ry) return true;
        return false;
    }

    ll size(ll x){
        return nums[root(x)];
    }
};  

int main(){
    ll N;
    cin >> N;
    vector<ll> x(N), y(N);
    ll stride = 1e5+100;
    union_find t(2*stride);
    rep(i, 0, N){
        cin >> x[i] >> y[i];
        t.unite(x[i], y[i] + stride);
    }
    map<ll, ll> mpx, mpy;
    rep(i, 0, stride) mpx[t.root(i)]++;
    rep(i, stride, 2*stride) mpy[t.root(i)]++;
    ll ans = 0;
    rep(i, 0, stride*2) ans += mpx[i] * mpy[i];
    cout << ans - N << endl;
    return 0;
}

Measured memory_bytes: 29952
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int  mod = 1e9 + 1;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int x = 1;
	while (c > 0 && d > 0) {
		if (x & 1) {
			c -= b;
		}
		else a -= d;
		x++;
	}
	if (a > 0)puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 3632
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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

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

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut info = vec![Vec::new(); n];
    for i in 0..m {
        let v = read_vec::<i64>();
        let l = v[0] as usize - 1;
        let r = v[1] as usize - 1;
        info[l].push((r, v[2]));
        info[r].push((l, -v[2]));
    }
    // println!("{:?}", info);

    let mut poses = vec![std::i64::MAX; n];
    let mut checked = HashSet::new();
    for i in 0..n {
        if poses[i] != std::i64::MAX {
            continue;
        }
        poses[i] = 0;
        let mut que = VecDeque::new();
        que.push_back(i);

        while let Some(l) = que.pop_back() {
            let origin = poses[l];
            for &(r, dist) in info[l].iter() {
                if poses[r] == std::i64::MAX {
                    poses[r] = origin + dist;
                    if !checked.contains(&l) {
                        que.push_back(r);
                    }
                }
                if poses[r] != origin + dist {
                    println!("No");
                    return;
                }
            }
            checked.insert(l);
        }
    }
    println!("Yes");
}


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

using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> f(n);
  for(auto&& x:f){
    for(int i=0;i<10;i++){
      int y;
      cin >> y;
      x <<= 1;
      x |= y;
    }
  }
  vector<vector<int> > p(n, vector<int>(11));
  for(auto&& x:p)for(auto&& y:x)cin >> y;
  int ans = -1e9-7;
  for(int i=1;i<(1<<10);i++){
   	int t = 0;
    for(int j=0;j<n;j++){
      int k = __builtin_popcount(i&f[j]);
      t += p[j][k];
    }
    ans = max(t, ans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d", &tmp);v.push_back(tmp);}}
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

llong solve(string s, bool used[3], int idx, bool all_ok){
  if(idx == s.length()){
    int cnt = 0;
    REP(i,3){
      if(used[i]) cnt++;
    }
    if(cnt == 3)
      return 1;
    else
      return 0;
  }
  llong res = 0;
  if(all_ok){
    REP(i,3){
      bool tmp[3];
      REP(j,3){
        tmp[j] = used[j];
      }
      tmp[i] = true;
      res += solve(s, tmp, idx+1, true);
    }
  }else{
    REP(i,3){
      bool tmp[3];
      REP(j,3){
        tmp[j] = used[j];
      }

      if(i == 0){
        if(s[idx] > '7'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1, true); 
        }else if(s[idx] == '7'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1,false);
        }
      }else if(i == 1){
        if(s[idx] > '5'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1, true); 
        }else if(s[idx] == '5'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1, false); 
        }
      }else{
        if(s[idx] > '3'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1, true); 
        }else if(s[idx] == '3'){
          tmp[i] = true;
          res += solve(s,tmp,idx+1, false); 
        }
      }
    }
  }
 return res; 
}

int main(){

  string n;
  cin >> n;

  llong ans = 0;
  string tmp = "";
  REP(i,n.length()){
    tmp = tmp + "9";
    bool used[3] = {};
    if(i == n.length()-1){
      ans += solve(n, used, 0, false);
    }else{
      ans += solve(tmp, used, 0, false);
    }
  }

  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i=0; i<n; i++){
			a[i] = sc.nextLong();
		}
		Arrays.sort(a);
		if(n==3){
			System.out.println(Math.max(a[2]*2-a[0]-a[1], a[1]+a[2]-a[0]*2));
		}
		else if(n%2==1){		
			long sum1 = 0L;
			long sum2 = 0L;
			for(int i=0; i<=(n-3)/2; i++){
				sum1 = sum1 - 2*a[i] + 2*a[i+(n+1)/2];
				sum2 = sum2 - 2*a[i] + 2*a[i+(n-1)/2];
			}
			sum1 = sum1 - a[(n-1)/2] + a[(n-3)/2];
			sum2 = sum2 + 2*a[n-1] - a[(n-1)/2] - a[(n+1)/2];
			System.out.println(Math.max(sum1, sum2));
		}
		else{
			long sum = 0;
			for(int i=0; i<=n/2-1; i++){
				sum = sum - 2*a[i] + 2*a[i+n/2];
			}
			sum = sum + a[n/2-1] - a[n/2];
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 63444
//Aleksander Łukasiewicz
#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int INF = 1000000009;
const int MAXN = 10003;

char text[MAXN + 3];

bool isPalindrome(int i, int j){
    for(int k=0; k<j-i+1; k++){
        if(text[i+k] != text[j-k])
            return false;
    }
    return true;
}

int main(){
    scanf("%s", text + 1);
    int n = strlen(text+1);
    if(isPalindrome(1, n) && isPalindrome(1, (n-1)/2) && isPalindrome((n+3)/2, n))
        puts("Yes");
    else
        puts("No");
    
return 0;
}

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


def solve(N: int, K: int, h: "List[int]"):
    h_sort = sorted(h, reverse=True)
    ans = h_sort[0] - h_sort[-1]
    for i in range(0, N-K+1):
        h_top = h_sort[i]
        h_bottom = h_sort[i+K-1]
        ans = min(ans, h_top - h_bottom)
    print(int(ans))


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 8272