akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 59);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------

// function -------------------------------------------

ll amari(string x, ll m){
	ll res = 0;
	ll n = x.length();
	ll prev = 0;
	REP(i, n){
		ll p = x[i] - '0';
		prev = (p + prev * 2) % m;
	}
	res = prev;
	return res;
}

ll popo(string x){
	ll res = 0;
	ll n = x.length();
	REP(i, n){
		if(x[i] == '1'){
			res ++;
		}
	}
	return res;
}

ll popo(ll x){
	// 10->2
	string s = "";
	while(x != 0){
		s += char((x % 2) + '0');
		x /= 2;
	}
	reverse(s.begin(), s.end());
	return popo(s);
}

// main -----------------------------------------------

int main() {
	ll n;
	string x;
	cin >> n >> x;
	ll memo1, memo2 = 0;
	ll pp = popo(x);
	ll yabaiwayo = -1;
	if(pp == 1){
		REP(i, n){
			if(x[i] == '1'){
				yabaiwayo = i;
				break;
			}
		}
	}else{
		memo2 = amari(x, pp - 1);
	}
	memo1 = amari(x, pp + 1);
	// cout << memo1 << memo2 << pp <<  endl;

	vector<ll> ans(n);
	ll nibeki1 = 1, nibeki2 = 1;
	// 下の桁から見ている
	REP(i, n){
		// x, ans専用
		ll index = n - i - 1;
		ll mini_ans, cnt = 0;
		if(yabaiwayo != -1 && yabaiwayo == index){
			ans[index] = 0;
			nibeki1 *= 2;
			nibeki1 %= (pp + 1);
			// cout << "y";
			continue;
		}
		// cout << x[index];
		if(x[index] == '1'){
			mini_ans = (((memo2 - nibeki2) % (pp - 1)) + (pp - 1)) % (pp - 1);
			// cout << "!" << endl;
		}else{
			mini_ans = (memo1 + nibeki1) % (pp + 1);
			// cout << "?" << endl;
		}
		nibeki1 *= 2;
		nibeki1 %= (pp + 1);
		if(pp - 1 != 0){
			nibeki2 *= 2;
			nibeki2 %= (pp - 1);
		}
		cnt ++;
		while(mini_ans != 0){
			mini_ans = mini_ans % popo(mini_ans);
			cnt ++;
		}
		ans[index] = cnt;
	}

	// cout << endl;

	REP(i, n){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 5224
#include<stdio.h>

int main(void)
{
    int a,b;
    scanf("%d%d",&a,&b);
    int i;
    int ans=0;

    for(i=0;i<2;i++){
        if(a>b){
            ans+=a;
            a-=1;
        }else{
            ans+=b;
            b-=1;
        }
    }

    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
A,B,C,X,Y=map(int,input().strip().split(' '))
m=min(X,Y)
print(min(2*C*max(X,Y),2*C*m+A*(X-m)+B*(Y-m),A*X+B*Y))
#print(C*max(X,Y),C*m+A*(X-m)+B*(Y-m),A*X+B*Y)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

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

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

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

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////



int main() {

	ll K, N;
	cin >> N >> K;

	vector<ll> x(N + 1), y(N + 1);

	repn(i, N) cin >> x[i] >> y[i];

	ll ans = 5e18;

	repn(d, N)repn(u, N)repn(l, N)repn(r, N) {
		if (x[r] < x[l] || y[u] < y[d]) { continue; }

		ll cnt = 0;
		repn(i, N) {
			if (x[l] <= x[i] && x[i] <= x[r] && y[d] <= y[i] && y[i] <= y[u]) { cnt++; }
		}

		if (cnt >= K) { ans = min(ans, (x[r] - x[l])*(y[u] - y[d])); }
	}

	cout << ans;

	system("PAUSE");

	

}


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

int main(){
  int N,K;
  cin>>N>>K;
  unordered_set<int> D;
  for(int i=0;i<K;i++){
    int j;
    cin>>j;
    D.insert(j);
  }
  for(;true;N++){
    bool bo=false;
    for(int j=N;j>0;j/=10)
      if(D.count(j%10))
        bo=true;
    if(bo)
      continue;
    break;
  }
  cout<<N<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

long long euclidean_gcd(long long a, long long b)
{
	if (a < b)
		return euclidean_gcd(b, a);
	long long r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

int main()
{
	long long a, b;
	cin >> a >> b;
	long long m = euclidean_gcd(a, b);
	m *= (a / m) * (b / m);
	printf("%lld", m);

	return 0;
}

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

int main(void){
  int a,b,c,n,k,x,y,z;
  string str,str2;
  cin >> x >> a;
  if(x < a)cout << 0 << endl;
  else cout << 10 << endl;
  return 0;
}

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

int main(){
  long n,m;
  cin >> n >> m;
  for(int i=0;i<m;i++){
    int a;
    cin >> a;
    n-=a;
  }
  if(n<0){
    cout << -1 << endl;
  }else{
    cout << n << endl;
  }
}


Measured memory_bytes: 3644
#include<stdio.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
  int N;
  scanf("%d", &N);
  int A[N];
  for (int i=0 ; i<N ; i++) {
    scanf("%d", &A[i]);
  }
  sort(A, A+N);
  int max = 0;
  for (int i=0 ; i<100000 ; i++) {
    int num1 = (int)(upper_bound(A, A+N, i-1) - lower_bound(A, A+N, i-1));
    int num2 = (int)(upper_bound(A, A+N, i) - lower_bound(A, A+N, i));
    int num3 = (int)(upper_bound(A, A+N, i+1) - lower_bound(A, A+N, i+1));
    if (max < num1 + num2 + num3) max = num1 + num2 + num3;
  }
  printf("%d\n", max);
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	public class Damage
	{
		public long Amount{get;set;}
		public int Index{get;set;}
		
		public override string ToString()
		{
			return Amount + " " + Index;
		}
	}
	public static void Main(string[] args)
	{
		var p = Input();
		var n = p[0].ToInt();
		var h = p[1].ToLong();
		var db = new HeapQueue<Damage>(n, (s, t) => (int)(s.Amount - t.Amount));
		long s2 = 0;
		for(int i = 0; i < n; i++)
		{
			var q = Input();
			var a = q[0].ToLong();
			var b = q[1].ToLong();
			db.Push(new Damage(){Index = i, Amount = b});
			s2 = Math.Max(s2, a);
		}
		
		long cnt = 0;
		for(;h > 0;)
		{
			var s1 = db.Peep();
			if(s1 != null && s1.Amount > s2)
			{
				h -= s1.Amount;
				db.Pop();
				cnt++;
			}
			else
			{
				long k = h / s2;
				h -= k * s2;
				cnt+= k;
				
				if(h > 0)
					cnt++;
				break;
			}
		}
		
		Console.WriteLine(cnt);
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static long Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}

class HeapQueue<T> //where T : IComparable<T>
{
	private List<T> _buffer;
	private Comparison<T> _comparer;
	
	public HeapQueue()
	{
		_buffer = new List<T>();
	}
	
	public HeapQueue(int capacity, Comparison<T> comparer = null)
	{
		_buffer = new List<T>(capacity);

		_comparer = comparer;
	}
	
	public void Push(T el)
	{
		List<T> array = _buffer;
		int n = array.Count;
		array.Add(el);
		
		while (n != 0)
		{
			int i = (n - 1) / 2;
			if (Compare(array[n], array[i]) > 0)
			{
				T tmp = array[n]; array[n] = array[i]; array[i] = tmp;
			}
			n = i;
		}
	}
	
	public T Pop()
	{
		T el = _buffer[0];
		
		List<T> array = _buffer;
		
		int n = array.Count - 1;
		array[0] = array[n];
		array.RemoveAt(n);

		for (int i = 0, j; (j = 2 * i + 1) < n; )
		{
			if ((j != n - 1) && (Compare(array[j], array[j + 1]) < 0))
				j++;
			if (Compare(array[i], array[j]) < 0)
			{
				T tmp = array[j]; array[j] = array[i]; array[i] = tmp;
			}
			i = j;
		}
		return el;
	}
	
	public T Peep()
	{
		if(_buffer.Count <= 0)
			return default(T);

		return _buffer[0];
	}
	private int Compare(T left, T right)
	{
		return _comparer(left, right);
	}
	
	public int Count
	{
		get{ return _buffer.Count; }
	}
	
}


Measured memory_bytes: 23108
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

//C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
const int dx[8] = { -1,0,1,-1,1,-1,0,1 };
const int dy[8] = { 1,1,1,0,0,-1,-1,-1 };


//LOVE NyantakoGG	https://www.youtube.com/channel/UC6XdFs8T6Ei54O0FYl3PVVA


using namespace std;



int main() {
	string S;
	cin >> S;
	int d = 0;
	for (int i = 0; i < S.size(); i++) {
		d += (int)S[i] - 48;
	}
	int D = stoi(S);
	if (D % d == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


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

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    int N;
    vector<int> W;

    cin>>N;
    int sum = 0;
    for(int i = 0;i < N;i++) {
        int w;
        cin>>w;
        W.push_back(w);
        sum += w;
    }

    int diff = sum;
    int take = 0;
    for(int i = 0;i < N;i++) {
        take += W[i];
        sum -= W[i];
        diff = min(diff,abs(sum-take));
    }

    cout<<diff<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 100111
#define inf 100000011
#define LOG 20
using namespace std;
vector<int> v;
int dp[MAX],dpp[MAX];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	int n;
	cin>>n;
	for(int i = 0 ; i <MAX ; i++) dp[i] = inf;

	dp[1] = 1;
	v.push_back(1);
	int t = 1;
	for(int i = 1 ; i < 7 ; i++){t*=6;dp[t] = 1;v.push_back(t);}
	t = 1;
	for(int i = 1 ; i < 6 ; i++){t*=9;dp[t] = 1;v.push_back(t);}
		
	for(int j = 2; j < 50; j++){
		memset(dpp,0x1F,sizeof dpp);
		for(int i = 1 ;i < MAX ; i++){
			if(dp[i] != inf){
				for(auto x : v){
					if( i + x < MAX ){
						dpp[i + x] = min(dp[i] + 1 ,dpp[i + x]);
					}
				}
			}
		}
		for(int i = 1; i < MAX ; i++){
			dp[i] = min(dp[i],dpp[i]);
		}

	}
	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
using namespace std;
int main()
{
	long long int n,m,sum = 0;
	scanf("%lld %lld",&n,&m);
	if(2*n>=m)  sum = m/2;
	else  sum = n + (m-2*n)/4;
	printf("%lld\n",sum);
}

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

long long int a, b, c;

int main(){
  cin >> a >> b >> c;
  long long int mx = max(a, max(b, c));
  long long int mn = min(a, min(b, c));
  long long int md = a + b + c - mx - mn;
  if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0){
    cout << 0 << endl;
  }else{
    cout << mn * md  << endl;
  }
  return 0;
}

Measured memory_bytes: 256
N = int(input())    

A = [[0] * N for _ in range(N)]
Al = [[0] * (N+1) for _ in range(N+1)]
Ar = [[0] * (N+1) for _ in range(N+1)]

for i in range(N) :
    a = [int(i) for i in input().split()]
    for j in range(N) :
        if i < j :
            A[i][j] = a[j-1]
        elif i > j :
            A[i][j] = a[j]

for i in range(N) :
    for j in range(i+1, N) :
        Al[j][i+1] = Al[j][i] + A[j][i]
        Ar[i][j] = Ar[i-1][j] + A[i][j]

# for al in Al :
    # print(al)
# print()
# for ar in Ar :
    # print(ar)

dp = [[float('inf')] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
        
for i in range(N+1) :
    for j in range(i, N+1) :        
        l, r = 0, 0
        for k in range(j+1, N+1) :
            l += Al[k-1][i]
            r += Ar[k-2][k-1] - Ar[j-1][k-1]
            dp[j][k] = min(dp[j][k], dp[i][j] + l + r)
            # print('i', i, 'j', j, 'k', k, l, r)
# print(dp)
print(min(dp[i][N] for i in range(N+1)))

Measured memory_bytes: 127368
#include <iostream>
#include <string.h>
using namespace std;
int main(int argc, char* argv[])
{
	char S[100];
	cin>>S;
	if (!memcmp(S,"YAKI",4)){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<string> s(N);
  for(int i=0;i<N;i++){
    cin >> s[i];
    sort(s[i].begin(),s[i].end()); //文字順
  }
  sort(s.begin(),s.end()); //文字列ソート(同じ文字列は連続して並ぶ)

  long long int ans=0;
  int count = 1;
  string s_tmp = s[0];
  for(int i=1;i<N;i++){
    if(s_tmp == s[i])count++;
    else{
      if(count>1)ans += ((long)count*(long)(count-1)/2);
      count = 1;
      s_tmp = s[i];
    }
  }
  if(count>1)ans += ((long)count*(long)(count-1)/2);
  //最後まで行った時の処理
  
  cout << ans << endl;

}

/*
参考にしました→
https://atcoder.jp/contests/abc137/submissions/8077943
*/

Measured memory_bytes: 7296
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
ll arr[200001];
ll XOR[200001],sum[200001];
ll ans=0;

int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  cin>>N;
  for (int i=1;i<=N;i++)
    cin>>arr[i];
  for (int i=1;i<=N;i++){
    XOR[i]=XOR[i-1] xor arr[i];
    sum[i]=sum[i-1]+arr[i];
  }
  int prev=1;
  for (int i=1;i<=N;i++){
    for (int j=prev;j<=N;j++){
      if ((XOR[j] xor XOR[i-1])!=(sum[j]-sum[i-1]))
	break;
      prev++;
    }
    ans+=prev-i;
  }
  cout<<ans<<endl;
  return 0;
}
  


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

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

const int N = 1e5 + 5;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);	
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; i++)
		cout << "x";
	cout << "\n";
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 10000 + 10;
vector<int> g[MAX_N];
int deg[MAX_N];

int main2() {
  REP(i, MAX_N) g[i].clear();
  CLR(deg, 0);

  int N = nextInt();
  REP(i, N-1) {
    int a = nextInt() - 1;
    int b = nextInt() - 1;
    g[a].push_back(b);
    g[b].push_back(a);
    deg[a]++;
    deg[b]++;
  }
  vector<int> c;
  REP(i, N) c.push_back(nextInt());
  sort(ALL(c));
  int ci = 0;
  vector<int> ans(N);

  queue<int> q;
  REP(i, N) if (deg[i] == 1) { q.push(i); deg[i]--; }

  while (!q.empty()) {
    int v = q.front(); q.pop();
    ans[v] = c[ci++];
    for (int u : g[v]) {
      deg[u]--;
      if (deg[u] == 1) {
        q.push(u);
      }
    }
  }

  ll ans_value = 0;
  REP(i, N) {
    for (int j : g[i]) if (i < j) {
      ans_value += min(ans[i], ans[j]);
    }
  }
  printf("%lld\n", ans_value);
  REP(i, ans.size()) {
    if (i > 0) printf(" ");
    printf("%d", ans[i]);
  }
  printf("\n");
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


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

int main(){
	int n;
	cin >> n;
	double sum,a;
	for(int i = 0 ; i < n ; i += 1){
		cin >> a;
		sum += 1/a;
	}
	sum = 1/sum;
	cout << setprecision(5) << fixed;
	cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll minn(ll x, ll y){
    if(x<y)
        return x;
    return y;
}
ll maxx(ll x, ll y){
    if(x>y)
        return x;
    return y;
}
int dp[100009];
int main() {
    int n,k,a[109];
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        dp[a[i]]=1;
    }
    for(int i=1;i<=k;i++){
        // cout<<dp[i-1]<<" ";
        if(dp[i]==1){
            continue;
        }   
        int x=1;
        for(int j=0;j<n;j++){
            if(i - a[j]>=0)
                x = x & dp[i - a[j]];
        }
        dp[i] =1-x;
    }
    if(dp[k])
        cout<<"First";
    else
        cout<<"Second";
    return 0;
}

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

#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, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int K;
  string S;
  cin >> K >> S;
  int N = S.size();
  if(N > K){
    cout << S.substr(0, K) << "..." << endl;
  }
  else{
    cout << S << endl;
  }
  return 0;
}


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

#define INF -1

typedef struct{
  int d;
  int f;
}timestamp;

typedef struct{
  int u;
  int k;
  int *v;
}graph;

graph g[110];
timestamp t[110];
int mytime = 0;
int q[110];

void bfs(void);

int main(void){
  int i,j,n;

  scanf("%d", &n);


  for(i = 0; i <= n; i++){
    q[i] = t[i].d = t[i].f = INF;
  }

  for(i = 1; i <= n; i++){
    scanf("%d%d", &g[i].u, &g[i].k);
    g[i].v = (int *)malloc(sizeof(int) * (g[i].k+1));
    for(j = 1; j <= g[i].k; j++){
      scanf("%d", &g[i].v[j]);
    }
  }

  bfs();

  for(i = 1; i <= n; i++)
    printf("%d %d\n", i, t[i].d);
 
  return 0;
}

void bfs(void){
  int s = 1;
  int first = 1, last = 1;
  int i, u;

  t[s].d = 0;
  //enqueue
  q[last] = s;
  last++;
  while(first != last){
    //dequeue
    u = q[first];
    q[first] = INF;
    first++;
    for(i = 1; i <= g[u].k; i++){
      if( t[ g[u].v[i] ].d == INF){
        t[g[u].v[i]].d = t[u].d + 1;
        //enqueue
        q[last] = g[u].v[i];
        last++;
      }
    }
  }
}

Measured memory_bytes: 600
n, m = map(int, input().split())
l = list(map(int, input().split()))
road = []
for i in range(n + 1): road.append([])
for i in range(m):
    a, b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
# print(road)
ans = 0
for i in range(1, n + 1):
    ch = 1
    for j in road[i]:
        if l[j - 1] >= l[i - 1]:
            ch = 0
            break
    if ch: ans -= -1
print(ans)

Measured memory_bytes: 29512
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,Y,a[1000][1000]={0};
    cin>>T>>Y;
    for(int i=0;i<T;i++){
        for(int j=0;j<Y;j++){
            cin>>a[i][j];
            a[T][j]+=a[i][j];
        }
    }
    for(int i=0;i<=T;i++){
        for(int j=0;j<Y;j++) a[i][Y]+=a[i][j];
    }
    for(int i=0;i<=T;i++){
        for(int j=0;j<Y;j++) cout<<a[i][j]<<" ";
        cout<<a[i][Y]<<endl;
    }
}

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

typedef long long ll;
int N,A,B;
vector<int> X;

int main() {
    cin>>N>>A>>B;
    X.resize(N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
    }

    ll ans = 0;

    for(int i = 0; i < N - 1; i++) {
        ans += min(1LL*A*(X[i + 1] - X[i]), 1LL*B);
    }

    printf("%lld", ans);
}


Measured memory_bytes: 640
s = input().strip()
k = int(input())


def bf(s):
    last = None
    count = 0
    ans = 0
    for c in s:
        if c != last:
            ans += count // 2
            last = c
            count = 1
        else:
            count += 1

    return ans + count // 2


if k < 10:
    print(bf(s * k))
else:
    if len(set(list(s))) == 1:
        print(len(s) * k // 2)
    else:
        delta = bf(s * 3) - bf(s * 2)
        print(bf(s * 2) + delta * (k - 2))


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


int max_sum(int a[],int as,int b[],int bs,int m){
	int j=bs-1;
	int res=0;
	for(int i=0;i<as;i++){
		while(0<=j && m<a[i]+b[j])j--;
		if(j==-1)break;
		res=max(res,a[i]+b[j]);
	}
	return res;
}

int p[1000],p2[1000*1000];
int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		int ans=0;
		for(int i=0;i<n;i++){
			cin>>p[i];
			if(p[i]<=m)ans=max(ans,p[i]);
		}
		sort(p,p+n);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				int a=p[i]+p[j];
				p2[i*n+j]=a;
				if(a<=m)ans=max(ans,a);
			}
		}
		sort(p2,p2+n*n);
		ans=max(ans,max_sum(p,n,p2,n*n,m));
		ans=max(ans,max_sum(p2,n*n,p2,n*n,m));
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 5088
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a[5];
  int answer = 0;
  int min = 10;
  for(int i = 0;i < 5;i++)cin >> a[i];
  for(int i = 0;i < 5;i++)answer += (a[i]+9)/10;
  answer *= 10;
  for(int i = 0;i < 5;i++){
    if(a[i] % 10 < min && a[i] %10 != 0)min = a[i]%10;
  }
  answer -= 10-min;
  cout << answer << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int A, B, C, D;
    scanf( "%d", &A);
    scanf( "%d", &B);
    scanf( "%d", &C);
    scanf( "%d", &D);
    if( A > B )
{
    if( C > D)
    printf( "%d\n", B+D );
    else
    printf( "%d\n", B+C );
}
    else
{
    if( C > D)
    printf( "%d\n", A+D );
    else
    printf( "%d\n", A+C );
}
    return 0;
}

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

namespace abc156_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int a = Convert.ToInt32(input[0]);
            int b = Convert.ToInt32(input[1]);

            if (a <= 10)
            {
                b = b + 100 * (10 - a);
            }

            Console.WriteLine(b);

            Console.Read();

        }
    }
}


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

