akhauriyash/Code-Regression huggingface dataset:
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)


Measured memory_bytes: 93996
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair

const int MAXN = 100100;

int n, a, b, c, d;

string s;

vector <int> pref[2][2];

vector <int> calc(int x) {
	vector <int> ret;
	ret.push_back(s[0] == x);
	FOR(i, 1, n) ret.push_back(ret.back() + (s[i] == x));
	return ret;
}

int get(int x, int a, int b, int t) {
	int k = 0;
	if (a) k = pref[x][t][a - 1];
	return pref[x][t][b] - k;
}

int main() {
	REP(i, 2) {
		cin >> s;
		n = (int)s.size();
		pref[i][0] = calc('A');
		pref[i][1] = calc('B');
	}

	int q;
	scanf("%d",&q);
	REP(i, q) {
		scanf("%d %d %d %d",&a,&b,&c,&d);
		a--; b--; c--; d--;
		int x = get(0, a, b, 0) + get(0, a, b, 1) * 2;
		int y = get(1, c, d, 0) + get(1, c, d, 1) * 2;
		x %= 3;
		y %= 3;
		if (x == y) puts("YES");
		else puts("NO");
	}

	return 0;
}

Measured memory_bytes: 2488
#include <cstdio>
int a[10], e[8], used[11];
bool ok() {
	for (int i = 0; i < 3; i++) e[i] = (a[i] + a[i + 3] + a[i + 6]) % a[9];
	for (int i = 0; i < 3; i++) e[i + 3] = (a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]) % a[9];
	e[6] = (a[2] + a[4] + a[6]) % a[9];
	e[7] = (a[0] + a[4] + a[8]) % a[9];
	for (int i = 0; i < 7; i++) if (e[i] != e[i + 1]) return false;
	return true;
}
int solve(int depth) {
	if (depth == 10) return ok() ? 1 : 0;
	if (a[depth]) return solve(depth + 1);
	int ret = 0;
	for (int i = 1; i <= 10; i++) {
		if (!used[i]) {
			used[i] = 1; a[depth] = i;
			ret += solve(depth + 1);
			used[i] = a[depth] = 0;
		}
	}
	return ret;
}
int main() {
	while (true) {
		for (int i = 1; i < 11; i++) used[i] = 0;
		for (int i = 0; i < 10; i++) {
			scanf("%d", a + i);
			if (a[i]) used[a[i]] = 1;
		}
		if (a[0] == -1) break;
		printf("%d\n", solve(0));
	}
}

Measured memory_bytes: 2604
#include<stdio.h>
#include<math.h>
int main(){
	int a,b,c;
	int count;
	scanf("%d %d %d",&a,&b,&c);
	count=0;
	for(int i=a;i<=b;i++){
		if(c%i==0){
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}


Measured memory_bytes: 2764
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD1 1000000007

int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  ll sum = 0;
  rep(i, N) {
    cin >> A[i];
    sum += A[i];
  }

  vector<ll> S(N, 0);
  for (int i = 1 ; i < N ; i += 2) {
    S[0] += A[i] * 2;
  }
  for (int i = 2 ; i < N + 1 ; i += 2) {
    S[1] += A[i % N] * 2;
  }

  for (int i = 2; i < N; i++) {
    S[i] = S[i - 2] - A[i - 1] * 2 + A[i - 2] * 2;
  }

  rep(i, N) cout << sum - S[i] << " ";
  cout << endl;


}


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

#define PI 4*atan(1);

int main(){
  int h[3][2], m[3][2], s[3][2];
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 2; j++){
      cin >> h[i][j] >> m[i][j] >> s[i][j];
    }
  }
  for(int i = 0; i < 3; i++){
    if(s[i][1] - s[i][0] >= 0){
      s[i][1] -= s[i][0];
      if(m[i][1] - m[i][0] >= 0){
        m[i][1] -= m[i][0];
        h[i][1] -= h[i][0];
      }else{
        h[i][1]--;
        h[i][1] -= h[i][0];
        m[i][1] += (60 - m[i][0]);
      }
    }else{
      if(m[i][1] >= 1){
        m[i][1]--;
        s[i][1] += (60 - s[i][0]);
        if(m[i][1] - m[i][0] >= 0){
          m[i][1] -= m[i][0];
          h[i][1] -= h[i][0];
        }else{
          m[i][1] += (60 - m[i][0]);
          h[i][1]--;
          h[i][1] -= h[i][0];
        }
      }else{
        h[i][1]--;
        h[i][1] -= h[i][0];
        m[i][1] += (59 - m[i][0]);
        s[i][1] += (60 - s[i][0]);
      }
    }
  }
  for(int i = 0; i < 3; i++){
    cout << h[i][1] << " " << m[i][1] << " " << s[i][1] << endl;
  }
}

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

using namespace std;

#define ll long long

