akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;
const ll INF=1LL<<60;


int main(){
  int n;
  cin >> n;
  vector<ll>a(n,0),cnt(n,0);
  rep(i,n){
    cin >> a[i];
    cnt[a[i]-1]++;
  }
  ll sum=0;
  rep(i,n){
    sum+=cnt[i]*(cnt[i]-1)/2;
  }
  rep(i,n)cout << sum-(cnt[a[i]-1]-1) << endl;
}


Measured memory_bytes: 5760
#include <stdio.h>

int main(){
	int i=0;
	char a[20]={'\n'};
	scanf("%c",&a[0]);

	while(a[i] != '\n'){
		i++;
		scanf("%c",&a[i]);
	}

	for(i=19;i>=0;i--){
		if(a[i] != '\n')
			printf("%c",a[i]);
	}

	printf("\n");

	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>

#define MOD 1000000007
#define INF INT_MAX
#define NINF INT_MIN
#define LLINF LLONG_MAX
using ll = long long;
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((abs(a - b) <= d && abs(b - c) <= d) || abs(a - c) <= d) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    getchar(); getchar();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const int M = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define vi vector
#define f(i,n) for(int i=0;i<n;++i)
#define endl "\n"
using namespace std;

//vector<ll> adj[1000001];
//int vis[1000001]; 
//
//int dfs(int node){
//	vis[node]=1;
//	for(int child: adj[node]){
//		if(!vis[child])
//		dfs(child);
//	}
//}


void solve()
{	
	int c; cin>>c;
	if(c>=30) cout<<"Yes"<<"\n"; else cout<<"No"<<"\n";
}

int main(void)
{
    fast;
//	ll t;
//	cin>>t;
//    while(t--)
        solve();
}


Measured memory_bytes: 3636
import re

def main():
    N = str(input())
    M = str(input())

    if len(N) <= 10 and len(N) >= 1 and len(N) + 1 == len(M) and N == M[0:len(N)]:
        c = M[len(N)]
        if re.match("[a-z]", c):
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()


Measured memory_bytes: 9864
#include<stdio.h>
 
int main(){
    double a,b,c,d,e,f;
    double ans,ans2;
 
    while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
 
            ans2=(c*d-a*f)/(b*d-a*e);
            ans=(c-b*ans2)/(a);
 
        printf("%.3f %.3f\n",ans,ans2);
    }
    return 0;
}


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

int main(){
    double c[3][3];
    for(int i=0;i<3;i++){
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }
    vector<int> x(3),y(3);
    for(int i=0;i<3;i++){
        y[i] = c[0][i] - x[0];
    }
    for(int i=0;i<3;i++){
        x[i] = c[i][0] - y[0];
    }
    bool frag = true;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(x[i] + y[j] != c[i][j]){
                frag = false;
            }
        }
    }
    if(frag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
use std::cmp::min;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let N: usize = read();
    let T: u32 = read();
    let t: Vec<u32> = (0..N).map(|_| read()).collect();

    let mut ans = T;
    for i in 1..N {
        ans += min(t[i] - t[i - 1], T);
    }

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char const* argv[])
{
	int n, a, m_max = -1000000, m_min = 1000000;
	long sum = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a;
		m_max = max(a, m_max);
		m_min = min(a, m_min);
		sum += a;
	}
	cout << m_min << " " << m_max << " " << sum << endl;
	return 0;
}


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

const int N=1e6+1;
int d[N],cnt[N];

int main(){
	int n; cin >> n;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
		cnt[arr[i]]++;
	}
	for(int i=1;i<N;i++){
		if(!cnt[i]) continue;
		for(int j=i+i;j<N;j+=i){
			d[j]=1;
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(!d[arr[i]] && cnt[arr[i]] == 1)ans++;
	}
	cout<<ans;	;
}


Measured memory_bytes: 12068
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma once
#include<bits/stdc++.h>
#define q register
#define qsize 1<<15
typedef long long ll;
using namespace std;
string s;
ll ans;
inline void qwrite(ll v)
{
	if(v>9)   qwrite(v/10);
	   putchar(v%10+'0');
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;
	for(q ll i=0;i<s.length()-1;i++){
		if(s[i]!=s[i+1])   ans++;
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}

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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c)

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

int a[2005];

bool palin(string x)
{
  auto  rx = x;
  reverse(all(rx));
  return x == rx;
}

