akhauriyash/Code-Regression huggingface dataset:
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

int main() {
    string a,b,c;
    cin >> a >> b >> c;
    cout << a[0] << b[0] << c[0] << endl;
    return 0;
}


Measured memory_bytes: 256
N,M,X=map(int,input().split())
l=[]
for i in range (N):
  l.append(list(map(int,input().split())))
ans=10000000
for i in range(2**N):
  score=[0]*M
  coin=0
  for j in range(N):
    if i>=2**(N-1-j):
      for p in range(M):
        score[p]+=l[j][p+1]
      coin+=l[j][0]
      i-=2**(N-1-j)
  flag=0
  for q in range(M):
    if score[q]<X:
      flag=1
  if flag==0:
    if ans>coin:
      ans=coin
if ans==10000000:
  print("-1")
else:
  print(ans)

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX = 510000;


int main(){
  int N,M;
  cin >>N>>M;
  unordered_set<ll>st;
  rep(i,M){
  	ll a;
    cin >>a;
    st.insert(a);
  }
  ll dp[N+1];
  rep(i,N+1){dp[i]=0;}
  dp[0]=1;
  for(int i=0;i<N;i++){
    if(st.count(i)){continue;}
  	if(!st.count(i+1)){
      dp[i+1]+=dp[i];
    }
    if(!st.count(i+2)&&i<N-1){
      dp[i+2]+=dp[i];
    }
    dp[i+1]%=MOD;
  }
 	cout<<dp[N];
}

Measured memory_bytes: 5156
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

template <typename T> using vec = std::vector<T>;
using vi = vec<int>;
using ll = long long;
using ld = long double;
// constexpr auto mod = 1000000007;
using namespace std;

int main() {
  string s;
  cin >> s;
  const auto size = s.size();
  vi changed = {0, 0};
  REP(i, size) {
    if (s[i] != (i % 2 == 0 ? '0' : '1')) {
      changed[0] += 1;
    } else if (s[i] != (i % 2 == 0 ? '1' : '0')) {
      changed[1] += 1;
    }
  }
  cout << min(changed[0], changed[1]) << endl;
  return 0;
}


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

int main()
{
  int N, a=0, b=0;
  cin >> N;
  vector<int> H(N);
  for (int i=0; i<N; i++){
    cin >> H.at(i);
  }
  for (int i=0; i<N-1; i++){
    if(H.at(i)>=H.at(i+1)) {
    a++;
    }
    else a=0;
    if (b<a) b=a;
  }
  cout << b << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int, nuint_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; 
#define int long long
#define MOD 1000000007
#define what_is(x) cerr << #x << " is " << x << endl;
#define loop(i,a,n) for(int i=a;i<n;i++)

#define pb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, szof(x))
#define sortall(x) sort(aint(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<int, int> pt;
unordered_map<int, int> used;
 
int arr[200010],q;
vector<int> arr1(200010);

signed main() {
	
	fastio();
	//#define LOCAL_DEFINE
	#ifdef LOCAL_DEFINE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	//https://codeforces.com/contest/1084/problem/D
	int n;
	cin>>n;
	int ans=0;
	int arr[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if((arr[i]-x)>0)
		{
			ans+=(arr[i]-x);
		}
	}
	cout<<ans;
	return  0;


}


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

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

using namespace std;
using ll = long long;

const int INF = INT_MAX;
ll cnt = 0;

void merge_sort(vector<int> &a) {
    if(a.size() == 1) return;
    int mid = a.size() / 2;
    vector<int> sorted1(mid), sorted2(a.size() - mid);
    copy(a.begin(), a.begin() + mid, sorted1.begin());
    copy(a.begin() + mid, a.end(), sorted2.begin());
    merge_sort(sorted1);
    merge_sort(sorted2);
    sorted1.emplace_back(INF);
    sorted2.emplace_back(INF);
    auto itr1 = sorted1.begin(), itr2 = sorted2.begin();
    rep(i, a.size()) {
        if(*itr1 <= *itr2) {
            a[i] = *itr1;
            itr1++;
        } else {
            a[i] = *itr2;
            itr2++;
            cnt += distance(itr1, --sorted1.end());
        }
    }
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    merge_sort(a);
    printf("%ld\n", cnt);

    return 0;
}


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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int P1 = A * N;
  int P2 = B;

  if (P1 < P2) {
    cout << P1 << endl;
  } else {
    cout << P2 << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		walker walk = new walker();
		while(true){
			int go,angle;
			String input[] = in.next().split(",");
			go=Integer.parseInt(input[0]);
			angle=Integer.parseInt(input[1]);
			if(go+angle==0)break;
			walk.fd(go);
			walk.turn(angle);
		}
		int x=(int)walk.x;
		int y=(int)walk.y;
		System.out.println(x);
		System.out.println(y);
	}
}
class walker{
	static double x,y;
	static int angle;
	walker(){
		x=0;y=0;angle=0;
	}
	static void turn(int s){
		
		angle+=s;
	}
	static void fd(int go){
		x +=Math.sin(Math.PI*angle/180.0)*go;
		y +=Math.cos(Math.PI*angle/180.0)*go;
	}
}

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