int main()
{
	ll L, R;
	cin >> L >> R;
	ll ans = 2019;
	for (int i = L; i < R && i - L <= 2019; i++) {
		for (int j = i + 1; j <= R && j - L <= 2019; j++) {
			ans = min(ans, (ll) i * j % 2019);
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
#define vi vector<long long>
#define pi pair<long long, long long>
#define mp make_pair
#define endl '\n'
#define _ << ' '
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
#define clog2(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1e9;
const ll N = (1<<5);
const double PI = 3.1415926535897;

ll f[1000001];
ll finv[1000001];
ll inv[1000001];

ll ncr(ll n, ll r){
    return f[n] * (finv[r] * finv[n-r] % mod) % mod;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("B.txt", "r", stdin);
    #endif
    int x, y;
    cin >> x >> y;
    f[0] = f[1] = finv[0] = finv[1] = inv[1] = 1;
    for(int i=2; i<=1000000; i++){
        f[i] = (f[i-1] * i) % mod;
        inv[i] = mod - inv[mod%i] * (mod/i) % mod;
        finv[i] = inv[i] * finv[i-1] % mod;
    }
    for(int i=0; i<=x/2; i++){
        int j = x - i * 2;
        if(j * 2 + i == y){
            cout << ncr(i + j, i);
            return 0;
        }
    }
    cout << 0;
}





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

int main() {
	int l,r,m;cin>>l>>r;
	if(r/2019-l/2019>=2019)
	{
	    cout<<0<<endl;
	    return 0;
	}
	l%=2019;
	r%=2019;
	int mi=min(l,r),ma=l+r-mi,mini=2019;
	//cout<<mi<<" "<<ma;
	for(int i=mi;i<ma;i++)
	for(int j=i+1;j<=ma;j++)
	{
	    m=(i%2019*(j%2019))%2019;
	    mini=min(mini,m);
	}
	cout<<mini;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int ab=a*b,cd=c*d;
  if (ab == cd){
    cout << ab;
  }else if(ab > cd){
    cout << ab;
  }else{
    cout << cd;
  }
}


Measured memory_bytes: 256
from itertools import permutations
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
l=[]
for i in range(1,n+1):
  l.append(i)
def chk(a,b):
  for i in range(len(a)):
    if a[i]!=b[i]:
      return False
  return True
p_list=list(permutations(l))
#a=0
#b=0
for i in range(len(p_list)):
  if chk(p_list[i],p):
    a=i
  if chk(p_list[i],q):
    b=i
print(abs(a-b))
    


Measured memory_bytes: 8052
MOD = 1000000007
N, K = map(int, input().split())
A = list(map(int, input().split()))

cnt_in = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt_in += 1
ans = (cnt_in * K) % MOD

cnt_next = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            cnt_next += 1

ans += (cnt_next * (K*(K-1))//2) % MOD
ans %= MOD

print(int(ans))


Measured memory_bytes: 3188
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = getLine >>= putStrLn . which "Yes" "No" . solve "CF"

solve [] _ = True
solve _ [] = False
solve s@(a:as) (b:bs)
	| a == b = solve as bs
	| otherwise = solve s bs

Measured memory_bytes: 508
def main():
    D, N = map(int, input().split())

    ans = f(D, N)
    print(ans)


def WA(D, N):
    D, N = map(int, input().split())

    if D == 0:
        ans = N
        if N == 100:
            ans = 101
    elif D == 1:
        xs = range(100, 100 * 101, 100)
        ans = xs[N-1]
    else:
        # D=2
        xs = range(100**2, (100 ** 2) * 101, 100**2)
        ans = xs[N-1]

    print(ans)


def f(D, N):
    xs = range(100**D, (100 ** D) * 102, 100**D)
    ans = xs[N-1]
    a = ans // (100**D)
    if a >= 100 and a % 100 == 0:
        ans = xs[N]

    return ans


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
/**
 * Stable Sort
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=ja
 */

#include<bits/stdc++.h>
using namespace std;

void trace(vector <string>A) {
  // 現在の並び替え状態を出力する
  int size = A.size();
  for (int i = 0; i < size; i++) {
    cout << A.at(i);
    if (i < size - 1) {
      cout << ' ';
    }
  }
  
  cout << endl;
}

/**
 * バブルソートを実行する
 */
vector<string> bubble(vector<string>A, int N) {
  // int count = 0;
  bool flag = true;
  while (flag) {
    flag = false;
    for (int j = N - 1; j > 0; j--) {
      // より小さい要素を先頭に移動していく
      if (A.at(j)[1] < A.at(j - 1)[1]) {
        swap(A.at(j), A.at(j - 1));
        // count++;
        flag = true;
        // trace(A);
      }
    }
  }
  return A;
}

/**
 * 選択ソートを実行する
 */
vector<string> selection(vector<string>A, int N) {
  // int count = 0;
  for (int i = 0; i < N; i++) {
    int minj = i;
    // 最小要素の位置を探索する
    for (int j = i; j < N; j++) {
      if (A.at(j)[1] < A.at(minj)[1]) {
        minj = j;
      }
    }

    // 最小要素を未ソート配列の先頭に移動する
    if (i != minj) {
      swap(A.at(i), A.at(minj));
      // count++;
    }
  }

  return A;
}

/**
 * ソートが安定的かどうかを判定する
 */
string isStable(vector<string>A, vector<string>S, int N) {
  // int count = 0;
  for (int i = 0; i < N - 1; i++) {
    for (int j = 0; j < S.size(); j++) {
      // 一致する要素が登場したら、一致した要素は安定的であるとして削除する
      if (S.at(j) == A.at(i)) {
        S.erase(S.begin() + j, S.begin() + j + 1);
        break;
      }
      // 一致する要素が登場する前に、数字が同じ他のカードが登場してしまった
      if (A.at(i)[1] == S.at(j)[1]) {
        return "Not stable";
      }
    }
  }

  return "Stable";
}

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

  vector <string>A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  // trace(A);

  vector <string>B = bubble(A, N);
  vector <string>S = selection(A, N);

  // バブルソートの結果を出力する
  trace(B);
  cout << isStable(A, B, N) << endl;

  // 選択ソートの結果を出力する
  trace(S);
  cout << isStable(A, S, N) << endl;
  // cout << count << endl;
}



Measured memory_bytes: 3176
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <queue>

using namespace std;

void solve() {
    int a, b;
    cin >> a >> b;
    long i = 0;
    while(true) {
        if((int)((double)i * 0.08) == a && (int)((double)i * 0.1) == b) {
            cout << i;
            return;
        } else if ((int)((double)i * 0.08) > a || (int)((double)i * 0.1) > b)
            break;
        i++;
    }
    cout << -1;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main(){
    int a[3]; rep(i,3) cin>>a[i];
    sort(a,a+3);
    rep(i,3) cout<<a[i]<<(i==2?"\n":" ");
    return 0;
}



Measured memory_bytes: 3116
n=int(input())
a=sorted(list(map(int,input().split())))
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
ans=0
for i in a:
    if d[i]==1 and e[i]==1:
        ans+=1
    if e[i]==1:
        for j in range(i,10**6+1,i):
            e[j]=0
print(ans)

Measured memory_bytes: 44812
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include <vector>
#include <map>
#include<cstdlib>


using namespace std;

void Solution()
{
    double xa1, ya1;
    double xa2, ya2;
    double xb1, yb1;
    double xb2, yb2;
    
    while(cin>>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2)
    {
        if(xa1 <= xb2 &&  //based the picture from question
           xb1 <= xa2 &&
           ya1 <= yb2 &&
           yb1 <= ya2)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
}

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

Measured memory_bytes: 1224
#include <stdio.h>
#include <string>
#include <algorithm>
#include <map>
#include <iostream>
#include<math.h>
using namespace std;

int main() {
	char c;
	cin >> c;
	if (c == 'A')cout << 'T' << endl;
	if (c == 'T')cout << 'A' << endl;
	if (c == 'C')cout << 'G' << endl;
	if (c == 'G')cout << 'C' << endl;


}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }

    let mut set = HashSet::new();
    let mut i = 0;
    let mut c = 0;
    set.insert(i);
    while i != 1 {
        i = a[i];
        c += 1;
        if !set.insert(i) {
            println!("-1");
            return;
        }
    }
    println!("{}", c);
}


Measured memory_bytes: 5196
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int x;
    cin>>x;
    int now=0;
    for(int i=1;i<=x;i++)
    {
        now+=i;
        if(now>=x)
        {
            cout<<i;
            break;
        }


    }
}

Measured memory_bytes: 256
def get_digit_sum(integer):
    digit_sum = 0
    while integer > 0:
        digit_sum += integer % 10
        integer //= 10
    return digit_sum


def main():
    number = int(input())
    if not number % get_digit_sum(number):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
const main = (input) => {
  const inputs = input.trim().split('\n');
  const N = Number.parseInt(inputs[0].split(" ")[0]);
  var M = Number.parseInt(inputs[0].split(" ")[1]);

  var shops = [];
  for(var i=1;i<=N;i++){
    var obj = {
      pri: Number(inputs[i].split(" ")[0]),
      num: Number(inputs[i].split(" ")[1]),
    };
    shops.push(obj);
  }
  shops = shops.sort(function(a,b){return a.pri-b.pri});
  var ans = 0;
  for(var i=0;M>0;i++){
    var num = Math.min(M, shops[i].num);
    ans += num*shops[i].pri;
    M -= num;
  }
  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));


Measured memory_bytes: 50972
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N = int(readline())
    m = map(int,read().split())
    AB = list(zip(m,m))

    A = [ab[0] for ab in AB]
    B = [ab[1] for ab in AB]

    A.sort()
    B.sort()

    # print(AB)
    # print(A)
    # print(B)

    if N % 2 == 1:
        Amed = A[N // 2]
        Bmed = B[N // 2]

        print(Bmed - Amed + 1)
    else:
        Amed = A[N // 2] + A[N // 2 - 1]
        Bmed = B[N // 2] + B[N // 2 - 1]

        print(Bmed - Amed + 1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 58880
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,x,ans,d; ans=1; d=0;
  cin>>n>>x; vector<int> C(n);
  rep(i,n) cin>>C.at(i);
  rep(j,n) {d=d+C.at(j); if(d<=x){ans++;};}
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from itertools import combinations

L, R = map(int, input().split())
MOD = 2019
if R - L >= MOD: print(0)
else:
    L, R = L % MOD, R % MOD
    if L < R: cands = list(range(L, R+1))
    else: cands = list(set(list(range(R+1)) + list(range(L, MOD))))
    ans = MOD
    for i, j in combinations(cands, 2):
        ans = min(ans, (i*j) % MOD)
    print(ans)

Measured memory_bytes: 3064
# -*- coding:utf-8 -*-

if __name__ == '__main__':
    S = input()
    T = input()
    S_ = S
    for i in range(len(S)):
        if S_ == T:
            print("Yes")
            exit()
        tmp = S_[0]
        S_ = S_[1:] + tmp
    print("No")


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

#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

   int a,b;
   cin>>a>>b;
   if((a*b)%2)cout<<"Odd"<<endl;
   else cout<<"Even"<<endl;
   return 0;
}


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

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}


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

  while(!IsPrime(x)){
    x++;
  }
  cout << x << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  int count=0,i,n;
  cin>>s>>t;
  n=s.length();
  for(i=0;i<n;i++){
    if(s[i]!=t[i])
      count++;
  }
  cout<<count;
}



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

int main(){
  vector<int> N(3);
  cin >> N.at(0) >> N.at(1) >> N.at(2);
  sort(N.begin(), N.end());
  N.at(0)-= N.at(2);
  N.at(1)-= N.at(2);
  N.at(2)=0;
  int ans=0;
  ans-=N.at(0)/2;
  N.at(0)-=N.at(0)/2*2;
  ans-=N.at(1)/2;
  N.at(1)-=N.at(1)/2*2;
  if(N.at(0)+N.at(1)+N.at(2)==0) ans=ans;
  if(N.at(0)+N.at(1)+N.at(2)==-1) ans+=2;
  if(N.at(0)+N.at(1)+N.at(2)==-2) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
cnt = [0] * 4
for _ in range(n):
    j = input()
    if j == "AC":
        cnt[0] += 1
    elif j == "WA":
        cnt[1] += 1
    elif j == "TLE":
        cnt[2] += 1
    elif j == "RE":
        cnt[3] += 1

print("AC x " + str(cnt[0]))
print("WA x " + str(cnt[1]))
print("TLE x " + str(cnt[2]))
print("RE x " + str(cnt[3]))

Measured memory_bytes: 9212
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
#define for1(i,a,n)  for(int i=0;i<n;i++)
#define rep(i, c) for(int i = 0; i < (int)c; i++)
#define set(x) cout<<fixed<<setprecision(x);
using namespace std;
//**********************************************DO IT NO****************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
signed main()
{   
    fastio();
    int t=1;
    //cin>>t;
    while(t--)
    {  
      string s1,s2,s3;
      cin>>s1>>s2>>s3;
      cout<<s1[0]<<s2[0]<<s3[0];
    }
}
// 🍪 🍪 🍪


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define tp tuple<int,int,int>
#define mtp make_tuple
using namespace std;

const int N=2e5+5;
int n,a[N],res[N],m,e[N],f[N];
vector<int>adj[N];

void dfs(int u,int p=-1)
{
    int prem=m;
    f[u]=lower_bound(e+1,e+m+1,a[u])-e;
    if(f[u]>m) m++;
    int pref=e[f[u]];
    e[f[u]]=a[u];
    res[u]=m;
    for(auto&v:adj[u])
    {
        if(v==p) continue;
        dfs(v,u);
    }
    m=prem;
    e[f[u]]=pref;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=n;i++) cout<<res[i]<<'\n';
}


Measured memory_bytes: 31264
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		Queue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			q.add(sc.nextInt());
		}
		for (int i = 0; i < m; i++) {
			int nebiki = q.poll() / 2;
			q.add(nebiki);
		}
		System.out.println(q.stream().mapToLong(Long::valueOf).sum());
		sc.close();
	}
}