int main()
{
  ios::sync_with_stdio(0);
  ll n,a,b;
  cin >> n >> a >> b;

  ll ans = a *( n / (a + b)) + min(a, n % (a+ b));
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n = ri()
    robots = []
    for i in range(n):
        x, l = rli()
        robots.append([x+l, x-l])
    robots.sort()
    r = -1*pow(10, 10)
    ans = 0
    for ro in robots:
        if ro[1] < r:
            continue
        ans += 1
        r = ro[0]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 20544
n=int(input())
count={}
a=[]
for i in range(n):
    tmp=int(input())
    a.append(tmp)
button=a[0]
cnt=1

while(True):
    if button==2:
        print(cnt)
        exit()
    else:
        if button in count:
            print(-1)
            exit()
        else:
            count[button]=1
            button=a[button-1]
            cnt+=1

Measured memory_bytes: 59480
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#define MAX_N 100001
#define INF 2147483647
#define REP(i,n) for(int i=0;i<(int)(n);i++)
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
using namespace std;
int main()
{
  char S[1001],res[1001];
  int i=0,w;
  REP(i,1001)res[i] = '\0';
  cin >> S;
  cin >> w;
  while(1){
    if(i >= strlen(S))
      break;
    res[strlen(res)] = S[i];
    i += w;
  }
  cout << res << endl;
  
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}



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

using namespace std;
#define int long long
#define INF 1ll<<60
signed main(){
  string s;
  int c=0;
  char a;
  cin>>s;
  for(int i=0; i<s.size(); i++){
    if (i==0){
     a=s[i];
   } else{
      if(s[i]==a){
        c++;
        a=s[i];
      }else{
        a=s[i];
      }
    }
  }
  if(c>0){
    cout<<"Bad"<<endl;
  }else{
    cout<<"Good"<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

unsigned long long lcm(unsigned long long a, unsigned long long b)
{
   return a * b / gcd(a, b);
}

int main()
{
  unsigned long long A, B, C, D;
  cin >> A >> B >> C >> D;
  // unsigned long long x = lcm(C,D);
  // unsigned long long ac,ad,ax;
  // if(A%C==0){
  //   ac = A/C;
  // }else{
  //   ac = A/C+1;
  // }
  // if(A%D==0){
  //   ad = A/D;
  // }else{
  //   ad = A/D+1;
  // }
  // if(A%x==0){
  //   ax = A/x;
  // }else{
  //   ax = A/x+1;
  // }
  // unsigned long long a = B/C-(ac)+1;
  // unsigned long long b = B/D-(ad)+1;
  // unsigned long long c = B/x-(ax)+1;
  // cout << B-A+1-a-b+c << endl;

  cout << (B-(B/C)-(B/D)+(B/lcm(C,D)))-(A-1-((A-1)/C)-((A-1)/D)+((A-1)/lcm(C,D))) << endl;
}

Measured memory_bytes: 256
N, A, B = gets.chomp.split(" ").map(&:to_i)
sum = 0
N.downto(0) do |num|
  original_num = num
  digit_sum = 0
  while num >= 1
    digit_sum += num % 10
    num /= 10
  end
  if digit_sum >= A && digit_sum <= B
    sum += original_num
  end
end
puts sum

Measured memory_bytes: 1788
N=int(input())
A=list(map(int,input().split()))
c=0
t=0
l=0
for r in range(N):
  if t+A[r]==t^A[r]:
    t+=A[r]
  else:
    while t+A[r]!=t^A[r]:
      t-=A[l]
      c+=r-l
      l+=1
    t+=A[r]
c+=(N-l)*(N-l+1)//2
print(c)

Measured memory_bytes: 24840
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			System.out.println(k * ((long) Math.pow(k - 1, n - 1)));
		}
	}
}


Measured memory_bytes: 35644
n = int(input())
nums = list(map(int,input().split()))

count = 0
most = 0
for val in range(n):
    if nums[val] >= count and nums[val]>= most:
        count = nums[val]-1
        if count > most:
            most =count
    else:
        print('No')
        val = -1
        break
if val == n - 1:         
    print('Yes')

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

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

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

    int sum = 0;
    int sum_squared = 0;
    rep(i, N)
    {
        cin >> d.at(i);
        sum += d.at(i);
        sum_squared += d.at(i) * d.at(i);
    }

    int ans = (sum * sum - sum_squared) / 2;

    cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: u64,
        m: u64,
    }

    let mut ans: u64 = 1;
    if n == m || n == m - 1 || n == m + 1 {
        for i in 1..=n {
            ans *= i;
            ans = ans % 1000000007;
        }
        for i in 1..=m {
            ans *= i;
            ans = ans % 1000000007;
        }
        println!("{}", if n == m { ans * 2 % 1000000007 } else { ans });
    } else {
        println!("{}", 0);
    }
}


Measured memory_bytes: 2168
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)));
#define Mx(a , b) ((a) > (b) ? (a) : (b))
#define Mn(a , b) ((a) < (b) ? (a) : (b))

const double EPS = 1e-10;
const int INF = 2147483647;

int N , M;
int x , y;
int b[100001];
bool a[100001];

