akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

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

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

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

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

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

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

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


vvint G, RG;
vint topo;

bitset<100005> flag;
void dfs(int u) {
	if (flag[u]) return;
	flag[u] = true;
	for (auto &v : G[u]) dfs(v);
	topo.push_back(u);
}

void Main() {
	int N, M; cin >> N >> M;
	G = vvint(N);
	RG = vvint(N);
	for (int i = 0; i < N-1+M; i++) {
		int A, B; cin >> A >> B; --A, --B;
		G[A].push_back(B);
		RG[B].push_back(A);
	}
	for (int i = 0; i < N; i++) dfs(i);

	vint pos(N);
	for (int i = 0; i < N; i++) {
		pos[topo[i]] = i;
	}

	vint ans(N);
	for (int i = 0; i < N; i++) {
		int u = topo[i];

		int p = -1, c = INF;
		for (auto &v : RG[u]) {
			if (c > pos[v]) {
				c = pos[v];
				p = v;
			}
		}
		if (p != -1) ans[u] = p+1;
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << el;
	}
}

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


Measured memory_bytes: 18556
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.Queue

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val X, Y = sc.nextInt
    println((math.pow(2, Y) * (Y * 1900 + (X - Y) * 100)).toLong)
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

Measured memory_bytes: 25536
num = map(int,raw_input().split())
n = num[0]
k = num[1]

tot = 0

for i in range(n - k):
    s = n / (k + i + 1)
    t = n % (k + i + 1) - k + 1
    if t < 0:
        t = 0
    tot += s * (i + 1) + t

if k == 0:
    tot -= n 
    
print tot

Measured memory_bytes: 5764
#include <stdio.h>

#define MAX_N 2000000
#define MAX_M 10000
#define max(a,b) ((a) < (b) ? (b) : (a))

void Counting_Sort(int*, int, int);

int ans[MAX_N];

int main(){
  int a[MAX_N], n, i, k = 0;

  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" , a + i);
    k = max(k ,a[i]);
  }
  Counting_Sort(a, k+1, n);

  return 0;
}

void Counting_Sort(int a[], int k, int n){
  int i, C[MAX_M];

  for(i = 0 ; i < k ; i++){
    C[i] = 0;
  }

  for(i = 0 ; i < n ; i++){
    C[a[i]]++;
  }

  for(i = 0 ; i < k ; i++){
    C[i] += C[i-1];
  }
  for(i = n-1 ; i >= 0 ; i--){
    ans[C[a[i]]-1] = a[i];
    C[a[i]]--;
  }

  for(i = 0 ; i < n ; i++){
    printf("%d%c" , ans[i], i != n-1 ?  ' ' : '\n');
  }
}

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

#define pb push_back
#define F first
#define S second
#define mp make_pair
#define vsort(x) sort(x.begin(), x.end())
#define out(x) cout << x << "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR(a, b, c) for(int a = b; a < c; a++)
typedef long long int ll;

int main(){
    IOS;
	ll n,i,j,ii;
	cin>>n;
	ll tmp[3];
	vector<ll>dp(3);
	for(i=0;i<n;i++){
		FOR(j,0,3){
			cin>>tmp[j];
		}
		/*FOR(j,0,3){
		    cout<<tmp[j]<<" ";
		}
		cout<<endl;*/
		vector<ll>new_dp(3,0);
		FOR(ii,0,3){
			FOR(j,0,3){
			    if(ii!=j)
				    new_dp[j] = max((dp[ii] + tmp[j]),new_dp[j]);
			}
		}
		dp = new_dp;
	}
	cout<<max(max(dp[0],dp[1]),dp[2])<<endl;
	return 0;
}


Measured memory_bytes: 256
// Didn't see editorial
#include <iostream>
#include <queue>
#include <iomanip>
#include <map>
#include <algorithm>

using namespace std;

using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main() {
    while(true) {
        int N; ll M;
        cin >> N >> M;
        if (N == 0) return 0;
        vector<ll> P(N+1);
        for (int i = 0; i < N; i++) {
            cin >> P[i];
        }
        P.push_back(0);
        N += 1;

        vector<ll> Q(N);
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                Q.push_back(P[a] + P[b]);
            }
        }
        sort(Q.begin(), Q.end());

        ll mx = 0;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                int x = upper_bound(Q.begin(), Q.end(), M - P[a] - P[b]) - 1 - Q.begin();
                if (x >= 0) {
                    mx = max(mx, P[a] + P[b] + Q[x]);
                }
            }
        }

        cout << mx << endl;
    }
}

Measured memory_bytes: 18736
/*
AizuOnline A2261
Title [[iwi]]
*/
#include <stdio.h>
#include <string.h>
#define max(x,y) (((x)>(y))?(x):(y))
char buf[12];
int char_symm(char c1,char c2)
{
        if(c1 == 'i' && c2 == 'i')
                return(-1);
        if(c1 == 'w' && c2 == 'w')
                return(-1);
        if(c1 == '(' && c2 == ')')
                return(-1);
        if(c1 == ')' && c2 == '(')
                return(-1);
        if(c1 == '{' && c2 == '}')
                return(-1);
        if(c1 == '}' && c2 == '{')
                return(-1);
        if(c1 == '[' && c2 == ']')
                return(-1);
        if(c1 == ']' && c2 == '[')
                return(-1);
        return(0);
}
int solve(char *s,int len)
{
        int i;

        if(0==strncmp(s,"iwi",3))
                return(3);
        if(0==strncmp(&s[len-3],"iwi",3))
                return(3);
        if(char_symm(s[0],s[len-1]))
                return(2+solve(s+1,len-2));
        else
                return(max(solve(s+1,len-1),solve(s,len-1)));
}

