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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  vector<std::pair<string, int>> v(N);
  rep(i, N)
  {
    string s;
    int p;
    cin >> s >> p;
    v[i] = std::make_pair(s, p);
  }

  vector<int> order(N);
  rep(i, N)
  {
    int count = 0;
    rep(j, N)
    {
      if (v[i].first > v[j].first)
        count++;
      else if (v[i].first == v[j].first && v[i].second < v[j].second)
        count++;
    }

    order[count] = i + 1;
  }

  rep(i, N)
  {
    cout << order[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
  int n,x;
  scanf("%d%d",&n,&x);
  int l[n],i;
  for(i=1;i<=n;++i)
      scanf("%d",&l[i]);
  
  int sum=0;
  for(i=1;i<=n;++i)
  {
    sum=sum+l[i];
    if(sum>x)
        break;
  }
  
  printf("%d",i);
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

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

int N, M;

int main() {
	cin >> N >> M;
	vector<int> L(M, 0);
	vector<int> R(M, 0);
	for (int i = 0; i < M; i++) {
		cin >> L[i] >> R[i];
	}

	int ans = 0;
	int left = L[0], right = R[0];
	for (int i = 1; i < M; i++) {
		if (L[i] > right || R[i] < left) { 
			ans = -1;
			break;
		}
		if (L[i] > left) { left = L[i]; }
		if (R[i] < right) { right = R[i]; }
	}
	if (ans != -1) {
		ans = right - left;
	}
	cout << ans + 1 << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>

#define MAX_N (100000)

using namespace std;

int main(int argc, char *argv[]) {
  // read inputs
  long N, K, ts[MAX_N], ds[MAX_N];
  scanf("%ld %ld", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%ld %ld", &ts[i], &ds[i]);
    ts[i]--;  // note modified input
  }

  // zip ts and ds and sort
  vector<pair<long, long>> vs;
  for (int i = 0; i < N; i++) {
    vs.push_back(pair<long, long>(ds[i], ts[i]));
  }
  sort(vs.begin(), vs.end());

  // first take K elements from the back of vs
  // record the sushis taken by type
  long sum_d = 0, num_types = 0;
  vector<vector<long>> uss(N, vector<long>());
  for (int i = N - 1; i >= N - K; i--) {
    const long t = vs[i].second, d = vs[i].first;
    if (uss[t].empty()) {
      num_types++;
    }
    uss[t].push_back(d);
    sum_d += d;
  }
  for (int i = 0; i < N; i++) {
    sort(uss[i].begin(), uss[i].end());
  }

  // gather candidates of sushis to remove
  vector<long> rs;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < (int) uss[i].size() - 1; j++) {
      rs.push_back(uss[i][j]);
    }
  }
  sort(rs.begin(), rs.end());
  // printf("rs = ");
  // for (long r : rs) {
  //   printf("%ld ", r);
  // }
  // printf("\n");

  // gather candidates of sushis to add
  vector<long> as(N, 0);
  for (int i = 0; i < N; i++) {
    const long t = ts[i], d = ds[i];
    if (uss[t].size() == 0) {
      as[t] = max(as[t], d);
    }
  }
  sort(as.begin(), as.end());
  reverse(as.begin(), as.end());
  // printf("as = ");
  // for (int i = 0; i < N && as[i] > 0; i++) {
  //   printf("%ld ", as[i]);
  // }
  // printf("\n");

  // solve
  long ans = sum_d + num_types * num_types;
  for (int i = 0; i < min(N, (long) rs.size()) && as[i] > 0; i++) {
    sum_d += as[i] - rs[i];
    num_types++;
    ans = max(ans, sum_d + num_types * num_types);
  } 
  printf("%ld\n", ans);

  return 0;
}


Measured memory_bytes: 9328
// Try AtCoder
// author: Leonardone

fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(&mut std::io::stdin(), &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let n = get!();
    let mut target = 1;
    for i in 1..n+1 {
        let x = get!();
        if x == target {
            target += 1;
        }
    }
    let ans = n - (target - 1);
    if ans < n {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 6396
import fractions

n=int(input())
a=list(map(int,input().split()))

gcd_r=[0]*n
gcd_r[n-1]=a[n-1]
for i in range(n-2,-1,-1):
  gcd_r[i]=fractions.gcd(gcd_r[i+1],a[i])
#gcd_r[i]は末尾からa[i]までのgcd

gcd_l=[0]*n
gcd_l[0]=a[0]
for i in range(1,n):
  gcd_l[i]=fractions.gcd(gcd_l[i-1],a[i])
#gcd_l[i]は先頭からa[i]までのgcd

ans=gcd_r[1]
for i in range(1,n-1):
  ans=max(fractions.gcd(gcd_l[i-1],gcd_r[i+1]),ans)
print(max(ans,gcd_l[n-2]))

Measured memory_bytes: 89580
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
//const int MOD=998244353;
const int INF=1e9;
const long long LINF=1e18;
#define int long long
//template
template <typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
int pw(int n,int k){
  if(k<0)return pw(n,k+MOD-1);
  int res=1;
  while(k){
    if(k&1)res*=n;///res%=MOD;
    n*=n;//n%=MOD;
    k>>=1;
  }
  return res;
}
//main
signed main(){
  int N,M;cin>>N>>M;
  std::vector<int> a(M),b(M),c[M];
  for(int i=0;i<M;i++){
    cin>>a[i]>>b[i];
    for(int j=0;j<b[i];j++){
      int k;cin>>k;k--;
      c[i].push_back(k);
    }
  }
  std::vector<int> key(M,0);
  for(int i=0;i<M;i++){
    for(int j=0;j<b[i];j++){
      key[i]|=(1<<c[i][j]);
    }
  }
  std::vector<int> open(10000,INF);
  open[0]=0;
  for(int i=0;i<M;i++){
    for(int j=0;j<pw(2,N);j++){
      open[j|key[i]]=min(open[j|key[i]],open[j]+a[i]);
    }
  }
  if(open[pw(2,N)-1]>=INF)fin(-1);
  fin(open[pw(2,N)-1]);
}


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


int N, M;
map<string, int> dict;
string s;

void input_info(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> s;
        dict[s]++;
    }
    cin >> M;
    for(int i = 0; i < M; i++){
        cin >> s;
        dict[s]--;
    }
}

/*
void solve(){
    sort(s.begin(), s.end());
    vector<pair<int, string>> words_num;
    int pivot, vec_num = 0;
    int count_up = 1;
    for(int i = 0; i < N - 1; i++){
        if(s.at(pivot) == s.at(i + 1)){
            count_up++;
        }
        else{
            words_num.at(vec_num) = make_pair(count_up, s.at(pivot));
            pivot = i + 1;
            count_up = 1;
            vec_num++;
        }
    }
    words_num.at(vec_num) = make_pair(count_up, s.at(pivot));

    vector<int> answer;

    for(int j = 0; j < words_num.size(); j++){
        for(auto i : t){
            if(i == words_num.at(j).second){
                count_up++;
            }
        }
        answer.at(j) = words_num.at(j).first - count_up;
        count_up = 1;
    }
    sort(answer.begin(), answer.end());
    cout << answer.at(0) << endl;
}
*/

int main(){
    input_info();

    int max = 0;
    for(auto i : dict){
        if(i.second > max){
            max = i.second;
        }
    }

    cout << max << endl;
    /*
    solve();
    int N, M;

    cin >> N;
    vector<string> s(N);
    for(int i = 0; i < N; i++){
        cin >> s.at(i);
    }
    cin >> M;
    vector<string> t(M);
    for(int i = 0; i < M; i++){
        cin >> t.at(i);
    }

    sort(s.begin(), s.end());
    
    vector<pair<int, string>> words_num;
    int pivot, vec_num = 0;
    int count_up = 1;

    for(int i = 0; i < N - 1; i++){
        if(s.at(pivot) == s.at(i + 1)){
            count_up++;
        }
        else{
            words_num.at(vec_num) = make_pair(count_up, s.at(pivot));
            pivot = i + 1;
            count_up = 1;
            vec_num++;
        }
    }
    words_num.at(vec_num) = make_pair(count_up, s.at(pivot));

    vector<int> answer;

    for(int j = 0; j < words_num.size(); j++){
        for(auto i : t){
            if(i == words_num.at(j).second){
                count_up++;
            }
        }
        answer.at(j) = words_num.at(j).first - count_up;
        count_up = 1;
    }
    sort(answer.begin(), answer.end());
    cout << answer.at(0) << endl;
    */
}

Measured memory_bytes: 256
import sys
n, m=map(int,sys.stdin.readline().split())
A=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
B=[list(map(int,sys.stdin.readline().split())) for i in range(m)]
C=[[0 for C in range(m)] for r in range(n)]
for r in range(n):
    for c in range(m):
        C[r][0]+=A[r][c]*B[c][0]
    print(C[r][0])



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



int main(){
  int N,L;
  scanf("%d%d",&N,&L);
  int i,j;
  char s[N][L+1];
  char tmp[L];
  for(i=0;i<N;i++){
    scanf("%s",s[i]);
  }
  //printf("%s\n",s[0]);
  for(i=1;i<N;i++){
    for(j=1;j<N;j++){
      if(strcmp(s[j-1],s[j])>0){
        strcpy(tmp,s[j-1]);
        strcpy(s[j-1],s[j]);
        strcpy(s[j],tmp);
      }
    }
  }//文字列を辞書中にソート
  for(i=0;i<N;i++){
    printf("%s",s[i]);
  }
}


Measured memory_bytes: 128
N, X = map(int, input().split())
li = list(map(int, input().split()))
D = [0]*(N+1)
flag = "0"
for i in range(N):
    D[i+1] = D[i] + li[i]
    if D[i+1] > X:
        flag = "1"
        break
if flag == "1":
    print(i + 1)
else:
    print(N + 1)


Measured memory_bytes: 3060
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

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

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

fn main() {
    input!{
        a: i32, b: i32,
    }

    let c = b -a;
    let b_height = (1 + c) * c / 2;
    let ans = b_height - b;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int sum(int k){
    if (k == 0){
        return 1;
    }
    else{
        int b = sum(k - 1);
        return b * k;
    }
}

int main(){
    int n;
    cin >> n;
    double anss = 0;
    double ans = 0;
    vector<vector<int>> date(n,vector<int>(2));
    for (int i = 0;i < n;i++){
        for (int j = 0;j < 2;j++){
            cin >> date.at(i).at(j);
        }
    }
    for (int i = 0;i < n;i++){
        for (int j = 0;j < n;j++){
            anss += sqrt((date.at(i).at(0)-date.at(j).at(0))*(date.at(i).at(0)-date.at(j).at(0)) + (date.at(i).at(1)-date.at(j).at(1))*(date.at(i).at(1)-date.at(j).at(1)));
        }
    }
    cout << setprecision(10) << fixed << anss / n << endl;
} 

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

int n;
int x[30],y[30],r[30],c[30];
int cover[30];
bool dp[1<<24];

inline bool cross(int a, int b){
  return (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b])
    < (r[a]+r[b])*(r[a]+r[b]);
}

int main(){
  while(cin >> n, n){
    for(int i=0;i<n;i++)cin >> x[i] >> y[i] >> r[i] >> c[i];
    
    for(int i=0;i<n;i++){
      cover[i] = 0;
      for(int j=0;j<i;j++){
	if(cross(i,j))cover[i] |= 1<<j;
      }
    }

    memset(dp,0,sizeof(dp));
    dp[0] = true;

    for(int bit=0;bit<(1<<n);bit++){
      if(!dp[bit])continue;
      for(int a=0;a<n;a++){
	if( (bit>>a) & 1)continue;
	if( (~bit)&cover[a] )continue;

	for(int b=a+1;b<n;b++){
	  if( (bit>>b) & 1)continue;
	  if( (~bit)&cover[b] )continue;
	  if(c[a] != c[b])continue;

	  dp[bit | (1<<a) | (1<<b)] = true;
	}
      }
    }

    int ans = 0;
    for(int bit=0;bit<(1<<n);bit++){
      if(dp[bit])ans = max(ans, __builtin_popcount(bit));
    }
    cout << ans << endl;
  }	  
}

Measured memory_bytes: 17556
using System;

public class Hello {
    public static void Main () {
        var s = Console.ReadLine ();
        var n = s.Length;
        var K = int.Parse (Console.ReadLine ());
        var dp = new int[105, 4, 2];
        dp[0, 0, 0] = 1;
        for (var i = 0; i < n; i++) {
            for (var j = 0; j < 4; j++) {
                for (var k = 0; k < 2; k++) {
                    var nd = s[i] - '0';
                    for (var d = 0; d < 10; d++) {
                        var ni = i + 1;
                        var nj = j;
                        var nk = k;
                        if (d != 0) nj++;
                        if (nj > K) continue;
                        if (k == 0) {
                            if (d > nd) continue;
                            if (d < nd) nk = 1;
                        }
                        dp[ni, nj, nk] += dp[i, j, k];
                    }
                }
            }
        }
        var ans = dp[n, K, 0] + dp[n, K, 1];
        Console.WriteLine (ans);
    }
}

Measured memory_bytes: 11092
#1 <= H, W <= 6から、総当たりで求めるのが丸い

import itertools
import pprint

def count_black(A):
    ans = 0
    for a in A:
        ans += a.count("#")
    return(ans)

def make(n):
    ans = []
    for i in range(2 ** n):
        addition = []
        now = bin(i)[2:]
        now = "0" * (n - len(now)) + now
        for j in range(n):
            if now[j] == "1":
                addition.append(j + 1)
        ans.append(addition)
    return(ans)

def remove(C, r):
    rem_col = set(r[0])
    rem_row = set(r[1])
    kouho_col = {i + 1 for i in range(len(C))}
    kouho_row = {i + 1 for i in range(len(C[0]))}
    col = kouho_col - rem_col
    row = kouho_row - rem_row
    ret = []
    for i in col:
        c = C[i - 1]
        new_col = []
        for j in row:
            new_col.append(c[j - 1])
        ret.append(new_col)
    return(ret)


H, W, K = map(int, input().split())
C = []
for i in range(H):
    C.append(list(input()))

#赤く塗る行と列の選び方を全パターン分つくる
#[[1,2,3],[1,2,4]]みたいなので2^(H + W)作る
all = []
collum = make(H)
row = make(W)
all = list(itertools.product(collum, row))

#全パターン試して、うまく行ったものを数え上げる
ans = 0
for i in all:
    now = remove(C, i)
    black = count_black(now)
    if black == K:
        ans += 1
print(ans)

Measured memory_bytes: 9896
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long long count[n+1],leftsum[n+1],rightsum[n+1],temp[n+1];
  for(int i=0;i<n+1;i++)
  {
    count[i]=0;
    
    leftsum[i] = 0;
    rightsum[i] = 0;
  }
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    count[a[i]]++;
  }
 
  for(int i=1;i<n+1;i++)
  {
    long long x = count[i];
    count[i] = (count[i]*(count[i]-1))/2;
    temp[i] = ((x-1)*(x-2))/2;
    leftsum[i] = leftsum[i-1] + count[i];
  }
  rightsum[n] = count[n];
  for(int i=n-1;i>0;i--)
  {
    rightsum[i] = rightsum[i+1] + count[i];
  }
  for(int i=0;i<n;i++)
  {
    cout<<(leftsum[a[i]]-count[a[i]])+(rightsum[a[i]]-count[a[i]])+temp[a[i]]<<endl;
  }
  return 0;
}