int main(){
	scanf("%d%d" , &N , &M);
	for(int i = 1 ; i <= N ; ++i){
		b[i] = 1;
	}
	a[1] = 1;
	for(int i = 0 ; i < M ; ++i){
		scanf("%d%d" , &x , &y);
		if(a[x]) a[y] = 1;
		b[y]++;
		b[x]--;
		if(b[x] == 0) a[x] = 0;
	}
	int ans = 0;
	for(int i = 1 ; i <= N ; ++i){
		if(a[i]) ans++;
	}
	printf("%d\n" , ans);
	return 0;
}


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

int n, m;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d%d", &n, &m);
    int s = 0;
    for (int i = 1; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        s += x;
    }
    if (s > n) {
        printf("-1\n");
    } else {
        printf("%d\n", n - s);
    }
}


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

int main(){
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n), f(n);
  for(auto& i : a) cin >> i;
  for(auto& i : f) cin >> i;
  sort(a.begin(), a.end());
  sort(f.rbegin(), f.rend());
  auto check = [&n, &k, &a, &f](ll ans) -> bool {
    ll cost = 0;
    for(ll i = 0; i < n; i++) cost += max(0ll, a[i] - ans / f[i]);
    return cost <= k;
  };
  ll ok = 1e12, ng = -1, cen;
  while(ok - ng > 1){
    cen = (ok + ng) / 2;
    if(check(cen)) ok = cen;
    else ng = cen;
  }
  cout << ok << endl;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  string S;
  cin >> S;

  while (true) {
    S.pop_back();
    int ssize = S.size();
    if (ssize%2 == 1) continue;
    if (S.substr(0, ssize/2) == S.substr(ssize/2)) {
      cout << S.size() << "\n";
      return;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define ll  long long 
const ll INF=1LL<<60;
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
vector<pair<ll,ll>>s[100001];
ll dis[100001];
int main(){
  string a,b;cin>>a>>b;
  ll c=0,d=0;
  rep(i,a.size()-b.size()+1){
    c=0;
    rep(o,b.size())if(a[i+o]==b[o])c++;
    d=max(c,d);
    //cout<<d;
  }
  cout<<b.size()-d;
}

Measured memory_bytes: 5972
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPI(i,a,b) for(int i=int(a);i<int(b);++i)
#define ALL(x) (x).begin(),(x).end()
inline cpp_int between(cpp_int n, cpp_int x) {
  if(n >= 0)
    return (n/x)+1;
  else
    return 0;
}

int main () {
  string s;
  cin >> s;

  if(s[2] == s[3] && s[4] == s[5]) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}


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

int main(){
 long long n;
 cin>>n;
  long long mem=1e13;
 for(long long i=1;i<=sqrt(n);i++){
   if(n%i==0) mem=min(mem,i+n/i);
 }
  cout<<mem-2<<endl;
}

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

const int N = 440;
const int mod = 998244353;

int dp[2][N][N];
int g[N], r[N], a[N], b[N], p[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for (int i = 0; i < N; i++) {
    	r[i] = i < 2 ? i : (long long)r[mod % i] * (mod - mod / i) % mod;
    	g[i] = i == 0 ? 1 : (long long)g[i - 1] * r[i] % mod;
    }
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    int S = accumulate(a, a + n, 0);
    for (int i = 0; i < n; i++) p[i] = (long long)r[S] * a[i] % mod;
    int now = 0;
    dp[0][0][0] = mod - 1;
    int asum = 0, bsum = 0;
    auto add = [&](int &a, int b) { ((a += b) >= mod) && (a -= mod); };
    for (int i = 0; i < n; i++) {
    	now ^= 1;
    	memcpy(dp[now], dp[!now], sizeof dp[now]);
    	for (int j = 0; j <= asum; j++) {
    		for (int k = 0; k <= bsum; k++) if (dp[!now][j][k]) {
    			for (int l = 0, cur = mod - 1; l < b[i]; l++) {
    				add(dp[now][j + a[i]][k + l], (long long)dp[!now][j][k] * g[l] % mod * cur % mod);
    				cur = (long long)cur * p[i] % mod;
    			}
    		}
    	}
    	asum += a[i];
    	bsum += b[i] - 1;
    }
    int ans = 0;
    for (int i = 1; i <= S; i++) {
    	int cur = (long long)S * r[i] % mod;
    	int ret = 1;
    	for (int j = 0; j <= bsum; j++) {
    		ret = (long long)ret * cur % mod;
    		add(ans, (long long)ret * dp[now][i][j] % mod);
    		ret = (long long)ret * (j + 1) % mod;
    	}
    }
    cout << ans << "\n";
    return 0;
}



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

using namespace std;

void solve()
{
    int n;
    cin >> n;
    int a[100][2];
    for(int i= 0 ; i < n ; i++){
        cin >> a[i][0] >> a[i][1];
    }
    for (int i= 0; i < n-2; i++){
        if(a[i][0] == a[i][1] && a[i+1][0] == a[i+1][1] && a[i+2][0] == a[i+2][1]){
            cout << "Yes";
            return ;
        }
    }
    cout << "No";

}

int main ()
{
   solve();
   cout << "\n";
   return 0;
}


Measured memory_bytes: 3640
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]
#a = [int(input()) for _ in range(n)]

a,b = map(int, input().split())

ans = 0
for i in range(a, b+1):
    s = str(i)
    if s[0] == s[4] and s[1] == s[3]:
        ans += 1
print(ans)








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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


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

    // R, G, B を面倒くさいので 0, 1, 2 に置き換える
    string T;
    REP(i, N){
        if(S[i] == 'R') T += '0';
        if(S[i] == 'G') T += '1';
        if(S[i] == 'B') T += '2';
    }
    vector<vector<int>> num(3, vector<int>(N+1));
    for(int i = N-1; i >= 0; --i){
        REP(j, 3) num[j][i] = num[j][i+1];
        ++num[int(T[i]-'0')][i];
    }

    long long ans = 0;
    REP(i, N){
        FOR(j, i+1, N-1){
            if(T[i] == T[j]) continue;
            int tmp = 3-int(T[i]-'0')-int(T[j]-'0');
            ans += num[tmp][j+1];
            if(2*j-i < N and T[2*j-i] == char('0'+tmp)) --ans;
        }
    }
    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 3204
// -*- mode:c++; coding:utf-8; c-basic-offset:2; -*-
// ALDS1_9_B: Maximum Heap

#include <algorithm>
#include <cstdio>

class MaxHeap {
  int n_;
  int* data_;

public:
  MaxHeap(unsigned int n) : n_(n), data_(new int[n]) { }

  ~MaxHeap() { delete[] data_; }

  int& operator[](unsigned int i) { return data_[i]; }

  void build()
  {
    for (auto i = (n_/2)-1; i >= 0; --i) {
      max_heapify(i);
    }
  }

  void print() const
  {
    for (auto i = 0; i < n_; ++i) {
      std::printf(" %d", data_[i]);
    }
    std::printf("\n");
  }
  
private:
  void max_heapify(int i)
  {
    auto left = 2*i + 1;
    auto right = 2*i + 2;
    auto max = i;
    if (left < n_ && data_[max] < data_[left]) {
      max = left;
    }
    if (right < n_ && data_[max] < data_[right]) {
      max = right;
    }
    if (max == i) {
     return;
   }
   std::swap(data_[i], data_[max]);
   max_heapify(max);
  }
};

int main()
{
  int h;
  std::scanf("%d", &h);
  MaxHeap mh(h);
  for (auto i = 0; i < h; ++i) {
    std::scanf("%d", &mh[i]);
  }
  mh.build();
  mh.print();
}

// eof

Measured memory_bytes: 4172
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    Q.append((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.append((c+1,np))
    return cost

n=int(input())
d=[deque()for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")


Measured memory_bytes: 121564
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
 ll k,a,b;
 cin>>k>>a>>b;
 ll cnt = a/k;
 cnt *= k;
 if( (a <= cnt && cnt<= b ) || (a <= cnt + k && cnt + k <= b ) ) cout<<"OK"<<endl;
 else cout<<"NG"<<endl;
    return 0;
}


Measured memory_bytes: 3604
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
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...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//省略
using vi  = vector<int>;
using vii = vector<vector<int>>;
using vl  = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
    ll N,X,T;
    cin>>N>>X>>T;
    ll ans=T;
    ans*=((N-1)/X+1);
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<(x)<<endl
#define fi first
#define se second

#define INF 1147483600

int main(){
  int n,t;
  cin>>n>>t;
  vector<int> vec(n);
  rep(i,n) scanf("%d", &vec[i]);

  int mxdiff=0, mn=vec[0], cnt=0;
  repl(i,1,n){
    if(vec[i]<mn) mn = vec[i];
    else if(vec[i] == mn+mxdiff) cnt++;
    else if(vec[i] > mn+mxdiff){ cnt=1; mxdiff = vec[i] - mn; }
  }
  cout<<cnt<<endl;

  return 0;
}


Measured memory_bytes: 640
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)
    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)
    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod
    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    x = a[-1]
    a = a[:-1]
    l = [abs(i - x/2) for i in a]
    print(x)
    print(a[l.index(min(l))])
main()


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

const int INF = (int) 1e9 + 7;
const int N = 1000;
vector<int> child[N];
int sum[N], black[N];

bool dfs(int u) {
    vector<int> f (sum[u] + 1, INF);
    f[0] = 0;
    for (auto v : child[u]) {
        if (!dfs(v)) return false;
        vector<int> g (sum[u] + 1, INF);
        for (int i = 0; i + sum[v] <= sum[u]; ++i) {
            g[i + sum[v]] = min(g[i + sum[v]], f[i] + black[v]);
        }
        for (int i = 0; i + black[v] <= sum[u]; ++i) {
            g[i + black[v]] = min(g[i + black[v]], f[i] + sum[v]);
        }
        f = g;
    }
    black[u] = *min_element(f.begin(), f.end());
    return black[u] < INF;
}

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int p; cin >> p; --p;
        child[p].emplace_back(i);
    }
    for (int i = 0; i < n; ++i) cin >> sum[i];
    cout << (dfs(0) ? "POSSIBLE" : "IMPOSSIBLE") << '\n';
    return 0;
}


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