#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 A, B;
  cin >> A >> B;
  string S;
  cin >> S;

  bool postal = true;
  rep(i, S.size()) {
    if (i == A) {
      if (S[i] != '-') {
        postal = false;
        break;
      }
    } else if (S[i] < '0' || S[i] > '9') {
      postal = false;
      break;
    }
  }

  if (postal) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
string grid[102];
int main() {
	// your code goes here
	int n,m,u,v;
	cin>>n>>m; getchar();
	for(int i=0;i<n;i++) cin>>grid[i];
	for(int i=0;i<m+2;i++) printf("#");
	printf("\n");
	
	for(int i=0;i<n;i++){
		printf("#%s#\n",grid[i].c_str());
	}
	for(int i=0;i<m+2;i++) printf("#");
	printf("\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void outi(int x) {if (x > 9) outi(x / 10);putchar(x % 10 + '0');}
inline void outl(ll x) {if (x > 9) outl(x / 10);putchar(x % 10 + '0');}

int n;
const int N=2e5+7;
const int mod=1e9+7;
ll a[N];
typedef long long ll;
ll sum=0,res,ans[N];
int main()
{
   read(n);
   read(a[1]);
   ans[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        read(a[i]);
        ans[i]=(ans[i-1]%mod+a[i]%mod)%mod;
    }
    for(int i=1;i<=n-1;i++)
    {
       res=((a[i]%mod)*(ans[n]%mod-ans[i]%mod+mod)%mod)%mod;
        sum+=res%mod;
    }
        printf("%lld",sum%mod);
}


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

set<int> s;

main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		if(s.find(a)!=s.end())
		{
			s.erase(a);
		}
		else
		{
			s.insert(a);
		}
	}
	printf("%d",s.size());
}

