akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int K= scan.nextInt();
		
		int[] L = new int[N];
		
		
		for(int i = 0;i<N;i++){
			
			L[i] = scan.nextInt();
			
		}
		
		Arrays.sort(L);		
		
		
		
		int max =0;
		
		
		for(int i = N-1;i>N-1-K;i--){
			max+=L[i];
		}
		
		
		
		
		
		
		System.out.println(max);
		
	}

}

Measured memory_bytes: 23764
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int getVal(const vector<long long>& sum, int i, int mod)
{
    int ans = (sum[i] - i) % mod;
    ans += mod;
    ans %= mod;
    return ans;
}

int main()
{
    int n, mod;
    cin >> n >> mod;
    vector<int> a(n);
    vector<long long> sum(n+1);
    for(int i=0; i<n; ++i){
        cin >> a[i];
        sum[i+1] = sum[i] + a[i];
    }

    long long ans = 0;
    map<int, int> cnt;
    for(int i=0; i<n; ++i){
        if(i >= mod - 1)
            -- cnt[getVal(sum, i-(mod-1), mod)];
        ++ cnt[getVal(sum, i, mod)];
        ans += cnt[getVal(sum, i+1, mod)];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 12032
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>

using namespace std;



int main() {
	int a, b, c, x, y, sum = 0,mini = 1000000000;
	cin >> a >> b >> c >> x >> y;
	for (int i = 0; i <= max(x, y); i++) {
		sum = 0;
		if (x - i > 0) {
			sum += (x - i) * a;
		}
		if (y - i > 0) {
			sum += (y - i) * b;
		}
		sum += 2 * i * c;
		mini = min(mini, sum);
	}
	cout << mini << endl;

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG //エラーを出すためのおまじない
#include <bits/stdc++.h>
#include <algorithm>
//#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
#include <math.h>
using namespace std;
#define coYES cout << "YES" << endl
#define coNO cout << "NO" << endl
#define coYes cout << "Yes" << endl
#define coNo cout << "No" << endl
#define coyes cout << "yes" << endl
#define cono cout << "no" << endl
//#define cocount cout << count << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define Cinint(n) int n;\
cin >> n;
#define Cinvecint(a, n) vector<int> a(n);\
for (int i = 0; i < (int)(n); i++) {\
  int num;\
  cin >> num;\
  a.at(i) = num;\
}
#define Cinstring(s) string s;\
cin >>s;

  

int main() {
  Cinint(n);
  Cinint(m);
  Cinvecint(a, m);
  int64_t sum = 0;
  rep(i, m) {
    sum += a.at(i);
  }
  if (sum > n) {
    cout << -1 << endl;
  }
  else {
    cout << n-sum << endl;
  }
}
  



Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    const ll MOD = 1e9+7;
    ll N, K;
    cin >> N >> K;
    ll ans = 0;
    for(ll i=K; i<=N+1; i++){
        ans += i * (N-i+1) + 1;
        ans %= MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
a = int(input())
b = int(input())

list = [1,2,3]

if a == 1 and b == 2:
  print(3)
if a == 2 and b == 3:
  print(1)
if a == 3 and b == 1:
  print(2)
if a == 1 and b == 3:
  print(2)
if a == 2 and b == 1:
  print(3)
if a == 3 and b == 2:
  print(1)

Measured memory_bytes: 3064
using System;
using System.Linq;

namespace aoj
{
    class Program
    {
        static void Main(string[] args)
        {
            var sNum = int.Parse(Console.ReadLine());
            int[] S = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var qNum = int.Parse(Console.ReadLine());
            int[] Q = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            InsertSort(ref S);
            InsertSort(ref Q);

            var count = 0;

            var prevTarget = 0;
            for (var qi = 0; qi < Q.Length; ++qi)
            {
                // 検索のダブりを排除
                if (qi < 0 && prevTarget == Q[qi]) { continue; }

                if (BinarySearch(S, Q[qi]) != -1) { ++count; }

                prevTarget = Q[qi];
            }

            Console.WriteLine(count);
        }

        static int BinarySearch(int[] _searched, int _target)
        {
            var left = 0;
            var right = _searched.Length;
            int middle = -1;

            while (left < right)
            {
                middle = (left + right) / 2;

                if (_searched[middle] == _target)
                {
                    while (0 <= middle - 1)
                    {
                        if (_searched[middle - 1] != _searched[middle]) { break; }
                        --middle;
                    }
                    return middle;
                }

                if (_searched[middle] < _target)
                {
                    left = middle + 1;
                }
                else
                {
                    right = middle;
                }
            }

            return -1;
        }

        static void InsertSort(ref int[] _array)
        {
            for (var i = 1; i < _array.Length; ++i)
            {
                var target = _array[i];
                var compIndex = i - 1;

                while (0 <= compIndex && target < _array[compIndex])
                {
                    _array[compIndex + 1] = _array[compIndex];
                    --compIndex;
                }

                _array[compIndex + 1] = target;
            }
        }
    }
}



Measured memory_bytes: 31324
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main(int argc, const char * argv[]) {
  string s;
  cin >> s;
  vector<bool> map(26, false);
  for(int i = 0; i < s.size(); i++){
    map.at(s.at(i) - 'a') = true;
  }
  for(int i = 0; i < 26; i++){
    //cout << (char)(i + 'a') << ":" << map.at(i) << endl;
    if(!map.at(i)){
      cout << (char)(i + 'a') << endl;
      return 0;
    };
  }
  cout << "None" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int N; cin >> N;
    int ans = 0;
    for(int n = 1; n<=N; n++){
        ans = 0;
        for(int x = 1; x <= sqrt(n); x++){
            for(int y = x; y <= sqrt(n); y++){
                if(x + y >= sqrt(2*n)) break;
                for(int z = y; z <= sqrt(n); z++){
                    if(x + z >= sqrt(2*n)) break;
                    if(y + z >= sqrt(2*n)) break;
                    if(pow(x+y, 2)+ pow(y+z, 2) + pow(z+x, 2) == 2*n){
                        if(x != y && y != z && z != x) ans += 6;
                        else if(x == y && y == z) ans++;
                        else ans += 3;
                    } 
                }
            }
        }
        cout <<  ans << endl;
    }

    
    return 0;
}

Measured memory_bytes: 3536
#include<iostream>
using namespace std;
 
int main(){
    int a, b;
     
    cin>> a >> b;
     
    if ( a < b ) cout << "a < b" << endl;
    else if ( a > b ) cout << "a > b" << endl;
    else cout << "a == b" << endl;
 
    return 0;
}

Measured memory_bytes: 3092
function main()
  
  n = parse(Int, readline())
  h = parse.(Int, split(readline()))
  
  dp = [0, abs(h[2]-h[1])]
  for i in 3:n
    push!(dp, min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2])))
  end
  
  println(dp[n])
  
end

main()

Measured memory_bytes: 190848
s=input()
a=int(s[:2])
b=int(s[2:])
if (1<=a<=12)and(1<=b<=12):
  print('AMBIGUOUS')
elif (1<=a<=12)and(b==0 or b>12):
  print('MMYY')
elif (a==0 or a>12)and(1<=b<=12):
  print('YYMM')
else:
  print('NA')

Measured memory_bytes: 3060
#include <bits/stdc++.h> 
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const LL MOD=1e9+7;

int main(){
    int N,K;
    cin>>N>>K;
    double res=0;
    for(int n=1;n<=N;n++){
        int nw=n;
        double tmp=1.0/N;
        while(nw<K){
            nw*=2;
            tmp/=2;
        }
        res+=tmp;
    }
    cout<<fixed<<setprecision(15)<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),c = sc.nextInt();
		int[] x=new int[n];
		for(int i=0;i<n;i++)
			x[i] = sc.nextInt();
		Arrays.sort(x);
		long sum = 0;
		for(int i=0;i<n-c;i++)
			sum+=x[i];
		System.out.print(sum);
	}
}


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