Measured memory_bytes: 60748
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

int a[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    n+=2;
    int sol = 0;
    for (int i = 1; i < n; ++i)
        sol += abs(a[i] - a[i - 1]);


    for (int i = 1; i < n - 1; ++i)
    {
        int zol = sol;
        if (i) zol -= abs(a[i] - a[i - 1]);
        if (i != n - 1) zol -= abs(a[i + 1] - a[i]);
        if (i && i != n - 1) zol += abs(a[i + 1] - a[i - 1]);
        cout << zol << '\n';
    }
}


Measured memory_bytes: 1664
n = int(input())
s = input()
ans = 0
for i in range(n):
    x, y = s[:i], s[i:]
    cnt = 0
    for j in range(26):
        if x.count(chr(ord('a') + j)) and y.count(chr(ord('a') + j)):
            cnt += 1
    ans = max(ans, cnt)
print(ans)


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

int main() {  
  int x1,y1,x2,y2,x3,y3,x4,y4;
  cin >> x1 >> y1 >> x2 >> y2;
  x3 = x2 + y1 - y2;
  y3 = y2 + x2 - x1;

  x4 = x3 - x2 + x1;
  y4 = y3 + y1 - y2;

  cout << x3 <<" "<< y3 <<" "<< x4 <<" "<< y4 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define ind(a) scanf("%lf", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a));