main()
{
        int ret;

        scanf("%s",buf);
        ret=solve(buf,strlen(buf));
        printf("%d\n",ret);

return(0);
}

Measured memory_bytes: 544
#include<iostream>
#define for1(i, n) for(int i = 1; i <= (n);i++)
using namespace std;
int n, a[234321], b[234321]; long long f;
signed main() {
	scanf("%d", &n);
	for1(i, n) {
		scanf("%d", &a[i]);
		f += b[a[i]]++;
	}
	for1(i, n) printf("%lld\n", f - b[a[i]] + 1);
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll X;
    cin >> X;
    rep2(i, -200, 200) {
        rep2(j, -200, 200) {
            if (i * i * i * i * i - j * j * j * j * j == X) {
                cout << i << " " << j << '\n';
                return;
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdlib>
#define abs(X) ((X) < 0 ? -1 * (X) : (X))
using namespace std;
using ll = long long;

int main()
{
    ll a, b;
    ll k;

    cin >> a >> b;
    k = (a + b) / 2;

    if (abs(a - k) == abs(b - k)) {
        cout << k << endl;
    }
    else {
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}


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

using namespace std;

void cookie ( int* x, int* y ){
  int tmp = *x;
  if ( tmp % 2 != 0 ){
    --*x;
  }
  //cout << "1 " << *x << " " << *y << endl;
  *y += *x / 2;
  *x /= 2;
  //cout << "2 " << *x << " " << *y << endl;
}

int main(){
  int a, b, k;
  
  cin >> a >> b >> k;
  
  for ( int i = 0; i < k; i++ ){
    if ( i % 2 == 0 ){
      cookie( &a, &b );
      //cout << "3 " << a << " " << b << endl;
    }else {
      cookie( &b, &a );
      //cout << "4 " << a << " " << b << endl;
    }
  }
  
  cout << a << " " << b << endl;


  return 0;
}

Measured memory_bytes: 384
s = input()
diff = 0
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] == "R" or s[i] == "U" or s[i] == "D":
            continue
        else:
            diff += 1
    if i % 2 == 1:
        if s[i] == "L" or s[i] == "U" or s[i] == "D":
            continue
        else:
            diff += 1
if diff == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 8796
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
int main()
{
  int N, Y;
  cin >> N >> Y;
  rep(x, N+1) {
    rep(y, N+1) {
      int z = N - x - y;
      if (z >= 0 && 10000*x + 5000*y + 1000*z == Y) {
        cout << x << " " << y << " " << z << endl;
        return 0;
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
k = max(A)
m = min(A)
C = Counter(A)
if m < (k+1)//2:
  print("Impossible")
else:
  if k & 1:
    for i in range((k+3)//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if not (k+1)//2 in C or C[(k+1)//2] != 2:
      print("Impossible")
      exit()
  else:
    for i in range(1+k//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if k//2 not in C or C[k//2] != 1:
      print("Impossible")
      exit()
  print("Possible")

Measured memory_bytes: 3316
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    S = input()
    for i in range(3):
        if S[i] == S[i + 1]:
            print("Bad")
            break
    else:
        print("Good")

if __name__ == '__main__':
    main()

Measured memory_bytes: 22040
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();
		int A = sc.nextInt();
		int B = sc.nextInt();
		String U = sc.next();
		if(U.equals(S))
			A--;
		else
			B--;
		System.out.println(A + " " + B);

	}

}

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

using namespace std;

int main() {
	int h, w, n, sr, sc;
	cin >> h >> w >> n >> sr >> sc;

	string S, T;
	cin >> S >> T;


	int idx_l = sc;
	int idx_r = sc;
	int idx_u = sr;
	int idx_d = sr;
	bool can_remove = false;
	for (int i = 0; i < n; i++) {
		switch (S[i]) {
			case 'L': idx_l--; break;
			case 'R': idx_r++; break;
			case 'U': idx_u--; break;
			case 'D': idx_d++; break;
			default: break;
		}

		// printf("S %c: L %d, R %d, U %d, D %d\n", S[i], idx_l, idx_r, idx_u, idx_d);

		if (idx_l <= 0 || w < idx_r || idx_u <= 0 || h < idx_d) {
			can_remove = true;
			// printf("remove!\n");
			break;
		}

		switch (T[i]) {
			case 'L': idx_r = max(1, idx_r - 1); break;
			case 'R': idx_l = min(w, idx_l + 1); break;
			case 'U': idx_d = max(1, idx_d - 1); break;
			case 'D': idx_u = min(h, idx_u + 1); break;
			default: break;
		}
		// printf("T %c: L %d, R %d, U %d, D %d\n", S[i], idx_l, idx_r, idx_u, idx_d);
	}

	cout << (can_remove ? "NO" : "YES") << endl;

	return 0;
}


Measured memory_bytes: 776
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;

using namespace std;
using ll = long long;
typedef pair <int, int> pii;
int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll n;
	ll memo[1003][1003] = {};
	ll memo2[1003][1003] = {};
	char tmp;
	//ll y[1003][1003] = {};
	//ll y[100005] = {};
	//ll z[100005] = {};
	string s[1003];
	IntStack xStack;
	IntStack yStack;
	charStack Stack;
	cin >> a;
	cin >> b;
	cin >> c;
	cin >> d;
	if (a==1||b==1||c==1||d==1)
	{
		if (a ==9  || b ==9  || c ==9  || d ==9 )
		{
			if (a ==7  || b ==7  || c ==7  || d ==7 )
			{
				if (a ==4  || b ==4  || c == 4 || d ==4 )
				{
					cout << "YES" << endl;
					return 0;
				}

			}

		}
	}
	cout << "NO" << endl;
	return 0;
	cout << ans << endl;
	//cout << ans << endl;

	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

Measured memory_bytes: 256
import java.util.Scanner;

//Dividing Snacks
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), INF = 1<<29;
		int[] a = new int[n+2];
		for(int i=1;i<n;i++)a[i]=sc.nextInt();
		int[][][] dp = new int[2][2][n/2+1];
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<=n/2;k++)dp[i][j][k]=INF;
		dp[0][0][0] = 0;
		int x = 1;
		for(int i=1;i<=n;i++,x=1-x)for(int j=0;j<2;j++){
			int t = Math.min(i, n>>1);
			for(int k=0;k<=t;k++){
				dp[x][0][k] = Math.min(dp[1-x][0][k], dp[1-x][1][k]);
				if(0<k){
					dp[x][1][k] = dp[1-x][0][k-1]+a[i-1]+a[i];
//					if(1<k)
						dp[x][1][k] = Math.min(dp[x][1][k], dp[1-x][1][k-1]-a[i-1]+a[i]);
				}
			}
		}
		System.out.println(Math.min(dp[1-x][0][n/2], dp[1-x][1][n/2]));
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include <stdio.h>
int main(void)
{
int a, b, c, d;
int x, y;
scanf("%d %d %d %d", &a, &b, &c, &d);

if(a > b){
x = b;
}else if(a < b){
x = a;
}else if(a = b){
x = a;
}

if(c > d){
y= d;
}else if(c < d){
y = c;
}else if(c = d){
y = c;
}
printf("%d\n", x + y);

return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{


	public static void main(String[] args){

		int n;

		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		int[] box=new int[n];
		int max=-1000000001;
		int min=1000000001;

		for(int i=0;i<n;i++){
		box[i]=scan.nextInt();
		}

		for(int i=0;i<n-1;i++){

			if(min>box[i]){
			for(int j=i+1;j<n;j++){
				if(box[j]-box[i]>0&&min>box[i])min=box[i];
				if(max<box[j]-box[i])max=box[j]-box[i];
			}
			}//if(min>box[i])
		}
		System.out.println(max);



		scan.close();

	}

}

Measured memory_bytes: 100912
#include<stdio.h>
main(){
  int a[4],b[4],i,j,hit,brow;
  while(scanf("%d",&a[0])!=EOF){
    for(i=1;i<4;i++)scanf("%d",&a[i]);
    for(i=0;i<4;i++)scanf("%d",&b[i]);
    hit=0;
    brow=0;
    for(i=0;i<4;i++){

    }
    for(i=0;i<4;i++){
      if(a[i]==b[i])hit++;
      else{
	for(j=0;j<4;j++){
	if(a[i]==b[j])brow++;
      }
    }
    }
  

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

}

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

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
const int maxn = 200010;
const int mod = 1000000007;

int fak[ maxn ], inv[ maxn ];

int modpow(int a, int n){
    int v = 1;

    while (n){
        if (n & 1)
            v = 1LL * v * a % mod;
        n >>= 1;
        a = 1LL * a * a % mod;
    }

    return v;
}

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

#ifdef MARX
    freopen("test.in", "r", stdin);
#endif

    fak[0] = inv[0] = 1;

    for (int i = 1; i < maxn; ++i){
        fak[i] = 1LL * fak[i - 1] * i % mod;
        inv[i] = modpow( fak[i], mod - 2 );
    }

    int n, x, y;
    cin >> n >> x >> y;

    vector<vi> id(n), adj(n);
    vector<int> c(n), w(n);

    auto add_edge = [&](int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    };

    for (int i = 0; i < n; ++i){
        cin >> c[i] >> w[i];
        id[ --c[i] ].push_back(i);
    }

    pii A(oo, -1), B(oo, -1);

    for (int i = 0; i < n; ++i){
        if (id[i].empty()) continue;

        vi &cid = id[i];

        int pos = min_element(cid.begin(), cid.end(), [&](int u, int v){
            return w[u] < w[v];
        }) - cid.begin();

        swap(cid[pos], cid[0]);

        for (int j = 1; j < (int)cid.size(); ++j){
            if (w[ cid[0] ] + w[ cid[j] ] <= x)
                add_edge( cid[0], cid[j] );
        }

        pii C( w[ cid[0] ], cid[0] );

        if (C < A) swap(A, C);
        if (C < B) swap(B, C);
    }

    for (int i = 0; i < n; ++i){
        if (A.second != -1 && c[i] != c[ A.second ] && w[i] + A.first <= y)
            add_edge(i, A.second);
        if (B.second != -1 && c[i] != c[ B.second ] && w[i] + B.first <= y)
            add_edge(i, B.second);
    }

    vector<bool> seen(n);
    vector<int> count(n), lst, last(n, -1);

    int answer = 1, tm = -1;

    function<void(int u)> dfs = [&](int u){
        seen[u] = true;

        if (last[ c[u] ] != tm){
            count[ c[u] ] = 0;
            last[ c[u] ] = tm;
            lst.push_back( c[u] );
        }

        count[ c[u] ]++;

        for (auto v : adj[u]){
            if (!seen[v])
                dfs(v);
        }
    };

    for (int i = 0; i < n; ++i){
        if (seen[i]) continue;

        lst.clear();
        tm = i;

        dfs(i);

        int cur_answer = 1;
        int total = 0;

        for (auto u : lst){
            cur_answer = 1LL * cur_answer * inv[ count[u] ] % mod;
            total += count[u];
        }

        cur_answer = 1LL * cur_answer * fak[ total ] % mod;
        answer = 1LL * answer * cur_answer % mod;
    }

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 26216
#include<bits/stdc++.h>
using namespace std;
int const nax = 2e5 + 10;

vector<int> a[nax], node[2];

int n , ct[3], c[3], col[nax];
int  ptr1 = -2, ptr2 = -1, ptr3  = 0;

void dfs (int nod,  int pa, int lv) {
    ct[lv % 2] ++;
    node[lv % 2].push_back(nod);
    for (int i : a[nod])
        if (i != pa)
            dfs(i, nod, lv + 1);
}

int main () {
    scanf("%d", &n);
    for (int i = 1 ; i < n ; ++ i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    c[0] = n / 3 ;
    c[1] = n / 3 + (n % 3 > 0);
    c[2] = n / 3 + (n % 3 > 1);

    dfs(1, 0, 0);

    if (max(ct[0], ct[1]) >= c[1] + c[2]) {
        int toCol = ct[0] >= ct[1] ? 0 : 1;
        for (int i = 0 ;i < c[1] ; ++ i)
            col[node[toCol][i]] = (ptr1 += 3);

        for (int i = 0 ; i < c[2] ; ++ i)
            col[node[toCol][i + c[1]]] = (ptr2 += 3);
    }
    else if (max(ct[0], ct[1]) >= c[1] && min(ct[0], ct[1]) >= c[2]) {
        int maxCol = ct[0] >= ct[1] ? 0 : 1;
        int minCol = (maxCol ^ 1);
        for (int i = 0 ; i < c[1] ; ++ i)
            col[node[maxCol][i]] = (ptr1 += 3);

        for (int i = 0 ; i < c[2] ; ++ i)
            col[node[minCol][i]] = (ptr2 += 3);
    }

    for (int i = 1 ; i <= n ; ++ i)
        printf("%d ", col[i] ? col[i] : ptr3 += 3);


}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 21364
def distance(ab, cd):
  return abs(ab[0] - cd[0]) + abs(ab[1] - cd[1])

N, M = map(int, input().split())
AB = []
for _ in range(N):
  a, b = map(int, input().split())
  AB.append((a, b))

CD = []
for _ in range(M):
  c, d = map(int, input().split())
  CD.append((c, d))

check_index = []
for i, ab in enumerate(AB):
  min_index = 0
  for j, cd in enumerate(CD):
    check_dis = distance(ab, cd)
    min_dis = distance(ab, CD[min_index])
    if(min_dis > check_dis):
      min_index = j
  
  check_index.append(min_index)

for ci in check_index:
  print(ci + 1)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int,input().split()))
ret = 0
right = 0
flag = 0
for left in range(n):
    while right<n and flag&a[right] == 0:
        flag |= a[right]
        right += 1
    ret += right-left
    flag^= a[left]
print(ret)


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

int main(){

	int* data;
	int** drink;
	int n_data;
	int n_drink;
	int i,j;
	int sum;

	scanf("%d",&n_data);
	data = (int*)calloc(n_data,sizeof(int));

	for(i=0; i<n_data; i++){
		scanf("%d",data+i);
	}

	scanf("%d",&n_drink);
	drink = (int**)calloc(n_drink,sizeof(int*));

	for(i=0; i<n_drink; i++){
		drink[i] = (int*)calloc(2,sizeof(int));
		scanf("%d",&drink[i][0]);
		scanf("%d",&drink[i][1]);
	}
	
	for(i=0; i<n_drink; i++){
		sum = 0;
		for(j=0; j<n_data; j++){
			if( drink[i][0] != j+1 ){
				sum += data[j];
			}else{
				sum += drink[i][1];
			}
		}
		printf("%d\n",sum);
	}

	return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int ans = 0;

    int3(r, g, b);
    Int(n);

    rep(i, n+1) {
        rep(j, n+1) {
            int num = i * r + j * g;
            if (num > n) continue;
            if ((n - num) % b == 0) ans++;
        }
    }

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

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<math.h>
#include<stack>
#include<set>
#define INF 2147483647
#define n 300000
#define loop(i, a, b) for(int i=a; i<=b; i++)
#define mem(arr) memset(arr, 0, sizeof(arr));
using namespace std;
typedef long long lli;
typedef double llf;
typedef pair<int, int> P;
struct edge{
	int to, weight;
};
void solve();
int main()
{
	int times = 1;
//	cin >> times;
	loop(i, 1, times)
	{
		solve();
		cout << '\n';
	}
	return 0;
}
vector<edge> V[n + 50];
int a, b, c, d, e, f;
//int arr[n + 50], arr1[n + 50], arr2[n + 50];
string str, str1, str2;
int dp[n + 50];
bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.first < b.first;
}
void solve()
{
	cin >> a >> b;
	pair<int, int> arr[a + 50]; 
	for(int i=0; i<a; i++)
		cin >> arr[i].first >> arr[i].second;
	int ans = 0;
	sort(arr, arr + a, cmp);
	for(int i=0; i<a; i++)
	{
		for(int j=100000; j>=arr[i].first; j--)
		{
			if(j - arr[i].first < b)
			{
				dp[j] = max(dp[j], dp[j - arr[i].first] + arr[i].second);
				ans = max(ans, dp[j]);
			}
		}
	}
	cout << ans << '\n';
}

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

using namespace std;

int main(){
	int l;
	cin >> l;
	int r = 32 - __builtin_clz(l);
	cout << r << " " << 2 * (r - 1) + __builtin_popcount(l) - 1 << '\n';
	for(int i = 1; i < r; ++ i){
		cout << i << " " << i + 1 << " " << 0 << '\n';
		cout << i << " " << i + 1 << " " << (1 << (i - 1)) << '\n';
	}
	int e = 1 << (r - 1);
	int curr = r - 1;
	while(curr--){
		if(l & (1 << curr)){
			cout << curr + 1 << " " << r << " " << e << '\n';
			e |= (1 << curr);
		}
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> container;

    string buff;
    for(int i = 0; i < 10; ++i){
        getline(cin, buff);
        stringstream ss;
        ss << buff;

        int height = 0;
        ss >> height;

        container.push_back(height);
    }

    sort(
         container.begin(),
         container.end(),
         [](int n1, int n2) -> bool {
            return (n1 > n2);
         }
    );

    for(int i = 0; i < 3; ++i)
        cout << container[i] << endl;

    return 0;
}



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



int main()
{
    ios_base::sync_with_stdio(false);

   long long int a,b,c,d,i,j,k,n,m;
   cin>>n;
   string s[n];
   long long int ar[n];
   for(i=0;i<n;i++)
   {
       //getchar();
       cin>>s[i];
       cin>>ar[i];
   }
   //getchar();
   string s2;
   cin>>s2;
   k=0;
   c=0;
   for(i=0;i<n;i++)
   {
       if(k==0 && s[i]==s2)
        k=1;
       else if(k==1)
        c+=ar[i];
   }
   cout<<c<<"\n";
    return 0;
}


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

using namespace std;
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; }

//using Matrix = vector< vector<int> >;
typedef long long ll;
typedef pair<int, int> P;
//const int INF = 1 << 30;
int dx[5] = {0, 0, 1, -1, 0}, dy[5] = {1, -1, 0, 0, 0};
bool cmp(P a, P b) { return a.second < b.second; } //End sort (Interval scheduling problem)

int n;
int h[100010];

ll dp[100010];
const ll INF = 1LL << 60;


int main(void){
	cin>>n;
	for(int i=0;i<n;i++) cin>>h[i];

	for(int i=0;i<n;i++) dp[i] = INF;

	dp[0] = 0;
	for(int i=1;i<n;i++) {
		chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
		if(1 < i) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i -2]));
	}

	cout<< dp[n - 1] <<endl;

	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> pair;
double rad(double a) {return a * 180 / PI;}

//dpTable
int dp[100050];

vector<ll> rsk(100050);

int main(){
    string S;
    cin >> S;
    int ans = 0,a = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T') {
            a++;
        }
        else {
            ans = max(a,ans);
            a = 0;
        }
    }
    if (ans < a) ans = a;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3864
#include <bits/stdc++.h>
    using namespace std;
    #define INF 2000000000
    typedef long long int ll;
    typedef pair<ll,ll> ii;
    typedef pair<ii,ll> iii;
    typedef vector<ll> vi;
    typedef vector<ii> vii;
    #define getbit(n,i) (((n)&(1<<(i)))!=0)
    #define setbit0(n,i) ((n)&(~(1<<(i))))
    #define setbit1(n,i) ((n)|(1<<(i)))
    #define togglebit(n,i) ((n)^(1<<(i)))
    #define lastone(n) ((n)&(-(n)))
    #define read freopen("debug\\in.txt","r",stdin)
    #define write freopen("debug\\out.txt","w",stdout)
    #define fi first
    #define se second
    #define getI(a) scanf("%d",&a)
    #define getII(a,b) scanf("%d%d",&a,&b)
    #define PI (acos(-1))
    #define fastread ios_base::sync_with_stdio(false);cin.tie(NULL)
    #define mod (1000000007)
    #define asz 500005
    #define pb push_back
    #define ppf pop_front
    #define ppb pop_back
    #define pf push_front
    queue<pair<ll,ll> >q;
    vector<pair<ll,ll> >v;
    void solver(){
      ll n,i,k,l,m,d,a;
      cin>>n>>d>>a;
      for(i=1;i<=n;i++){
        cin>>k>>l;
        v.pb({k,l});
      }
      sort(v.begin(),v.end());
      ///q.push(v[0].fi,(v[0].se+a-1)/a);
      ll sum=0;
      ll res=0;
      for(i=0;i<n;i++){
        while(!q.empty()&&v[i].fi-q.front().fi>0){
          sum-=q.front().se;
          q.pop();
        }
        ll temp=(v[i].se+a-1)/a;
        if(temp>sum)
        {
          temp-=sum;
          q.push(make_pair(v[i].fi+2*d,temp));
          sum+=temp;
          res+=temp;
          }
      }
      cout<<res;
    }
    int main()
    {
        fastread;
        solver();
        return 0;
    }

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

using namespace std;
using ll = long long;

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

int main() {
  int N, W;
  cin >> N >> W;
  int w[N + 1], v[N + 1];
  rep(i, N) cin >> w[i + 1] >> v[i + 1];

  ll dp[N + 1][W + 1];
  rep(i, W + 1) dp[0][i] = 0;

  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= W; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (j - w[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
    }
  }

  cout << dp[N][W] << endl;
  return 0;
}


Measured memory_bytes: 79104
import Control.Monad
import Data.List

composition :: [Int] -> [[Int]] -> [(Int, Int, Int, Int)]
composition _ [] = []
composition ls (b:bs) = comp (zip ls b) (0, 0, 0, 0) : composition ls bs
  where comp :: [(Int, Int)] -> (Int, Int, Int, Int) -> (Int, Int, Int, Int)
        comp [] c = c
        comp (n:ns) (a, b, c, d)
          | snd n == 1 = comp ns (a + fst n, b, c, d + cost a)
          | snd n == 2 = comp ns (a, b + fst n, c, d + cost b)
          | snd n == 3 = comp ns (a, b, c + fst n, d + cost c)
          | otherwise  = comp ns (a, b, c, d)
             where cost x = if x == 0 then 0 else 10

solve :: (Int, Int, Int) -> [(Int, Int, Int, Int)] -> [Int]
solve _ [] = []
solve abc@(a, b, c) ((aa, bb, cc, cost):cs) = total : solve abc cs
  where total = abs (aa - a) + abs (bb - b) + abs (cc - c) + cost

main :: IO ()
main = do
  [n, a, b, c] <- map read . words <$> getLine
  ls <- replicateM n readLn
  let check n = 1 `elem` n && 2 `elem` n && 3 `elem` n
  let bits = filter check $ replicateM n [1..4] 
  let comp = composition ls bits
  print . minimum $ solve (a, b, c) comp


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

int main(){
	int n;
	cin>>n;
	long long int tarr[n];
	long long int aarr[n];
	for(int i=0;i<n;i++){
		cin>>tarr[i]>>aarr[i];
	}
	for(int i=1;i<n;i++){
		if(tarr[i]>=tarr[i-1]&&aarr[i]>=aarr[i-1]){
			//continue;
		}else if(tarr[i]<tarr[i-1]&&aarr[i]>=aarr[i-1]){
			long long int mul1=(tarr[i-1]-1)/tarr[i];
			mul1+=1;
			tarr[i]*=mul1;
			aarr[i]*=mul1;
		}else if(tarr[i]>=tarr[i-1]&&aarr[i]<aarr[i-1]){
			long long int mul1=(aarr[i-1]-1)/aarr[i];
			mul1+=1;
			//cout<<mul1<<" mul1<<endl; "<<aarr[i-1]<<" "<<aarr[i]<<endl;
			tarr[i]*=mul1;
			aarr[i]*=mul1;
		}else{
			long long int mul1=(tarr[i-1]-1)/tarr[i];
			mul1+=1;
			long long int sum1=(tarr[i]*mul1)+(aarr[i]*mul1);
			long long int mul2=(aarr[i-1]-1)/aarr[i];
			mul2+=1;
			long long int sum2=(tarr[i]*mul2)+(aarr[i]*mul2);
			if(aarr[i]*mul1<aarr[i-1]){
				tarr[i]*=mul2;
				aarr[i]*=mul2;
			}else if(tarr[i]*mul2<tarr[i-1]){
				tarr[i]*=mul1;
				aarr[i]*=mul1;
			}else{
				if(sum1<sum2){
					tarr[i]*=mul1;
					aarr[i]*=mul1;
				}else{
					tarr[i]*=mul2;
					aarr[i]*=mul2;
				}
			}
		}
		//cout<<tarr[i]<<" "<<aarr[i]<<endl;
	}
	cout<<tarr[n-1]+aarr[n-1]<<endl;
}


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

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  ll play = 0;
  if ((B-A) % 2 == 0) {
    play = (B-A) / 2;
  }
  else {
    ll p1, p2;
    if (A-1 < N-B) {
      p1 = A;
      p2 = (B-A) / 2;
    }
    else {
      p1 = N + 1 - B;
      p2 = (B-A) / 2;
    }
    play = p1 + p2;
  }
  
  cout << play << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define mod (ll)(1e9+7)
#define nax (ll)(1e5)
#define INFL LLONG_MAX
#define INF INT_MAX
#define disp(a,n,arr) for(int i=a;i<(ll)n;i++) cout << arr[i] << " "; cout << "\n";
#define check cout << "Working\n";
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vpl vector<pl>
#define vpi vector<pi>
#define vb vector<bool>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;



int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	FIO;

	// Write your code here

	int t = 1;
	//cin >> t;
	while (t--) {
		string a, b;
		cin >> a >> b;
		ll ans = 0;
		for (int i = 0; i < (int)a.length(); i++) {
			if (a[i] != b[i]) ans++;
		}
		cout << ans << "\n";
	}


	return 0;
}

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

int main(){
  long long X;
  long long A;
  long long B;
  cin >> X;
  for(long long i=-1000; i<1000; i++){
    A = i;
    long long a = pow(i, 5);
    for(long long j=-1000; j<1000; j++){
      B = j;
      long long b = pow(j, 5);
      if(a-b==X){  
        goto OUT;
      }
    }
  }
  OUT:
  cout << A << " " << B << endl;
  return 0;
}

Measured memory_bytes: 4100
w = []
10.times do
    w.push(gets.to_i)
end

k = []
10.times do
    k.push(gets.to_i)
end
w.sort!.reverse!
k.sort!.reverse!
puts "#{w[0] + w[1] + w[2]} #{k[0] + k[1] + k[2]}"



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

int main() {
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
  string S;
  cin>>S;
  if(S[2]==S[3]&&S[4]==S[5])
    cout<<"Yes";
  else
    cout<<"No";
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	sc = initScanner(os.Stdin)
	s := scanString(sc)

	fmt.Println(resolve(s))
}

func resolve(s string) string {
	ss := strings.Split(s, "")
	sort.Strings(ss)

	az := strings.Split("abcdefghijklmnopqrstuvwxyz", "")

	for _, v := range az {
		if !contains(v, ss) {
			return v
		}
	}
	return "None"
}

func contains(c string, s []string) bool {
	for _, v := range s {
		if v == c {
			return true
		}
	}
	return false
}

// --------------- BASE DEFINITIONS ---------------

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	return sc
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanIntSlice(sc *bufio.Scanner, n int) []int {
	is := make([]int, n)
	for i := 0; i < n; i++ {
		is[i] = scanInt(sc)
	}

	return is
}

func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 3760
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main() {
    int a, p;

    scanf("%d %d\n", &a, &p);
    
    printf("%d\n", (int)((a * 3 + p) / 2));

    return 0;
}


Measured memory_bytes: 128
n = int(input())
xyh = []
for i in range(n):
    xyh.append(list(map(int, input().split())))
xyh.sort(key = lambda x: x[2], reverse = True)
for i in range(101):
    for j in range(101):
        h = xyh[0][2] + abs(xyh[0][0] - i) + abs(xyh[0][1] - j)
        flag = True
        for k in range(1, n):
            if xyh[k][2] == 0:
                if abs(xyh[k][0] - i) + abs(xyh[k][1] - j) < h:
                    flag = False
                    break
            else:
                temp = xyh[k][2] + abs(xyh[k][0] - i) + abs(xyh[k][1] - j)
                if h != temp:
                    flag = False
                    break
        if flag == True and h >= 1:
            print(i, j, h)
            break
    if flag == True:
        break

Measured memory_bytes: 9152
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>
#include <set>
//#include <bits/stdc++.h>
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
using namespace std;
#define ALL(X) X.begin(),X.end()
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=2147483647;
const ll LLMAX=9223372036854775807;

ll modadd(ll a,ll b,ll mod=MOD){
    return (a%mod+b%mod)%mod;
}

ll modsub(ll a,ll b,ll mod=MOD){
    a%=mod;
    b%=mod;
    if(a>=b) return a-b;
    else return mod-b+a;
}

ll modmul(ll a,ll b,ll mod=MOD){
    return ((a%mod)*(b%mod))%mod;
}

ll modpow(ll a, ll n,ll mod=MOD) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll moddiv(ll a,ll b,ll mod=MOD) {
    return modmul(a, modpow(b, mod-2));
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string S;
    cin>>S;
    ll N=S.size();
    
    vll T(N+1);
    T[N]=0;
    ll pow10=1;
    for(ll i=N-1;i>=0;i--){
        T[i]=modadd(modmul(S[i]-'0',pow10,2019),T[i+1],2019);
        pow10=modmul(10,pow10,2019);
        //printf("T[%d]=%d\n",i,T[i]);
    }
    
    vll count(2019);
    for(ll i=0;i<N;i++){
        count[T[i]]++;
    }
    
    ll ans=count[0];
    for(ll i=0;i<2019;i++){
        ans+=count[i]*(count[i]-1)/2;
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 5112
H,W=map(int,input().split())
s=[]
count=[[10**9 for _ in range(W)] for i in range(H)]
for i in range(H):
    S=input()
    s.append(S)
if s[0][0]=="#":
    count[0][0]=1
else:
    count[0][0]=0
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        val1=10**9
        val2=10**9
        if i==0:
            pass
        else:
            val1=count[i-1][j]
            if s[i][j]=="#" and s[i-1][j]==".":
                val1+=1
        if j==0:
            pass
        else:
            val2=count[i][j-1]
            if s[i][j]=="#" and s[i][j-1]==".":
                val2+=1
        count[i][j]=min(val1,val2)
print(count[-1][-1])

Measured memory_bytes: 42096
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int main(void) {
  double N, K;
  cin >> N >> K;
  int count = 0;
  for (int i = 1; i <= N; i+=2) {
    count++;
  }
  cout << (count >= K ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
N, M = map(int,input().split())
KS = [list(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
for i in range(2**N):
  switch = []
  for j in range(N):
    switch.append((i >> j) & 1)
  lights = 0
  for u in range(M):
    connect = 0
    for v in range(KS[u][0]):
      if switch[KS[u][v+1]-1] == True:
        connect += 1
    if connect % 2 == P[u]:
      lights += 1
  if lights == M:
    ans += 1
  #print(switch, connect, lights)
    
print(ans)

    



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

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

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

void solve(std::string S){
    cout << S[0] << S[1] << S[2] << endl;
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3628
a = []
b = []

n, m = gets.split.map(&:to_i)
n.times do
  a.push(gets.split.map(&:to_i))
end

m.times do
  b.push(gets.to_i)
end

a.each do |row|
  puts row.zip(b).inject(0) { |sum, ab| sum + ab[0] * ab[1] }
end

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

typedef long long ll;

int main() {
  int n; cin >> n;
  int m; cin >> m;
  vector<int> path[m];
  rep(i, 0, m){
    int tmp1, tmp2;
    cin >> tmp1 >> tmp2;
    path[i].push_back(tmp1);
    path[i].push_back(tmp2);
  }

  vector<int> perm(n);
  rep(i, 0, n) perm[i] = i + 1;

  int ans = 0;
  do{

    if(perm[0] != 1) break;

    int goalcount = 0;
    rep(i, 0, n - 1){
      int from = perm[i];
      int to   = perm[i + 1];
      rep(j, 0, m){
        if((from == path[j][0] && to == path[j][1]) || (from == path[j][1] && to == path[j][0])){
          goalcount++;
          break;
        }
      }
    }
    if(goalcount == n -1) ans++;

  }while(next_permutation(perm.begin(), perm.end()));

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

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
	int x, y,arr[1000],sum=0;
	cin >> x >> y;
	for (int i = 0; i < x; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + x);
	for (int i = 0; i < y; i++) {
		sum = sum + arr[i];
	}
	cout << sum;
}

Measured memory_bytes: 3192
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = input()
N = [int(i) for i in N]
# 数え上げ問題なので多分dp
dp = [[0, 0] for i in range(len(N))]

# ぴったし払うための最小値
dp[0][0] = min(N[0], 11 - N[0])
# お釣りをもらう用の紙幣を１枚余分にとっておく場合の最小値
dp[0][1] = min(N[0] + 1, 10 - N[0])

for i in range(1, len(N)):
    # dp[i - 1][1] + 10 - N[i]:とっておいた紙幣を使用し、お釣りを10 - N[i]枚もらう
    dp[i][0] = min(dp[i - 1][0] + N[i], dp[i - 1][1] + 10 - N[i])
    # dp[i - 1][1] + 9 - N[i]:お釣りを10 - N[i]枚もらい、そのうち１枚は次のお釣りを
    # もらう試行のためにとっておく
    dp[i][1] = min(dp[i - 1][0] + N[i] + 1, dp[i - 1][1] + 9 - N[i])
print(dp[len(N) - 1][0])

Measured memory_bytes: 231216
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

int main () {
    int n, k; cin >> n >> k;
    V<ll> p(n), c(n);
    rep(i, n) cin >> p[i];
    rep(i, n) p[i]--;
    rep(i, n) cin >> c[i];
    ll ans = -1e18;
    rep(s, n) {
        ll loop_score = 0, loop_num = 0, now = s;
        while (true) {
            now = p[now];
            loop_score += c[now];
            loop_num++;
            if (now == s) break;
        }
        if (loop_score <= 0) {
            now = s;
            ll score = 0, num = 0;
            while (true) {
                now = p[now];
                score += c[now];
                num++;
                chmax(ans, score);
                if (num == k) break;
                if (num == loop_num) break;
            }
        }
        else {
            ll loop = k / loop_num - 1;
            ll score = loop_score * loop;
            ll num = loop_num * loop;
            now = s;
            while (true) {
                now = p[now];
                score += c[now];
                num++;
                chmax(ans, score);
                if (num == k) break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3704
N, M = list(map(int,input().split()))
H = list(map(int,input().split()))
A, B = [], []
for i in range(M):
  temp = list(map(int,input().split()))
  A.append(temp[0])
  B.append(temp[1])
roadlist = []
for i in range(N):
  roadlist.append([])
for i in range(M):
  roadlist[A[i]-1].append(B[i]-1)
  roadlist[B[i]-1].append(A[i]-1)
ans = 0
for i in range(N):
  if(len(roadlist[i])==0):
    ans += 1
  else:
    flag = 0
    for j in range(len(roadlist[i])):
      if(H[i] <= H[roadlist[i][j]]):
        flag = 1
        break
    if(flag==0):
      ans += 1
print(ans)

Measured memory_bytes: 37984