akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;

public class Don
{
    public Don() { }
    private Reader r = new Reader();

    public void Solve()
    {
        var w = r.next();
        for(var i = 0; i < w.Length; i++)
        {
            if (w.Count(c => c == w[i]) % 2 != 0)
            {
                Console.WriteLine("No");
                return;
            }
        }
        Console.WriteLine("Yes");
    }

    public static void Main(string[] args)
    {
        new Don().Solve();
    }

}

class Reader
{
    string[] s;
    int i;
    char[] cs = new char[] { ' ' };

    public Reader()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length)
            return s[i++];
        var input = Console.ReadLine();
        while (input == "")
            input = Console.ReadLine();
        s = input.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return next();
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Measured memory_bytes: 2776
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let _n: usize = input();
    let m: usize = input();
    let (l, r): (Vec<i32>, Vec<i32>) = (0..m)
        .map(|_| {
            let l = input();
            let r = input();
            (l, r)
        })
        .unzip::<i32, i32, _, _>();

    let lmax = l.iter().max().unwrap();
    let rmin = r.iter().min().unwrap();
    println!("{}", std::cmp::max(0, rmin - lmax + 1));
}


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

int main(void){
    int x;
    cin >> x;
    for(int i = x;;i++){
        if(i < 2)continue;
        else {
            bool check = true;
            for(int j = 2;j*j <= i;j++){
                if(i % j == 0)check = false;
            }
            if(check == true){
                cout << i << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 256
import numpy as np

def dist(x,y,d):
    sum=0
    for length in range(d):
       sum=sum+pow(x[length]-y[length],2)
    if not(int(np.sqrt(sum))==float(np.sqrt(sum))):
        return 0
    else:
        return 1

buf=0
count=0
N,D=map(int,input().split())
X=np.zeros((N,D))
for i in range(N):
    buf=input().split()
    for j in range(D):
        X[i][j]=buf[j]

#print(X)
for i in range(N-1):
    for j in range(N-i-1):
        count=count+dist(X[i],X[j+i+1],D)
print(count)

Measured memory_bytes: 12488
from operator import itemgetter
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
edge = set()

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

row, col, cost = zip(*edge)

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)


Measured memory_bytes: 99440
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n;
    cin>>n;
    vvi vec(n,vi(3));
    REP(i,n){
        REP(j,3){
            cin>>vec[i][j];
        }
    }
    vvi dp(n+1,vi(3));
    REP(i,n){
        REP(j,3){
            REP(k,3){
                if(j!=k){
                    chmax(dp[i+1][k],dp[i][j]+vec[i][k]);
                }
            }
        }
    }
    cout<<*max_element(all(dp[n]))<<endl;
    return 0;
}

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


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n; cin >> n;
    int sum = 0, tmp = n;
    while (tmp > 0) {
        sum += tmp % 10;
        tmp /= 10;
    }
    if (n % sum == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#!/snap/bin/pypy3

def main():
    s = input()
    t = input()

    dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
    for i, sc in enumerate(s):
        for j, tc in enumerate(t):
            if sc == tc:
                dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i][j] + 1 else dp[i][j] + 1
            dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i+1][j] else dp[i+1][j]
            dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i][j+1] else dp[i][j+1]

    ans = ''
    i = len(s)
    j = len(t)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1]
            i -= 1
            j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 121180
a=input()
N=len(a)
count=0
bonus=0
for i in range(N-1,-1,-1):
    if int(a[i])+bonus>=6 or (int(a[i])+bonus==5 and (i!=0 and int(a[i-1])>=5)):
        count+=(10-int(a[i])-bonus)
        if i!=0:
            bonus=1
        else:
            count+=1
    else:
        count+=int(a[i])+bonus
        bonus=0
print(count)

Measured memory_bytes: 5492
hoge = input().split()
N = int(hoge[0])
K = int(hoge[1])
score = 0
kcount = 0
for i in range(1,N+1):
  buf = i
  while buf < K:
    kcount += 1
    buf = buf * 2
  score += (1/N) / pow(2,kcount)
  kcount = 0
  buf = 0
    
print(score)

Measured memory_bytes: 3064
n,*a=map(int,open(0).read().split())
c=[0]+a+[0]
y=sum(abs(c[t]-c[t+1])for t in range(n+1))
for i in range(n):
  s,t,r=c[i:i+3]
  print(y+abs(r-s)-abs(t-s)-abs(t-r))

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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long s;
  cin >> s;
  long long d = sqrt(s);
  int x1 = 0, y1 = 0, x2, y2, x3, y3;
  if (d * d == s) {
    x2 = y3 = 0;
    x3 = y2 = d;
  } else {
    ++d;
    x2 = 1;
    y3 = d * d - s;
    x3 = y2 = d;
  }
  cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << endl;
  return 0;
}


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

ll min(ll a, ll b){
	if (a<b) return a;
	else return b;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << min(a, b) + min(c, d) << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int k,t;
    cin >> k >> t;
    vector<int> a(t);
    for (int i=0;i<t;i++) cin >> a[i];
    sort(a.begin(),a.end());
    int s=0;
    for (int i=0;i<t-1;i++) s+=a[i];
    cout << max(0,a[t-1]-s-1) << endl;
}

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