Measured memory_bytes: 4864
#include<iostream>

typedef long long ll;

ll period( ll a, ll m )
{
	ll p = 1, cnt = 0;

	do
	{
		p = ( a * p ) % m;
		++cnt;
	}while( p != 1 );

	return cnt;
}

ll gcd( ll a, ll b )
{
	if( b == 0 )
		return a;

	return gcd( b, a % b );
}

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

ll a[3], m[3];

int main()
{
	while( true )
	{	
		for( int i = 0; i != 3; ++i )
			std::cin >> a[i] >> m[i];

		bool f = false;

		for( int i = 0; i != 3; ++i )
			f |= a[i] | m[i];

		if( !f )
			break;

		ll ans = 1;
		for( int i = 0; i != 3; ++i )
			ans = lcm( ans, period( a[i], m[i] ) );

		std::cout << ans << std::endl;
	}

	return 0;
}

Measured memory_bytes: 1156
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define ll long long
#define P pair<int, int>
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    ll x;
    int cnt = 0;
    double n = 100;
    cin >> x;
    while(n < x){
        n = floor(n * 1.01);
        cnt++;
    }
    cout << cnt << endl;
    solve();
    return 0;
}




Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n{};
    std::cin >> n;
    std::vector<int> dp(n + 1, n);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        dp[i + 1] = std::min(dp[i + 1], dp[i] + 1);
        int n6 = 6;
        while (i + n6 <= n) {
            dp[i + n6] = std::min(dp[i + n6], dp[i] + 1);
            n6 *= 6;
        }
        int n9 = 9;
        while (i + n9 <= n) {
            dp[i + n9] = std::min(dp[i + n9], dp[i] + 1);
            n9 *= 9;
        }
    }
    std::cout << dp.back() << std::endl;
    return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll 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()

