akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n, k, q;
  cin >> n >> k >> q;
  int a[n];
  REP(i, n) cin >> a[i];
  int ans = 2000000000;
  for (int y : a) {
    vector<int> vec;
    multiset<int> st;
    REP(i, n + 1) {
      if (i == n || a[i] < y) {
        sort(ALL(vec));
        int len = vec.size();
        REP(j, len - k + 1) st.insert(vec[j]);
        vec.clear();
      } else {
        vec.push_back(a[i]);
      }
    }
    if (st.size() < q) continue;
    auto it = st.begin();
    REP(i, q - 1) it++;
    int x = *it;
    ans = min(ans, x - y);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007

int now,n,k;

int main(){
  ll ans=0;
  string s;cin>>s;
  n=s.size();
  if (s[n-1]=='0')ans=1LL;
  if (s[n-1]=='1')ans=3LL;
  ll t=1LL;
  REP(i,n-1){
    t=t*3LL%MOD;
    if (s[n-i-2]=='1'){
      ans=(ans*2LL+t)%MOD;
    }
  }

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

Measured memory_bytes: 512
N = int(input())
p = list(map(int, input().split()))

l = list()
for i in range(1,N+1):
    l.append(i)
cnt = 0
for i, c in enumerate(p):
    if c != l[i]:
        cnt += 1
if cnt == 2 or cnt ==0:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,c,d,a[100],b,e;
string s;
int main(){
  for(cin>>n;i<n;i++){
    cin>>a[i];
    c+=a[i];
  }
  c/=n;
  e=c+1;
  for(i=0;i<n;i++){
    d+=pow(c-a[i],2);
    m+=pow(e-a[i],2);
  }
  cout<<min(m,d);
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        while (true)
        {
            int a = Int32.Parse(Console.ReadLine());
            if (a == 0) { break; }
            for (int i = 0; i < 9; i++) { a -= int.Parse(Console.ReadLine()); }
        
            Console.WriteLine(a);
        }
    }
}

Measured memory_bytes: 9036
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
 
int main(){
  //入力
  int a,b,c,d,e;
  int k;
  cin >> a >> b >> c >> d >> e;
  cin >> k;
  
  //長さ5の配列作成
  vector<int> v = { a,b,c,d,e };
  bool ok = true;
  
  //i, jの組み合わせを全て調べる
  for (int i = 0; i < v.size(); i++)
  {
    for (int j = 0; j < v.size(); j++)
    {
      //kを超えている
      if (v[j]- v[i] > k)
      {
        ok = false;
      }
    }
  }
  
  string ans;
  
  if(ok) ans = "Yay!";
  else ans = ":(";
  
  cout << ans << endl;
  return 0;
}

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

int main() {
    int N, K, x=1;
    cin >> N >> K;

    for (int i=0; i<N; i++) {
        x = (x*2 <= x+K ? x*2: x+K);
    }
    cout << x << endl;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld long double
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pi 3.14159265358979323846
#define mod 1000000007
int main()
{ 
    IOS;
    ll p;
    p=1;
    while(p--)
    {
        ll a,b,c,d,e,lcm=1,ans1=0,ans2,ans3,ans4;
        cin>>a>>b>>c>>d;
        ans1=a*c;
        ans2=b*d;
        ans3=a*d;
        ans4=b*c;
        cout<<max(ans1,max(ans2,max(ans3,ans4)))<<endl;
    }
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
#define SET(x) memset(x, 0, sizeof(x))
#define SET2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define SETBOOL(x) memset(x,false,sizeof(x))
#define CLR(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define PII pair<int, int>
#define pf printf

#define sf scanf

#define ALL(x) x.begin(),x.end()
#define pb push_back

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define for0(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=n-1;i>=0;i--)
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
typedef long long ll;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}

template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
int main()
{
    IOS;
    int n,m;
    cin>>n>>m;
    int k = n-1, l = m-1 ;
    cout<<(k*(k+1))/2 + (l*(l+1))/2<<endl;
    return 0;
}


Measured memory_bytes: 256
n, y = gets.strip.split.map(&:to_i)
_i, _j, _k = -1, -1, -1

(0..n).each do |i|
  (0..n-i).each do |j|
    if i*10000+j*5000+(n-i-j)*1000 == y
      _i, _j, _k = i, j, n - i - j
    end
  end
end

puts "#{_i} #{_j} #{_k}"


Measured memory_bytes: 1916
#include <cstdio>
#include <cmath>
using namespace std;
int n, x[10], y[10];
double tot;

int main()
{
    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d %d ", &x[i], &y[i]);

    for (i = 1; i <= n; i++)
        for (j = 1 ; j <= n; j++)
            tot += sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

    tot /= n;
    printf("%lf", tot);

    return 0;
}

Measured memory_bytes: 128
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * 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.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=mp()
uf=UnionFind(n+1)
fr=[[] for i in range(n+1)]
br=[[] for i in range(n+1)]
for i in range(m):
    a,b=mp()
    fr[a].append(b)
    fr[b].append(a)
    uf.union(a,b)
for i in range(k):
    c,d=mp()
    br[c].append(d)
    br[d].append(c)
ans=[]
for i in range(1,n+1):
    c=uf.size(i)-len(fr[i])
    for j in br[i]:
        if uf.same(i,j):
            c-=1
    ans.append(c-1)
print(*ans)

Measured memory_bytes: 114252
sx, sy, tx, ty = map(int, input().split())
dx = tx - sx
dy = ty - sy

s = ''
s += 'R' * dx
s += 'U' * dy
s += 'L' * dx
s += 'D' * dy
s += 'D'
s += 'R' * (dx + 1)
s += 'U' * (dy + 1)
s += 'L'
s += 'U'
s += 'L' * (dx + 1)
s += 'D' * (dy + 1)
s += 'R'

print(s)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	static Scanner sc;
	static char[] ans;

	public static void main(String[] args) throws Exception {
		sc = new Scanner(System.in);
		int n = sc.nextInt();

		StringBuilder sb = new StringBuilder();
		sb.append("? ");
		for (int i = 1; i <= n; i++) {
			sb.append(i).append(' ');
		}
		sb.deleteCharAt(sb.length() - 1);
		System.out.println(sb.toString());
		String s0 = sc.next();
		if (s0.equals("-1")) return;

		int l = 1;
		int r = n + 1;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			sb = new StringBuilder();
			sb.append("? ");
			for (int i = mid; i < mid + n; i++) {
				sb.append(i).append(' ');
			}
			sb.deleteCharAt(sb.length() - 1);
			System.out.println(sb.toString());
			String s = sc.next();
			if (s.equals("-1")) return;
			if (s.equals(s0)) {
				l = mid;
			} else {
				r = mid;
			}
		}

		int n2 = n * 2;
		ans = new char[n2 + 1];
		if (s0.equals("Red")) {
			ans[l] = 'R';
			ans[l + n] = 'B';
		} else {
			ans[l] = 'B';
			ans[l + n] = 'R';
		}

		StringBuilder sb1 = new StringBuilder();
		sb1.append("? ");
		for (int i = l + 1; i < l + n; i++) {
			sb1.append(i).append(' ');
		}
		String s1 = sb1.toString();
		for (int i = 1; i < l; i++) {
			exec(s1, i);
		}
		for (int i = l + n + 1; i <= n2; i++) {
			exec(s1, i);
		}

		StringBuilder sb2 = new StringBuilder();
		sb2.append("? ");
		for (int i = 1; i < l; i++) {
			sb2.append(i).append(' ');
		}
		for (int i = l + n + 1; i <= n2; i++) {
			sb2.append(i).append(' ');
		}
		String s2 = sb2.toString();
		for (int i = l + 1; i < l + n; i++) {
			exec(s2, i);
		}
		sc.close();

		StringBuilder sba = new StringBuilder();
		sba.append("! ");
		for (int i = 1; i <= n2; i++) {
			sba.append(ans[i]);
		}
		System.out.println(sba.toString());
	}

	static void exec(String s1, int i) {
		System.out.println(s1 + i);
		String s = sc.next();
		if (s.equals("-1")) return;
		ans[i] = s.charAt(0);
	}
}


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

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define itrdebug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