Measured memory_bytes: 9600
n,q=map(int, input().split())
s=input()
cnt=[0]*(n-1)
for i in range(n-1):
  if s[i:i+2]=='AC':
    cnt[i]=1
cnt2=[0]*(n)
for i in range(1,n):
  cnt2[i]=cnt2[i-1]+cnt[i-1]
for i in range(q):
  l,r=map(int, input().split())
  print(cnt2[r-1]-cnt2[l-1])

Measured memory_bytes: 13812
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
#include <bits/stdc++.h>
using namespace std;
 
 
int main(){
    int N;
	vector<int> A;
	map<int, int> map;
	int res;
 
	cin >> N;
 
	rep(i, N){
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
		map[tmp] = map[tmp] + 1;		
	}
 
	res = A.size();

	if(map[1] == 1){
		cout << 1;
		return 0;	
	}
	if(map[1] > 1){
		cout << 0;
		return 0;
	}
 
	rep(i, A.size()){
		if(map[A[i]] > 1){
			res--;
		}else{
			for(int j=2; j*j<=A[i]; j++){
				if(A[i]%j == 0 && (map[j] !=0 || map[A[i]/j] !=0)){
					res--;
					break;
				}
			}
		}
	}
 
 
	cout << res;
 
	return 0;
}

Measured memory_bytes: 32964
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
typedef pair<int, int> pii;