int main(){
  ll n; cin >> n;
  map<string, ll> cnt;
  REP(i,n){
    string s; cin >> s;
    sort(ALL(s));
    cnt[s]++;
  }
  ll ans = 0;
  FOREACH(x,cnt){
    ans += x.second * (x.second-1)/2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11136
#include <iostream> 
#include<bits/stdc++.h>
using namespace std; 
  
int main() 
{ 
 	int n = 0;
  int m = 0;
     
  std::cin>>n>>m;
  int sum = 0;
  for(int i =0; i<m;i++){
    int a;
    cin>>a;
    sum += a;
  } 
  
  int ans = -1;
  if(sum > n) {
    cout<<ans;
    return 0;
    
  }

  cout<< (n-sum);
  
  return 0; 
} 


Measured memory_bytes: 3600
import math

if __name__ == '__main__':
    X, Y = map(int, input().split())
    # print(int(math.log2(Y//X)+1))
    print((Y//X).bit_length())
    # ans = 0
    # while X <= Y:
    #     ans += 1
    #     X *= 2
    # print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[5];
int main()
{
	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}
	sort(a, a + 5, std::greater<int>());
	//reverse(a, a + 5);
	for (int i = 0; i < 5; i++) {
		if (i == 4)cout << a[i] << endl;
		else cout << a[i] << " ";
	}
    return 0;
}

Measured memory_bytes: 3108
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] r = new int[n];
		for (int i = 0; i < n; i++)
			r[i] = 0;
		for (int i = 0; i < n * (n - 1) / 2; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int d = sc.nextInt();
			if (c > d)
				r[a - 1] += 3;
			if (c < d)
				r[b - 1] += 3;
			if (c == d) {
				r[a - 1]++;
				r[b - 1]++;
			}
		}
		int[] rank = new int[n];
		for (int i = 0; i < n; i++)
			rank[i] = 1;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (r[i] > r[j]) {
					rank[j]++;
				}
				if (r[i] < r[j])
					rank[i]++;
			}
		}
		for (int i = 0; i < n; i++)
			System.out.println(rank[i]);
	}
}