//def   puts(a) printf("%s\n", a) 文字はこっち
//your code here!

#define MAX_HEAP 100005
ll a[MAX_HEAP];
ll g_idx = -1; //ヒープの末尾の添字 最初は空っぽだから-1

ll PQ_pop(void){//最小値を取り出す
    ll i, j, ret = a[0];  //返り値
    if(g_idx<0) exit(1);  //ヒープが空っぽかどうか確認
    a[0] = a[g_idx--];     //末尾の要素を先頭にもってく
    //a[0]=a[g_idx];  g_idx=g_idx - 1; 後からマイナス
    //根に置かれている要素を適切なとこまで下におろす。
    i = 0;              //根から始める
    while(i*2+1<=g_idx){//子が存在するという条件
        j = i*2+1;
        if(j+1<=g_idx && a[j]<a[j+1]){
            j++;        //2つ(or1つ)の子供の内、小さい方の添字をjとしている
        }
        if(a[i] >= a[j]){
            break;      //子供の方が大きければ、終了
        }
        //終了していないと言うことは、親子関係が逆なのでswap
        swap(a[i],a[j]);
        i = j;          //子供が親になって次のループへ
    }
    return ret;
}

void PQ_push(ll elem){//ヒープに要素elemを追加する
    if(g_idx >= MAX_HEAP-1){//ヒープに空きがあるか確認
        exit(1);
    }
    a[++g_idx] = elem;      //末尾にelemを入れる
    //g_idx+=1;  a[g_idx]=elem  先にプラス
    //末尾に置かれている要素を適切なとこまで上にあげる
    ll x = g_idx;                 //グローバル変数をいじる訳にはいかないので代入
    while(x>0 && a[(x-1)/2]<a[x]){//親がいる&&親が子供より大きい なら継続
        swap(a[(x-1)/2], a[x]);   //親と子供をswap
        x = (x-1)/2;              //親を子供にしてループへ
    }
}