vector<pii> read_times(){
	int k;
	cin >> k;
	vector<pii> a(k);
	for(int i = 0; i < k; ++i){
		int h1, m1, h2, m2;
		cin >> h1; cin.ignore(); cin >> m1;
		cin.ignore();
		cin >> h2; cin.ignore(); cin >> m2;
		a[i] = pii(h1 * 60 + m1, h2 * 60 + m2);
	}
	return a;
}

int main(){
	ios_base::sync_with_stdio(false);
	const vector<pii> lectures = read_times();
	int n, m, k = lectures.size();
	cin >> n;
	vector<int> teacher(k);
	for(int i = 0; i < n; ++i){
		const vector<pii> times = read_times();
		for(int j = 0; j < k; ++j){
			for(int t = 0; t < times.size(); ++t){
				if(times[t].first > lectures[j].first){ continue; }
				if(times[t].second < lectures[j].second){ continue; }
				++teacher[j];
				break;
			}
		}
	}
	cin >> m;
	vector<int> student(k);
	for(int i = 0; i < m; ++i){
		const vector<pii> times = read_times();
		for(int j = 0; j < k; ++j){
			for(int t = 0; t < times.size(); ++t){
				if(times[t].first > lectures[j].first){ continue; }
				if(times[t].second < lectures[j].second){ continue; }
				++student[j];
				break;
			}
		}
	}
	int answer = 0;
	for(int i = 0; i < k; ++i){
		answer += min(student[i], teacher[i]);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 1208
n, x =map(int, input().split())
a = list(map(int, input().split()))
s = [0]*(n-1)
ans=0
for i in range(1, n-1):
  temp = a[i]
  left = a[i-1]+temp
  right = a[i+1]+temp
  if left>x and right>x:
    t=min(right, left)-x
    if t<=a[i]:
      ans+=t
      a[i]-=t
    else:
      ans+=a[i]
      a[i]=0
    
#print(a)
#print(" ")
for i in range(n-1):
  temp = a[i]+a[i+1]
  if temp>x:
    t = temp-x
    ans+=t
    a[i]-=t
    if a[i]<0:
      t = 0-a[i]
      a[i+1]-=t
#print(a[-3:])
print(ans)

Measured memory_bytes: 20060
import math
def dist(a,b,d):
  distance=0
  for i in range(d):
    distance+=(a[i]-b[i])**2
  return distance
n,d=map(int,input().split())
x=[]
c=0
for i in range(n):
  x.append(list(map(int,input().split())))
for i in range(1,n):
  for j in range(i):
    k=dist(x[i],x[j],d)
    if k==(int(math.sqrt(k)))**2:
      c+=1
print(c)

Measured memory_bytes: 38492
N, D = list(map(int, input().split()))
X = []
Y = []

for i in range(N):
    xi, yi = list(map(int, input().split()))
    X.append(xi)
    Y.append(yi)

square = lambda x: x * x
X_sq = list(map(square, X))
Y_sq = list(map(square, Y))
D_sq = D * D

count = 0
for i in range(N):
    if X_sq[i] + Y_sq[i] <= D_sq:
        count += 1

print(count)

Measured memory_bytes: 40844
#include<bits/stdc++.h>
#define P 3.1415926535897932384626433832
using namespace std;

void fun()
{
    int n,m;
    cin>>n>>m;

    int sum=0;
    while(m--)
    {
        int x;
        cin>>x;

        sum+=x;


    }

    if(n>=sum)
        cout<<n-sum;
    else
        cout<<"-1";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    fun();
    return 0;
}


Measured memory_bytes: 3656
#include <stdio.h>
#include <stdlib.h>

int n, a[100050], last = 0, dif[100050], t=0;

int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
        dif[i] = abs(a[i] - last);
        t += dif[i];
        last = a[i];
        //printf("%d ", dif[i]);
    }
    dif[n] = abs(last - 0);
    t += dif[n];
    //printf("%d %d %d\n", dif[n], a[n-1], last);
    for(int i=0; i<n; i++){
        int v = t - dif[i] - dif[i+1], c, b;
        if(i > 0) b = a[i-1];
        else b = 0;
        if(i < n-1) c = a[i+1];
        else c = 0;
        v += abs(c-b);
        printf("%d\n", v);
    }

}