void solve(long long A, long long B, long long C, long long K){
    ll answer = 0;
    answer += min(A, K);
    K -= min(A, K);
    K -= min(B, K);
    answer -= min(C, K);
    cout << answer << endl;
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long K;
    scanf("%lld",&K);
    solve(A, B, C, K);
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define fi first
#define se second

int n,x[1001],y[1008];

int NO(){
    int p;
    set<int>st;
    r(i,n){
        st.insert((abs(x[i])+abs(y[i]))%2);
        p=(abs(x[i])+abs(y[i]))%2;
    }
    if(st.size()>1){
        cout<<-1<<endl;
        exit(0);
    }
    return p;
}

signed main(){
    cin>>n;
    r(i,n)cin>>x[i]>>y[i];

    int p=NO();
    int m;

    if(p)m=40;
    else m=40;
    cout<<m<<endl;

    int d[m];

    d[0]=1;

    if(p){r(i,m){
        if(i!=m-1)d[i+1]=d[i]*2;
    }}
    else{
        d[1]=1;
        for(int i=1;i<m;i++){
            if(i!=m-1)d[i+1]=d[i]*2;
        }
    }

    r(i,m/2)swap(d[i],d[m-i-1]);

    r(i,m){
        if(i)cout<<' ';
        cout<<d[i];
    }

    cout<<endl;


        r(i,n){
            int X=x[i];
            int Y=y[i];
            r(j,40){
                if(abs(X)>abs(Y)){
                    if(X>0){
                        cout<<'R';
                        X-=d[j];
                    }
                    else{
                        cout<<'L';
                        X+=d[j];
                    }
                }
                else{
                    if(Y>0){
                        cout<<'U';
                        Y-=d[j];
                    }
                    else{
                        cout<<'D';
                        Y+=d[j];
                    }
                }
                //cout<<X<<' '<<Y<<endl;
            }
            cout<<endl;
            //cout<<X<<' '<<Y<<endl;
        }
    
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
using namespace std;
typedef long long int lli;
struct AB
{
    int a;
    int b;
};
int main(void)
{
    int N, M;
    cin >> N >> M;
    int *H;
    H = new int[N + 1];
    fill(H, H + N + 1, 0);
    int tmp;
    for (int i = 1; i <= N; i++)
    {
        cin >> H[i];
    }
    AB *c;
    c = new AB[M];
    for (int i = 0; i < M; i++)
    {
        cin >> c[i].a >> c[i].b;
    }
    int *mx;
    mx = new int[N + 1];
    fill(mx, mx + N + 1, 0);
    for (int i = 0; i < M; i++)
    {
        mx[c[i].a] = max(H[c[i].b], mx[c[i].a]);
        mx[c[i].b] = max(H[c[i].a], mx[c[i].b]);
    }
    lli cnt = 0;
    for (int i = 1; i <= N; i++)
    {
        if (H[i] > mx[i])
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 5204
/*
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 300010
#define ll long long
#define pii pair<ll,ll>
int a[maxn]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51} ;
int main()
{
	ios::sync_with_stdio(false);
	int k;cin>>k;
	cout<<a[k-1]<<endl;
	return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h = sorted(h)
hMin = 10**9
for i in range(n - k + 1):
    a = h[k + i - 1]-h[i]
    if a < hMin:
        hMin = a
print(hMin)


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

int main(void)
{
  int a,b;
  cin>>a>>b;
  int n=1;
  if(b==100){
    b++;
  }
  for(int i=0;i<a;i++){
    n*=100;
  }
  n*=b;
  cout<<n<<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)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<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);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


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

    if(a+b==15) pl("+")
    else if(a*b==15) pl("*")
    else pl("x")

    return 0;
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

struct edge{
    int to;
    int cost;
    edge(int t, int c){
        to = t;
        cost = c;
    }
};

vector<edge> nodes[100000];
int zahyou[100000];

void init(){
    rep(i, 100000) zahyou[i] = mod;
}

bool dfs(int p, int s){
    bool res = true;
    rep(i, nodes[s].size()){
        int to = nodes[s][i].to;
        if(to == p) continue;
        int cost = nodes[s][i].cost;
        if(zahyou[to] == mod){
            zahyou[to] = zahyou[s] + cost;
            res &= dfs(s, to);
        }
        else if(zahyou[to] != zahyou[s] + cost) return false;
    }
    return res;
}



int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int N, M; cin >> N >> M;
    rep(i, M){
        int l, r, d; cin >> l >> r >> d;
        l--; r--;
        nodes[l].push_back(edge(r, d));
        nodes[r].push_back(edge(l, -d));
    }
    bool ok = true;
    rep(i, N){
        if(zahyou[i] == mod){
            zahyou[i] = 0;
            ok &= dfs(-1, i);
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 13824
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

int main()
{
	int n, r;
	scanf("%d%d", &n, &r);
	if (n <= 10)
	{
		printf("%d\n", r + 100 * (10 - n));
	}
	else
	{
		printf("%d\n", r);
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int64_t n, k; cin >> n >> k;
	vector<int64_t> as(n);
	int64_t maxv = 0;
	FOR_LT(i, 0, n) {
		cin >> as[i];
		maxv = max(maxv, as[i]);
	}

	int64_t ng = 0;
	int64_t ok = maxv;
	while (ng + 1 < ok) {
		int64_t mid = (ng + ok) / 2;
		int64_t ck = 0;
		FOR_LT(i, 0, n) {
			ck += ((as[i] + mid - 1) / mid) - 1;
		}

		if (ck <= k) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	cout << ok << endl;

	return 0;
}

Measured memory_bytes: 4752
n = int( input() )
mod = 10 ** 9 + 7

def njou( x, k ):
    if k == 1:
        return x % mod
    else:
        return njou( x, k - 1 ) * x % mod

# ans = njou( 10, n )
# ans = ans - 2 * ( njou( 9, n ) % mod )
# ans = ( ans + njou( 8, n ) ) % mod
# print( ans )

ans = pow( 10, n, mod )
ans = ans - 2 * pow( 9, n, mod )
ans = ( ans + pow( 8, n, mod ) ) % mod
print( ans )

Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << " = " << x << ".\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define print(xx) cout << (xx) << endl
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
const int INF = ((1LL << 30) + (1LL << 29));
const ll MOD = 1000000007;

/* 
    TITLE:
*/

//=================================================
int N, M, X;
vector<int> A;
//=================================================
void input()
{
cin>>N>>M>>X;
  A.resize(M);
  rep(i,M){
    cin>>A[i];
  }
}

//=================================================
void solve()
{
  int a1 = 0;
  int a2 = 0;
  for (int i = X+1; i < N; ++i){
    for (int j = 0; j < M; ++j){
      if (A[j] == i) {
        a1++;
      }
    }
  }
  for (int i = X-1; i >= 0; --i){
    for (int j = 0; j < M; ++j){
      if (A[j] == i ) {
        a2++;
      }
    }
  }
  cout<<min(a1,a2)<<endl;

}

//=================================================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define queint queue<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>()>
#define pb push_back
#define vec vector<int>
#define vecvec vector<vector<int>>
#define vecll vector<ll>
#define vecvecll vector<vector<ll>>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    ll r=in(),d=in(),x=in();
    rep(i,10){
        x=r*x-d;
        cout<<x<<endl;
    }
}


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


int main(void) {
	int n, x, y, ans[2003] = {}, i, j;
	vector<int> g[2003];

	cin >> n >> x >> y;

	for (i = 0; i < n - 1; i++) {
		g[i].push_back(i + 1);
		g[i + 1].push_back(i);
	}

	g[x - 1].push_back(y - 1);
	g[y - 1].push_back(x - 1);

	int p;
	for (i = 0; i < n; i++) {
		int d[2003] = {};
		queue<int> q;
		q.push(i);
		d[i] = 1;
		while (!q.empty()) {
			p = q.front();
			q.pop();
			for (j = 0; j < g[p].size(); j++) {
				if (d[g[p][j]] == 0) {
					d[g[p][j]] = d[p] + 1;
					q.push(g[p][j]);
				}
			}
		}
		for (j = 0; j < n; j++) {
			if (i != j) ans[d[j]]++;
		}
	}

	for (i = 2; i <= n; i++) {
		cout << ans[i] / 2 << endl;
	}

	return 0;
}

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

bool G[101][101];

int main(){
    int n, u, k, v;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> u >> k;
        for (int j = 0; j < k; j++)
        {
            cin >> v;
            G[u][v] = 1;
        }
        
    }
    
    for (int i = 1; i <= n; i++)
    {
        cout << G[i][1];
        for (int j = 2; j <= n; j++)
        {
            cout << " " << G[i][j];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3116
# ALDS1_6_A Counting Sort
import sys
def counting_sort(A, B):
    k = max(A) + 1
    C = [0] * k  # k = max(A)

    for i in range(len(A)):
        C[A[i]] += 1

    for j in range(1, k):
        C[j] = C[j - 1] + C[j]

    for i in range(len(A) - 1, -1, -1):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1


n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
B = [0] * n

counting_sort(A, B)
print(' '.join(map(str, B)))


Measured memory_bytes: 240328
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

template<long long mod>
struct modint{
    long long num;

    constexpr modint(long long x = 0) : num((x + mod) % mod) {}

    constexpr modint &operator += (const modint& rhs){
        num = (num + rhs.num) % mod;
        return *this;
    }
    constexpr modint &operator -= (const modint& rhs){
        num  -= rhs.num;
        while(num < 0) num += mod;
        num %= mod;
        return *this;
    }
    constexpr modint &operator *= (const modint& rhs){
        num = num * rhs.num % mod;
        return *this;
    }
    constexpr modint &operator /= (modint rhs){
        int exp = mod - 2;
        while(exp > 0){
            if(exp % 2){
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }

    constexpr modint operator ++ (){
        ++num;
        return *this;
    }
    constexpr modint operator ++ (int n){
        modint tmp = *this;
        ++(*this);
        return tmp;
    }
    constexpr modint operator -- (){
        --num;
        return *this;
    }
    constexpr modint operator -- (int n){
        const modint tmp = *this;
        --(*this);
        return tmp;
    }

    void modpow(ll y){
        modint tmp = (*this);
        (*this) = 1;
        while(y > 0){
            if(y % 2){
                (*this) *= tmp;
            }
            tmp *= tmp;
            y /= 2;
        }
    }

    constexpr modint operator + (const modint& rhs) const {
        return modint(*this) += rhs;
    }
    constexpr modint operator - (const modint& rhs) const {
        return modint(*this) -= rhs;
    }
    constexpr modint operator * (const modint& rhs) const {
        return modint(*this) *= rhs;
    }
    constexpr modint operator / (const modint& rhs) const {
        return modint(*this) /= rhs;
    }

    
    friend ostream &operator << (ostream& lhs, const modint& rhs){
        return lhs << rhs.num;
    }

    friend istream &operator >> (istream& lhs, modint& rhs){
        long long tmp;
        lhs >> rhs.num;
        return lhs;
    }
};

#define mint modint<1000000007>

mint fac[2000010];
mint culc(int r, int c){
    return (fac[r + c + 2] / fac[r + 1] / fac[c + 1]) - 1;
}

int r1, r2, c1, c2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r1 >> c1 >> r2 >> c2;
    fac[1] = 1;
    for(int i = 2; i <= 2e6 + 5; i++){
        fac[i] = fac[i - 1] * i;
    }
    cout << culc(r2, c2) - culc(r1 - 1, c2) - culc(r2, c1 - 1) + culc(r1 - 1, c1 - 1) << endl;
    return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int H,W;
int m;
int h[300005],w[300005];
int numh[300005],numw[300005];
int hh[300005],hw[300005];
set<int> sh,sw;
bool flag;
int main(){
    scanf("%d %d",&H,&W);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&h[i],&w[i]);
        numh[h[i]]++;
        numw[w[i]]++;
    }
    int mx=0;
    for(int i=1;i<=H;i++) 
        mx=max(mx,numh[i]);
    for(int i=1;i<=H;i++)
        if(mx==numh[i])
            sh.insert(i);
    int mx2=0;
    for(int i=1;i<=W;i++)
        mx2=max(mx2,numw[i]);
    for(int i=1;i<=W;i++)
        if(mx2==numw[i])
            sw.insert(i);
    flag=0;
    int num=0;
    for(int i=1;i<=m;i++)
        if(sh.find(h[i])!=sh.end() && sw.find(w[i])!=sw.end())
            num++;
    printf("%d\n",mx+mx2-((ll)num==sh.size()*sw.size()));
    return 0;
}

Measured memory_bytes: 36564
/*
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
*/
#include<bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define db double
#define ull unsigned long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 1e6+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int a[maxn],vis[maxn],cnt[maxn];
vector<int> g[maxn];
void init()
{
    int n = 1e6;
    rep(i,2,n)if(!vis[i]){
        for(int j = i;j<=n;j += i) g[j].pb(i);
        for(ll j = (ll)i*i;j<=n;j+=i) vis[j] = 1;
    }
}
int main()
{
    fastio();init();
    int n; cin>>n;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n){
        int r = a[i];
        for(int x:g[r]){
            while(r % x == 0) cnt[x]++,r/=x;
        }
    }
    int pc = 1;
    rep(i,1,n){
        int r = a[i];
        for(int x:g[r]){
            int tmp = 0;
            while(r % x == 0) tmp++,r/=x;
            if(cnt[x] > tmp) pc = 0;
        }
    }
    if(pc) return cout<<"pairwise coprime"<<endl,0;

    set<int> st;
    for(int x:g[a[1]]) st.insert(x);
    rep(i,2,n){
        set<int> tmp,nst;
        for(int x:g[a[i]]) tmp.insert(x);
        for(int x:st) if(tmp.count(x)) nst.insert(x);
        st = nst;
    }
    if(st.size()==0) cout<<"setwise coprime"<<endl;
    else cout<<"not coprime"<<endl;
    return 0;
}


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

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


int main() {

int a,b,c,d;
cin >> a >> b >> c >> d;

if((min(b,d)-max(a,c))>=0)cout << min(b,d)-max(a,c) << endl;
else cout << 0 << endl;



return 0;

}

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

using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    string s;
    cin >> s;
    ll ans = 0, cnt = 0;
    for(int i = 0; i + 1 < s.size(); i++) {
        if (s[i] == 'B') {
            cnt++;
        }
        if (s[i] == 'B' && s[i + 1] == 'W') {
            ans += cnt;
            cnt--;
            swap(s[i], s[i + 1]);
        }
    }
    cout << ans << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Measured memory_bytes: 720
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define rrep(i, n) for(i = n - 1; i >= 0; i--)
using namespace std;

string s;
int ans[200000];
int Next[401][200000];

signed main() {
	int i, j;
	
	cin >> s;
	int n = s.length();
	
	rep(i, n) {
		if (s[i] == 'L') Next[0][i] = i - 1;
		else Next[0][i] = i + 1;
	}
	
	rep(i, 400) {
		rep(j, n) {
			Next[i + 1][j] = Next[i][Next[i][j]];
		}
	}
	
	
	int num[400] = {0};
	num[0] = 1;
	rep (i, 100) {
		rep(j, 400) num[j] *= 10;
		rep(j, 399) {
			num[j + 1] += num[j] / 2;
			num[j] %= 2;
		}
	}
	
	rep(i, n) {
		int pos = i;
		rrep(j, 400) {
			if (num[j] == 1) {
				pos = Next[j][pos];
			}
		}
		ans[pos]++;
	}
	
	rep(i, n) {
		cout << ans[i];
		if (i + 1 < n) cout << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 313472
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
#include <deque>
#define pb push_back
#define make make_pair
#define kaku(a) cout << a << endl
#define isort(a) sort(a.begin(),a.end())

using namespace std;

#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define PI 3.14159265359
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}
long long lcm(long long a,long long b){ return a/gcd(a,b)*b;}

typedef pair<ll,ll> Pair;
const ll inf =1000000007;

//マンハッタン距離
ll mandis(Pair a,Pair b){
    return abs(a.first-b.first)+abs(a.second-b.second);
}

void solve(){
    ll n;
    cin >> n;
    bool ans=true;
    Pair now=make(0,0);
    ll time=0;
    rep(i,n){
        ll t,a,b;
        Pair x;
        cin >> t>>a>>b;
        x=make(a,b);
        ll borrow=t-time;
        time=t;
        if(mandis(x,now)<=borrow && (mandis(x,now)-borrow)%2==0){
            now=x;
        }
        else {
            ans=false;
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout <<"No" << endl;
}


int main(){
    solve();
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
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;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const ll mod = 1e9 + 7ll;
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    int n = readint();
    int k = readint();
    ll ans = 0ll;
    ll r = (1ll * n * (n + 1)) / 2;
    ll l = r;
    ll val1 = 0ll;
    ll val2 = n;
    for (int i = n; i >= k - 1; --i)
    {
        // printf("%d %lld %lld\n", i, l, r );
        ans += (r - l + 1) % mod;
        ans %= mod;
        r -= val1;
        val1++;
        l -= val2;
        val2--;
    }
    printf("%lld\n", ans );
    return 0;
}




Measured memory_bytes: 3772
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
V<ll>F,R;void setF(int n,int mod){F=R=V<ll>(++n);F[0]=1;FOR(i,1,n)F[i]=F[i-1]*i%mod;R[n-1]=modInv(F[n-1],mod);FORR(i,n-1,1)R[i-1]=R[i]*i%mod;}
ll comb(int a,int b,int m){return a<b||b<0?0:F[a]*R[b]%m*R[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7; //998244353;
const int N = 2e3;
int n, a[N];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n) cin >> a[i];
  int ans = 0;
  FOR(i, 0, n)FOR(j, 0, i) ans += a[i]*a[j];
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <random>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
ll mod = 1e9 + 7;

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

	int n;
	cin >> n;
	ll s = 0;
	map<ll, int> m = { { 0, 1 } };
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		ans += m[s += x]++;
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 12800
import heapq
x, y, z, k = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
Z = [int(i) for i in input().split()]
X.sort(reverse=1)
Y.sort(reverse=1)
Z.sort(reverse=1)

Q = []
s = set()
heapq.heappush(Q, (-(X[0]+Y[0]+Z[0]), 0, 0, 0))

def push(i, j, l):
    if (i,j,l) not in s and i<x and j<y and l<y:
        heapq.heappush(Q, (-(X[i]+Y[j]+Z[l]), i, j, l))
        s.add((i, j, l))

for _ in range(k):
    answer, a, b, c = heapq.heappop(Q)
    print(-answer)
    push(a+1, b, c)
    push(a, b+1, c)
    push(a, b, c+1)

Measured memory_bytes: 4852
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,pair<ll,char>>
#define sorted(a_1) sort(a_1.begin(),a_1.end())
#define rsorted(a_1) sort(a_1.rbegin(),a_1.rend())
#define t1(a_1) cout<<a_1<<endl;
#define t2(a_1) for(auto it_test : a_1) cout<<it_test<<" ";
#define MOD 1000000007

ll dp[100001][2];
ll topDown(vector<int>adj[],int parent, int gp, int color){
	
	if(dp[parent][color]>-1) return dp[parent][color];
	ll ways=1;
	for(auto i : adj[parent]){
		ll localways = 0;
		if(i!=gp){
			if(color==1){
				localways = topDown(adj,i,parent,1);
				localways += topDown(adj,i,parent,0);
				localways%=MOD;
			}
			else{
				localways = topDown(adj,i,parent,1);
			}
			ways*=localways;
			ways%=MOD;
		}
	}
	dp[parent][color] = ways;
	return ways;
}

void solve(){
    int n;
    cin>>n;
    vector<int>adj[n];
    for(int i=0;i<n-1;i++){
    	int x,y;
    	cin>>x>>y;
    	adj[x-1].pb(y-1);
    	adj[y-1].pb(x-1);
    }
    memset(dp,-1,sizeof(dp));
    ll ans1 = topDown(adj,0,-1,0);
    ll ans2 = topDown(adj,0,-1,1);
    t1((ans1+ans2)%MOD);

    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    while(t--){
        solve();
    }

return 0;
}

Measured memory_bytes: 18768
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;


int main()
{
    char s[3];
    scanf("%s",s);

    if(s[0]==s[1])
    {
        if(s[1]==s[2])
        {
            printf("No\n");
        }
        else
        {
            printf("Yes\n");
        }
    }
    else
    {
        printf("Yes\n");
    }
    

    return 0;
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
n = int(input())
a = [0]*n
b = list(map(int, input().split()))

a[0]=b[0]
a[n-1]=b[n-2]
for i in range(0,n-2):
    a[i+1] = min(b[i],b[i+1])
    
print(sum(a))

Measured memory_bytes: 3064
#include <cstdio>
#include <cmath>

using namespace std;

int N;
int X;

int main()
{
    scanf("%d", &N);
    X = floor(N / 1.08);
    if (floor(X * 1.08) == N)
    {
        printf("%d\n", X);
    }
    else if (floor((X + 1) * 1.08) == N)
    {
        printf("%d\n", X + 1);
    }
    else
    {
        printf(":(\n");
    }
    return 0;
}


Measured memory_bytes: 128
import itertools

n = int(input())
ln = [int(num) for num in input().split()]

count = 0
for a, b, c in itertools.combinations(ln, 3):
  if a != b and b != c and c != a:
    if (a + b) > c and (b + c) > a and (c + a) > b:
      count += 1

print(count)

Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int) n; i++)
using ll = long long;
template <class T>
using vt = vector<T>;
using vvi = vector<vector<int>>;

int main(){
  //type
  int N, K;
  cin >> N >> K;

  vt<int> x(N);
  rep(i,N)
    cin >> x[i];

  //solve
  int total = 0;
  rep(i,N){
    if(K-x[i] > x[i])
      total += 2*x[i];
    else
      total += (K-x[i])*2;
  }

  cout << total << endl;

  return 0;
}


Measured memory_bytes: 256
n = gets.to_i
s,*w = n.times.map{gets.chomp}
h = {}
h[s] = 1
w.each{|t|
  if s[-1]!=t[0] || h[t]
    puts "No"
    exit
  end
  s = t
  h[t] = 1
}
puts "Yes"

Measured memory_bytes: 1788
from collections import Counter

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

cums = [0]
for a in A:
    cums.append((cums[-1] + a) % M)

ctr = Counter(cums)

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

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

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  
  cout << "L";
  
  for (int i=0; i<ty+1-sy; i++)
    cout << "U";
  for (int i=0; i<tx-sx+1; i++)
    cout << "R";
  for (int i=0; i<ty+1-sy; i++)
    cout << "D";
  for (int i=0; i<tx-sx; i++)
    cout << "L";
  for (int i=0; i<ty-sy; i++)
    cout << "U";
  for (int i=0; i<tx-sx+1; i++)
    cout << "R";
  for (int i=0; i<ty-sy+1; i++)
    cout << "D";
  for (int i=0; i<tx-sx+1; i++)
    cout << "L";
  cout << "U";

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, M, d;
	long long c, sum = 0, digit = 0;
	scanf("%d", &M);
	for (i = 1; i <= M; i++) {
		scanf("%d %lld", &d, &c);
		sum += c * d;
		digit += c;
	}
	printf("%lld\n", digit - 1 + (sum - 1) / 9);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1720
//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
char inp[30];
int x[80][30];
int main() {
	int n;
	cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%s", inp);
		int l = strlen(inp);
		ll cur = 0, e = 0;
		int fl = 0;
		int cnt = 0;
		for (int j = 0; j < l; j++) {
			if (inp[j] == '.') fl = 1;
			else {
				cnt += fl;
				cur = cur * 10 + inp[j] - '0';
			}
		}
		for (int j = 0; j < 9 - cnt; j++)
			cur = cur * 10;
		e = cur;
		int s[2] = {0, 0};
		while (e % 2 == 0) e /= 2, s[0]++;
		while (e % 5 == 0) e /= 5, s[1]++;
		for (int j = max(0, 18 - s[0]); j < 80; j++)
			for (int k = max(0, 18 - s[1]); k < 30; k++)
				ans += x[j][k];
		x[s[0]][s[1]]++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  int n; cin >> n;
  vector<pair<lint, lint>> job(n);
  for(int i = 0; i < n; i++) {
    int x, l; cin >> x >> l;
    job[i] = {x + l, x - l};
  }

  sort(ALL(job));

  int ans = 0;
  lint curTime = -INF;
  for(int i = 0; i < n; i++) {
    int l = job[i].second;
    int r = job[i].first;
    if(curTime <= l) {
      ans++;
      curTime = r;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792