int main(){
  int b[1000];
  int a,s=0;
  cin >> a ;
  for(int i=0;i<a;i++){
    cin >> b[i];
  }
  for(int i=0;i<a;i++){
    for(int k=i+1;k<a;k++){
      s = s+b[i]*b[k];
    }
  }


  cout << s << endl;
}

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

import static java.lang.StrictMath.abs;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        String[] a = new String[4];
        a = n.split("");
        int count =0;
        for(int i= 0; i< 3 ; i++){
            if(!(a[i].equals(a[i+1]))){
                count++;
                if(count ==3){
                    System.out.println("Good");
                }else{
                    continue;}
            }else{
                System.out.println("Bad");
                break;
            }
        }
    }

        }


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int food[1000];
int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;

    for (int i = 0; i < n; i++) {
        int k; cin >> k;
        for(int i = 0; i < k; i++) {
            int t; cin >> t;
            food[t]++;
        }
    }
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        if (food[i] == n)
            ans++;
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,ans,a[N],b[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
	int a=read(),b=read(),c=read();
	swap(a,b);
	swap(a,c);
	cout<<a<<" "<<b<<" "<<c;
	return 0;
}


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

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  x -= a;
  int i;
  for(i = 0; 0 < x; ++i) {
    x -= b;
  }
  if(x < 0) {
    x += b;
  }
  cout << x << endl;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        for (int i = 0; i < M; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        System.out.println( solve(N, M, A, B) );
    }

    private static String solve(int N, int M, int[] A, int[] B) {
        Set<Integer> from_1 = new HashSet<>();
        for (int i = 0; i < M; i++) {
            int a = A[i];
            int b = B[i];

            if( a == 1 ) {
                from_1.add(b);
            } else if( b == 1 ) {
                from_1.add(a);
            }
        }

        for (int i = 0; i < M; i++) {
            int a = A[i];
            int b = B[i];

            if( a == N && from_1.contains(b) ) return "POSSIBLE";
            if( b == N && from_1.contains(a) ) return "POSSIBLE";
        }
        return "IMPOSSIBLE";
    }
}


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

int Cnt(ll t) {
	int cnt = 0;
	while(t) {
		cnt++;
		t /= 10;
	}
	return cnt;
}

int main() {
	int minT = 13;
	cin >> n;
	for(ll i = 1; i <= sqrt(n); i++) {
		if(n % i) continue;
		else {
			int t1 = Cnt(i), t2 = Cnt(n / i);
			ans = max(t1, t2);
			minT = min(minT, ans);
		}
	}
	cout << minT << endl;
}

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

int main() {
    int n, max, min;
    cin >> n;
    cin >> max;
    min = max;

    for(int i = 1; i < n; ++i) {
        int a;
        cin >> a;
        if(a < min) min = a;
        if(a > max) max = a;
    }
    cout << max - min << endl;
}

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

constexpr int D = 365;
constexpr int T = 26;
int c[D];
int s[D][T];

int maxday[T];
int last[T];
int score = 0;
vector<int> ans;

void Input() {
    int tmp; cin >> tmp;
    REP(i, T) cin >> c[i];
    REP(i, D) REP(j, T) cin >> s[i][j];
    return;
}

int CalcMaxDay(int type) {
    int max_profit = s[type][0], argmax = 0;
    REP(day, D) {
        if(s[type][day] > max_profit) {
            max_profit = s[type][day];
            argmax = day;
        }
    }
    return argmax;
}

double lambda2 = 6.1; // 6.0 is better

int FindMaxProfitContest(int day) {
    double max_profit = -1e9;
    int argmax = -1;
    REP(type, T) {
        double profit = 0;
        profit += s[day - 1][type];
        // if(maxday[type] == day) profit += lambda1 * s[day - 1][type];
        profit += lambda2 * c[type] * (day - last[type]);
        if(profit > max_profit) {
            max_profit = profit;
            argmax = type;
        }
    }
    return argmax;
}

void Commit(int day, int contest) {
    ans.push_back(contest);
    last[contest] = day + 1;
    score += s[day - 1][contest];
    REP(type, T) score -= c[type] * (day - last[type]);
    return;
}



void ReverseClimbing() {

}