int main(void){
    ll N, M, A, ans=0;
    in(N); in(M);
    rep(i,N){
        in(A);
        PQ_push(A);
    }
    rep(_,M){
        A = PQ_pop();
        PQ_push(A/2);
    }
    rep(i,N) ans += a[i];
    put(ans);
    return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define N 100009
using namespace std;

int n,a[N],lg2[N];
struct node{ int x,y; }f[17][N],b[N];
struct matrix{ int p[2][2]; };
bool operator <(node u,node v){ return u.x<v.x; }
int getmin(int x,int y){
	int k=lg2[y-x+1];
	//cout<<"	"<<x<<' '<<y<<endl;
	//cout<<k<<' '<<x<<' '<<y<<' '<<f[k][x].y<<' '<<f[k][y-(1<<k)+1].y<<endl;
	return min(f[k][x],f[k][y-(1<<k)+1]).y;
}
void calc(int k){
	int flag=0,i=a[k];
	for (; i>1; i>>=1){
		b[k].x++;
		if (i&1) flag=1;
	}
	b[k].y=flag;
}
matrix solve(int l,int r,int dep){
	//cout<<l<<' '<<r<<endl;
	if (l>r){
		matrix x;
		x.p[0][0]=0; x.p[0][1]=x.p[1][0]=x.p[1][1]=1;
		return x;
	}
	int mid=getmin(l,r),i,j,k,x=b[mid].x,y=b[mid].y;
	matrix u=solve(l,mid-1,x),v=solve(mid+1,r,x),z;
	for (i=0; i<2; i++)
		for (j=0; j<2; j++){
			z.p[i][j]=1000000000;
			for (k=0; k<=y; k++) z.p[i][j]=min(z.p[i][j],u.p[i][k]+v.p[y-k][j]);
		}
	//cout<<l<<' '<<r<<' '<<mid<<' '<<x<<' '<<dep<<endl;
	for (i=0; i<2; i++)
		for (j=0; j<2; j++) z.p[i][j]+=x-dep;
	if (dep<x)
		for (i=0; i<2; i++)
			for (j=0; j<2; j++) z.p[i][j]=z.p[0][0];
	//for (i=0; i<2; i++)
		//for (j=0; j<2; j++) cout<<z.p[i][j]<<' ';puts("");
	return z;
}
int main(){
	scanf("%d",&n);
	int i,j;
	for (i=2; i<=n; i++) lg2[i]=lg2[i>>1]+1;
	for (i=1; i<=n; i++){
		scanf("%d",&a[i]); calc(i);
		//cout<<i<<' '<<b[i].x<<' '<<b[i].y<<endl;
	}
	for (i=1; i<=n; i++) f[0][i]=(node){a[i],i};
	for (i=1; i<=16; i++)
		for (j=1; j<=n; j++){
			f[i][j]=f[i-1][j];
			if (j+(1<<i-1)<=n) f[i][j]=min(f[i][j],f[i-1][j+(1<<i-1)]);
		}
	printf("%d\n",solve(1,n,0).p[0][0]);
	return 0;
}


Measured memory_bytes: 25984
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define INF 100000000
using namespace std;
const int mod = 1000000007;

int main() {

  string a,b,ans;
  cin>>a>>b;
  vector<vector<int>> dp(3200,vector<int>(3200,0));
  for(int i=0; i<a.size(); i++){
    for(int j=0; j<b.size(); j++){
      if(a[i]==b[j])dp[i+1][j+1]=dp[i][j]+1;
      else dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
    }
  }   //cout << dp[a.size()][b.size()] << endl;
//    for(int i=0; i<a.size(); i++){
  //  for(int j=0; j<b.size(); j++){cout<<dp[i+1][j+1];if(j==b.size()-1)cout<<endl;}}
  int i=a.size(), j=b.size();
   while(i > 0 && j > 0){
        if(dp[i][j] == dp[i-1][j-1]+1&&a[i-1]==b[j-1]){
            i--;
            j--;
            ans = a[i] + ans;
        }else if(dp[i][j] == dp[i-1][j]){
            i--;
        }else{
            j--;
        } 
    }
    cout << ans << endl;
  }




Measured memory_bytes: 40448
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef int64_t ll ;

const ll MOD = 1000000007;

ll K,N;
vector<ll> A(500,0);

int main() {
  ll at = 0;
  cin >> N >> K;
  REP(i,N) {
    cin >> A[i];
    at += A[i];
  }

  vector<ll> d;
  vector<ll> am(N,0);
  vector<ll> amn(N,0);

  // 合計の約数のリストを求める
  for (ll i=1;i*i<=at; ++i ) {
    if ( at%i==0 ) {
      d.push_back(i);
      if ( at / i != i ) {
        d.push_back(at/i);
      }
    }
  }

  ll ans = 1;
  for ( auto di: d ) {
    // 約数候補diに対して、各A要素での余りを求める
    ll num = 0;
    REP(i,N) {
      am[i] = A[i] % di;
    }
#if 0
    cout << di << " : ";
    REP(i,N) cout << am[i] << " ";
    cout << endl;
#endif
    
    sort( am.begin(), am.end() );
    
    amn[N-1] = di - am[N-1];
    for( int i=N-1; i>0; --i ) {
      // diにするのに必要な数の累積和
      amn[i-1] = amn[i] + (di - am[i-1]);
    }
    
    REP(i,N-1) {
      // 0にするのに必要な数の累積和
      am[i+1] += am[i];
    }
#if 0
    cout << "  "; REP(i,N) cout << am[i] << " "; cout << endl;
    cout << "  "; REP(i,N) cout << amn[i] << " "; cout << endl;
#endif
    REP(i,N-1) {
      if ( am[i] == amn[i+1] ) {
        // 2つの累積和が左右で同じになるポイントを探す
        num = di;
        if (am[i] > K) {
          num = 0;
        }
        break;
      }
    }
    ans = max(ans,num);
  }

  cout << ans << endl;
  

}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

struct Info{
	Info(){
		rank = cost = point = 0;
	}
	int cost,point,rank;
};

int main(){

	int num_sport,num_member,cost_limit,maximum,max_index;

	Info info[1000];

	scanf("%d %d",&num_sport,&num_member);

	for(int i = 0; i < num_sport; i++){
		scanf("%d",&info[i].cost);
		info[i].rank = i+1;
	}

	for(int i = 1; i <= num_sport-1; i++){
		for(int k = num_sport-1; k >= i; k--){
			if(info[k].cost < info[k-1].cost)swap(info[k],info[k-1]);
		}
	}

	for(int i = 0; i < num_member; i++){
		scanf("%d",&cost_limit);
		maximum = 1000000000;
		for(int k = 0; k < num_sport; k++){
			if(info[k].cost > cost_limit)break;
			if(info[k].rank < maximum){
				maximum = info[k].rank;
				max_index = k;
			}
		}
		info[max_index].point++;
	}

	maximum = -1;

	for(int i = 0; i < num_sport; i++){
		if(info[i].point > maximum){
			maximum = info[i].point;
			max_index = i;
		}
	}

	printf("%d\n",info[max_index].rank);
	return 0;
}

Measured memory_bytes: 2764
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

vector<int>fri[101010];
vector<int>blo[101010];
int visited[101010],visited2[101010],par[101010],sz[101010];
int cnt;

void dfs(int now, int parent) {
	par[now] = parent;
	visited[now] = 1;
	cnt++;
	fore(x, fri[now]) {
		if (!visited[x]) {
			dfs(x, parent);
		}
	}
}
void dfs2(int now) {
	visited2[now] = 1;
	sz[now] = cnt;
	fore(x, fri[now]) {
		if (!visited2[x]) {
			dfs2(x);
		}
	}
}

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

	int N, M, K;
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		fri[a].pb(b);
		fri[b].pb(a);
	}
	for (int i = 0; i < K;i++) {
		int c, d;
		cin >> c >> d;
		c--, d--;
		blo[c].pb(d);
		blo[d].pb(c);
	}

	for (int i = 0; i < N; i++) {
		if (visited[i])continue;
		cnt = 0;
		dfs(i,i);
		dfs2(i);
	}

	for (int i = 0; i < N; i++) {
		int block = 0;
		fore(x, blo[i])if (par[i] == par[x])block++;
		int ans = sz[i] - fri[i].size() - block - 1;
		cout << ans << " ";
	}
	puts("");
	return 0;
}


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