Measured memory_bytes: 41948
if $stdin.eof?
  $stdin = DATA
end

ARGF.each_line do |line|
  break if line =~ /\A0 0/
  n, x = line.split.map(&:to_i)
  last =
  if n > (x - 3)
    x - 3
  else
    n
  end

  combinations = [*1..last].combination(3)

  puts combinations.select{|arr| arr.inject(:+) == x}.size

end


__END__
5 9
0 0

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

using namespace std;

typedef int itn;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef map<int, int> M;
typedef pair<int, int> P;
typedef stack<int> S;
typedef queue<int> Q;

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    if (n < 1000) cout << "ABC" << endl;
    else cout << "ABD" << endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String ans;
            int m = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();

            if(m == -1 && f == -1 && r == -1){
                break;
            }

            int sum = m + f;

            if(sum >= 80){
                ans = "A";
            }else if(sum >= 65){
                ans = "B";
            }else if(sum >= 50){
                ans = "C";
            }else if(sum >= 30){
                if(r >= 50){
                    ans = "C";
                }else{
                    ans = "D";
                }
            }else{
                ans = "F";
            }

            if(m == -1 || f == -1){
                ans = "F";
            }
            
            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 26148
import sys
import os
import re
import datetime
import bisect

def DFS(tmpN, N, bitFlags):
    if(tmpN > N):
        return 0

    countAll = 0
    if bitFlags == 0b111:
        countAll += 1

    countAll += DFS(tmpN * 10 + 3, N, bitFlags | 0b100)
    countAll += DFS(tmpN * 10 + 5, N, bitFlags | 0b010)
    countAll += DFS(tmpN * 10 + 7, N, bitFlags | 0b001)

    return countAll