void Output() {
    for(auto contest: ans) cout << contest + 1 << endl;
    return;
}

int main() {
    Input();
    REP(i, T) maxday[i] = CalcMaxDay(i);
    for(int day = 1; day <= D; day++) {
        int contest = FindMaxProfitContest(day);
        Commit(day, contest);
    }
    Output();
    // cerr << score << endl;
    return 0;
}


Measured memory_bytes: 3676
using System;
using System.Linq;
using System.Collections.Generic;
using static program.Input;
using static program.MyMath;
using static System.Console;

namespace program {
  class Program {
    static void Main()
    {
      var n = ScanInt();
      var s = ScanStr();
      int count =0;
      for(int i=0; i<n-2; i++){
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
          count++;
      }
      WriteLine(count);
    }
  }
  
  static class Input {
    static public int ScanInt() { return int.Parse(Console.ReadLine()); }
    static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
    static public double ScanDouble() { return double.Parse(Console.ReadLine()); }
    static public long ScanLong() { return long.Parse(Console.ReadLine()); }
    static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
    static public int[] ScanIntArray() { return Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); }
    static public uint[] ScanUintArray() { return Console.ReadLine().Split().Select(x => uint.Parse(x)).ToArray(); }
    static public double[] ScanDoubleArray() { return Console.ReadLine().Split().Select(x => double.Parse(x)).ToArray(); }
    static public long[] ScanLongArray() { return Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray(); }
    static public ulong[] ScanUlongArray() { return Console.ReadLine().Split().Select(x => ulong.Parse(x)).ToArray(); }