ll gcd(ll x,ll y){
  if(x%y==0) return y;
  else gcd(y,x%y);
}

int main() {
  ll n, m;
  string s, t;
  cin >> n >> m >> s >> t;
  ll G = gcd(n,m);
  ll L = (n*m)/G;
  
  bool can;
  if(s[0]!=t[0])can = false;
  else if(G==1) can = true;
  else{
    ll N = n/G;
    ll M = m/G;
    bool ok = true;
    for(ll i=1;i<G;i++){
      if(s[N*i]!=t[M*i]) ok = false;
    }    
    if(ok) can = true;
    else can = false;
  }
  ll ans = can ? L : -1;
  cout << ans << endl;
  return 0; 
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

// auto mod int
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
      if ((x += a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator-=(const mint a) {
      if ((x += mod-a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
      if (!t) return 1;
      mint a = pow(t>>1);
      a *= a;
      if (t&1) a *= *this;
      return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}

    // bool operator==(const mint a) { return x == a.x; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

// combination mod prime
// mintと併用
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    if(n < k) return 0;
    return fact[n]*ifact[n-k];
  }
} comb(1000100);

int main() {
    int sum; cin >> sum;
    mint ans = 0;
    for(int i = 1; ; ++i) {
        int now = 3*i;
        if(now > sum) break;
        int rest = sum-now;
        ans += comb(rest+(i-1), rest);
    }
    cout << ans << endl;
}

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

auto keta(ll n) {
    ll res;
    for(ll i = 0; i < 100; i++) {
        n = n / 10;

        if(n == 0) {
            res = i + 1;
            break;
        }
    }
    return res;
}

int main() {
    int n, sum = 0;
    cin >> n;
    vector<int> a(n), b(n), c(n-1);
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }

    rep(i, n) cin >> b[i];
    rep(i, n - 1) cin >> c[i];
    rep(i, n - 1) {
        sum += b[a[i]];
        if(a[i + 1] - a[i] == 1) sum += c[a[i]];
    }
    sum += b[a[n - 1]];
    cout << sum << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a, b, c[] = new int[5], cnt = 0;
    
    a = Integer.parseInt(sc.next());
    b = Integer.parseInt(sc.next());
    
    for (int i = a; i <= b; i++) {
        int temp = i;
        for (int j = 4; j >= 0; j--) {
            c[j] = temp / (int)Math.pow(10, j);
            temp = temp % (int)Math.pow(10, j);
        }
        if (c[0] == c[4] && c[1] == c[3])
            cnt++;
    }
    
    System.out.println(cnt);
  }
}

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

typedef vector<int> vec;
typedef vector<vec> mat;

int n;
long long k;

const int MOD = 1e9 + 7;

inline void add(int &a, int b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}
mat mul(mat A, mat B) {
	mat C(n, vec(n));
	
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < n; k++) {
			for (int j = 0; j < n; j++) {
				add(C[i][j], (int)(1ll * A[i][k] * B[k][j] % MOD));
			}
		}
	}
	
	return C;
}
mat mod_pow(mat A, long long k) {
	mat B(n, vec(n));
	
	for (int i = 0; i < n; i++) {
		B[i][i] = 1;
	}
	
	while (k > 0) {
		if (k & 1) {
			B = mul(B, A);
		}
		
		A = mul(A, A);
		k >>= 1;
	}
	
	return B;
}
int main() {
	cin >> n >> k;
	
	mat A(n, vec(n));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> A[i][j];
		}
	}
	
	A = mod_pow(A, k);
	
	int res = 0;
	
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		add(res, A[i][j]);
	}
	
	cout << res;
}


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