Measured memory_bytes: 1920
K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
    



Measured memory_bytes: 69840
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def ceil(A, B):
    if A%B == 0:
        return A//B
    return A//B+1

def solve() -> Any:
    N = read_int()
    answer = 0
    # BxA, Bx, xA
    BxA = 0
    Bx = 0
    xA = 0
    for _ in range(N):
        S = input()
        for i in range(1, len(S)):
            if S[i-1] == 'A' and S[i] == 'B':
                answer += 1
        if S[0] == 'B' and S[-1] == 'A':
            BxA += 1
        elif S[0] == 'B':
            Bx += 1
        elif S[-1] == 'A':
            xA += 1
    if BxA:
        answer += BxA-1
        if Bx:
            answer += 1
            Bx -= 1
        if xA:
            answer += 1
            xA -= 1
    k = min(Bx, xA)
    Bx -= k
    xA -= k
    answer += k
    return answer


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 78252
n = gets.to_i
monsters = gets.split.map(&:to_i)
heroes = gets.split.map(&:to_i)

count = 0

heroes.each_with_index do |hero, index|
  deduction = [monsters[index], hero].min
  monsters[index] -= deduction
  hero -= deduction
  count += deduction
  deduction_2 = [monsters[index + 1], hero].min
  monsters[index + 1] -= deduction_2
  hero -= deduction_2
  count += deduction_2