    static public string ScanStr() { return Console.ReadLine(); }
    static public string[] ScanStrArray() { return ScanStr().Split(); }
  }
  
  static class MyMath {
    public static int GCD(int a, int b) {
        Func<int, int, int> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static long GCD(long a, long b) {
        Func<long, long, long> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static ulong extGCD(ulong a, ulong b, ref ulong x, ref ulong y) {
      if(b==0) {
        x=1; 
        y=0;
        return a;
      }
      var d = extGCD(b, a%b, ref y, ref x);
      y -= a/b *x;
      return d;
    }
    public static int LCM(int a, int b) { return a * b / GCD(a, b); }
    public static long LCM(long a, long b) { return a * b / GCD(a, b); }
  }
}


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

#include <atcoder/all>
typedef long long ll;
#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (ll i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (ll i = ((ll)(n)-1); i >= 0; --i)
#define rreps(i, n) for (ll i = ((ll)(n)); i > 0; --i)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define repc2(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
using namespace atcoder;

int op(int a, int b) {
    return max(a, b);
}

int e() {
    return -1;
}

int target;

bool f(int v) {
    return v < target;
}

int n, q;
int main() {
    cin >> n >> q;
    vector<int> v(n + 1);
    reps(i, n) cin >> v[i];
    segtree<int, op, e> st(v);

    rep(i, q) {
        int c;
        cin >> c;
        if (c == 1) {
            int x, v;
            cin >> x >> v;
            st.set(x, v);
        } else if (c == 2) {
            int l, r;
            cin >> l >> r;
            cout << st.prod(l, r + 1) << endl;
        } else {
            int x;
            cin >> x >> target;
            int res = st.max_right<f>(x);
            cout << res << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 6196
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class MyStack {
    // s[0] は常に空
    int size = 81;
    String[] s;
    int top;

    MyStack() {
        s = new String[size];
        top = 0;
    }

    void push(String str) {
        s[++top] = str;
    }

    String pop() {
        return s[top--];
    }

    double eval() {
        String x = pop();
        if (isNumber(x)) {
            return Integer.parseInt(x);
        }

        double a = eval();
        double b = eval();

        switch (x) {
        case "+":
            return a + b;
        case "-":
            return b - a;
        case "*":
            return a * b;
        case "/":
            return b / a;
        }
        return 0;
    }

    boolean isNumber(String x) {
        try {
            Integer.parseInt(x);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        while ((line = br.readLine()) != null) {
            MyStack ms = new MyStack();
            String[] input = line.split(" ");
            for (String s : input) {
                ms.push(s);
            }

            while (ms.top != 1) {
                ms.push(String.valueOf(ms.eval()));
            }

            System.out.printf("%.6f%n", Double.parseDouble(ms.pop()));
        }

    }
}


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

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()

#define uint8_t unsigned char
#define uint16_t unsigned short
#define uint32_t unsigned int
#define uint64_t unsigned long long

#define int8_t signed char
#define int16_t signed short
#define int32_t signed int
#define int64_t signed long long



using namespace std;
// #define PI 3.14159265358979323846
// cout << fixed << setprecision(20);
int main(int argc, char const* argv[])
{
    int x, t, n;
    cin >> n >> x >> t;
  	int time = ceil(n/double(x))*t;
    cout << time << endl;
    return 0;
}










Measured memory_bytes: 3564
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        Integer N = sc.nextInt();
        Integer M = sc.nextInt();
        Integer X = sc.nextInt();

        Integer[] C = new Integer[N];
        Integer[][] A = new Integer[N][M];

        for (int i = 0; i < N; i++) {
            C[i] = sc.nextInt();
            for (int j = 0; j < M; j++){
                A[i][j] = sc.nextInt();
            }
        }

        boolean isCleared = false;
        int minCost = Integer.MAX_VALUE;
        int iterationNum = (int) Math.pow(2, N);
        for (int i = 0; i < iterationNum; i++){
            String binaryString = String.format("%" + String.valueOf(N) + "s", Integer.toBinaryString(i));
			binaryString = binaryString.replace(" ", "0");

            int sumCost = 0;
            Integer[] levels = new Integer[M];
            for (int m = 0; m < M; m++) {
                levels[m] = 0;
            }

            for (int n = 0; n < N; n++) {
                if (binaryString.substring(n, n+1).equals("1")) { 
                    sumCost += C[n];
                    for (int m = 0; m < M; m++) {
                        levels[m] += A[n][m];
                    }
                }
            }

            boolean isSatisfied = true;
            for (int m = 0; m < M; m++) {
                if (levels[m] < X) {
                    isSatisfied = false;
                    break;
                }
            }

            if (isSatisfied) {
                isCleared = true;
                if (sumCost < minCost) {
                    minCost = sumCost;
                }
            }
        }
    
        if (isCleared) {
            System.out.println(minCost);
        } else {
            System.out.println(-1);
        }
    }
}

Measured memory_bytes: 55688
#include<iostream>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

const int N = 100;

int x[N][N];
int y[N][N];
int vis[N][N];


int ans;
void dfs(int yy,int xx,int sy,int sx,int now){
  if (vis[yy][xx]){
    if (vis[yy][xx]== now)ans++;
    return;
  }
  vis[yy][xx]=now;
  dfs(y[yy][xx],x[yy][xx],sy,sx,now);
}

main(){
  int n;
  while(cin>>n && n){
    ans=0;
    rep(i,n){
      rep(j,n)cin>>x[i][j]>>y[i][j];
    }
    rep(i,n)rep(j,n)vis[i][j]=false;

    int now=1;
    rep(i,n){
      rep(j,n)if (!vis[i][j]){
	dfs(i,j,i,j,now++);
      }
    }
    cout << ans << endl;

  }
  return false;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ld = long double;
const int maxn = 303, mod = 119<<23|1;
int n, pw[maxn];
vector<array<int, 2>> v;
bool onl(array<int, 2> a, array<int, 2> b, array<int, 2> c) {
	if(a[1] == b[1] || b[1] == c[1]) return a[1] == b[1] && b[1] == c[1];
	ld r1 = ld(a[0]-b[0])/ld(a[1]-b[1]);
	ld r2 = ld(c[0]-b[0])/ld(c[1]-b[1]);
	ld r3 = ld(a[0]-c[0])/ld(a[1]-c[1]);
	return fabs(r1-r2) < 1e-8 && fabs(r3-r2) < 1e-8;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	pw[0] = 1;
	for(int i = 1; i < maxn; i++) pw[i] = (pw[i-1]+pw[i-1])%mod;
	cin >> n;
	v.resize(n);
	for(auto &i : v) cin >> i[0] >> i[1];
	sort(all(v));
	int ans = pw[n];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < i; j++) {
			int c = 0;
			array<int, 2> mn = v[j];
			array<int, 2> mx = v[i];
			for(auto &[x, y] : v) if(v[i] == array<int, 2>{x, y} || v[j] == array<int, 2>{x, y} || onl(v[i], v[j], {x, y})) {
				c++;
				mn = min(mn, {x, y});
				mx = max(mx, {x, y});
			}
			if(v[j] != mn || v[i] != mx) continue;
			//cout << v[i][0] << " " << v[i][1] << " | " << v[j][0] << " " << v[j][1] << " | " << pw[c] - c - 1 << endl;
			ans = (mod + ans - (pw[c] - c - 1))%mod;	
		}
	ans = (mod + ans - n - 1)%mod;
	cout << ans << '\n';
}


Measured memory_bytes: 3548
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
#include <map>
#include <numeric>
#include <string>
#include <queue>
using namespace std;
typedef long long int ll;

bool can[101][101];

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

int num[6][2][4]=
{{{2,5,4,3},{5,2,3,4}},
{{1,6,3,4},{6,1,4,3}},
{{2,5,1,6},{5,2,6,1}},
{{2,5,6,1},{5,2,1,6}},
{{1,6,4,3},{6,1,3,4}},
{{2,5,3,4},{5,2,4,3}}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w; cin >> h >> w;
    char fi[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> fi[i][j];
        }
    }
    can[0][0]=1;
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(0,0),make_pair(6,0)));
    while(q.size()){
        auto p=q.front(); q.pop();
        int x=p.first.first,y=p.first.second;
        for(int i=0;i<4;i++){
            int nx=dx[i]+x,ny=dy[i]+y;
            if(0<=nx&&nx<h&&0<=ny&&ny<w){
                if(can[nx][ny])continue;
                if(fi[nx][ny]=='#')continue;
                if(fi[nx][ny]-'0'!=num[p.second.first-1][p.second.second][i])continue;
                can[nx][ny]=1;
                int v=fi[x][y]-'0';
                int w=fi[nx][ny]-'0';
                int t=0;
                if(i==0||i==1){
                    if(v>=4&&i==1)t=1;
                    if(v<=3&&i==0)t=1;
                }
                else{
                    if(num[p.second.first-1][p.second.second][0]>=4)t=1;
                }
                q.push(make_pair(make_pair(nx,ny),make_pair(fi[nx][ny]-'0',t)));
            }
        }
    }
    if(can[h-1][w-1]){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}




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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

#define endl '\n'

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;


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

//#define int ll


const int N = 2e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 2e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P2 = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-6;
const double PI = acos(-1.0);


template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
bool prime(int n) {
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){return 0;}
    }return 1;}