### main ###
 
N = int(input())

bitFlags = 0b000
result = DFS(0, N, bitFlags)

print(result)

Measured memory_bytes: 3444
n,m = map(int,input().split())

A = [-1]*n

ans = 0
is_kaburi = 0
for i in range(m):
    
    s,c = map(int,input().split())
    
    if A[s-1] == -1 or A[s-1] == c:
        A[s-1] = c
          
    else:

        is_kaburi=1


if is_kaburi==1:
    print(-1)    

else:
    if n>1 and A[0] == -1:
        A[0] = 1
        
    elif n==1 and A[0] == -1:
        A[0] = 0
        
    if n != 1 and A[0] == 0:
        print(-1)
        
    else:
        
        for i in range(n):
            
            if A[i] == -1:
                A[i] = 0
                
            ans = ans*10 +A[i]
        
        print(ans)

Measured memory_bytes: 61912
n = int(input())
x = list(map(int, input().split()))
def median(L):
    L = sorted(L)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
x_median = median(x)
l = median(sorted(x)[:-1])
r = median(sorted(x)[1:])
for i in range(n):
    if x[i] > x_median:
        print(l)
    else:
        print(r)

Measured memory_bytes: 25472
#include <bits/stdc++.h>
#include<string>
using namespace std;
#define N 100001
int x[N];
int main(){
    int n ;
    cin >> n;
    for(int i=0;i<n;i++) cin >> x[i];

    int ans=0;
    for(int i=n-2;i>=0;i--){
        if(i == 0){
            if(x[i] > x[i+1]) x[i]--;
        } else {
            if(x[i-1] <= x[i] && x[i] > x[i+1]) x[i]--;
        }
    }

    for(int i=0;i<n-1;i++){
        if(x[i]>x[i+1]){
             ans=1;
             break;
        }
    }
    if(ans == 0) cout << "Yes"<<endl;
    else cout << "No"<<endl;
    
    }