struct UnionFind {
  vector<int> par; //par[i]:iの親の番号

  //最初は全てが根であるとする。-1のときに根である。
  UnionFind(int N) : par(N, -1){}

  // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
  int root(int x) {
    if(par[x] < 0) return x;
    else return par[x] = root(par[x]);
  }

  // データxが根かどうか
  bool cond_root(int x){
    if(par[x] < 0) return true;
    else return false;
  }

  //xとyが同じ集合に属するか
  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  void merge(int x, int y) {
    x = root(x); y = root(y);
    if(x == y) return;
    if(par[x] > par[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
  }

  int size(int x) {
    return -par[root(x)];
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  UnionFind uf(n);
  rep(i, m){
    int x, y, z;
    cin >> x >> y >> z;
    x--; y--;
    uf.merge(x, y);
  }
  int ans = 0;
  rep(i, n){
    if(uf.cond_root(i))ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3764
n, w = map(int, input().split())

value = []
weight = []

for _ in range(n):
  vi , wi = map(int,input().split())
  value.append(vi)
  weight.append(wi)

dp = [0 for _ in range(w+1)]

for i in range(n):
  for j in range(w, weight[i] - 1, -1):
    #前者は品物を選択しない、　後者は品物を選択する
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

print(dp[w])



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

#define WIDTH 3001
#define HEIGHT 51

int dp[HEIGHT * WIDTH];

int main(void)
{
	int i, j, k;
	int n, m, s;
	while(scanf("%d%d%d", &n, &m, &s), n){
		n *= n;
		dp[0] = 1;
		for(i=1; i<WIDTH*HEIGHT; ++i)
			dp[i] = 0;

		for(i=1; i<=m; ++i){
			for(j=n; j>=0; --j){
				for(k=s; k>=0; --k){
					if(j && i <= k){
						dp[j*WIDTH + k] = (dp[j*WIDTH + k] + dp[(j-1)*WIDTH + k-i]) % 100000;
					}
				}
			}
		}

		printf("%d\n", dp[n*WIDTH + s]);
	}

	return 0;
}

Measured memory_bytes: 1008
import java.io.PrintWriter;
import java.util.*;

public class Main {

    static String br = System.getProperty("line.separator");
    static Scanner sc = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int N = nextInt();
        int L = nextInt();

        int sum = 0;
        int min = 0;
        for(int i=1; i<=N; i++){
            int num = L+i-1;
            if(i == 1) min = num;
            min = Math.abs(min) > Math.abs(num) ? num : min;

            sum += num;
        }

        println(sum - min);
    }

    static int nextInt() {
        return Integer.parseInt(next());
    }

    static Long nextLong() {
        return Long.parseLong(next());
    }

    static String next() {
        return sc.next();
    }

    static String nextLine(){
        return sc.nextLine();
    }

    static void println(Object o) {
        out.println(o);
        out.flush();
    }

    static void print(Object o) {
        PrintWriter out = new PrintWriter(System.out);
        out.print(o);
        out.flush();
    }
}


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

int main () {
    int a, b, c, k;
    while (scanf("%d %d %d %d", &a, &b, &c, &k) == 4) {
        while (k && b <= a) b *= 2, k--;
        while (k && c <= b) c *= 2, k--;
        printf(a < b && b < c ?  "Yes\n" : "No\n");
    }
}



Measured memory_bytes: 3744
from collections import Counter

n = int(input())
s = input()
cnt = Counter(s)

ans = cnt['R'] * cnt['G'] * cnt['B']
for i in range(n):
    for j in range(n):
        k = 2 * j - i
        if k > n-1:
            break
        if i < j < k and s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
            ans -= 1

print(ans)


Measured memory_bytes: 74144
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<double,double>
#define pb push_back
#define f first
#define s second
#define ll long long int
#define vi vector<ll>
#define rs resize
int main()
{
     std::ios::sync_with_stdio(false);
     ll a,b,c;
     cin>>a>>b>>c;
     a = 100*a + 10*b+c;
     if(a%4==0)
      cout<<"YES";
     else
      cout<<"NO";
     return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const ld PI = acos(-1.0);
const ld EPS = 1e-11;

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, n) cin >> v[i];
  sort(all(v));
  int ans = 0;
  rep(i, n) REP(j, i + 1, n)
  {
    auto itr = upper_bound(all(v), v[j] - v[i]);
    int d = max((int)distance(itr, v.begin() + i), 0);
    ans += d;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;    // 現在地はで，nにいきたい, m種類の船
    vector<vector<int>> to(n);
    rep(i, m) {
        int a, b; cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    // to[n-1] <- to[j] <- to[1]
    rep(i, to[0].size()) {
        int mid = to[0][i];
        rep(j, to[mid].size()) {
            int des = to[mid][j];
            if (des == n - 1) { 
                puts("POSSIBLE");
                return 0;
            }
        }
    }
    puts("IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 12016
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <cmath>
#include <stdlib.h> 
#include <stdio.h>
#include <iterator>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>
#include <limits>
#include <unordered_map>
#include <bitset>
#include <numeric>
#include <sstream>
#include <random>
#include <cassert>

using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)
int INF = 1e9 + 7;

int main(void) {
	cin.tie(0); ios::sync_with_stdio(0);
	
	int n; long long ans = 0;
	cin >> n;
	vector <int> v(n);
	ffor(n) cin >> v[i];
	int maximum = v[0];
	for (int i = 0; i < n; i++) {
		maximum = max(maximum, v[i]);
		ans += maximum - v[i];
	}
	cout << ans;
}
	




/*
C:\Users\User\Desktop\comp_programming\final_straw_after_this_im_switching_to_vs_code\final_straw_after_this_im_switching_to_vs_code.cpp
*/

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

void solve() {
  int n; scanf("%d", &n);
  int sum = 0;
  for (int i = 1; sum < n; ++i) {
    sum += i;
  }
  if (sum > n) {
    printf("No");
    return;
  }
  int k = 1+(int)sqrt(2*n);
  printf("Yes\n%d\n", k);
  for (int sum = 1, i = 0; i < k; sum += i, ++i) {
    printf("%d ", k-1);
    for (int sum2 = 1, j = 0; j < k-1; ++j) {
      sum2 += j;
      if (j < i) {
	printf("%d ", sum+j);
      } else {
	printf("%d ", sum2+i);
      }
    }
    printf("\n");
  }
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3820