ll bp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int p[N] , sum[N] , dp[N];

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> p[i];
    }
    int cur = 1 , last = 1;
    sum[p[1]] = 1;
    for(int i = 2; i <= n; i ++) {
        if(p[i] != p[i-1]) {
            cur += sum[p[i]];
            if(cur > mod)
                cur -= mod;
            sum[p[i]] += last;
            if(sum[p[i]] > mod)
                sum[p[i]] -= mod;
        }
        last = cur;
    }
    cout << cur;
}


signed main() {
    ios;
    int tt = 1;
//    cin >> tt;
    while(tt--) {
        solve();
    }
    return 0;
}
/*

0 0 0
0 0 1
0 1 0

0 1 1
1 0 1
1 0 0
1 1 0
1 1 1

*/


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
string s,t;
int n;
int main(void){
    cin>>s>>t;
    n=s.size();
    s+=s;
    for(int i=0;i<n;i++){
        if(s.substr(i,n)==t){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, x;
    cin >> N >> x;
    int a[N];
    for (int i = 0; i < N; i++) cin >> a[i];

    sort(a, a + N);
    int res = 0;
    int i = 0;

    for (int i = 0; i < N; i++)
    {
        if (i == N-1 && x != a[i])
        {
            break;
        }
        if (x < a[i])
        {
            break;
        }
        x -= a[i];
        res++;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "3 2 6" ].parse.expand.solve == 1 );
	assert( [ "3 1 3" ].parse.expand.solve == 0 );
	assert( [ "5 10 1" ].parse.expand.solve == 4 );
}



import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto wab = input.front.split.to!( long[] );
	return tuple( wab[ 0 ], wab[ 1 ], wab[ 2 ] );
}

auto solve( long w, long a, long b )
{
	auto d = ( a - b ).abs;
	if( d <= w ) return 0;
	else         return d - w;
}


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

vector<ll> v;

ll check(ll b) {
    ll ret = 0;
    for(int i = 0; i < v.size(); ++i) {
        ret += abs(v[i] - (b+1+i));
    }
    return ret;
}

ll ternarySearch(ll low, ll high) {
    ll ret = 10000000000000000LL;
    while((high - low) > 2) {
        ll mid1 = low + (high - low) / 3;
        ll mid2 = high - (high - low) / 3;
        ll cost1 = check(mid1);
        ll cost2 = check(mid2);
        if(cost1 < cost2) {
            high = mid2;
            //cerr << cost1 << " :: " << mid1 << endl;
            ret = min(cost1, ret);
        }
        else {
            low = mid1;
            //cerr << cost2 << " :: " << mid2 << endl;
            ret = min(cost2, ret);
    }}
    for(int i = low; i <= high; ++i) {
        //cerr << i << " " << check(i) << endl;
        ret = min(ret, check(i));
    }
    return ret;
}

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

    v.resize(n);
    for(int i= 0; i < n; ++i)
        scanf("%lld", &v[i]);

    cout << ternarySearch(-2000000009, 20000000009) << endl;
    return 0;
}