Measured memory_bytes: 640
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	ll I=gi(),O=gi(),T=gi(),J=gi(),L=gi(),S=gi(),Z=gi();
	//T,S,Z都没用，O直接计入答案
	//然后只有 II JJ LL JLI 三种拼法
	ll o=std::max(0ll,std::min(std::min(J,L),I)-1);
	I-=o,J-=o,L-=o;
	o=3*o+O;
	if(I)o+=(I-1)/2*2,I-=(I-1)/2*2;
	if(J)o+=(J-1)/2*2,J-=(J-1)/2*2;
	if(L)o+=(L-1)/2*2,L-=(L-1)/2*2;
	if(I&&J&&L){
		o+=3;int r=(I==2)+(J==2)+(L==2);
		if(r==2)++o;
		else if(r==3)o+=3;
	}else o+=I/2*2+J/2*2+L/2*2;
	printf("%lld\n",o);
	return 0;
}


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


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

    long E[N+1]={0};
    for(long i=0;i<N;i++){
        if(S[i]=='E')E[i+1]++;
        E[i+2]+=E[i+1];
    }
    long ans[N];
    for(long i=0;i<N;i++){
        ans[i]=i-E[i]+E[N]-E[i+1];
    }
    sort(ans,ans+N);
    cout<<ans[0]<<endl;
}