using namespace std;
typedef long long ll;
#define MOD 1000000007
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

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

    int P[n];
    for(int i=0; i<n; i++) cin >> P[i];

    int cnt = 1, j = 0;
    for(int i=1; i<n; i++) {
        if(P[i] <= P[j]) {
            cnt++;
            j = i;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
string s;
int a[]={1,10,9,12,3,4};
int cnt[6];
int ans=0;
int sum;
int memo;
int dp[6][2][13];
int tori[6][13];
signed main(){
	cin>>s;
	reverse(all(s));
	rep(i,s.size()){
		if(s[i]=='?'){
			cnt[i%6]++;
		}
		else{
			sum+=(int)(s[i]-'0')*a[i%6];
		}
	}
	memo=1300000005-sum;
	memo%=13;
	rep(i,6){
		dp[i][0][0]=1;
		rep(j,cnt[i]){
			rep(k,13){
				rep(l,10){
					dp[i][(j+1)%2][(k+l)%13]+=dp[i][j%2][k];
					dp[i][(j+1)%2][(k+l)%13]%=MOD;
				}
				dp[i][j%2][k]=0;
			}
		}
		rep(j,13){
			tori[i][j]=dp[i][cnt[i]%2][j];
		}
	}
	rep(A,13){
		rep(B,13){
			rep(C,13){
				rep(D,13){
					rep(E,13){
						rep(F,13){
							int x=(A*a[0])+(B*a[1])+(C*a[2])+(D*a[3])+(E*a[4])+(F*a[5]);
							x%=13;
							if(x!=memo)continue;
							int pl=1;
							pl*=tori[0][A];
							pl%=MOD;
							pl*=tori[1][B];
							pl%=MOD;
							pl*=tori[2][C];
							pl%=MOD;
							pl*=tori[3][D];
							pl%=MOD;
							pl*=tori[4][E];
							pl%=MOD;
							pl*=tori[5][F];
							pl%=MOD;
							ans+=pl;
							ans%=MOD;
						}
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
s = list(input())
n = len(s) + 1

l = [0] * n
r = [0] * n

for i, c in enumerate(s, 1):
    if c == '>':
        l[i] = 0
    else:
        l[i] = l[i - 1] + 1

for i, c in enumerate(s[::-1]):
    i = n - 2 - i
    if c == '<':
        r[i] = 0
    else:
        r[i] = r[i + 1] + 1

seq = [x if x > y else y for x, y in zip(l, r)]

ans = sum(seq)
print(ans)
    

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

int main()
{
  int n; cin >> n;
  string s; cin >> s;
  int ans = 0;
  rep(i, n-2) {
    if (s.substr(i, 3)=="ABC") ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
while 1:
  n = input()
  if n==0: break
  d = [0]*n
  for i in range(n):
    x = map(int, raw_input().split())
    d[i]=[sum(x[1::2])*60+sum(x[2::2]),x[0]]
  d = sorted(d)
  print d[0][1]
  print d[1][1]
  print d[-2][1]

Measured memory_bytes: 4988
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
// #define MULTIPLE_TESTS 1

int n;
vector<ll> arr;
void readArray() {
    arr.resize(n);
    for (auto &a: arr) {
        cin >> a;
    }
}

void solve() {
    ll a;
    double b;
    cin >> a >> b;
    ll res = round(b*100);
    res *= a;
    res /= 100;
    cout << res << endl;
}

int main() {
    FAST_IO;
    int t = 1;
    #ifdef MULTIPLE_TESTS
    cin >> t;
    #endif

    while (t--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3720
n = int(input())
a = list(map(int, input().split()))
def f(x):
    b = '0' * 64 + bin(x)[2:]
    b = b[::-1]
    b = b[:64]
    return list(map(int, list(b)))

bit_count = [0] * 64
for i in a:
    b = f(i)
    for j in range(64):
        bit_count[j] += b[j]

ans = 0
for i in range(64):
    bc = bit_count[i]
    ans += (2**i) * bc * (n - bc)
    ans %= 10**9 + 7

print(ans)

Measured memory_bytes: 116592
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long ll;

int N, K;
int a[105];
bool dp[100005], mem[100005];


bool func(int k) {
	if (k <= 0) return false;
	if (mem[k]) return dp[k];
	for (int i = 0; i < N; i++) {
		if (a[i] > k) continue;
		if (!func(k - a[i])) return dp[k] = mem[k] = true;
	}
	mem[k] = true;
	return dp[k] = false;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> a[i];
	cout << (func(K) ? "First" : "Second") << endl;
	return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> A(n, vector<int>(m));
    vector<int> b(m);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> A.at(i).at(j);
        }   
    }

    vector<int> ans(n, 0);
  
  	for(int i = 0; i < m; i++) {
    	cin >> b.at(i);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            ans.at(i) += A.at(i).at(j)*b.at(j);
        }   
    }

    for(int i = 0; i < n; i++) {
        cout << ans.at(i) << endl;
    }
}


Measured memory_bytes: 3140
import collections
n = int(input())
v = list(map(int, input().split()))
odd = [k for i, k in enumerate(v) if i % 2 == 1]
even = [k for i, k in enumerate(v) if i % 2 == 0]

odd = collections.Counter(odd).most_common()
even = collections.Counter(even).most_common()

odd.append([0, 0])
even.append([0, 0])
ans = odd[0][1] + even[0][1]
if odd[0][0] == even[0][0]:
    ans = max(odd[0][1] + even[1][1], odd[1][1]+even[0][1])
print(n - ans)


Measured memory_bytes: 66572
def rpn(eq)
  # Reverse Polish Notation
  stack = []
  infix = [] # << infix notation
  eq.each{|i|
    case i
    when "+"
      b = stack.pop
      return nil if stack.size == 0
      stack[-1] += b

      n2 = infix.pop
      n1 = infix.pop
      infix << "(#{n1}+#{n2})"
    when "-"
      b = stack.pop
      return nil if stack.size == 0
      stack[-1] -= b

      n2 = infix.pop
      n1 = infix.pop
      infix << "(#{n1}-#{n2})"
    when "*"
      b = stack.pop
      return nil if stack.size == 0
      stack[-1] *= b

      n2 = infix.pop
      n1 = infix.pop
      infix << "(#{n1}*#{n2})"
    else
      stack << i
      infix << i
    end
  }
  return [stack[0], infix[0]] if stack.size == 1
  return nil
end

ope = ["+", "-", "*"]
opes = ope.repeated_combination(2).to_a
while input = gets
  input.chomp!
  break if input == "0 0 0 0"
  found = false
  lists = input.split.map(&:to_i).permutation.to_a.uniq
  lists.each{|list|
    eq = list[0,2]
    opes.each{|o|
      (list[2,2] + o[0,2]).permutation.to_a.uniq.each{|arr|
        ope.each{|p|
          ans = rpn(eq + arr + [p])
          if ans && ans[0] == 10
            found = ans[1]
            break
          end
        }
        break if found
      }
      break if found
    }
    break if found
  }
  if found
    puts found
  else
    puts 0
  end
end

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }

template<typename T>
vector<T> makeVector(size_t a, T b) { return (vector<T>(a, b)); }
template<typename... Ts>
auto makeVector(size_t a, Ts... ts) { 
	return (vector<decltype(makeVector(ts...))>(a, makeVector(ts...)));
}

template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	if (v.size()) {
		os << v[0];
		for (int i = 1; i < v.size(); i++) os << " " << v[i];
	}
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


void Main() {
	ll N, X; cin >> N >> X;
	ll length = 1;
	for (int i = 0; i < N; i++) {
		length = 3 + 2*length;
	}

	ll cnt = 0;
	while (N > 0 && X > 0) {
		ll nxtlength = (length-3)>>1;
		if (X >= nxtlength+2) {
			cnt += (1ll<<N);
			X -= nxtlength+2;
		} else {
			X--;
		}
		N--;
		length = nxtlength;
	}
	if (N == 0 && X > 0) cnt++;
	cout << cnt << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 3632
def main():
  N = int(input())
  ans = ''
  abc = "abcdefghijklmnopqrstuvwxyz"
  
  
  while N > 0:
    N -=1
    ans += abc[N % 26]
    
    N = N//26
  
  print(ans[::-1])
  
  
  
main()

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

int main() {
  int N,x;
  cin >> N >> x;
  int a[N];
  for(int i=0; i<N; i++){
    cin >> a[i];
  }
  
  sort(a,a+N);
  int count =0;
  for(int i=0;i<N;i++){
    if((x >= a[i] && i != N-1) || (x == a[i] && i == N-1)){
      //      cout << x << " " << a[i] << endl;
      x -= a[i];
      count++;
    }
    else break;
  }
  cout << count << endl;

}


Measured memory_bytes: 256
N = int(input())
C = input()
ALL_R = "R" * len(C)
ALL_W = "W" * len(C)
RW = "R" * C.count("R") + "W" * C.count("W")
cnt1 = 0
cnt2 = 0
cnt3 = 0
for i in range(len(C)):
    if C[i] != ALL_R[i]:
        cnt1 += 1
    if C[i] != ALL_W[i]:
        cnt2 += 1
    if C[i] != RW[i]:
        cnt3 += 1
cnt3 //= 2
print(min(cnt1, cnt2, cnt3))


Measured memory_bytes: 68640
// 127_C_Prison.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


//回答方針
//閉区間[l_i, r_i]（i=1,...,m）の共通部分に含まれる整数の個数を求めればよい。
//その閉区間は[max(l_i), min(r_i)]で表される。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m = 0;
	cin >> n >> m;

	vector<int> l;
	vector<int> r;

	for (int i = 0; i < m; i++)
	{
		int a, b = 0;
		cin >> a >> b;
		l.push_back(a);
		r.push_back(b);
	}
	
	//最大値
	decltype(l)::iterator l_max = max_element(l.begin(), l.end());

	//最小値
	decltype(r)::iterator r_min = min_element(r.begin(), r.end());

	int count = *r_min - *l_max + 1;
	if (count < 0) count = 0;

	cout << count;

	return 0;
}


Measured memory_bytes: 1276
let n = Scanf.scanf " %d" (+) 0
let cs, ss, fs, t, k = Array.(make (n - 1) 0, make (n - 1) 0, make (n - 1) 0, ref 0, ref 0)
let _ = Array.init (n - 1) @@ fun i -> Scanf.scanf " %d %d %d" @@ fun a b c -> cs.(i) <- a; ss.(i) <- b; fs.(i) <- c
let _ = for j = 0 to n - 2 do t := 0; for i = j to n - 2 do k := max 0 @@ (!t - ss.(i) + fs.(i) - 1) / fs.(i); t := ss.(i) + !k * fs.(i) + cs.(i) done; Printf.printf "%d\n" !t done; print_endline "0"

Measured memory_bytes: 896
#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int d[2]={0},t;
	rep(i,2) rep(j,4)cin >> t , d[i] += t;
	cout << max(d[0],d[1]) << endl;
}

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

using namespace std;

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

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

int a, b, c, d, e, n, m, k;
string s, t, r;
char c1, c2, c3;

int A[200005];
int B[200005];
int C[200005];

int main() {
	int n, k;
	cin >>k>>n;
	int f = -1;
	int l = 0;
	int maxx = 0;
	for (int i=0 ; i<n ; i++) {
		int x;
		cin >>x;
		if (!i) {
			f = x;
		} else {
			maxx = max(maxx, x-l);
		}
		l=x;
	}
	maxx = max(maxx, k-l+f);
	cout <<k-maxx<<endl;
	return 0;
}

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

int main()
{

        int a = 0;
        int b = 0;
        int k = 0;


        cin >> a >> b >> k;

        int total = b - a;

        for (int i = 1, ii = a; ii <= b; ++i, ++ii) {

                if (i <= k || i >= total - k + 2) {
                        cout << ii << endl;
                }


        }


}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int ct = 0,N;
  char c;
  scanf("%d\n",&N);
  for(;N>0;N--){
    scanf("%c",&c);
    if(c == 'R'){ct++;}else{ct--;}
  }
  if(ct > 0){printf("Yes\n");}
  else{printf("No\n");}
  return 0;
}

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

using namespace std;

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

    int n;
    char c;

    while (cin >> n, n) {
        vector<int> cnt((int)('Z' - 'A') + 1);
        pair<int, int> idx(0, 1);
        int find = -1;

        for (int i = 0; i < n; ++i) {
            cin >> c;

            if (find != -1) continue;

            int cur = (int)(c - 'A');
            ++cnt[cur];
            if (cur != idx.first && cnt[idx.second] < cnt[cur]) idx.second = cur;
            if (cnt[idx.first] < cnt[idx.second]) swap(idx.first, idx.second);

            if (cnt[idx.second] + (n - i - 1) < cnt[idx.first]) find = i + 1;
        }

        if (cnt[idx.first] == cnt[idx.second]) cout << "TIE\n";
        else cout << (char)(idx.first + 'A') << " " << find << '\n';
    }

    return 0;
}



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

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++){
		if(i%2==0 && s[i] == 'L' || i%2 && s[i] == 'R'){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int MOD = 1000 * 1000 * 1000 + 7;
int mod(int n) {
    n %= MOD;
    if (n < 0) return n + MOD;
    else return n;
}   
int fp(int a, int p) {
    int ans = 1, c = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) ans = mod(ans * c);
        c = mod(c * c);
    }   
    return ans;
}   
int dv(int a, int b) { return mod(a * fp(b, MOD - 2)); }

const int N = 1e6 + 7;
int f[N], inv[N];
void prec() {
    f[0] = 1;
    for (int i = 1; i < N; ++i)
        f[i] = mod(f[i - 1] * i);
    inv[N - 1] = fp(f[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i)
        inv[i] = mod(inv[i + 1] * (i + 1));
}
int C(int n, int k) {
    return mod(f[n] * mod(inv[k] * inv[n - k]));
}   

void add(int &a, int b) { a = mod(a + b); }

int dp[N];
int t[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    prec();
    int n, h, d;
    cin >> n >> h >> d;
    for (int mx = 1; mx <= d; ++mx)
        dp[mx] = f[n];

    int fc = 0;
    for (int cnt = 1; cnt <= n; ++cnt)
        add(fc, f[cnt]);

    int cur = 0;
    for (int mx = 1; mx <= h; ++mx) {
        add(cur, t[mx]);
        add(dp[mx], cur);
        int de = mod(dp[mx] * fc);
        add(t[mx + 1], de);
        int r = min(mx + d, h);
        add(t[r + 1], -de);
    }                       
    cout << dp[h] << endl;
}

Measured memory_bytes: 31488
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	m := map[int]int{}
	for i := 0; i < 3; i++ {
		m[nextInt()]++
	}
	fmt.Println(len(m))
}


Measured memory_bytes: 640
#include <stdio.h>

int main(){
  int a,b,c;
  scanf("%d%d%d",&a,&b,&c);

  if(a + b <= a + c){
    if(a + b <= b + c){
      printf("%d\n",a + b);
    }else{
      printf("%d\n",c + b);
    }
  }else{
    if(a + c <= b + c){
      printf("%d\n",a + c);
    }else{
      printf("%d\n",b + c);
    }
  }
  return 0;
}


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

int main() {
    string S, T;
    cin >> S >> T;

    vector<string> res;
    for (int i = 0; i < S.size() - T.size() + 1; i++) {
        bool flag = true;
        string t = S;
        if (S[i] == '?' || S[i] == T[0]) {
            for (int j = 0; j < T.size(); j++) {
                if (S[i + j] != '?' && S[i + j] != T[j]) {
                    flag = false;
                    break;
                }
                t[i + j] = T[j];
            }
            if (flag) {
                for (int j = 0; j < t.size(); j++) {
                    if (t[j] == '?') {
                        t[j] = 'a';
                    }
                }
                res.push_back(t);
            }
        }
    }

    if (res.empty()) {
        cout << "UNRESTORABLE" << endl;
    } else {
        sort(res.begin(), res.end());
        cout << res[0] << endl;
    }
    return 0;
}

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

using namespace std;
typedef long long lint;

#define RPT(i, b, e) for (int i = (b); i <= (e); i++)
#define RPT0(i, n) RPT(i, 0, n - 1)
#define RPT1(i, n) RPT(i, 1, n)
#define EACH(it, v) for (const auto& it : v)
#define ALL(v) v.begin(), v.end()

bool IsLL(int x)
{
    if (x < 10) return true;
    string str = to_string(x);
    int keta = str.length();
    bool b = true;
    RPT0(i, keta - 1) if (abs(str[i + 1] - str[i]) > 1) return false;
    return true;
}

void resolve()
{
    int K;
    cin >> K;

    if (K <= 9) {
        cout << K << endl;
        return;
    }

    vector<lint> a;
    RPT1(i, 9) a.push_back(i);
    while (1) {
        if (K <= a.size()) {
            cout << a[K - 1] << endl;
            return;
        }
        K -= a.size();
        vector<lint> old;
        swap(old, a);
        EACH(it, old)
        {
            for (int i = -1; i <= 1; i++) {
                int d = it % 10 + i;
                if (d < 0 || d > 9) continue;
                a.push_back(it * 10 + d);
            }
        }
    }
}

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


Measured memory_bytes: 1712
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int x,y,a,b,c; cin >> x >> y >> a >> b >> c;
    ll total = 0;
    int apples[3][100000];
    FOR(i,a) cin >> apples[0][i];
    FOR(i,b) cin >> apples[1][i];
    FOR(i,c){
        cin >> apples[2][i];
//        if(i<a) apples[2][i] = max(apples[2][i],apples[0][i]);
//        if(i<b) apples[2][i] = max(apples[2][i],apples[1][i]);
    }
    sort(apples[0],apples[0]+a);
    sort(apples[1],apples[1]+b);
    sort(apples[2],apples[2]+c,greater<int>());
    int ptr1 = a-x,ptr2 = b-y,ptr3 = 0;
    cerr << apples[0][ptr1] << " " << apples[1][ptr2] << " " << apples[2][ptr3]<< endl;
    while(ptr3<c){
        if(ptr1<a){
            if(ptr2<b){
                if(apples[0][ptr1] < apples[1][ptr2]){
                    if(apples[2][ptr3] > apples[0][ptr1]){
                        total += apples[2][ptr3++]; ptr1++;
                    }else break;
                }else{
                    if(apples[2][ptr3] > apples[1][ptr2]){
                        total += apples[2][ptr3++]; ptr2++;
                    }else break;
                }
            }else{
                if(apples[2][ptr3] > apples[0][ptr1]){
                    total += apples[2][ptr3++]; ptr1++;
                }else break;
            }
        }else if(ptr2 < b){
            if(apples[2][ptr3] > apples[1][ptr2]){
                total += apples[2][ptr3++]; ptr2++;
            }else break;
        }else break;
    }
    F0R(i,ptr1,a-1) total += apples[0][i];
    F0R(i,ptr2,b-1) total += apples[1][i];
    cout << total << endl;
    return 0;
}


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

#define REP(i, s,  n) for(int i = s;i < (n);i++)
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> PP;

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

//---------------------------------------------------------------
// 20:43 - 
//---------------------------------------------------------------

int N, K;

signed main(){
	cin >> N >> K;
	
	// Ｎ以下でＫで割り切れる数字の数（これが a, b, c の対象）
	long long x1 = N / K;
//	long long x1 = 0;
//	REP(i, 1, N+1) {
//		if(i % K == 0)	x1++;
//	}
	
	long long x2 = 0;
	if(K % 2 == 0) {
		// 偶数ならあまりがＫ／２も a, b, c の対象
		x2 = (N + (K / 2)) / K;
//		REP(i, 1, N+1) {
//			if(i % K == K/2)	x2++;
//		}
	}
	// x1 と x2 は混ざらない
	long long ans = x1 * x1 * x1 + x2 * x2 * x2; 
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	char str[5];
	
	scanf("%s",str);
	
	if(str[0]==str[1]&&str[0]==str[2]&&str[1]==str[2]){
		printf("No\n");
	}
	else{
		printf("Yes\n");
	}

	return 0;
}

Measured memory_bytes: 1608
import java.util.*;       

public class Main{
     public static void main(String[] args){
            int mx=3;
            int table[]=new int[mx];
            Scanner sc = new Scanner(System.in);
            int i;
            for(i=0;i<mx;i++){
                table[i]=sc.nextInt();
            }
            
            for(i=1;i<mx;i++){
                if(table[i-1]>table[i]){
                    int c=table[i-1];
                    table[i-1]=table[i];
                    table[i]=c;
                }
            }
            for(i=1;i<mx;i++){
                if(table[i-1]>table[i]){
                    int c=table[i-1];
                    table[i-1]=table[i];
                    table[i]=c;
                }
            }
            
            
            for(i=0;i<mx;i++){
                System.out.printf("%d",table[i]);
                if(i+1!=mx){
                    System.out.printf(" ");
                }
            }
            System.out.printf("\n");
            
            
        }
    }


Measured memory_bytes: 26436
#include<bits/stdc++.h>
using namespace std;
int main(){
    const int inf=2000000000;
    int n,m;
    cin>>n>>m;
    int l[m],r[m],d[m];
    vector<vector<pair<int,int>>>pas(n);//情報をグラフと見て、BFSで座標を確定させる
    for(int i=0;i<m;i++){
        cin>>l[i]>>r[i]>>d[i];
        pas[l[i]-1].push_back({r[i]-1,d[i]});
        pas[r[i]-1].push_back({l[i]-1,d[i]*-1});
    }
    vector<int>x(n,inf);
    vector<int>check(n,0);
    x[0]=0;
    for(int i=0;i<n;i++){
        if(check[i])continue;
        check[i]=1;
        queue<int>q;
        q.push(i);
        while(q.size()){
            int f=q.front();
            q.pop();
            for(int j=0;j<pas[f].size();j++){
                int next=pas[f][j].first;
                int dist=pas[f][j].second;
                if(x[next]!=inf && x[next]!=x[f]+dist){
                    cout<<"No"<<endl;
                    return 0;
                }
                if(check[next]==0){
                    x[next]=x[f]+dist;
                    check[next]=1;
                    q.push(next);
                }
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 12160
def inpl(): return list(map(int, input().split()))
N = int(input())
a = inpl()

ans = 0
temp = 200000
c = 0
for i in a:
    if temp != i:
        ans += c//2
        c = 0
    c += 1
    temp = i
ans += c//2
print(ans)

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

using namespace std;

typedef struct Data
{
	int p;
	int x;
}Data;

int main()
{
	int N; cin >> N;
	vector<int> time( N );

	for (int n = 0; n < N; n++)
	{
		cin >> time[n];
	}

	int M; cin >> M;
	vector<Data> drink( M );
	
	for (int m = 0; m < M; m++)
	{
		cin >> drink[m].p >> drink[m].x;
	}

	for (int i = 0; i < M; i++)
	{
		int sum = 0;
		for (int j = 0; j < N; j++)
		{
			if (drink[i].p - 1 == j)
			{
				sum += drink[i].x;
				continue;
			}
			else
			{
				sum += time[j];
			}
		}
		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 888
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    S,T=input().split()
    A,B=map(int,input().split())
    U=input()
    if S==U:
        A-=1
    else:
        B-=1
    print(A,B)


    return 

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
from fractions import gcd
n, k = map(int, input().split())
a = list(map(int, input().split()))

a_gcd = a[0]
for i in range(1, n):
    a_gcd = gcd(a_gcd, a[i])
ans = True
if k > max(a):
    ans = False
if k % a_gcd != 0:
    ans = False
if k in a:
    ans = True

print('POSSIBLE' if ans else 'IMPOSSIBLE')

Measured memory_bytes: 16240
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
int main(){
    double x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << fixed << sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) << endl;
}


Measured memory_bytes: 3268
from collections import deque

LI = lambda: list(map(int, input().split()))

n, m, k = LI()
adj = [[] for i in range(n)]
for i in range(m):
    a, b = LI()
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
c = []
d = []
for i in range(k):
    tmp = LI()
    c.append(tmp[0]-1)
    d.append(tmp[1]-1)

cc = [i for i in range(n)]
num = [0 for i in range(n)]
for i in range(n):
    if cc[i] == i:
        dq = deque([i])
        while dq:
            j = dq.popleft()
            for l in adj[j]:
                if cc[l] != i:
                    cc[l] = i
                    num[i] += 1
                    dq.append(l)

sf = []
for i in range(n):
    sf.append(num[cc[i]])

for i in range(n):
    sf[i] -= len(adj[i])

for i in range(k):
    if cc[c[i]] == cc[d[i]]:
        sf[c[i]] -= 1
        sf[d[i]] -= 1

print(' '.join(map(str, sf)))

Measured memory_bytes: 49052
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,n,h) for(int i = n; i < h; ++i)
#define rep3(l,n,h) for(int l = n; l <= h; ++l)
typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;

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

int main(void) {
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x = x2 - x1, y = y2 - y1;
    int x3 =x2 - y;
    int y3 = y2 + x;
    int x4 = x1 - y;
    int y4 = y1 + x;
    cout << x3 << " "<< y3 << " " << x4  << " " << y4;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
	int w,len;
	char s[1010];
	scanf("%s",s+1);
	cin>>w;
	len=strlen(s+1);
	for(int i = 1; i<=len;i+=w){
		printf("%c",s[i]);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;
#define ll long long int
#define ld long long double
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define nl '\n'
#define mp make_pair
#define debug1(x) cout <<#x<<" "<<x<<'\n';
#define debug2(x,y) cout <<#x<<" "<<x <<" "<<#y<<" "<<y <<'\n';
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<'\n';
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define inf 1e18
const int mod = (int)1e9 + 7;
pair<ll, ll>s4[4] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};
pair<ll, ll>s8[8] = {{ -1, -1}, { -1, 0}, { -1, 1}, {0, -1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};

void judge() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

void solve() {
	ll n;
	cin >> n;
	map<int, int>mp;
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		mp[x]++;
		sum += x;
	}
	ll q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		int tmp = mp[a];
		mp[a] = 0;
		mp[b] += tmp;

		sum += tmp * (b - a);
		cout << sum << nl;
	}


}

signed main() {
	judge();
	boost;
	solve();
}


Measured memory_bytes: 7924
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace AtCoder
{
    class Program
    {
        #region
        private static int ReadInt() => int.Parse(ReadLine());
        private static IEnumerable<int> ReadSplitInt() => Console.ReadLine().Split(' ').Select(i => int.Parse(i));
        private static IEnumerable<double> ReadSplitDouble() => Console.ReadLine().Split(' ').Select(i => double.Parse(i));

        private static bool IsEven(int n) => n % 2 == 0;
        #endregion

        public static void Main(string[] args)
        {
            var nm = ReadSplitInt().ToArray();
            var x = ReadSplitInt().OrderBy(v => v).ToArray();

            if (nm[0] >= nm[1])
            {
                WriteLine(0);
                return;
            }

            List<int> d = new List<int>();
            for (int i = 0; i < x.Count() - 1; i++)
            {
                d.Add(x[i + 1] - x[i]);
            }
            int[] da = d.OrderByDescending(val => val).ToArray();

            if (nm[0] == 1)
            {
                WriteLine(d.Sum());
                return;
            }

            int sum = d.Sum();
            for (int i = 0; i < nm[0] - 1; i++)
            {
                sum -= da[i];
            }
            WriteLine(sum);
        }
    }
}

Measured memory_bytes: 24032
#include<bits/stdc++.h>
using namespace std;
int MIN=9999;
string S;
long long int MOD = 1000000007;
const int MAX = 1000001;
long long int fac[MAX],finv[MAX], inv[MAX];

void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i=2;i<MAX;i++){
        fac[i] = fac[i-1]* i % MOD;
        inv[i] = MOD - inv[MOD%i]*(MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

long long COM(int n,int k){
    if(n < k)return 0;
    if(n < 0 || k< 0)return 0;
    return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;
}

int main(){
    long long int N,K,p[200001],k[200001];

    
    cin >> N >> K;
    int a,b;
        vector<vector<int> > graph = vector<vector<int> >(N+1,vector<int>(0));
    for(int i=0;i<N-1;i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    queue<pair<int,int> > que;
    que.push(make_pair(0,1));
    for(int i=0;i<200000;i++)
        p[i] = 0;
    while(!que.empty()){
        pair<int,int> target = que.front();
        int parent = target.first;
        int node = target.second;
        que.pop();
        long long int iro = p[node];
        long long int point = K - iro;
        if(node != 1){
            point--;
        }
        if(parent != 1 && node != 1){
            point--;
        }
        k[node] = point;
        int is = 0;
        for(int i=0;i<graph[node].size();i++){
            if(graph[node][i] == parent)
                continue;
            else{
                int ns = graph[node][i];
                p[ns] = is;
                is++;
                que.push(make_pair(node,ns));
            }
        }
    }
    long long int res=1;
    for(int i=1;i<=N;i++){
        res = (res*k[i]) % MOD;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 9976
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;

int main() {
	string S;
	cin >> S;
	int ans = 0;
	for (int i = 1; i < S.size(); i++) {
		if (S[i - 1] != S[i]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
from collections import defaultdict
def solve():
    N = int(input())
    d = defaultdict(int)

    for _ in range(N):
        S = input()
        d[S] += 1

    items = list(d.items())
    items.sort(key=lambda x:x[1], reverse=True)
    mx = items[0][1]
    cand = []
    for item in items:
        if item[1] == mx:
            cand.append(item[0])
        else:
            break
    
    ans = sorted(cand)
    print(*ans, sep='\n')
    
if __name__ == '__main__':
    solve()

Measured memory_bytes: 122712
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  int l=s.length();
  for(int i=0;i<l;i++){
   // if(s.at(i)=='?' && s.at(i+1)=='D') 
     // s.at(i)='P'; 
    //if(s.at(i)=='?'&& s.at(i+1)=='?') {
      //s.at(i)='P';
      //s.at(i+1)='D';
    
    if(s.at(i)=='?')
      s.at(i)='D';
  }
    cout<<s;
}


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N;
    cin >> N;
    vector<string> s(N);
    for (int i=0; i<N; ++i) cin >> s[i];

    vector<ll> cnt(5);
    for (string S : s) {
        if (S.front() == 'M') cnt[0]++;
        else if (S.front() == 'A') cnt[1]++;
        else if (S.front() == 'R') cnt[2]++;
        else if (S.front() == 'C') cnt[3]++;
        else if (S.front() == 'H') cnt[4]++;
    }
    ll ans = 0;
    for (int i=0; i<5; ++i) {
        for (int j=i+1; j<5; ++j) {
            for (int k=j+1; k<5; ++k) {
                ans += cnt[i] * cnt[j] * cnt[k];
            }
        }
    }
    cout << ans << endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 6284
import sys
N,A,B = map(int,input().split())

if not (1 <= N <= 10000 and 1 <= A <= 36 and 1 <= B <= 36):
    sys.exit()

sum = 0
for I in range(1,N+1):
    tmp = list(str(I))
    check = 0
    for J in range(len(tmp)):
        check += int(tmp[J])
    if A <= check <= B:
        sum += I
print(sum)


Measured memory_bytes: 9132
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {

    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      String[] lines = in.readLine().split(" ");
      int[] params = new int[lines.length];
      int k=0;
      for (String s : lines) {
        params[k++] = Integer.parseInt(s);
      }

      int ans = Integer.MAX_VALUE;
      int max = params[3] + params[4];
      for(int i=0; i<max; i++) {
        int t = 2 * params[2] * i
          + Math.max(params[3] - i, 0) * params[0]
          + Math.max(params[4] - i, 0) * params[1];
        ans = Math.min(ans, t);
      }

      System.out.println(ans);

    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 23252
#include<stdio.h>
#include<string.h>
#define POINT_MAX 21

enum
{
	EXISTENCE,			//宝石有
	NON_EXISTENCE,		//宝石無
};


typedef struct coord_info
{
	short x_point;
	short y_point;
} COORD_INFO;

typedef struct move_operation
{
	char course;
	short distance;
} MOVE_OPE;

main()
{
	while(1)
	{
		COORD_INFO current_place;
		current_place.x_point = 10;
		current_place.y_point = 10;
		short i = 0, j = 0;
		short gems_count = 0;			//宝石個数
		short gems_info[POINT_MAX][POINT_MAX];
		for( i = 0; i < POINT_MAX; i++ )
		{
			for( j = 0; j < POINT_MAX; j++ )
			{
				gems_info[i][j] = NON_EXISTENCE;
			}
		}
		
		short gems_num = 0;
		scanf( "%hd", &gems_num );
		if( gems_num == 0 )
		{
			break;
		}
		//宝石情報の入力
		for( i = 0; i < gems_num; i++ )
		{
			short gems_xpoint = 0, gems_ypoint = 0;
			scanf( "%hd %hd", &gems_xpoint, &gems_ypoint );
			gems_info[gems_xpoint][gems_ypoint] = EXISTENCE;
		}
		
		short move_num = 0;					//移動回数
		scanf( "%hd", &move_num );
		getchar();
		MOVE_OPE move_info[move_num];
		memset( move_info, 0, sizeof( MOVE_OPE ) * move_num );
		//移動情報の入力
		for( i = 0; i < move_num; i++ )
		{
			scanf("%c %hd", &move_info[i].course, &move_info[i].distance );
			getchar();
		}
		
		//移動＋宝石の収集
		for( i = 0; i < move_num; i++ )
		{
			//北方向に移動
			if( move_info[i].course == 'N' )
			{
				for( j = 0; j < move_info[i].distance; j++ )
				{
					current_place.y_point++;
					if( gems_info[current_place.x_point][current_place.y_point] == EXISTENCE )
					{
						gems_info[current_place.x_point][current_place.y_point] = NON_EXISTENCE;
						gems_count++;
					}
				}
			}
			//東方向に移動
			else if(  move_info[i].course == 'E' )
			{
				for( j = 0; j < move_info[i].distance; j++ )
				{
					current_place.x_point++;
					if( gems_info[current_place.x_point][current_place.y_point] == EXISTENCE )
					{
						gems_info[current_place.x_point][current_place.y_point] = NON_EXISTENCE;
						gems_count++;
					}
				}
			}
			//南方向に移動
			else if(  move_info[i].course == 'S' )
			{
				for( j = 0; j < move_info[i].distance; j++ )
				{
					current_place.y_point--;
					if( gems_info[current_place.x_point][current_place.y_point] == EXISTENCE )
					{
						gems_info[current_place.x_point][current_place.y_point] = NON_EXISTENCE;
						gems_count++;
					}
				}
			}
			//東方向に移動
			else if(  move_info[i].course == 'W' )
			{
				for( j = 0; j < move_info[i].distance; j++ )
				{
					current_place.x_point--;
					if( gems_info[current_place.x_point][current_place.y_point] == EXISTENCE )
					{
						gems_info[current_place.x_point][current_place.y_point] = NON_EXISTENCE;
						gems_count++;
					}
				}
			}
		}
		if( gems_count == gems_num )
		{
			printf( "Yes\n" );
		}
		else
		{
			printf( "No\n" );
		}
	}
	
	return 0;
}

Measured memory_bytes: 596