Measured memory_bytes: 1792
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
//#define double long double

using namespace std;

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

const int MOD = 1e9 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;

vector<int>v[100010];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N, M; cin >> N >> M;
	REP(i, N) {
		int A, B; cin >> A >> B;
		v[A].pb(B);
	}
	priority_queue<int>que;
	ll ans = 0;
	FOR(i, 1, M + 1) {
		for (auto x : v[i]) {
			que.push(x);
		}
		if (que.empty())continue;
		int x = que.top(); que.pop();
		ans += x;
	}
	print(ans);
 }



Measured memory_bytes: 5760
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
#include <iomanip>
#include <limits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;

#define INF 1e+9
#define MAX_V 300

struct edge {
    int to;
    int cost;
};
using P = pair<ll, ll>;

ll func(ll s){
  ll ans=0;
  for(ll x=1;x<102;x++){
    for(ll y=1;y<102;y++){
      for(ll z=1;z<102;z++){
        ll tmp=x*x+y*y+z*z+x*z+y*z+x*y;
        if(tmp==s){
          ans++;
          break;
        }
        if(tmp>s){
          break;
        }
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}
int main(){
  ll n;cin>>n;
  for(ll i=1;i<=n;i++){
    func(i);
  }
}

Measured memory_bytes: 3180
#include <iostream>
#include <string>

using namespace std;

int main(){
  string a,b,ans;
  int i=0,j=0;
  cin>>a>>b;
  int A=a.length();
  int B=b.length();
  for(int k=0;k<A+B;k++){
    if(k%2==0){
      ans.push_back(a[i]);
      i++;
    }else if(k%2==1){
      ans.push_back(b[j]);
      j++;
    }
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define f(i,a,b) for(ll i=a;i<b;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define MAX 1e9
 
ll modpow(ll base, ll exp, ll modulus) {base %= modulus;ll result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}
const ld pi=acos(-1);
 
int main(){
    IOS;
    ll n;cin>>n;
    ll a[15][15];
    memset(a,0,sizeof(a));
    f(i,1,n+1){
        string x=to_string(i);
        ll d=x.size();
        ll f=x[0]-'0';
        ll l=x[d-1]-'0';
        a[f][l]++;
    }
    ll ans=0;
    f(i,1,10){
        f(j,1,10){
            ll one=a[i][j];
            ll two=a[j][i];
            ans+=(one*two);
        }
    }
    cout<<ans;
    return 0;
}   

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;


int ds(int v) {
	int ret=0;
	while(v) {
		ret+=v%10;
		v/=10;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int mi=101010;
	for(int A=1;A<=N-1;A++) {
		mi=min(mi,ds(A)+ds(N-A));
	}
	cout<<mi<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(int argc, char const *argv[])
{
	int n, m; cin >> n >> m;
	vector<int> x(m); rep(i, m) cin >> x[i];

	if (n >= m) {
		printf("0\n");
		return 0;
	}

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

	vector<int> b(m - 1);
	rep(i, m - 1) b[i] = x[i + 1] - x[i];
	sort(b.begin(), b.end()); reverse(b.begin(), b.end());

	int ma = 0;
	rep(i, n - 1) ma += b[i];
	cout << accumulate(b.begin(), b.end(), 0) - ma << endl;

	return 0;
}


Measured memory_bytes: 1024
let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n

type seat = Male | Female

let read_seat i =
  Printf.printf "%d\n" i;
  let str = read_line () in
  match str with
    | "Vacant" -> exit 0
    | "Male" -> Male
    | "Female" -> Female
    | _ -> failwith "input format error"

let rec loop (l, ls) (r, rs) =
  let mid = (l + r) / 2 in
  let mids = read_seat mid in
  if (mid - l + 1) mod 2 = 0 then 
    if mids = ls then loop (l, ls) (mid, mids)
    else loop (mid, mids) (r, rs)
  else
    if mids = ls then loop (mid, mids) (r, rs)
    else loop (l, ls) (mid, mids)

let () = loop (0, read_seat 0) (n - 1, read_seat (n - 1))

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

struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

int main() {

	int n, q;
	cin >> n >> q;

	UnionFind uni(n);
	
	for(int i = 0; i < q; ++i){
		int order, x, y;
		cin >> order >> x >> y;
		
		if(order == 0){
			uni.merge(x, y);
		}else{
			cout << uni.same(x, y) << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3132
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, M, A, B;
	int ans = 0;
	bool flag = true;
	vector<int> D, T;
	
	cin>>N>>M>>A>>B;
	
	D.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>D[i];
		if(flag && D[i] >= A) T.push_back(D[i]);
		else flag = false;
	}
	
	ans = T.size();
	
	if(N - T.size() < M){
		for(int i = T.size() - 1; i >= 0; i--){
			if(T[i] <= B) ans--;
			else break;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 3244
import math
n, a, b = map(int, input().split(" "))
mod_num = 10**9 + 7

# n, aは正整数(n >= a), pは素数
def comb_mod(n, a, p):
  X = 1
  for num in range(n, n-a, -1):
    X *= num
    X %= p
  Y = math.factorial(a) % p
  return (X * (pow(Y, p-2, p))) % p

print((pow(2, n, mod_num) - (comb_mod(n, a, mod_num) + comb_mod(n, b, mod_num) + 1)) % mod_num)

Measured memory_bytes: 5444
#D
n = int(input())
s = input()
s_l = list(s)

a = s_l.count('R') * s_l.count('G') * s_l.count('B')
cnt = 0
#i,j,kがそれぞれ異なり、j-i = k-jであるものを求める
for i in range(n-2):
    for j in range(i,n-1):
        if 2*j - i < n:
            if s_l[i] != s_l[j] and s_l[i] != s_l[2*j-i] and s_l[j] != s_l[2*j-i]:
                cnt += 1
                
print(a - cnt)

Measured memory_bytes: 73964
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<((ll)n);i++)
#define rep1(i,n) for(ll i=1;i<=((ll)n);i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define meow(a) cout<<a<<" meow\n";
typedef pair<long long,long long> pii;
const ll maxn=200005;
const ll MOD=998244353;
double mypow(ll a,ll b){
	double res=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a;

		b>>=1;
	}
	return res;
}
ll n;
set<ll> s;

int main()
{
    //IOS;
    while(cin>>n)
    {
        s.clear();
        ll countt=0;
        while(!s.count(n))
        {
            s.insert(n);
            if(n%2==0) n=n/2;
            else n=3*n+1;
            countt++;
        }
        cout<<countt+1<<"\n";
    }
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W)->np.ndarray:
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N, K = ints()
A = read_matrix(N, N)


# from numba import njit


# @njit('i8[:,:](i8[:,:],i8[:,:])', cache=True)
def matmul_mod(X: np.ndarray, Y: np.ndarray)->np.ndarray:
    MOD = 10**9 + 7
    # return X @ Y
    ret = np.empty((X.shape[0], Y.shape[1]), dtype=np.int64)
    for i in range(X.shape[0]):  # Xの行
        for j in range(Y.shape[1]):  # Yの列
            tmp = (X[i, :] * Y[:, j]) % MOD
            ret[i, j] = tmp.sum() % MOD
    return ret


def matmul_mod_try(X: np.ndarray, Y: np.ndarray)->np.ndarray:
    MOD = 10**9 + 7
    # return X @ Y
    ret = np.empty((X.shape[0], Y.shape[1]), dtype=np.int64)
    YT = Y.T
    for i in range(X.shape[0]):  # Xの行
        Xi = X[i, :]
        tmp = (YT * Xi) % MOD
        ret[i, :] = tmp.sum(1) % MOD
    return ret


def matmul_mod_fast(X: np.ndarray, Y: np.ndarray)->np.ndarray:
    MOD = 10**9 + 7
    X3d = X[:, :, np.newaxis].transpose(0, 2, 1)
    Y3d = Y[:, :, np.newaxis].transpose(2, 1, 0)
    return ((X3d * Y3d) % MOD).sum(2) % MOD


A_double = np.asanyarray(A, dtype=np.int64)
ans = np.eye(N, dtype=np.int64)
for j in range(int(K).bit_length()):
    if (K >> j) & 1:
        # t1, t2 = matmul_mod(ans, A_double), matmul_mod_try(ans, A_double)
        # assert np.array_equal(t1, t2), (t1, t2)
        ans = matmul_mod_fast(ans, A_double)
    A_double = matmul_mod_fast(A_double, A_double)

print(ans.sum() % MOD)


Measured memory_bytes: 29104
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));

int main() {

	double t, x;
	cin >> t >> x;

	cout << fixed << setprecision(10) << t / x << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int a,b,h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int a, b;

  cin >> a >> b;

  cout << abs(a-b) << endl;
  
  return 0;
}



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

using namespace std;

int main()
{
    int a[3][3],b[3][3]={0};
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        cin >> a[i][j] ;
    }
    int n,x;
    cin >>n;
    int brr[n];
    for(int i=0;i<n;i++)
    cin >> brr[i];
    for(int i=0;i<n;i++)
    {
        
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            if(a[j][k]==brr[i])
            b[j][k]=1;
        }
    }
    int count=0;int p=1;
    for(int i=0;i<3;i++ )
    {
        p=1;
        for(int j=0;j<3;j++)
            p=p&b[i][j];
            if(p==1)
            count++;
    }
     for(int i=0;i<3;i++ )
    {
        p=1;
        for(int j=0;j<3;j++)
            p=p&b[j][i];
            if(p==1)
            count++;
    }
    if(b[0][0]&b[1][1]&b[2][2]==1)
    count++;
    if(b[0][2]&b[1][1]&b[2][0]==1)
    count++;
    if(count)
    cout << "Yes";
    else
    {
        cout << "No";
    }
    
    return 0;
}

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

int main() {
    int n;
    ll ans=0;
    cin>>n;
    vector<ll> a(3*n);
    rep(i,3*n) cin>>a[i];
    sort(a.begin(),a.end());
    for (int i=n; i<3*n; i++) {
        if ((i-n)%2==0) ans+=a[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2688
// 0202_AtBosssExpense.cpp
//
#include <bits/stdc++.h>
using namespace std;
const int MAX_X = 1000001;
const int MAX_N =30;
bool prime[MAX_X], dp[MAX_X];
int v[MAX_N];
int n, x;
void table() {
  fill(prime,prime+MAX_X,1);

  for(int i=2;i*i<MAX_X;++i)
    if(prime[i])
      for(int j=i*i;j<MAX_X;j+=i)
        prime[j]=0;
}
void solve() {
  fill(dp,dp+MAX_X,0);
  dp[0]=1;
  for(int i=0;i<=x;++i)
    for(int j=0;j<n;++j)
      //if(v[j]<=i&&dp[i-v[j]]) dp[i]=1;
      if(i+v[j]<=x&&dp[i]) dp[i+v[j]]=1;

  for(int i=x;i>0;--i) {
    if(prime[i]&&dp[i]) {
      cout << i << endl;
      return;
    }
  }
  cout << "NA" << endl;
}
int main() {
  table();
  while(cin >> n >> x && n && x) {
    for(int i=0;i<n;++i) cin >> v[i];
    solve();
  }
  return 0;
}



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

int main(){
  int n,timelim;
  cin>>n>>timelim;
  int cost[n],time[n];
  int mincost=10000;
  for(int i=0;i<n;i++){
    cin>>cost[i]>>time[i];
    if(time[i]<=timelim){
      mincost=min(mincost,cost[i]);
    }
  }
  if(mincost==10000){
    cout<<"TLE"<<endl;
  }else{
    cout<<mincost<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
N,K,C = map(int, input().split())
S = input()
w = []
for i in range(len(S)):
   if S[i]=="o":
      w.append(i)
# print(w)
# early date
early = []
tmpwd = -1
for i in range(len(w)):
   if len(early) >= K:
      continue
   if tmpwd<0:
      tmpwd = w[i]
   elif w[i]>tmpwd+C:
      tmpwd = w[i]
   else:
      continue
   early.append(w[i])
# print(early)

# later date
late = []
tmpwd = -1
for i in reversed(range(len(w))):
   if len(late)>=K:
      continue      
   if tmpwd < 0:
      tmpwd = w[i]
   elif w[i] < tmpwd-C:
      tmpwd = w[i]
   else:
      continue
   late.append(w[i])

wd = set(early) & set(late)
early.sort()
late.sort()
# print(early,late)
for i in range(K):
   if early[i]==late[i]:
      print(early[i]+1)

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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


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

    vector<string> a(N);
    rep(i,N) cin >> a[i];
    vector<string> b(M);
    rep(i,M) cin >> b[i];

    rep(i, N-M+1)
    {
        rep(j, N-M+1)
        {
            vector<string> templete;

            // ここからテンプレ切り出し
            REP(I, i, M+i)
            {
                string tmp = "";
                REP(J, j, M+j)
                {
                    tmp += a[I][J];
                }
                templete.push_back(tmp);
            }
            //rep(I,templete.size()) cout << templete[I] << endl;
            //cout << endl;
            if( b == templete )
            {
                cout << "Yes" << endl;
                return 0;
            }
        } 
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  double d;
  while(cin >> d){
    double a=d,b=0;
    for(int i=0;i<10;i++){
      b+=a;
      if(i%2==1) a/=3.0;
      else a*=2.0;
      //cout << a << endl;
    }
    //cout << b << endl;
    printf("%.10lf\n",b);
  }
}

Measured memory_bytes: 1236
from collections import defaultdict
N = int(input())
dic = defaultdict(int)
for i in range(N):
    s = input()
    dic[s]+=1
m = 0
for i in dic:
    m = max(m, dic[i])
ans = []
for i in dic:
    if dic[i]==m:
        ans.append(i)
ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 147916