int main() {
  int n, q;
  string s;
  cin >> n >> q >> s;
  
  int x[n] = {0};
  int sum = 0;
  for (int i = 0; i < n - 1; i++) {
    if (s.substr(i, 2) == "AC")
      sum++;
    x[i + 1] = sum;
  }
  
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    
    cout << (x[r - 1] - x[l - 1]) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */

struct UnionFind {
  vector<int> par;
  vector<int> sizes;

  UnionFind(int N) : par(N), sizes(N, 1) {
    for(int i = 0; i < N; i++) par.at(i) = i;
  }

  int find(int x) { 
    if (par.at(x) == x) return x;
    return par.at(x) = find(par.at(x));
  }

  void unite(int x, int y) {
    int rx = find(x); 
    int ry = find(y); 
    if (rx == ry) return; 
    if (sizes.at(rx) < sizes.at(ry)) swap(rx,ry);
    par.at(ry) = rx;
    sizes.at(rx) += sizes.at(ry);    
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  int size(int x){
    return sizes.at(find(x));
  }

  int num_of_connected_components(){
    int ret = 0;
    for(int i = 0; i < par.size(); i++){
      if(find(i) == i) ret++;
    }
    return ret;
  }
};

struct edge {
  int from;
  int to;
  ll cost;
};

int main() {
  int N; cin >> N ;
  vector<pair<int,int>> x(N), y(N);
  REP(i, N){
    int a, b;
    cin >> a >> b;
    x[i] = {a, i};
    y[i] = {b, i};
  }
  sort(ALL(x));
  sort(ALL(y));

  vector<edge> edges;

  REP(i, N-1){
    edges.push_back({x[i].second, x[i+1].second, abs(x[i].first-x[i+1].first)});
    edges.push_back({y[i].second, y[i+1].second, abs(y[i].first-y[i+1].first)});
  }

  sort(ALL(edges), [](auto& e1, auto& e2){
    return e1.cost < e2.cost;
  });

  // REP(i, edges.size()){
  //   DUMP(i);
  //   edge& e = edges[i]; 
  //   DUMP(e.from);
  //   DUMP(e.to);
  //   DUMP(e.cost);
  // }

  UnionFind uf(N);

  ll ans = 0;
  REP(i, edges.size()){
    edge& e = edges[i];
    if(uf.same(e.from,e.to)) continue;
    uf.unite(e.from, e.to);
    ans += e.cost;
  }

  cout << ans << endl;
}


Measured memory_bytes: 8048
from sys import exit

time = [int(input()), int(input()), int(input()), int(input()), int(input())]

total = 0
loss = []

for t in time:
    total += t
    if t % 10 != 0:
        loss.append(10 - t % 10)

if loss:
    total += sum(loss) - max(loss)

print(total)


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

namespace AtCoder.Contest.C
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			var cin = new Scanner();

			int n = cin.NextInt();
			int q = cin.NextInt();
			string s = cin.Next();
			var c = new int[n + 2];
			for (int i = 1; i < n; i++)
			{
				if (s[i - 1] == 'A' && s[i] == 'C')
				{
					c[i]++;
				}
				c[i + 1] += c[i];
			}
			c[n + 1] = c[n];
			for (int i = 0; i < q; i++)
			{
				int l = cin.NextInt();
				int r = cin.NextInt();
				Console.WriteLine(c[r - 1] - c[l - 1]);
			}

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

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

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

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

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

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
#define ll long long
using namespace std;


const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 7;

ll a,b;

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

    cout << abs((a * b) - (a + b - 2) * 1ll * 2) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for(auto v:(V))cout<<v<<" "<<endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;

int main()
{
    string s;
    cin >> s;
    if (s[5] == '0' && (s[6] == '1' || s[6] == '2' || s[6] == '3' || s[6] == '4'))
    {
        cout << "Heisei" << endl;
    }
    else
    {
        cout << "TBD" << endl;
    }
}

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

int main(){
    int n;cin>>n;
    if(n%2==0)cout<<"0.5000000000";
    else{
        float x=(float)n;
        float ans=(x+1)/(2*x);
        printf("%.10f",ans);
    }
    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	scn := newScanner()
	H := scn.nextInt()
	W := scn.nextInt()
	A := make([]string, H)
	for i := 0; i < H; i++ {
		A[i] = scn.nextLine()
	}
	var cnt1, cnt2 int
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if A[i][j] == '#' {
				cnt1++
			}
		}
	}
	cnt2++
	var i, j int
	for i < H && j < W {
		if (i < H && j+1 < W) && A[i][j+1] == '#' {
			j++
			cnt2++
		} else if (i+1 < H && j < W) && A[i+1][j] == '#' {
			i++
			cnt2++
		} else {
			break
		}
	}
	if cnt1 == cnt2 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}
	return
}

type scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func newScanner() *scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 10000)
	return &scanner{r: rdr}
}
func (s *scanner) next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *scanner) nextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *scanner) nextInt() int {
	v, _ := strconv.Atoi(s.next())
	return v
}
func (s *scanner) nextInt64() int64 {
	v, _ := strconv.ParseInt(s.next(), 10, 64)
	return v
}
func (s *scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 2e5 + 7;
int n, m, a, b, c;
long long ans = 0, it[4 * N], lz[4 * N];
vector < pair <int, int> > add[N], sub[N];

void lazy(int k, int l, int r){
	if(lz[k] == 0) return;
	it[k] += lz[k];
	if(l != r) lz[k << 1] += lz[k], lz[k << 1 | 1] += lz[k];
	lz[k] = 0;
}

void update(int k, int l, int r, int L, int R, long long val){
	lazy(k, l, r);
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		it[k] += val;
		if(l != r) lz[k << 1] += val, lz[k << 1 | 1] += val;
		return;
	}
	int mid = (l + r) >> 1;
	update(k << 1, l, mid, L, R, val);
	update(k << 1 | 1, mid + 1, r, L, R, val);
	it[k] = max(it[k << 1], it[k << 1 | 1]);
}

void update(int k, int l, int r, int pos, long long val){
	lazy(k, l, r);
	if(l > pos || r < pos) return;
	if(l == r){
		it[k] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(k << 1, l, mid, pos, val);
	update(k << 1 | 1, mid + 1, r, pos, val);
	it[k] = max(it[k << 1], it[k << 1 | 1]);
}

long long get(int k, int l, int r, int L, int R){
	lazy(k, l, r);
	if(l > R || r < L) return (long long)-1e18;
	if(l >= L && r <= R) return it[k];
	int mid = (l + r) >> 1;
	return max(get(k << 1, l, mid, L, R), get(k << 1 | 1, mid + 1, r, L, R));
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b >> c;
		add[a].pb(mp(b, c));
		sub[b].pb(mp(a, c));
	}
	for(int i = 1; i <= n; i++){
		for(pair <int, int> x : add[i]) update(1, 1, n, 1, i, x.se);
		long long cur = get(1, 1, n, 1, i);
		ans = max(ans, cur);
		//cout << cur << endl;
		if(i < n) update(1, 1, n, i + 1, cur);
		for(pair <int, int> x : sub[i]) update(1, 1, n, 1, x.fi, -x.se);
	}
	cout << ans;
}