Measured memory_bytes: 5380
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n,k;
    cin>>n>>k;
    vector<pair<int,int>> pa(n);
    for(int i = 0; i < n; i++)
        cin>>pa[i].first>>pa[i].second;
    sort(pa.begin(),pa.end(),[](auto x,auto y){return x.first<y.first;});
    long sum = 0;
    for(auto x:pa){
        sum += x.second;
        if(k<=sum){
            cout<<x.first;
            return 0;
        }
    }
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vpll vector < pair<long long,long long> >
#define fill(a,val)  memset(a,val, sizeof (a))
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(cont) cont.begin(), cont.end()
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(max(a,d),max(b,c))
#define MAX   1e9
#define MIN  -1e9
#define PI 3.14159265358979
#define eps 1e-9
typedef map<int,int> mpi;
typedef set<int> seti;
typedef multiset<int> mseti;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i, n)    for(long long int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(long long int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(long long int i = a; i >= (n); --i)
#define repn(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define trav(a, x) for(auto& a : x)
#define dbg(x) cout << #x << " = " << x << '\n'
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl
#define inp(a,start,len) for(long long int i = start;i < len;i++) cin>>a[i]
struct Interval{ll start,end;};
bool compare(Interval i1, Interval i2) {return (i1.start < i2.start);}

ll dp[200005][2];// 0 for me and 1 for friend
ll mod = 998244353;

ll power(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 

int main(){
	fio;
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	ll T = 1;
	// cin>>T;
	while(T--){
		ll n,k;
		cin>>n>>k;
		ll a[n+1];
		repA(i,1,n)
		cin>>a[i];
		ll sum[n+1];
		sum[0] = 0;
		repA(i,1,n)
		sum[i] = sum[i-1] + a[i];
		ll arr[n+1];
		arr[0] = 0;
		rep(i,n+1)
		arr[i] = (sum[i] - i)%k;
		map<ll,ll> count;
		count[0]++;
		ll ans = 0;
		// cout<<ans
		repA(i,1,n){
			if(i<=k-1){
				ans+=count[arr[i]];
				count[arr[i]]++;
			}
			else{
				count[arr[i-k]]--;
				ans+=count[arr[i]];
				count[arr[i]]++;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}


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

const int INF = 2147483647;

class Backet{
  int n, sqrtN, B;
  vector<int> val, backet;
public:
  Backet(vector<int> a):val(a){
    n = a.size(); sqrtN = ceil(sqrt(n));
    B = (n + sqrtN -1) / sqrtN;

    backet.resize(B,INF);
    for(int i=0;i<B;i++){
      for(int j=sqrtN*i;j<sqrtN*(i+1);j++){
	if(j>=n)break;
	backet[i] = min(backet[i], val[j]);
      }
    }
  }

  int RMQ(int l, int r){
    int L = (l + sqrtN -1) / sqrtN + 1, R = r / sqrtN;

    int res = INF;
    if(L<=R){
      for(int i=l;i<sqrtN*L;i++)res = min(res, val[i]);
      for(int i=L;i<R;i++)res = min(res, backet[i]);
      for(int i=sqrtN*R;i<r;i++)res = min(res, val[i]);
    }else{
      for(int i=l;i<r;i++)res = min(res, val[i]);
    }

    return res;
  }

  void update(int k, int v){
    val[k] = v;
    int x = k/sqrtN;
    backet[x] = INF;
    for(int i=sqrtN*x;i<sqrtN*(x+1);i++){
      if(i>=n)break;
      backet[x] = min(backet[x], val[i]);
    }
  }
};

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> a(n,INF);
  Backet b(a);

  for(int i=0;i<q;i++){
    int c,x,y;
    cin >> c >> x >> y;
    if(c==0)b.update(x,y);
    else cout << b.RMQ(x,y+1) << endl;
  }
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    rep(k, K) {
        vector<ll> B(N + 1);
        rep(i, N) {
            B[max(0LL, i - A[i])]++;
            B[min(N, i + A[i] + 1)]--;
        }
        rep(i, N) B[i + 1] += B[i];
        B.pop_back();
        if(A == B) break;
        A = B;
    }
    iter(i, A) cout << i << endl;
    return 0;
}


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

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> sub(N);
    for(int i = 0; i < M; ++i) {
        int p; cin >> p;
        string s; cin >> s;
        if(s[0] == 'W') sub[p - 1].push_back(0);
        else sub[p - 1].push_back(1);
    }
    int correct = 0, panalty = 0;
    for(int i = 0; i < N; ++i) {
        int pt = 0;
        for(auto &x : sub[i]) {
            if(x == 1) {
                panalty += pt;
                correct += 1;
                break;
            }
            ++pt;
        }
    }
    cout << correct << " " << panalty << endl;
}

Measured memory_bytes: 5760
S = str(input())
T = str(input())

N = len(T)

s_list = []
for i in range(len(S) - N + 1):
    s = S[i:i + N]
    s_list.append(s)
    
answer = N
for s in s_list:
    counter = 0
    for i in range(N):
        if s[i] != T[i]:
            counter += 1
    answer = min(answer, counter)

print(answer)

Measured memory_bytes: 68092
#include<bits/stdc++.h>
#define pi 3.141592653897932384626
//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
using namespace std;
long long a[200005];
int main()
{
    long long s=0;
    long n;
    cin>>n;
    ++n;
    for(long i=1;i<n;i++){scanf("%lld",&a[i]);}
    for(long i=2;i<n;i++){a[i]+=a[i-1];}
    a[0]=0;
    sort(a,a+n);
    a[n]=LONG_LONG_MAX;
    for(long i=1,j=1;i<=n;i++){
         //   cout<<a[i]<<' ';
        if(a[i]==a[i-1])j++;
        else{
            s+=j*(long long )(j-1)/2;
            j=1;
        }
    }
    printf("%lld\n",s);
    return 0;
}


Measured memory_bytes: 1792
import collections

def prime_return(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, p = map(int, input().split())
t = collections.Counter(prime_return(p))
ans = 1
for k, v in t.items():
    if v >= n:
        ans *= (k ** (v // n))
print(ans)

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

#define ll long long
#define MAX 100001

int taken[37];
int check(int n) {
    int sum = 0;
    while (n != 0) {
        int temp = n % 10;
        sum += temp;
        n = n / 10;
    }
    return sum;
}

int main() {
    int n, a, b, ctx = 0;
    cin >> n >> a >> b;

    memset(taken, 0, sizeof taken); taken[0] = 1;
    for (int i = a; i <= b; i++) taken[i] = 1;
    for (int i = 1; i <= n; i++) {
        int sum = check(i);
        if (taken[sum] == 1) ctx+=i;
    } cout << ctx << endl;
}


Measured memory_bytes: 256
n = int(input())
S = input().split()
q = int(input())
T = input().split()

#print(len(S&T))
#set:???????????????????????????

cnt = 0

for i in range(len(T)):
    left = 0
    right = n
    while left < right:
        mid = (left+right) // 2
        if int(S[mid]) == int(T[i]):
            cnt += 1
            break
        elif int(S[mid]) < int(T[i]):
            left = mid+1
        else:
            right = mid
print(cnt)

Measured memory_bytes: 17636
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
cnt=0
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      cnt+=1
    
if cnt==H+W-1:
  print('Possible')
else:
  print('Impossible')

Measured memory_bytes: 3060
fn input() -> String {
	let mut s = String::new();
	std::io::stdin().read_line(&mut s).unwrap();
	s.trim().to_owned()
}

fn main() {
	let s = input();
    println!("{}", match s.as_ref() {
    	"Sunny"  => "Cloudy",
        "Cloudy" => "Rainy",
        "Rainy"  => "Sunny",
        _        => "",
    });
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include<string>
#include<utility>
#include<iterator>
#include<regex>
#include<math.h>

#define lli long long
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(lli i=0;i<j;i++)
#define rep1(i,j) for(lli i=1;i<=j;i++)
#define rep0d(i,j) for(lli i=j-1;i>=0;i--)
#define MAX 1000000007
typedef struct tree Tree;

using namespace std;

bool cmpf(pair<lli, lli> left, pair<lli, lli> right) {
	return left.first < right.first;
}
bool cmp(pair<lli, lli> left, pair<lli, lli> right) {
	if (left.first != right.first)return left.first < right.first;
	else return left.second < right.second;
}

int main() {
	lli n,k;
	string s;
	cin >> n >> k >> s;
	int frag = 0;
	if (s.front() == 'R' && s.back() == 'L' || s.front() == 'L' && s.back() == 'R')frag = 1;
	char temp = s[0];
	lli num = 0, ans = 0, diff = 0;
	rep1(i, n-1) {
		if (temp != s[i]) {
			diff++;
			ans += num;
			temp = s[i];
			num = 0;
		}
		else {
			num++;
		}
	}
	diff = (diff+1)/2;
	ans += num;
	if (diff <= k) {
		diff -= frag;
		ans += diff * 2 + frag;
	}
	else {
		ans += k * 2;
	}
	cout << ans;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()

#define endl "\n"
#define pb push_back
#define elif else if
#define cout_db cout << fixed

#define MOD 1000000007
#define PI 3.1415926
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};

typedef long long ll;

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

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

	int d;
	cin >> d;
	string ans = "Christmas";
	for (int i = 0; i < 25-d; i++) {
		ans += " Eve";
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n,m;
	scanf("%d %d",&n,&m);
	if(n+m==0) printf("0\n");
	if(n+m>=1) printf("1\n");
	if(n+m<0) printf("-1\n");
	return 0;
}	

Measured memory_bytes: 2620