end

puts count

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

using namespace std;
typedef long long ll;

int main(){
    ll a,v,b,w,t;
    cin>>a>>v>>b>>w>>t;
    if(b-w*t>=a-v*t&b+w*t<=a+v*t){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3624
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;
import std.math;

void main()
{
    immutable N = 100;
    immutable S = N*(N+1)/2;
    auto a = stdin.byLine().map!(s=>s.split().map!(to!int).array()).array().until!(a=>a[0]==0&&a[1]==0).array();
    int n=0, s=0;
    foreach(v;a) n=max(n,v[0]),s=max(s,v[1]);
    n=min(n,N);
    s=min(s,S-(N-n)*(N-n+1)/2);
    auto dp = new long[][](n+1,s+1);
    dp[0][0]=1;
    foreach(i;0..min(s,N)+1)
        foreach_reverse(j;0..n)
            foreach(k;0..s-i+1)
                dp[j+1][k+i]+=dp[j][k];
    foreach(v;a)
        writeln(v[0]>n||v[1]>s?0:dp[v[0]][v[1]]);
}

Measured memory_bytes: 1104
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <queue>
#include <climits>
#include<cmath>
#include <sstream>
#include <iomanip>

int main()
{
    int64_t a,b;
    std::cin>> a;

    std::string c;
    c = "No";

    for( int i = 1; i < 10; i++ )
    {
        for( int r = 1; r < 10; r++ )
        {
            if( i * r == a )
            {
                c = "Yes";
            }
        }
    }

    std::cout<< c ;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll ans = 0;
	ll a;
	rep(i,n){
		cin >> a;
		while(a%2 == 0 && a > 0){
			a /= 2;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n,MOD;
vector<int> adj[MAXN];
int ans[MAXN];

int wayssubtree[MAXN];
int waysabove[MAXN];

void dfs1(int at,int par) {
	wayssubtree[at]=1;
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		dfs1(to,at);
		wayssubtree[at]=(ll)wayssubtree[at]*(1+wayssubtree[to])%MOD;
	}
}
int cur[MAXN],ncur;
int val[MAXN];
int pref[MAXN+1],suff[MAXN+1];
void dfs2(int at,int par) {
	ncur=0;
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		cur[ncur++]=to;
	}
	REP(i,ncur) val[i]=(1+wayssubtree[cur[i]])%MOD;
	pref[0]=waysabove[at]; REP(i,ncur) pref[i+1]=(ll)pref[i]*val[i]%MOD;
	suff[ncur]=1; for(int i=ncur-1;i>=0;--i) suff[i]=(ll)suff[i+1]*val[i]%MOD;
	REP(i,ncur) {
		int to=cur[i];
		waysabove[to]=(1+(ll)pref[i]*suff[i+1])%MOD;
	}
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		dfs2(to,at);
	}
}

void solve() {
	dfs1(0,-1);
	waysabove[0]=1; dfs2(0,-1);
	//printf("a:"); REP(i,n) printf(" %d",wayssubtree[i]); puts("");
	//printf("b:"); REP(i,n) printf(" %d",waysabove[i]); puts("");
	REP(i,n) ans[i]=(ll)wayssubtree[i]*waysabove[i]%MOD;
}

void run() {
	scanf("%d%d",&n,&MOD);
	REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); }
	solve();
	REP(i,n) printf("%d\n",ans[i]);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 13440
n,a,b,c,d=map(int,input().split())
s="."+input()
if(c>d):
    if("..." in s[b-1:d+2] and not "##" in s[a:c+1]):
        print("Yes")
    else:
        print("No")
else:
    if("##" in s[a:d+1]):
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
#define mod 1000000007;

int main(void){
  long long int n,a=1;
  cin >> n;
  for(int i=1;i<=n;i++){
    a*=i;
    a%=mod;
  }
  cout << a << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

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

ANS=[]

NOW=N
while NOW!=0:
    for i in range(M,0,-1):
        if NOW-i>=0 and S[NOW-i]=="0":
            NOW-=i
            ANS.append(i)
            break
    else:
        print(-1)
        sys.exit()

print(*ANS[::-1])

Measured memory_bytes: 50416
n = gets.to_i
ss = n.times.map { gets.strip }

# アナグラムである = 文字列中の文字をソートした結果が一致する

# すべてのsをソートして、同じものが何回登場するかで組み合わせの数がわかるので
# それらの総和が答え

def comb(n, r)
    if r == 0
        return 1
    end
    
    (n - r + 1) * comb(n, r - 1) / r
end

puts ss.map {|s| s.chars.sort.join}
        .each_with_object(Hash.new(0)) {|s, hash| hash[s] += 1}.values
        .map {|n| comb(n, 2)}.inject(:+)

Measured memory_bytes: 38524
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

namespace n91 {

  using i8 = std::int_fast8_t;
  using i32 = std::int_fast32_t;
  using i64 = std::int_fast64_t;
  using u8 = std::uint_fast8_t;
  using u32 = std::uint_fast32_t;
  using u64 = std::uint_fast64_t;
  using isize = std::ptrdiff_t;
  using usize = std::size_t;

  constexpr usize operator"" _z(unsigned long long x) noexcept {
    return static_cast<usize>(x);
  }

  class rep {
    const usize f, l;

  public:
    class itr {
      friend rep;
      usize i;
      constexpr itr(const usize x) noexcept : i(x) {}

    public:
      void operator++() noexcept { ++i; }
      constexpr usize operator*() const noexcept { return i; }
      constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
    };
    constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
    constexpr itr begin() const noexcept { return itr(f); }
    constexpr itr end() const noexcept { return itr(l); }
  };
  class revrep {
    const usize f, l;

  public:
    class itr {
      friend revrep;
      usize i;
      constexpr itr(usize x) noexcept : i(x) {}

    public:
      void operator++() noexcept { --i; }
      constexpr usize operator*() const noexcept { return i; }
      constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
    };
    constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
    constexpr itr begin() const noexcept { return itr(l); }
    constexpr itr end() const noexcept { return itr(f); }
  };
  template <class T> using vec_alias = std::vector<T>;
  template <class T> auto md_vec(const usize n, const T& value) {
    return std::vector<T>(n, value);
  }
  template <class... Args> auto md_vec(const usize n, Args... args) {
    return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
  }
  template <class T> constexpr T difference(const T& a, const T& b) {
    return a < b ? b - a : a - b;
  }
  template <class T> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
  }

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

  void main_() {
    const usize n = scan<usize>();
    std::vector<usize> a(n);
    std::vector<u32> b(n), c(n - 1_z);
    for (auto& e : a) {
      std::cin >> e;
      --e;
    }
    for (auto& e : b) {
      std::cin >> e;
    }
    for (auto& e : c) {
      std::cin >> e;
    }
    u32 ans = static_cast<u32>(0);
    usize prev = n;
    for (const auto e : a) {
      ans += b[e];
      if (prev + 1_z == e) {
        ans += c[prev];
      }
      prev = e;
    }
    std::cout << ans << std::endl;
  }

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pq priority_queue
using namespace std;
const ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
const ll MAX=100100;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
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(){
    string S;
    cin>>S;
    string t="coffee";
    if(S[2]==S[3]&&S[4]==S[5]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 764
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define NDEBUG
#define int ll
#define F1R(i, a)     for (int i=1; i<=a; i++)
#define F0R(i, a)     for (int i=0; i<a; i++)
#define FOR(i, a, b)  for (int i=a; i<b; i++)
#define F1Rd(i, a)    for (int i=a; i>0; i--)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a)    for (int i = (a)-1; i >= 0; i--)
#define trav(a, x)    for (auto& a : x)
#define whats(x)      cerr << #x << " is " << x << '\n';
#define MOD           1000000007
#define INF           1e18
#define f             first
#define s             second
#define mp            make_pair
#define pb            push_back
#define en(x)         x.end()
#define beg(x)        x.begin()
#define sz(x)         (int)x.size()
#define all(x)        beg(x), en(x)
#define rsz           resize
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree = tree<T,null_type,less<T>,
rb_tree_tag,tree_order_statistics_node_update>;
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<ll>  vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
const
int MN = 2005;

int N, K, A[MN], invcnt, sum;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> K;
    F0R(i,N) cin >> A[i];
    F0R(j,N) F0R(i,j) if(A[i] > A[j]) invcnt++;
    F0R(i,N) F0R(j,N) if(A[i] > A[j]) sum++;
    cout << (((((((K*(K-1))/2)%MOD)*sum)%MOD)+((K*invcnt)%MOD))%MOD) << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <ios>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>

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

using namespace std;

const int INF = 100000000;

char a[51][51];
char b[51][51];

bool isSame(int y,int x,int m){
  for (int i = y; i < y + m; i++) {
    for (int j = x; j < x + m; j++) {
      if (a[i][j] != b[i-y][j-x]) {
        return false;
      }
    }
  }
  return true;
}

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

  REP(i,n){
    string s;
    cin >> s;
    REP(j,n){
      a[i][j] = s[j];
    }
  }

  REP(i,m){
    string s;
    cin >> s;
    REP(j,m){
      b[i][j] = s[j];
    }
  }

  int limit = n - m;
  REP(i,limit + 1){
    REP(j,limit + 1){
      if (isSame(i,j,m) == true) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

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

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  char before = s.at(k - 1);
  char after;
  if (before == 'A') after = 'a';
  else if (before == 'B') after = 'b';
  else if (before == 'C') after = 'c';
  s.at(k - 1) = after;
  cout << s << endl;
}

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

#define println(msg) cout << msg << endl
#define yes_or_no(flag) if (flag) { println("Yes"); } else { println("No"); }
#define sort_vec(vec) sort(vec.begin(), vec.end())
#define rsort_vec(vec) sort(vec.rbegin(), vec.rend()) // greater<int>()

int main() {
  // 入力
  vector<vector<int>> data;
  for (int i = 0; i < 3; i++) {
    vector<int> row(3);
    data.push_back(row);
    for (int j = 0; j < 3; j++) {
      cin >> data[i].at(j);
    }
  }
  
  // 計算
  bool flag = false;
  int a1max = *max_element(data[0].begin(), data[0].end());
  for (int i = 0; i <= a1max; i++) {
    int a1 = i;
    int b1 = data[0][0] - a1;
    int b2 = data[0][1] - a1;
    int b3 = data[0][2] - a1;
    if (b1 < 0 || b2 < 0 || b3 < 0) {
      continue;
    }
    int a2 = data[1][0] - b1;
    int a3 = data[2][0] - b1;
    if (a2 < 0 || a3 < 0) {
      continue;
    }
    if ((data[1][1] - a2) == b2 &&
        (data[1][2] - a2) == b3 &&
        (data[2][1] - a3) == b2 &&
        (data[2][2] - a3) == b3) {
      flag = true;
      break;
    }
  }
  
  // 出力
  yes_or_no(flag);
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define inf 1000000007
#define inf16 0x3f3f3f3f
#define INF 1000000000000000007LL
#define VI vector<int>
#define VPII vector<pair<int, int> >
#define VLL vector<ll>
#define PII pair<int, int>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
using namespace std;

int n, res = inf;

int dig(int a)
{
	int res = 0;

	while(a)
	{
		res += a%10;
		a /= 10;
	}

	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i < n; ++i)
	{
		res = min(res, dig(i)+dig(n-i));
	}

	cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)


void solve(long long K){
    vector<ll> x = {
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
    };
    cout << x.at(K - 1) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
    return 0;
}


Measured memory_bytes: 256
def main():
    K = int(input())
    ans = set()

    def rec(S):
        if 3234566667 < int(S):
            return
        c = S[-1]
        d = int(c)
        for plus in range(d-1, d+2):
            if plus < 0:
                continue
            ans.add(int(S+str(plus)))
            rec(S+str(plus))

    for i in range(1, 10):
        ans.add(i)
        rec(str(i))

    ansc = ans.copy()
    for a in ansc:
        S = str(a)
        pre = ""
        for i, s in enumerate(S):
            if i == 0:
                pre = s
                continue
            if abs(int(pre) - int(s)) > 1:
                ans.discard(a)
                break
            pre = s
    answer = sorted(ans)
    print(answer[K-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 87000
import java.util.*;
import java.lang.*;

// Working program with FastReader 
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
class Main{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

     

   public static void main(String[] args){

      
      FastReader sc=new FastReader();

      int n=sc.nextInt();
      int k=sc.nextInt();
      int arr[]=new int[n];
      for(int i=0;i<n;i++){
        arr[i]=sc.nextInt();
      }

      int dp[]=new int[n];
      dp[0]=0;
      for(int i=1;i<n;i++){
          int j=1;
          int min=Integer.MAX_VALUE;
          while((i-j)>=0&&j<=k){
           
              min=Math.min(min,dp[i-j]+Math.abs(arr[i-j]-arr[i]));
              j++;
          }
           dp[i]=min;
           
      }

      System.out.println(dp[n-1]);



     
   }


}

Measured memory_bytes: 33580
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
vector<vector<int>> g;
int d_time[55];
int a_time[55];
int visited[55];
int ans;
int t;
void bridge(int src,int parent)
{
    visited[src]=true;
    d_time[src]=a_time[src]=++t;
    for(auto i:g[src])
    {
        if(i!=parent && visited[i]==1)
        a_time[src]=min(a_time[src],d_time[i]);
        else if(i!=parent)
        {
            bridge(i,src);
            a_time[src]=min(a_time[src],a_time[i]);
            if(a_time[i]>d_time[src])
            ans++;
        }
    }


}
int32_t main()
{
    int m,n;
    cin>>n>>m;
    ans=0;
    t=0;
    memset(d_time,0,sizeof(d_time));
    memset(a_time,0,sizeof(a_time));
    memset(visited,0,sizeof(visited));
    g=vector<vector<int>>(n+1);
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    if(!visited[i])
    bridge(i,-1);
    cout<<ans<<endl;
}

Measured memory_bytes: 3640
N, M = (int(x) for x in input().split())
lst = [None] * N
for _ in range(M):
    s, c = (int(x) for x in input().split())
    if lst[s-1] is None:
        lst[s-1] = c
    elif lst[s-1] != c:
        print(-1)
        break
else:
    if N > 1 and lst[0] == 0:
        print(-1)
    else:
        if N > 1 and lst[0] is None:
            lst[0] = 1
        num = 0
        for i in range(N):
            if lst[i] is None: continue
            num += lst[i] * 10 ** (N - i - 1)
        print(num)

Measured memory_bytes: 3064
#include <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem0595 : Schedule **/
vector<int> list;
const int MOD = 10007;
int N;
int dp[1001][8][8];

int solve(int n, int pre, int old)
{
	bool ok=false;
	rep(i, 3) {
		if (pre>>i&1 && old>>i&1)
			ok=true;
	}
	if (!ok)
		return 0;
	
	if (n==N-1)
		return 1;
	
	if (dp[n][pre][old]>=0)
		return dp[n][pre][old];
	
	int res=0;
	rep(i, 1<<3) {
		if (i>>list[n+1]&1)
			res += solve(n+1, i, pre);
		res %= MOD;
	}
	
	return dp[n][pre][old] = res;
}

int main()
{
	string s;
	cin>>N>>s;
	int ans=0;
	
	memset(dp, -1, sizeof(dp));
	
	rep(i, s.size()) {
		if (s[i] == 'J')
			list.push_back(0);
		else if (s[i] == 'O')
			list.push_back(1);
		else if (s[i] == 'I')
			list.push_back(2);
	}
	
	rep(i, 1<<3) {
		if (i>>list[0]&1)
			ans += solve(0, i, 1);
		ans %= MOD;
	}

	cout << ans << endl;
}

Measured memory_bytes: 1580
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
//repマクロ定義
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
//allマクロ定義
#define all(v) v.begin(),v.end()
using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  vector<long long> h(n);
  for(int i=0;i<n;i++){
    cin >> h.at(i);
  }

  sort(h.begin(),h.end());

  long long ans=10000000000;
  for(int i=0;(i+k-1)<n;i++){
    ans = min(ans,h[i+k-1]-h[i]);
  }

  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pl = pair<ll,ll>;
using pi = pair<int,int>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll LINF = (1LL<<60);
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; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
int dp[10][10];
int table[500][500];

signed main(){
	//cout << fixed << setprecision(10);
    int n,m; cin >> n >> m;
	rep(i,0,10){
		rep(j,0,10){
			cin >> dp[i][j];
		}
	}
	rep(i,0,n){
		rep(j,0,m){
			cin >> table[i][j];
		}
	}
	rep(k,0,10){
		rep(i,0,10){
			rep(j,0,10){
				chmin(dp[i][j] , dp[i][k] + dp[k][j]);
			}
		}
	}
	int ans = 0;
	rep(i,0,n){
		rep(j,0,m){
			if(table[i][j] == -1)continue;
			ans += dp[table[i][j]][1];
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3960
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		int k = scn.nextInt();
		int[] a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		System.out.println(a[k-1]);
	}
}

Measured memory_bytes: 35772
#include <stdio.h>
int main(void){
	int a[101]={0},n,max=0;
	int i;
	
	while(~scanf("%d",&n)){
		a[n]++;
		if(max<a[n]) max=a[n];
	}
	for(i=1;i<101;i++) if(a[i]==max) printf("%d\n",i);
	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,k,cnt,L[70004],R[70004],dp[102][70004];
signed main()
{
	cin>>n>>k;
	int x=1,xu,jia;
	while(x<=n)
	{
		jia=n/x,xu=n/jia;
		L[++cnt]=x,R[cnt]=xu;
		x=xu+1;
	}
	for(int i=1;i<=cnt;i++)dp[1][i]=R[i];
	for(int i=2;i<=k;i++)
	{
		for(int j=1;j<=cnt;j++)dp[i][j]=dp[i-1][cnt-j+1]*(R[j]-L[j]+1)%mod;
		for(int j=1;j<=cnt;j++)(dp[i][j]+=dp[i][j-1])%=mod;
	}
	cout<<dp[k][cnt];
	return 0;
}
/*
dp[i][j]±íÊ¾µÚiÎ»ÓÃÁËÇ°j¶ÎµÄÊý×ÖµÄ·½°¸Êý
dp[i][j]=dp[i-1][cnt-j+1]*(R[j]-L[j]+1)ÓÃµÚj¶Î
dp[i][j]+=dp[i][j-1]ÓÃÇ°j¶Î 
*/

Measured memory_bytes: 55936
#include <vector>

template<class T, class E, class U, class To, class Adj, class Ope, class Merge>
std::vector<T> rerooting(const std::vector<std::vector<E>>& G, int r, U ide, To to, Adj adj, Ope ope, Merge merge) {
  int N = G.size();
  std::vector<T> tdp(N);
  std::vector<int> par(N, -1);
  std::vector<int> que(N);
  int qi = 0;
  que[qi++] = r;

  int MAX = 1;
  for(int i = 0;i < qi;i++) {
    int v = que[i];
    for(const auto& e: G[v]) {
      int t = to(e);
      if(t == par[v]) continue;
      par[t] = v;
      que[qi++] = t;
    }
    MAX = std::max(MAX, (int)G[v].size() + 1);
  }

  for(int i = qi; i --> 0;) {
    int v = que[i];
    U sum = ide;
    for(const auto& e : G[v]) {
      int t = to(e);
      if(t == par[v]) continue;
      sum = ope(sum, adj(tdp[t], e));
    }
    tdp[v] = merge(sum, v);
  }

  std::vector<U> f(MAX);
  std::vector<U> b(MAX);

  for(int i = 0; i < qi; i++) {
    int v = que[i];
    for(int j = 0;j < G[v].size();j++) {
      int t = to(G[v][j]);
      f[j + 1] = adj(tdp[t == par[v] ? v : t], G[v][j]);
    }
    b[G[v].size()] = ide;
    for(int j = G[v].size(); j --> 0;) b[j] = ope(f[j + 1], b[j + 1]);
    f[0] = ide;
    for(int j = 0;j < G[v].size(); j++) {
      int t = to(G[v][j]);
      f[j + 1] = ope(f[j], f[j + 1]);
      if(t != par[v]) {
        tdp[t] = merge(ope(f[j], b[j + 1]), v);
      }
      tdp[v] = merge(f[G[v].size()], v);
    }
  }
  return tdp;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }


int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  i64 N, M;
  cin >> N >> M;
  vector<vector<int>> G(N);
  rep(i,0,N - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  auto res = rerooting<i64>(G, 0, 1,
        [](int t) { return t; },
        [&](int t, int) { return (t + 1) == M ? 0 : t + 1; },
        [&](int a, int b) { return (int)(i64(a) * b % M); },
        [](int a, int) { return a; }
      );

  rep(i,0,N) {
    cout << res[i] << "\n";
  }
}


Measured memory_bytes: 8440
def abc126_e():
    n, m = map(int, input().split())
    par = [x for x in range(n)]
    rank = [0]*n

    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]: rank[x] += 1

    for _ in range(m):
        x, y, z = map(int, input().split())
        unite(x-1, y-1)

    for i in range(n):
        _ = find(i)

    ans = len(set(par))
    print(ans)

if __name__ == '__main__':
    abc126_e()

Measured memory_bytes: 19836