Measured memory_bytes: 33280
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<math.h>
#include<set>
#include<iomanip>
#include<stdio.h>
#include<deque>
#include<stack>
#include<map>
#include<queue>
#include<cstring>
#define M 1000000007
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
void dfs(vector<int> v[],int s,int e,int counter[])
{
	counter[s]+=counter[e];
	for(auto u:v[s])
	{
		if(u!=e)
			dfs(v,u,s,counter);
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N,Q,i;
	cin>>N>>Q;
	vector<int> tree[N+1];
	int counter[N+1]={0};
	for(i=0;i<N-1;i++)
	{
		int x,y;
		cin>>x>>y;
		tree[x].pb(y);
		tree[y].pb(x);
	}
	for(i=0;i<Q;i++)
	{
		int p,x;
		cin>>p>>x;
		counter[p]+=x;
	}
	dfs(tree,1,0,counter);
	for(i=1;i<=N;i++)
		cout<<counter[i]<<' ';
	cout<<endl;
}

Measured memory_bytes: 27392
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>

#define MOD 1000000007

using namespace std;

long long n;
vector<long long> graph[200001];
vector<long long> subtree[200001];
long long tot[200001] = { 0, };
bool visited[200001] = { 0, };
bool visited2[200001] = { 0, };

long long dfs(long long cur)
{
	for (long long i = 0; i < graph[cur].size(); i++)
	{
		long long next;

		next = graph[cur][i];

		if (!visited[next])
		{
			visited[next] = true;
			
			long long ret;

			ret = dfs(next);

			subtree[cur].push_back(ret);

			tot[cur] += ret;
		}

		else
		{
			subtree[cur].push_back(0);
		}
	}

	return tot[cur] + 1;
}

void dfs2(long long cur,long long parent,long long add)
{
	if (parent)
	{
		subtree[cur].push_back(add);
	}

	for (long long i = 0; i < graph[cur].size(); i++)
	{
		long long next;

		next = graph[cur][i];

		if (!visited2[next])
		{
			visited2[next] = true;

			dfs2(next, cur, add + tot[cur] + 1 - subtree[cur][i]);
		}
	}
}

long long exp(long long base, long long pw)
{
	long long temp;
	vector<long long> bits;

	temp = pw;

	while (temp)
	{
		bits.push_back(temp % 2);

		temp /= 2;
	}

	temp = base;

	long long rvalue = 1;

	for (long long i = 0; i < bits.size(); i++)
	{
		if (bits[i])
		{
			rvalue = rvalue*temp%MOD;
		}

		temp = temp*temp%MOD;
	}

	return rvalue;
}

long long div(long long val)
{
	return exp(val, MOD - 2);
}

int main()
{
	scanf("%lld", &n);
	
	for (long long i = 0; i < n - 1; i++)
	{
		long long u, v;

		scanf("%lld %lld", &u, &v);

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	visited[1] = true;
	dfs(1);
	visited2[1] = true;
	dfs2(1, 0, 0);

	long long lmax = 0;

	vector<pair<long long, long long>> parts;

	for (long long i = 1; i <= n; i++)
	{
		if (!tot[i])
		{
			continue;
		}

		long long curmax = 0;
		long long sum = 1;
		long long divs = 1;

		for (long long j = 0; j < subtree[i].size(); j++)
		{
			if (!subtree[i][j])
			{
				continue;
			}

			sum = (sum + exp(2, subtree[i][j]) + (MOD - 1)) % MOD;
			divs = (divs + subtree[i][j]) % MOD;
		}

		sum = (MOD + exp(2, divs - 1) - sum) % MOD;

		parts.push_back({ sum,divs });

		if (divs > lmax)
		{
			lmax = divs;
		}
	}

	long long divd = 0;
	long long divs;

	divs = exp(2, lmax);

	for (long long i = 0; i < parts.size(); i++)
	{
		long long dd;

		dd = parts[i].first * exp(2, lmax - parts[i].second) % MOD;

		//dd = (MOD + divs - dd) % MOD;

		divd = (divd + dd) % MOD;
	}

	long long sol;

	sol = divd*div(divs) % MOD;

	printf("%lld\n", sol);

	return 0;
}


Measured memory_bytes: 42864
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int a[n];
	map<int, int> m;
	int sum = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		m[a[i]]++;
		sum += a[i];
	}
	int q;
	cin >> q;
	while(q--) {
		int b, c;
		cin >> b >> c;
		sum -= m[b] * b;
		sum -= m[c] * c;
		m[c] += m[b];
		m[b] = 0;
		sum += m[c] * c;
		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 10340
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i, m) {
        int k;
        cin >> k;
        rep(j, k) {
            int s;
            cin >> s;
            s--;
            a[s] |= 1 << i;
        }
    }
    int p = 0;
    rep(i, m) {
        int x;
        cin >> x;
        p |= x << i;
    }
    int ans = 0;
    for(int s = 0; s < (1 << n); s++) {
        int t = 0;
        rep(i, n) {
            if(s >> i & 1) {
                t ^= a[i];
            }
        }
        if(t == p) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m
transmap = list(zip(*frommap))

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in transmap]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Measured memory_bytes: 3188
import os
import numpy as np

if os.path.exists('input.txt'):
    test_mode = True
else:
    test_mode = False

if test_mode:
    f = open('input.txt')
    
def get_input():
    if test_mode:
        return f.readline().rstrip()
    else:
        return input().rstrip()

x = get_input().split()
for x_i in x:
    if int(x_i) == 0:
        print(x.index(x_i) + 1)
        break

if test_mode:
    f.close()

Measured memory_bytes: 27132
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>
#include<bitset>
#include<functional>

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

int main(void) {
	int a, b;
	int c[6];
	int count = 0;
	int p;

	cin >> a >> b;

	FOR(i, a, b) {
		p = i;
		FOR(t, 1, 5) {
			c[t] = p % 10;
			p /= 10;
		}
		if (c[1] == c[5] && c[2] == c[4]) {
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; int64 d; cin >> n >> d;
  int cnt = 0;

  for (int i = 0; i < n; ++i) {
    int64 x, y; cin >> x >> y;
    if (x * x + y * y <= d * d) ++cnt;
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 3632
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
X = []
Y = Counter()
for i in range(1, N+1):
    X.append(i-A[i-1])
    Y[A[i-1]+i] += 1
ans = 0
for x in X:
    if x < 2:
        continue
    ans += Y[x]
print(ans)


Measured memory_bytes: 46724
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main(){
  int n,k;cin>>n>>k;
  string s;cin>>s;
  int count=0;
  int now=1;
  vector<int> Nums;
  int i,j;

  for(i=0;i<n;i++){
    if(s[i]-'0'==now) count++;
    else{
      Nums.push_back(count);
      now=1-now;
      count=1;
    }
  }

  if(count!=0) Nums.push_back(count);

  int add=2*k+1;
  int ans=0;
  vector<int> Sum(Nums.size()+1);

  for(i=0;i<Nums.size();i++){
    Sum.at(i+1) = Sum[i]+Nums[i];
  }

  for(i=0;i<Nums.size();i+=2){
    int left=i;
    int right=min(i+add,(int)Nums.size());
    int tmp=Sum[right]-Sum[left];
    ans=max(tmp,ans);
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 1272
#include<cstdio>
#include<vector>


using namespace std;

using vc=vector<char>;
using vvc=vector<vc>;
using vi=vector<int>;


int main(void)
{
	int h, w;

	while(scanf("%d%d\n", &h, &w)==2)
	{
		vi c(26);
		vi v(4);

		for(int y=0;y<h;y++)
		{
			char s[w+2];
			scanf("%[a-z]\n", s);

			for(int x=0;x<w;x++)
			{
				c[s[x]-'a']++;
			}
		}

		for(int i=0;i<26;i++)
		{
			v[c[i]%4]++;
		}

		int ans=0;
		if(h%2==0)
		{
			if(w%2==0)
			{
				if(v[1]==0 && v[2]==0 && v[3]==0) ans=1;
			}
			else
			{
				if(v[1]==0 && v[2]*2<=h && v[3]==0) ans=1;
			}
		}
		else
		{
			if(w%2==0)
			{
				if(v[1]==0 && v[2]*2<=w && v[3]==0) ans=1;
			}
			else
			{
				if((v[1]+v[3])==1 && v[2]*2<=w+h-2) ans=1;
			}
		}
//		printf("w=%d  h=%d  v=%d %d %d %d\n", w, h, v[0], v[1], v[2], v[3]);
		printf("%s\n", ans?"Yes":"No");
	}

	return 0;
}


Measured memory_bytes: 256
s = input()

a = int(s[:2])
b = int(s[2:])

if 1 <= a <= 12 and 1 <= b <= 12:
  ans = "AMBIGUOUS"
elif 1 <= a <= 12:
  ans = "MMYY"
elif 1 <= b <= 12:
  ans = "YYMM"
else:
  ans = "NA"
  
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int N,M; cin>>N>>M;
  vector<int> vec(M+5,0);
  
  for(int i=0;i<N;i++){
    int K; cin>>K;
    for(int j=0;j<K;j++){
      int a; cin>>a;
      vec[a]++;
    }
  }
  int ans=0;
  for(int i=0;i<=M;i++){
    if(vec[i]==N) ans++;
  }

  cout<<ans<<endl;

  return 0;
}



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

using namespace std;

inline int abs(int a, int b)
{
    return a<b ? b-a : a-b;
}

int w[301];
bool rm[301][301];
int rmct[301][301];

int main()
{
    int n;
    while(cin >> n, n)
    {
        for(int i=0; i<n; i++) cin >> w[i];
        for(int i=0; i<=n; i++)
            for(int j=0; j<=n; j++)
                rm[i][j] = i==j;
        for(int r=2; r<=n; r+=2)
        {
            for(int i=0; i+r<=n; i++)
            {
                for(int s=2; s<r; s+=2)
                {
                    if(rm[i][i+s] && rm[i+s][i+r]) rm[i][i+r] = true;
                }
                if(!rm[i][i+r] && rm[i+1][i+r-1] && abs(w[i], w[i+r-1])<=1)
                    rm[i][i+r] = true;
            }
        }
        /*
        int rmw = -1;
        for(int rmr = n / 2 * 2; rmw==-1 && rmr >= 0; rmr-=2)
        {
            for(int i=0; i+rmr<=n; i++)
            {
                if(rm[i][i+rmr])
                {
                    rmw = rmr;
                    break;
                }
            }
        }
        */
        for(int y=0; y<=n; y++)
            for(int x=0; x<=n; x++)
                rmct[y][x] = rm[y][x] ? x - y : 0;
        for(int r=1; r<=n; r++)
        {
            for(int i=0; i+r<=n; i++)
            {
                for(int s=1; s<r; s++)
                {
                    rmct[i][i+r] = max(rmct[i][i+r], rmct[i][i+s]+rmct[i+s][i+r]);
                }
            }
        }
        cout << rmct[0][n] << endl;
        // XXX DEBUG
        /*
        printf("i\\j ");
        for(int x=0; x<=n; x++) printf("%3d ", x);
        cout << endl;
        for(int y=0; y<=n; y++)
        {
            printf("%3d ", y);
            for(int x=0; x<=n; x++)
            {
                printf("%3d ", rm[y][x]);
            }
            cout << endl;
        }
        */
        // XXX DEBUG
        //cout << rmw << endl;
    }
}

Measured memory_bytes: 3516