int main(){
	long long int a, b, x;

	scanf("%lld %lld", &a, &b);

	if (a * -1 == b) {
		printf("Zero");
	}
	else if (a > 0 && b > 0) {
		printf("Positive");
	}
	else if (a % 2 == 0 && b > 0) {
		printf("Positive");
	}
	else if (a % 2 == 1 && b > 0) {
		printf("Negative");
	}
	else if (a < 0 && b < 0) {
		x = (a - b) * -1 + 1;
		if (x % 2 == 0) {
			printf("Positive");
		}
		else {
			printf("Negative");
		}
	}
}

Measured memory_bytes: 1736
from fractions import gcd

def debug(*args):
    import sys
    #print(*args, file=sys.stderr)

def solve(A, B, C, D):
    L = C * D // gcd(C, D)
    A-=1
    debug("A=%d, B=%d, C=%d, D=%d" %(A,B,C,D))
    debug((B//C, A//C), (B//D, A//D) , (B//L , A//L))
    debug((B//C - A//C), (B//D - A//D) , (B//L - A//L))
    return B-A- ((B//C - A//C) + (B//D - A//D) - (B//L - A//L))

def main():
    A, B, C, D = [int(x) for x in input().split()]
    print(solve(A, B, C, D))
    pass

main()



Measured memory_bytes: 6624
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    int N,A[100007],B[100007];
    ll c;
    c=0;
    cin  >> N;
    rep(i,N+1){
        cin >> A[i];
    }
    rep(i,N){
        cin >> B[i];
    }
    rep(i,N){
        if(B[i]>=A[i]+A[i+1]){
            c+=A[i]+A[i+1];
            A[i+1]=0;
        }
        else if(B[i]>A[i]){
            c+=B[i];
            A[i+1]=A[i+1]+A[i]-B[i];
        }
        else{
            c+=B[i];
        }
    }

    cout << c << endl;
    return 0;
}

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

vector<int> A(3);

int N;

int sum = 0;

void solve() {

    for (int j = 0; j < 3; j++) {
        cin >> A.at(j);
    }

    cin >> N;

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

    for (int j = 0; j < N; j++) {

        A.at(2) = 2 * A.at(2);

    }



    for (int j = 0; j < 3; j++) {
        sum += A.at(j);
    }
}


int main() {

    solve();

    cout << sum << endl;
}

Measured memory_bytes: 256
n, a = map(int, input().split())
x = [int(x)-a for x in input().split()]

ans = [[0]*5001 for _ in range(n)]  # -2500 ~ 2500

for i in range(n):
    if i == 0:
        ans[0][x[i]+2500] += 1
    else:
        for j in range(5001):
            if 5000 >= j-x[i] >= 0:
                ans[i][j] = ans[i-1][j] + ans[i-1][j-x[i]]
        ans[i][x[i]+2500] += 1

print(ans[n-1][2500])

Measured memory_bytes: 40816
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    all_members = uf.get_all_members()
    # all_members = list(uf.all_group_members())
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs[1:]):
            # if i > 0:
            other_vals.append(v)

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

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

ll t1, t2, a1, a2, b1, b2;

int main() {
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    ll p1, p2, q1, q2;
    p1 = t1 * a1;
    p2 = p1 + t2 * a2;
    q1 = t1 * b1;
    q2 = q1 + t2 * b2;
    if (p2 == q2) {
        cout << "infinity" << endl;
        return 0;
    }
    if (p2 > q2) {
        swap(p1, q1);
        swap(p2, q2);
    }
    if (p1 < q1) {
        cout << 0 << endl;
        return 0;
    }
    ll d1 = q1 - p1;
    ll d2 = p2 - q2;
    ll x = d1 / d2 + 1;
    ll ans;
    if (d1 % d2 == 0) ans = 2 * x - 2;
    else {
        x++;
        ans = 2 * x - 3;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
def main(n):
	a = list(input().split())
	b = list(a)
	c = list(a)
	achk = [[] for _ in range(10)]
	bchk = [[] for _ in range(10)]
	cchk = [[] for _ in range(10)]
	for i in range(n):
		for j in range(n-1, i, -1):
			if int(b[j][1]) < int(b[j-1][1]):
				b[j], b[j-1] = b[j-1], b[j]
	print(" ".join(b))
	print("Stable")
	for i in range(n):
		minj = i
		for j in range(i, n):
			if int(c[j][1]) < int(c[minj][1]):
				minj = j
		c[i], c[minj] = c[minj], c[i]
	print(" ".join(c))
	if c == b:
		print("Stable")
	else:
		print("Not stable")

main(int(input()))


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

#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int NAX = 2e5 + 5, MOD = 1000000007;

struct Solution
{
    Solution() {}
    void solveCase();
};

void Solution::solveCase()
{
    int x;
    cin >> x;
    cout << 1 - x << '\n';
}

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
    // cin >> t;
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef LOCAL
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}


Measured memory_bytes: 3644
n=int(input())
h = list(map(int,input().split()))
cnt=0
while h != [0 for _ in range(n)]:
    key=0
    for i in range(n):
        if h[i]!=0:
            while i<n and h[i]>0:
                h[i]-=1
                i+=1
                key=1
        if key==1:
            cnt+=1
            break
print(cnt)

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

#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int NAX = 2e5 + 5, MOD = 1000000007;

struct Solution
{
    Solution() {}
    void solveCase();
};

void Solution::solveCase()
{
    string s;
    cin >> s;
    char back = '$';
    int len = 0, maxLen = 0;
    for (auto &x : s)
    {
        if (back == x)
            len++;
        else
        {
            if (back == 'R')
                maxLen = max(maxLen, len);
            len = 1;
            back = x;
        }
    }
    if (back == 'R')
        maxLen = max(maxLen, len);

    cout << maxLen << '\n';
}

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
    // cin >> t;
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef LOCAL
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAX 100005

struct node{
	int nxt, t;
}edge[MAX * 2];

int head[MAX], inde, oc[MAX];
int arr[MAX];

void init(){
	memset(head, -1, sizeof(head));
	memset(oc, 0, sizeof(oc));
	inde = 0;
}

void addedge(int s, int t){
	edge[inde].t = t;
	edge[inde].nxt = head[s];
	head[s] = inde++;
}

int mstack[MAX], top;

int rarr1[MAX], rarr2[MAX], rtop;

int bfs(int s, int flg){
	int now, i, j;
	rtop = top = 0;
	
	mstack[top++] = s;
	rarr1[rtop] = s;
	rarr2[rtop++] = arr[s];
	oc[s] = flg;

	while(top > 0){
		now = mstack[--top];
		i = head[now];
		while(i >= 0){
			if(oc[edge[i].t]){
				i = edge[i].nxt;
				continue;
			}
			oc[edge[i].t] = flg;
			mstack[top++] = edge[i].t;
			rarr1[rtop] = edge[i].t;
			rarr2[rtop++] = arr[edge[i].t];
			i = edge[i].nxt;
		}
	}
	
	int cnt = 0;
	std::sort(rarr1, rarr1 + rtop);
	std::sort(rarr2, rarr2 + rtop);
	i = j = 0;
	while(i < rtop && j < rtop){
		if(rarr1[i] == rarr2[j])
			cnt++;
		if(rarr1[i] < rarr2[j]) i++;
		else j++;
	}

	return cnt;
}




int main()
{
	int n, m, i, s, t;
	while(~scanf("%d%d", &n, &m)){
		init();
		for(i = 1; i <= n; i++){
			scanf("%d", &arr[i]);
		}
		for(i = 1; i <= m; i++){
			scanf("%d%d", &s, &t);
			addedge(s, t);
			addedge(t, s);
		}
		int res = 0;
		for(i = 1; i <= n; i++){
			if(!oc[i]) res += bfs(i, i);
			
		}

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


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define debug(x) std::cerr<<#x<<":"<<(x)<<std::endl;
#define INIT ios::sync_with_stdio(false);cin.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}

//
// eratosthenes
//  + 値は1-indexedで格納されている
//  + prime
//    - 素数か否かがbool型で格納
//    - prime[n] ? 素数 : 素数ではない
//  + prime_factorize
//    - 素因数分解をする関数
//    - 引数nを素因数分解して, 
//      どの素数がどれだけ含まれているかをvector< pair<int,int> >で返す 
//    - e.g.) n=20 => (2,2), (5,1)

struct Eratosthenes {
	// 1-indexedで検索可能
  vector< bool > prime;
  // sizeは1e6くらいまでならおk
  Eratosthenes(int _size) {
    init(_size);
  }	
	
  void init(int n) {
    prime.resize(n + 1);
    for(int i=0; i<prime.size(); ++i) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i=2; i*i<=n; i++) {
      if (prime[i]) {
        for (int j=0; i*(j + 2)<n; ++j) {
					prime[i*(j+2)] = false;
				}
      }
    }
  }

	vector< pair< int, int > > prime_factorize(int n) {
		vector< pair< int, int > > res;
		for (int p=2; p*p<=n; ++p) {
			if (n%p != 0) continue;
			int num = 0;
			while (n%p == 0) ++num, n /= p;
			res.push_back(make_pair(p, num));
		}
		if (n != 1) res.push_back(make_pair(n, 1));
		return res;
	}
};

signed main() {
  INIT;
  int a,b;cin>>a>>b;
  int g = gcd(a,b);

  Eratosthenes e(1);
  auto primes = e.prime_factorize(g);
  cout<<primes.size()+1<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int h,w,k;
  cin >> h >> w >> k;
  vvi board(h, vi(w));
  rep(i, h){
    rep(j, w){
      char s; cin >> s;
      board[i][j] = (s == '#') ? 1 : 0;
    }
  }
  int ans = 0;
  rep(i, 1 << h){
    rep(j, 1 << w){
      vvi temp = board;
      rep(y, h){
        if((i >> y) & 1){
          rep(x, w) temp[y][x] = 0;
        }
      }
      rep(x, w){
        if((j >> x) & 1){
          rep(y, h) temp[y][x] = 0;
        }
      }
      int cnt = 0;
      rep(y, h) rep(x, w) if(temp[y][x]) cnt++;
      if(cnt == k) ans++;
    }
  }
  cout << ans << endl;
}

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

#define ll long long

using namespace std;

int main() {
	int n; cin >> n;
	ll k; cin >> k;
	vector<int> a(n+1);
	for (int i=0; i<n; i++) cin >> a[i+1];
	if (k > n) {
		vector<int> visit(n+1, -1);
		int cur = 1;
		visit[1] = 0;
		int cycle = n;
		for (int i=1; i<=n+1; i++) {
			cur = a[cur];
			if (visit[cur] != -1) {
				cycle = i-visit[cur];
				break;
			}
			visit[cur] = i;
		}
		k = (k-n) % cycle + n;
	}
	int cur = 1;
	while (k--) {
		cur = a[cur];
	}
	cout << cur;
}


Measured memory_bytes: 4844
#include<iostream>
#include<map>
using namespace std;
typedef long long LL;
int main(){
	map<LL,int>m;
	LL n,t;
	cin>>n;
	m.clear();
	while(n--){
		cin>>t;
		m[t]++;
	}
	LL a=-1,b=-1;
	map<LL,int>::iterator it;
	for(it=m.begin();it!=m.end();it++){
		if(it->second>=2){
			b=a;
			a=it->first;
		}
		if(it->second>=4){
			a=b=it->first;
		}
	}
	LL c=a*b;
	if(b==-1)printf("0\n");
	else printf("%lld\n",c);
} 

Measured memory_bytes: 6528
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int st_dist[100001], ed_dist[100001];
vector<int> node_list[100001];

void dfs1(int curr, int prev){

    st_dist[curr] = st_dist[prev] + 1;
    for(int i : node_list[curr]){
        if(i != prev){
            dfs1(i, curr);
        }
    }
}

void dfs2(int curr, int prev){
    if(ed_dist[curr] > 0){return;} /*visited*/

    ed_dist[curr] = ed_dist[prev] + 1;
    for(int i : node_list[curr]){
        if(i != prev){
            dfs2(i, curr);
        }
    }
}

int main(void){
    int N, a, b;
    memset(st_dist, 0, sizeof(st_dist));
    memset(ed_dist, 0, sizeof(ed_dist));

    cin >> N;

    for(int i=0;i<N;i++){
        cin >> a >> b;
        node_list[a].push_back(b);
        node_list[b].push_back(a);
    }
    dfs1(1 ,1);
    dfs2(N, N);

    int dist_count=0;

    for(int i=1;i<=N;i++){
        if(st_dist[i] <= ed_dist[i]){
            dist_count++;
        }
    }
    
    if(dist_count > N - dist_count){
        cout << "Fennec" << endl;
    }
    else{
        cout << "Snuke" << endl;
    }
    return 0;

}

Measured memory_bytes: 11136
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <numeric>
#include <climits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <utility>
#include <cctype>
#include <iterator>
////////////////////////////////////////////////
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
////////////////////////////////////////////////
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  int n;
  cin >> n;
  vector<ll> a(n, 0);
  REPe(e, a) cin >> e;
  sort(all(a), greater<ll>());
  ll ans = 0;
  if (n % 2 == 0) {
    int k = n / 2;
    // cout << k << endl;
    REP(i, k) { ans += 2LL * a[i]; }
    ans -= a[0];
  } else {
    int k = n / 2;
    // cout << k << endl;
    REP(i, k) { ans += 2LL * a[i]; }
    ans += a[k];
    ans -= a[0];
  }
  cout << ans << endl;
}


Measured memory_bytes: 4764
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    map<string, long long> mp;
    for (int i = 0; i < N; i++)
    {
        string S;
        cin >> S;
        sort(S.begin(), S.end());
        ++mp[S];
    }
    long long ans = 0;
    for (auto p : mp)
    {
        ans += p.second * (p.second - 1) / 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 11136
import math
def main():
  n,d = list(map(int,input().split()))
  x = [input().split() for l in range(n)]
  ans=0
  for i in range(0,n):
    for j in range(i+1,n):
      dist=0
      for k in range(0,d):
        dist+=abs(int(x[j][k])-int(x[i][k]))*abs(int(x[j][k])-int(x[i][k]))
      if math.sqrt(dist)%1==0:
        ans+=1
  print(ans)
main()

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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int inf=LLONG_MAX/3;

void First(){
	cout<<"First"<<endl;
	exit(0);
}
void Second(){
	cout<<"Second"<<endl;
	exit(0);
}

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

signed main(){
	int n=read();
	vi a;
	REP(i,n)
		a.PB(read());
	int s=0;
	REP(i,n)
		s=(s+a[i])%2;
	if(n==1){
		if(a[0]==1)
			Second();
		else
			First();
	}else if(n%2){
		if(s%2==0)
			First();
		else{
			int k=0;
			while(1){
				int c=0;
				bool can=true;
				for(auto& t:a){
					if(t==1) can=false;
					c+=t%2;
				}
				if(c%2==0){
					if(k%2)
						Second();
					else
						First();
				}
				if(c>1||!can)
					break;
				int g=a[0]-a[0]%2;
				for(auto& t:a)
					g=gcd(g,t-=t%2);
				assert(g%2==0);
				for(auto& t:a)
					t/=g;
				k++;
			}
			if(k%2==0)
				Second();
			else
				First();
		}
	}else{
		if(s%2==1)
			First();
		else
			Second();
	}
}


Measured memory_bytes: 1528
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであるに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO verify both in directed and non-directed
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = WarshallFloyd(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)

d = graph.WarshallFloyd_search()
ans = float('inf')
for each in itertools.permutations(r):
    cur = 0
    for i in range(R - 1):
        cur += d[each[i] - 1][each[i + 1] - 1]
    ans = min(ans, cur)

print(ans)

Measured memory_bytes: 60888
#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int m,n;
	int a[1000];
	int kari;
	int sum;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			break;
		}
		sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		for (int i = n-1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] < a[j+1]) {
					kari = a[j];
					a[j] = a[j+1];
					a[j+1] = kari;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if ((i + 1) % m != 0) {
				sum += a[i];
			}
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;

char s[20];
int64 dp[20], cnt[20];

int main() {
  scanf("%s", s);
  int n = strlen(s);
  dp[n] = 0;
  cnt[n] = 1;
  for (int i = n - 1; i >= 0; --i) {
    int64 sum = 0;
    for (int j = i; j < n; ++j) {
      sum = sum * 10 + (s[j] - '0');
      dp[i] += sum * cnt[j + 1] + dp[j + 1];
      cnt[i] += cnt[j + 1];
    }
  }
  printf("%lld\n", dp[0]);
  return 0;
}


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

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;
#pragma endregion

#pragma region const
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#pragma endregion

#pragma region util
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

template<typename T = i64>
T IN() { T x; cin >> x; return (x); }
template<typename T = i64>
void OUT(T& x) { cout << x << endl; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}
#pragma endregion

#pragma region init
struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

vector<i64> to[200005];
vector<i64> ans;

void dfs(i64 v, i64 p = -1)
{
	for (int u : to[v])
	{
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}

#ifdef _DEBUG
signed Main()
#else
signed main()
#endif
{
	auto N = IN();
	auto Q = IN();
	REP(i, N - 1)
	{
		i64 a, b;
		cin >> a >> b;
		--a; --b;
		to[a].push_back(b);
		to[b].push_back(a);
	}

	ans.resize(N);

	REP(i, Q)
	{
		i64 p, x;
		cin >> p >> x;
		--p;
		ans[p] += x;
	}

	dfs(0);
	REP(i, N)
	{
		cout << ans[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 26112
from math import factorial

def comb(n,r):
    return factorial(n) // (factorial(n-r) * factorial(r))

def main():
    N,P = map(int,input().split())
    A = list(map(int,input().split()))

    even,odd = 0,0
    for i in range(N):
        if A[i] % 2 == 0:
            even += 1
        else:
            odd += 1

    a,b = 0,0
    b = 2**even

    for i in range(odd+1):
        if i % 2 == P:
            a += comb(odd,i)

    print(a*b)

if __name__ == "__main__":
    main()


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

int main() {
	int n,l;
	cin>>n>>l;
	int A[n];
	int shuma=0;
	for(int i=0;i<n;i++)
    {
        A[i]=l+i;
        shuma+=A[i];
    }
    int max=abs(A[0]);
    for(int i=1;i<n;i++)
    {
        if(abs(A[i])<abs(max))
        {
            max=A[i];
        }
    }
    cout<<shuma-max;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
string a,b;
int la,lb;
int dp[10000][10000];

void dpf(void){
	for(int i=1;i<=la;i++){
		for(int j=1;j<=lb;j++){
			if(a[i]==b[j]){
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}	
	return ;
}
int n;

int main(void){
	cin>>n;
	
	
for(int i=0;i<n;i++){	
	cin>>a>>b;
	la=a.length();
	lb=b.length();
	a=' '+a;
	b=' '+b;
	dpf();
	cout<<dp[la][lb]<<endl;
}


}


Measured memory_bytes: 11036
#B
inf = float("inf")
N,K = map(int,input().split())
H = list(map(int,input().split()))

dp = [inf for _ in range(N)] #dp[i] = cost
dp[0] = 0
for i in range(N):
    for j in range(K):
        if i+j+1 < N:
            dp[i+j+1] = min(dp[i+j+1],dp[i]+abs(H[i]-H[i+j+1]))
            
#print(dp)
print(dp[N-1])



Measured memory_bytes: 58848
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	string s="";
	while(n>0){/*
		int w=0,a=1,ss=s;
		while(ss>0){
			ss/=10;
			w++;
		}
		for(int i=1;i<w;i++)    a*=10;*/
		 s+=(n%k-'0');
		 n/=k;
	}
	cout<<s.size()<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
	int n, d, ans = 0;
	double dist=0;
	cin >> n >> d;
	int x[11][11];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= d; j++)
		{
			cin >> x[i][j];
		}
	}

	for (int k = 1; k < n; k++)
	{
		for (int i = k + 1; i <= n; i++)
		{
			for (int j = 1; j <= d; j++)
			{
				dist += (double)pow((x[k][j] - x[i][j]), 2);
			}
			dist = pow(dist, 0.5);
			if ((double)((int)dist) == dist)ans++;
			dist = 0;
		}
	}
	cout << ans;
}

Measured memory_bytes: 384
A,B,C,X,Y = map(int,input().split())

if A+B>=2*C:
    if X>Y:
        if A>=2*C:
            ans = Y*2*C + (X-Y)*2*C
        else:
            ans = Y*2*C + (X-Y)*A
    else:
        if B>=2*C:
            ans = X*2*C + (Y-X)*2*C
        else:
            ans = X*2*C + (Y-X)*B
else:
    ans = X*A + Y*B

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[3005][3005],pr[3005][3005][2];
char s[3005],t[3005];
void pri(int i,int j)
{
	if(i==0||j==0) return;
	int a=pr[i][j][0],b=pr[i][j][1];
	pri(a,b);
	if(dp[a][b]+1==dp[i][j]) putchar(s[i]);
}
int main ( )
{
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1),m=strlen(t+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			pr[i][j][0]=i-1,pr[i][j][1]=j;
			if(dp[i][j-1]>dp[i-1][j])
			{
				dp[i][j]=dp[i][j-1];
				pr[i][j][0]=i,pr[i][j][1]=j-1;
			}
			if(s[i]==t[j]&&dp[i-1][j-1]+1>dp[i][j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				pr[i][j][0]=i-1,pr[i][j][1]=j-1;
			}
		}
	}
	pri(n,m);
	putchar('\n');
	return 0;
}

Measured memory_bytes: 106112
k=int(input())
x,y=map(int,input().split())
d=abs(x)+abs(y)
if k%2==0 and d%2==1:
  print(-1)
  exit()

nx,ny=0,0
ans=[]
flg=True
xty=False
if abs(x)<abs(y):
  pass
else:
  x,y=y,x
  xty=True
while d>2*k:
  dx=min(k,abs(x-nx))
  dy=k-dx
  if abs(x-nx):nx+=dx*(x-nx)//abs(x-nx)
  if abs(y-ny):ny+=dy*(y-ny)//abs(y-ny)
  ans.append([nx,ny])
  d=abs(x-nx)+abs(y-ny)
if d%2==1:
  dx=min(k,abs(x-nx))
  dy=k-dx
  if abs(x-nx):nx+=dx*(x-nx)//abs(x-nx)
  if abs(y-ny):ny+=dy*(y-ny)//abs(y-ny)
  ans.append([nx,ny])
  d=abs(x-nx)+abs(y-ny)

# dは必ず偶数になる。中間地点が定まる
dd=d//2
dx=min(dd,abs(x-nx))
dy=dd-dx
mx,my=nx,ny
if abs(x-nx):mx=nx+dx*(x-nx)//abs(x-nx)
if abs(y-ny):my=ny+dy*(y-ny)//abs(y-ny)
flg=False
#print('now:',nx,ny)
#print('mid:',mx,my)
while [nx,ny]!=[x,y]:
  d=abs(x-nx)+abs(y-ny)
  #if d>10:exit()
  #print(d,nx,ny)
  # 距離がkの倍数になればあとは近づくだけ
  if d%k==0:
    dx=min(k,abs(x-nx))
    dy=k-dx
    if abs(x-nx):nx+=dx*(x-nx)//abs(x-nx)
    if abs(y-ny):ny+=dy*(y-ny)//abs(y-ny)

  # 中間地点通過済みなら、ゴールから離れる
  elif flg:
    if abs(x-nx):
      nx-=k*(x-nx)//abs(x-nx)
    else:
      ny-=k*(x-ny)//abs(x-ny)
      
  # 中間地点未通過ならそこに近づく。
  else:
    flg=True
    #必ず中間地点を通過する。中間地点から見て、ゴールとnowの両方から離れる。
    dy=min(k,abs(my-ny))
    dx=k-dy
    ny=my
    if mx-nx>0:
      nx+=dx
    else:
      nx-=dx

  ans.append([nx,ny])
print(len(ans))
for a,b in ans:
  if xty:
    print(b,a)
  else:
    print(a,b)

Measured memory_bytes: 100892
import sys

def main():
    n, c = getLineInts()
    ss = [0 for i in range(n)]
    ts = [0 for i in range(n)]
    cs = [0 for i in range(n)]
    ics = [[] for c in range(31)]
    for i in range(n):
        ss[i], ts[i], cs[i] = getLineInts()
        ics[cs[i]].append(i)
        
    icms = []
    for c in range(31):
        prepS = None
        prepT = None
        for i in sorted(ics[c], key = lambda i: ss[i]):
            if prepS is not None and prepT == ss[i]:
                prepT = ts[i]
            else:
                if prepS is not None:
                    icms.append((prepS, 0))
                    icms.append((prepT, 1))
                prepS = ss[i]
                prepT = ts[i]
        if prepS is not None:
            icms.append((prepS, 0))
            icms.append((prepT, 1))
    
    vMax = 0
    cur = 0
    icms = sorted(icms, key = lambda e: e[1])
    icms = sorted(icms, key = lambda e: e[0])
    for (t, type) in icms:
        if type == 0:
            cur += 1
            if vMax < cur:
                vMax = cur
        else:
            cur -= 1
    print(vMax)


def getLineInts():
    return [int(x) for x in sys.stdin.readline().rstrip().split(' ')]


if __name__ == '__main__':
    main()


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

int main() {
	int n, k, r, s, p;
	cin >> n >> k;
	cin >> r >> s >> p;
	string t;
	cin >> t;
	vector<vector<int>>ts(k, vector<int>(0));
	for (int i = 0; i < t.length(); i++) {
		int z;
		if (t.at(i) == 'r')z = 1;
		else if (t.at(i) == 's')z = 2;
		else z = 3;
		ts.at(i % k).push_back(z);
	}
	ll ans = 0;
	for (int i = 0; i < k; i++) {
		vector<vector<int>>dp(ts.at(i).size(), vector<int>(4, 0));
		for (int j = 0; j < ts.at(i).size(); j++) {
			//グー(r)==1,チョキ(s)==2,パー(p)==3;
			int x;
			if (ts.at(i).at(j) == 2)x = 1;
			else if (ts.at(i).at(j) == 3)x = 2;
			else x = 3;
			dp.at(j).at(0) = x;
			if (j == 0) {
				if (x == 1)dp.at(j).at(1) = r;
				else if (x == 2)dp.at(j).at(2) = s;
				else dp.at(j).at(3) = p;
			}
			else {
				if (x == 1) {
					dp.at(j).at(1) = max(dp.at(j - 1).at(2), dp.at(j - 1).at(3)) + r;
					dp.at(j).at(2) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(3));
					dp.at(j).at(3) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(2));
				}
				else if (x == 2) {
					dp.at(j).at(1) = max(dp.at(j - 1).at(2), dp.at(j - 1).at(3));
					dp.at(j).at(2) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(3)) + s;
					dp.at(j).at(3) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(2));
				}
				else {
					dp.at(j).at(1) = max(dp.at(j - 1).at(2), dp.at(j - 1).at(3));
					dp.at(j).at(2) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(3));
					dp.at(j).at(3) = max(dp.at(j - 1).at(1), dp.at(j - 1).at(2)) + p;
				}
			}
			//cout << dp.at(j).at(0) << dp.at(j).at(1) << dp.at(j).at(2) << dp.at(j).at(3) << endl;
		}
		int y = ts.at(i).size() - 1;
		ans += max(dp.at(y).at(1), max(dp.at(y).at(2), dp.at(y).at(3)));
	}
	cout << ans << endl;
}

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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(vec) vec.begin(),vec.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define SZ(x) (int)x.size()

typedef  vector<string> vs;
typedef  vector<int> vi;


int main(){
	
	
	int k; 
	
	int ans = 0;
	
	cin >> k;
	
	f(i,1,k+1){
		f(j,i,k+1){
			
			if(i%2==0 && j%2==1 ){
				ans++;
			}
			if(i%2==1 && j%2==0 ){
				ans++;
			}
		}
	}
	
	cout << ans << endl;
	
	
 return 0;
}


Measured memory_bytes: 256
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 1. INPUT                : ABCACARCACAGCWA
 * 2. cumulative n of "AC" : 000111112222222
 * 3. OUTPUT : difference between right and left
 */

int main (void) {
    int i;
    int len_str, n_que;
    scanf("%d%d", &len_str, &n_que);
    char str[len_str];
    scanf("%s", str);

    int cum_sum=0;
    int ac_array[len_str];
    memset(ac_array, 0, sizeof(int)*len_str);
    for ( i=1; i<len_str; i++ ) {
        if ( str[i-1] == 'A' && str[i] == 'C' )
            cum_sum++;
        ac_array[i] = cum_sum;
    }
    ac_array[len_str-1] = cum_sum;

    int l, r;
    int ans[n_que];
    for ( i=0; i<n_que; i++ ) {
        scanf("%d%d", &l, &r);
        ans[i] = ac_array[r-1] - ac_array[l-1];
        assert(ans[i] >= 0);
    }

    for ( i=0; i<n_que; i++ )
        printf("%d\n", ans[i]);

    return EXIT_SUCCESS;
}


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

typedef long long 		ll;
typedef vector<ll> 		vll;
typedef pair<ll,ll> 	pll;
typedef vector<pll> 	vpll;
typedef vector<int> 	vi;
typedef pair<int,int> 	pii;
typedef vector<pii> 	vpii;

#define fi				first
#define se 				second
#define pb 				push_back
#define mp 				make_pair
#define all(v)			v.begin(),v.end()
#define sz(v)			s.size()
#define rep(i,a,b) 		for(int i=a;i<=b;i++)
#define per(i,a,b) 		for(int i=a;i>=b;i--)
#define fill(a,v)		memset(a,v,sizeof(a))
#define tc				int T;cin>>T;while(T--)
#define nl				printf("\n")
#define aya				cerr<<"yaha aya"<<"\n"
#define debug(x,y)		printf("%d %d\n",x,y)
#define fast_io			ios_base::sync_with_stdio(false);cin.tie(NULL);
#define grt				greater<int>()

const ll mod = 1e9+7;
const int mod2= 1e9+9;

inline int pow_(ll a, int n, int p=mod){
	int r=1;while(n){if(n&1)r=r*a%p;n>>=1;a=a*a%p;}return r;
}

int main(void)
{
	int n, k;
	cin >> n >> k;
	ll res = 0;
	ll presum[n+1];
	rep(i, 0, n){
		presum[i] = i;
	}
	rep(i, 1, n){
		presum[i] += presum[i-1];
		presum[i] %= mod;
	}

	rep(i, k, n+1){
		ll low = presum[i-1];
		ll high = presum[n] - ( i != n+1 ? presum[n - i] : 0);
		res += high - low + 1;
		res %= mod;
		if(res < 0){
			res += mod;
		}
	}

	cout << res << "\n";
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        a[x] = i;
    }
    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
    cout << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;

//ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll resa=1e18;
ll resb=1e18;

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


	int n;
	cin>>n;

	string s[n+5];
	int t[n+5];
	map<string,int> mp;

	for(int i=0;i<n;i++)
	{
		cin>>s[i]>>t[i];
		mp[s[i]]=i;
	}

	string x;
	cin>>x;
	int index= mp[x];

	ll ans=  0;

	for(int i=index+1;i<n;i++)
	{
		ans+=t[i];
	}
	cout<<ans<<'\n';


return 0;
}

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

int main(){
  int n,i,c=0; cin>>n;
  int s[n];
  for(i=0;i<n;i++) cin>>s[i];
  
  for(i=0;i<n-2;i++){
    if(s[i]<s[i+1] && s[i+1]<s[i+2])c += 1;
    if(s[i]>s[i+1] && s[i+1]>s[i+2])c += 1;
  }
  
  cout<<c<<endl;
  return 0;
}


Measured memory_bytes: 256