akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		DSU uf = new DSU(n);
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]) - 1;
			int b = Integer.parseInt(sa[1]) - 1;
			uf.merge(a, b);
		}
		br.close();

		System.out.println(uf.num() - 1);
	}
}

/**
 * Disjoint Set Union（Union Find）
 */
class DSU {
	private int n;
	private int[] parentOrSize;
	private int num;

	/**
	 * n頂点0辺の無向グラフを作る。<br>
	 * O(n)
	 * 
	 * @param n 頂点数
	 */
	public DSU(int n) {
		this.n = n;
		this.parentOrSize = new int[n];
		Arrays.fill(parentOrSize, -1);
		num = n;
	}

	/**
	 * 辺(a, b)を足す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @param b 頂点番号（0≦b＜n）
	 * @return 代表元
	 */
	int merge(int a, int b) {
		assert 0 <= a && a < n : "a=" + a;
		assert 0 <= b && b < n : "b=" + b;

		int x = leader(a);
		int y = leader(b);
		if (x == y) {
			return x;
		}
		if (-parentOrSize[x] < -parentOrSize[y]) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		parentOrSize[x] += parentOrSize[y];
		parentOrSize[y] = x;
		num--;
		return x;
	}

	/**
	 * 頂点a, bが連結かどうか。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @param b 頂点番号（0≦b＜n）
	 * @return true：連結　false：非連結
	 */
	boolean same(int a, int b) {
		assert 0 <= a && a < n : "a=" + a;
		assert 0 <= b && b < n : "b=" + b;

		return leader(a) == leader(b);
	}

	/**
	 * 頂点aの属する連結成分の代表元を返す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @return 代表元
	 */
	int leader(int a) {
		assert 0 <= a && a < n : "a=" + a;

		if (parentOrSize[a] < 0) {
			return a;
		} else {
			return parentOrSize[a] = leader(parentOrSize[a]);
		}
	}

	/**
	 * 頂点aの属する連結成分の要素数を返す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @return 要素数
	 */
	int size(int a) {
		assert 0 <= a && a < n : "a=" + a;

		return -parentOrSize[leader(a)];
	}

	/**
	 * 連結成分の数を返す。<br>
	 * O(1)
	 * 
	 * @return 連結成分数
	 */
	int num() {
		return num;
	}

	/**
	 * グラフを連結成分に分けた情報を返す。<br>
	 * O(n)
	 * 
	 * @return 「1つの連結成分の頂点番号のリスト」のリスト
	 */
	List<List<Integer>> groups() {
		int[] leaderBuf = new int[n];
		int[] groupSize = new int[n];
		for (int i = 0; i < n; i++) {
			leaderBuf[i] = leader(i);
			groupSize[leaderBuf[i]]++;
		}
		List<List<Integer>> result = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			result.add(new ArrayList<>(groupSize[i]));
		}
		for (int i = 0; i < n; i++) {
			result.get(leaderBuf[i]).add(i);
		}
		result.removeIf(List::isEmpty);
		return result;
	}
}


Measured memory_bytes: 54184
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  ll n;
  string s;
  ll ans = 0;
  cin >> n >> s;
  for(int i=0;i<n-2;i++){
    if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C'){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
set<char>s;
char c;
for(int i=0;i<n;i++){
    cin>>c;
    s.insert(c);
}
if(s.size()==4)cout<<"Four";
else cout<<"Three";
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
int sum1,sum2;
scanf("%d %d %d %d",&a,&b,&c,&d);
sum1=a*b;
sum2=c*d;
if(sum1>=sum2)
cout<<sum1;
if(sum1<sum2)
cout<<sum2;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stdio.h>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
#include <map>
#define FORi(N) for(int i=0;i<N;++i)
#define FORj(N) for(int j=0;j<N;++j)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll gcd(ll m,ll n){
  if(n==0)return abs(m);
  return(gcd(n,m%n));
}
void putYN(bool b){
  if(b){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

int main(){
  ll S;
  cin>>S;
  ll u=S/100;
  ll d=S%100;
  bool uism = (u>0&&u<=12);
  bool dism = (d>0&&d<=12);
  if(uism&&dism){
    cout<<"AMBIGUOUS"<<endl;
  }else if(uism&&!dism){
    cout<<"MMYY"<<endl;
  }else if(!uism&&dism){
    cout<<"YYMM"<<endl;
  }else{
    cout<<"NA"<<endl;
  }
  return 0;
}


Measured memory_bytes: 384
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final long MIN = (long)-1e16;
		int N = sc.nextInt();
		int[] a = new int[N];
		for(int i=0; i<N; i++) {
			a[i] = sc.nextInt();
		}

		long[][][] dp = new long[N+1][3][2];
		for(int i=0; i<=N; i++)
			for(int j=0; j<3; j++)
				dp[i][j][0] = dp[i][j][1] = MIN;
		if(N%2==0) {
			dp[0][1][0] = 0;
		} else {
			dp[0][2][0] = 0;
		}
		
		for(int i=0; i<N; i++) {
			dp[i+1][0][0] = Math.max(dp[i+1][0][0], dp[i][1][0]);
			dp[i+1][1][0] = Math.max(dp[i+1][1][0], dp[i][2][0]);
			dp[i+1][0][0] = Math.max(dp[i+1][0][0], dp[i][0][1]);
			dp[i+1][1][0] = Math.max(dp[i+1][1][0], dp[i][1][1]);
			dp[i+1][2][0] = Math.max(dp[i+1][2][0], dp[i][2][1]);

			dp[i+1][0][1] = Math.max(dp[i+1][0][1], dp[i][0][0] + a[i]);
			dp[i+1][1][1] = Math.max(dp[i+1][1][1], dp[i][1][0] + a[i]);
			dp[i+1][2][1] = Math.max(dp[i+1][2][1], dp[i][2][0] + a[i]);
		}
		long ans = MIN;
		for(int i=0; i<3; i++) {
			for(int j=0; j<2; j++) {
				ans = Math.max(ans, dp[N][i][j]);
			}
		}
		System.out.println(ans);
		
		sc.close();
	}

}


Measured memory_bytes: 74092
N,M = map(int,input().split())
PY = [[int(py) for py in input().split()] for _ in range(M)]

for i in range(1,M+1):
    PY[i-1].append(i)

PY.sort(key=lambda x:x[1])

count = [1 for _ in range(N)]

ans = []

for cell in PY:
    row = '{0:06d}'.format(cell[0]) + '{0:06d}'.format(count[cell[0]-1])
    ans.append([row,cell[2]])
    count[cell[0]-1] += 1


ans.sort(key=lambda x:x[1])

for row in ans:
    print(row[0])

Measured memory_bytes: 43732
// Problem : C - Average Length
// Contest : AtCoder - AtCoder Beginner Contest 145
// URL : https://atcoder.jp/contests/abc145/tasks/abc145_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

db dist(int x1, int y1, int x2, int y2){
    return (db)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void solve(){
    int n;
    cin>>n;
    vi x(n),y(n),perm(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
        perm[i] = i;
    }
    db ans = 0;
    int tot = 0;
    do{
        db cur = 0;
        for(int i=1;i<n;i++){
            cur += dist(x[perm[i]],y[perm[i]],x[perm[i-1]],y[perm[i-1]]);
        }
        ans += cur;
        tot++;
    } while(next_permutation(all(perm)));
    cout<<fixed<<setprecision(10)<<ans/tot<<endl;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3812
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

//for loop関係
#define rep(i,a,n) for(int i=(a);i<(n);++i)
#define repe(i,a,n) for(int i=(a);i<=(n);++i)
#define rrep(i,n,a) for(int i=(n);n>(a);--i)
#define rrepe(i,n,a) for(int i=(n);n>=(a);--i)

//略記
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ENDL << "\n"

using ll = long long;
using P = pair<int,int>;
using itn = int;

//定数
const int INF = 1<<30;
const ll MOD = 1000000007;
const long double PI =(acos(-1));

//Degree <-> Radian
double toRad(double d){ double rad; rad=d*PI/180; return rad; }
double toDegree(double rad){ double d; d=rad*180/PI; return d; }
//The least common multiple : lcm
ll lcm(int a,int b){ return a*b/__gcd(a,b); }
//素数判定
bool isPrime(int n){
    int i; 
    if(n<2) return 0;
    else if(n==2) return 1;
    if(n%2==0) return 0;
    for(i=3;i*i<=n;i+=2) if(n%i==0) return 0;
    return 1;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x,y,z;
    cin >> x >> y >> z;
    swap(x,y);
    swap(x,z);
    cout << x <<" " << y <<" " << z ENDL;
    
    return 0;
}

Measured memory_bytes: 3612
#include<iostream>
using namespace std;
int main(){
  int n,i,j,ans=0;
  cin >> n;
  for(i=1;i<=n;i=i+2){
    int count=0;
    for(j=1;j<=i;j++){
      if(i%j==0){
        count++;
      }
    }
    if(count==8){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define rev(x) reverse(x.begin(),x.end())

int main() {
	int n, k; cin >> n >> k;
	vector<int> l(n); rep(i, 0, n) cin >> l[i];

	int ans = 0;
	SORT(l); rev(l);
	rep(i, 0, k) ans += l[i];

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
using System;    
     
class sample14{    
    static void Main(string[] args){
        
        double r = double.Parse( Console.ReadLine());
        double area = r * r*  Math.PI;
        double around = r * 2* Math.PI;
        
        //バリデーション
        if(r< 0 || r >= 10000 ){
            
                    Console.WriteLine("入力した値は範囲外です。");
                    Environment.Exit(0);
        } 
            
        Console.WriteLine("{0:f6} {1:f6}",area,around);
    }    
}  



Measured memory_bytes: 20012
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    S = INPUT()
    T = INPUT()
    
    cnt = 0
    for s, t in zip(S, T):
        if s != t: cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;

int a, b, c, k;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c >> k;
    cout << min(a, k) - max(0, min(c, k - (a + b))) << "\n";
    return 0;
}


Measured memory_bytes: 3588
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(K: int, X: int):
    if 500 * K >= X:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(K, X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cassert>
#include <cstring>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

int main(void) {
    string s;
    cin >> s;
    s[3] = '8';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <tuple>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

using ll=long long;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<string,int> si;
typedef pair<int,ii> iii;
typedef vector <si> vsi;
typedef vector <ii> vii;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vll> vl2d;
typedef vector <vi> vi2d;
typedef vector <char> vc;
typedef vector <bool> vb;
typedef vector <string> vs;
typedef map <string,vs> msvs;
typedef map <string,int> msi;
typedef map <char,int> mci;
typedef map <int,int> mii;
typedef map <long,long> ml;
typedef map <string,string> mss;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define foreach(x,arr) for(auto& x:arr)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define endl '\n' // Normal `cout << endl` flushes the output every time wich hit performance badly
#define INF 1000000000LL
#define MOD 1000000007
#define deb(x) cout<<#x<<": "<<x<<endl;
#define printArray(arr) for(auto x: arr) { cout<<x<<"\n"; }
#define printMatrix(mat) for(auto x: mat) { cout<<" "; printArray(x); cout<<endl; }
#define printMap(mmap) for(auto p: mmap) { cout<< p.first<<": "<<p.second<<endl; }
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define forch(ch,str) for(char& c : str)
#define FILL(a,b) memset(a,b,sizeof(a))
//Swift related stuff
#define append push_back
#define nil nullptr
#define guard(_condition) if (bool(_condition)){}
#define count size()
#define let const auto
#define var auto
#define startsWith(str) rfind(str, 0)
#define prq priority_queue
#define tostr(argument) to_string(argument)
#define alphabet "abcdefghijklmnopqrstuvwxyz"

void join(const vector<string>& v, char c, string& s) {

   s.clear();

   for (vector<string>::const_iterator p = v.begin();
        p != v.end(); ++p) {
      s += *p;
      if (p != v.end() - 1)
        s += c;
   }
}

unordered_map<int, vector<int>> graph;
int n;
ll mod = 1e9 + 7;

pair<ll, ll> dfs(int v, int p) {
    ll b = 1, w = 1;

    foreach(n, graph[v]) {
        guard(n != p) else {
            continue;
        }
        let child = dfs(n, v);
        w = ((child.first + child.second) * w)%mod;
        b = (child.first * b)%mod;
    }
    return pair<ll,ll>(w, b);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); // Fast input
    
    cin>>n;
    rep(i,0,n-1) {
        int s,d;
        cin>>s>>d;
        graph[s].push_back(d);
        graph[d].push_back(s);
    }
    var res = dfs(1,0);
    cout<<(res.first + res.second)%mod<<endl;
    return 0;
}


Measured memory_bytes: 17652
import java.io.*;
import java.util.*;


public class Main{
	
	public static void main(String[] args){
	
	MyScanner sc = new MyScanner();
	out = new PrintWriter(new BufferedOutputStream(System.out));
	
	/**/
	
	int numberOfRolls = sc.nextInt();
	
	int[][] array = new int[numberOfRolls][2];
	
	for(int i = 0; i < numberOfRolls; i++){
		
		array[i][0] = sc.nextInt();
		array[i][1] = sc.nextInt();
		
	}
	
	for(int i = 0; i <= array.length - 3; i++){
		
		if(array[i][0] == array[i][1] && array[i+1][0] == array[i+1][1] && array[i+2][0] == array[i+2][1]){
			System.out.println("Yes");
			return;
		}
	
		
		
	}
	
	System.out.println("No");
	
	/**/
	 
	 out.close();	
	}
	
	public static PrintWriter out;
	
	public static class MyScanner{
		
		BufferedReader br;
		StringTokenizer st;
		
		public MyScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }

   }
	
}


Measured memory_bytes: 32956
#include <iostream>

#define d 1000000007

using namespace std;

long long mat[1010][1010];	
int h,w;
string s;

int main(){
        cin >> h >> w;
	mat[1][1] = 1;

	//for (int i = 0; i <= h; i++) mat[i][0] = 0;
		
	//for (int i = 0; i <= w; i++) mat[0][i] = 0;

	for (int i = 1; i <= h; i++){
		cin >> s;
		for (int j = 1; j <= w; j++){
			if (i == 1 && j == 1) continue;						
			if (s[j - 1] == '.')
				mat[i][j] = (mat[i - 1][j] + mat[i][j - 1]) % d; 
			if (s[j - 1] == '#')
				mat[i][j] = 0;
			
		}
	}
	
	cout << mat[h][w];

	/*for (int i = 0; i <= h; i++){
		cout << endl;
		for (int j = 0; j <= w; j++)
			cout << mat[i][j] << " ";
	}*/

}

Measured memory_bytes: 8192
#include<iostream>
using namespace std;
int main(){
    int n;
    const int mod=1000000007;
    cin>>n;
    long long res=1;
    for(int i=1;i<=n;i++){
        res*=i;
        res%=mod;
    }
    
    cout<<res<<endl;
    return 0;

}

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

int main() {
    char strS[11] = {};
    char strT[11] = {};
    char strU[11] = {};
    scanf("%s", strS);
    scanf("%s", strT);
    int a, b;
    scanf("%d%d", &a, &b);
    scanf("%s", strU);
    if (strcmp(strS, strU) == 0)
        a--;
    else
        b--;
    printf("%d %d", a, b);
    return 0;
}


Measured memory_bytes: 128
# coding: utf-8
# Your code here!

import numpy as np

N, M = map(int, input().rstrip().split(' '))
A = np.array(sorted(list(map(int, input().rstrip().split(' ')))))

BC = []
for _ in range(M):
    b, c = map(int, input().rstrip().split(' '))
    BC.append([b, c])
BC = sorted(BC, key=lambda x: -x[1])
   
count = 0 
for b, c in BC:
    if A[min(count+b, N-1)] > c:
        for i in range(count, min(count+b, N-1)):
            if A[i] < c:
                A[i] = c
            else:
                break
        break
    else:
        A[count:count+b] = c
    count += b
        
print(sum(A))

Measured memory_bytes: 35784
n, k = map(int, input().split())

class Combination:
    def __init__(self, N=10**6, mod=10**9 + 7):
        self.mod = mod
        self.N = N
        self.fact = [1, 1]  # fact[n] = (n! mod p)
        self.factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
        self.inv = [0, 1]  # factinv 計算用
        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)

    def nCr(self, n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n-r] % self.mod

comb = Combination(2 * 10**5+100)
ans = 0
mod = 10**9 + 7
for ki in range(min(n+1, k+1)):
    ans = ans % mod + (comb.nCr(n, ki) * comb.nCr(n-1, n-ki-1)) % mod
print(ans%mod)



Measured memory_bytes: 28824
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 998244353

// x^n
ll mod_pow(ll x, ll n) {
  if (n == 0) return 1;
  ll res = mod_pow(x * x % MOD, n / 2);
  if (n & 1) res = res * x % MOD;
  return res;
}

// x^{-1}
ll mod_inv(ll x) { return mod_pow(x, MOD - 2); }

vector<ll> fact;
vector<ll> fact_inv;

void init_fact(int n) {
  fact.resize(n + 1);
  fact_inv.resize(n + 1);
  fact[0] = fact_inv[0] = 1;
  for (int i = 0; i < n; ++i) {
    fact[i + 1] = fact[i] * (i + 1) % MOD;
    fact_inv[i + 1] = fact_inv[i] * mod_inv(i + 1) % MOD;
  }
}

ll nCr(ll n, ll r) {
  if (n < r || n < 0 || r < 0) return 0;
  return fact[n] * fact_inv[r] % MOD * fact_inv[n - r] % MOD;
}

ll nPr(ll n, ll r) { return nCr(n, r) * fact[r] % MOD; }

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  init_fact(n);
  ll ans = 0;
  for (int i = 0; i <= k; ++i) {
    ll res = nCr(n - 1, n - 1 - i);
    res = (res * m) % MOD;
    res = (res * mod_pow(m - 1, n - 1 - i)) % MOD;
    ans = (ans + res) % MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6356
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define pll pair<ll,ll>
#define pint pll
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

const int MAX = 510000;
const int MOD = 1e9+7;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll cnt0[100],cnt1[100];

int main(){
  COMinit();
  int n;
  cin >> n;
  ll a[n];
  rep(i,n){
    cin >> a[i];
  }
  rep(dig,61){
    rep(i,n){
      if(a[i] & (1ull << dig))cnt1[dig]++;
      else cnt0[dig]++;
    }
  }
  ll sum=0;
  ll t=1;
  rep(dig,60){
    ll temp=0;
    temp+=(t*((cnt1[dig]*cnt0[dig])%mod))%mod;
    t*=2;
    t%=mod;
    sum+=temp;
    sum%=mod;
  }
  cout << sum << endl;
return 0;}

Measured memory_bytes: 14592
import javax.net.ssl.SSLContext;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));


        String[] input = reader.readLine().split(" ");

        char[] a = input[0].toCharArray();
        char[] b = input[1].toCharArray();
        char[] c = input[2].toCharArray();

        if (a[a.length-1] != b[0] || b[b.length-1] != c[0]) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }

//        PrintWriter writer = new PrintWriter(System.out);
//
//        writer.close();


    }
}


Measured memory_bytes: 22484
X = int(input())

if 400 <= X and X <= 599:
    print(8)
elif 600 <= X and X <= 799:
    print(7)
elif 800 <= X and X <= 999:
    print(6)
elif 1000 <= X and X <= 1199:
    print(5)
elif 1200 <= X and X <= 1399:
    print(4)
elif 1400 <= X and X <= 1599:
    print(3)
elif 1600 <= X and X <= 1799:
    print(2)
elif 1800 <= X and X <= 1999:
    print(1)
else:
    pass


Measured memory_bytes: 9184
import java.util.*;

public class Main
{
	public static void main(String[] args)
    {
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int k = sc.nextInt();
      	int[] arr = new int[n];
      	for(int i = 0; i < n; i++){
        	arr[i] = sc.nextInt();
        }
      	Arrays.sort(arr);
      	int i;
      	for(i = 0; i < n; i++){
        	if(arr[i] >= k){
            	break;
            }
        }
      	System.out.println(n - i);
    }
}

Measured memory_bytes: 48648
def get_char_set(word):
    char_index = {}
    for i, c in enumerate(word):
        if c not in char_index.keys():
            char_index[c] = []
        char_index[c].append(i)
    char_set = set()
    for char_index_list in char_index.values():
        char_set.add(tuple(char_index_list))
    return char_set

s = input()
t = input()

s_char_set = get_char_set(s)
t_char_set = get_char_set(t)
if s_char_set == t_char_set:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 27332
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,char> p2;
void solve(){
	char c;
	cin>>c;
	if(c>='A'&&c<='Z')
	cout<<"A";
	else
	cout<<"a";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll qc=1;
    for(ll i=1;i<=qc;i++)
    solve();
}


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

using namespace std;

int main(){
	
	int a,b;
	
	cin >> a >> b;
	
	for(int i=1;i<3;i++){
		if((a*b*i)%2==1){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
N=int(input())
points=[input().split() for i in range(N)]
import math
def calc_dist(start, end):
    return math.sqrt((int(start[0]) - int(end[0])) ** 2 + (int(start[1]) - int(end[1])) ** 2)

from itertools import combinations, permutations
total_dist = []
for root in permutations(range(N), N):
    dist = 0
    for num in range(len(root)-1):
        dist += calc_dist(points[root[num]], points[root[num+1]])
    total_dist.append(dist)
from statistics import mean
print(mean(total_dist))




Measured memory_bytes: 6500
x, y = map(int, input().split())

crain = int((4 * x - y) / 2)
turtle = int((y - 2 * x) / 2)

if crain >= 0 and turtle >= 0:
    if x == crain + turtle:
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 61640
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto Q = s[1];

    if (N == 1) {
        while (Q--) {
            s = readln.split.map!(to!int);
            auto v = s[0];
            auto w = s[1];
            writeln(min(v, w));
        }
        return;
    }

    while (Q--) {
        s = readln.split.map!(to!int);
        auto v = s[0]-1;
        auto w = s[1]-1;
        while (v != w) {
            if (v > w)
                swap(v, w);
            int q = w % N;
            if (q == 0) q = N;
            w = (w-q) / N;
        }
        writeln(v+1);
    }

}


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if ((A+B) > (C+D)){
    cout << "Left" << endl;
  }
  else if ((A+B) < (C+D)){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
S = 0
for i in range(1, N):
    S += i

Ans = []

if N % 2 == 1:
    for i in range(1, N):
        Ans.append((i, N))
    for i in range(1, N):
        for j in range(i+1, N):
            if j != N-i:
                Ans.append((i, j))
else:
    for i in range(1, N):
        for j in range(i+1, N+1):
            if j != N - i + 1:
                Ans.append((i, j))


print(len(Ans))
for a in Ans:
    print(" ".join(map(str, a)))



Measured memory_bytes: 3700
from heapq import heappush, heappop
from collections import deque
n,m=map(int,input().split())
data=[[] for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m:
        data[a].append([-b,a])
for i in range(1,m+1):
    data[i].sort()
    data[i]=deque(data[i])
h=[]
s=0
for i in range(1,m+1):
    if data[i]:
        heappush(h,data[i].popleft())
    if h:
        d=heappop(h)
        if data[d[1]]:
            heappush(h,data[d[1]].popleft())
        s+=-d[0]
print(s)

Measured memory_bytes: 85020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int N, M, ans, a, b, c, d, e;
string s, t;

int main()
{
    cin >> N;
    cout << (N - 2) * 180 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }



signed main(){

    int N, L, T; cin >> N >> L >> T;
    vec X(N), W(N);
    REP(i, N) cin >> X[i] >> W[i];
    vec Y(N);
    REP(i, N){
        if(W[i] == 1) Y[i] = (X[i] + T) % L;
        else Y[i] = ((X[i] - T) % L + L) % L;
    }
    int p0 = Y[0];
    SORT(Y);

    //0が衝突する回数 
    int n0 = 0;
    REP(i, N){
        if(W[i] == W[0]) continue;
        if(W[0] == 1) n0 += (2 * T - (X[i] - X[0]) - 1 + L) / L;
        else n0 += (2 * T - (X[0] + L - X[i]) + L) / L;
    }
    //cout << n0 << endl;
    if(W[0] == 2) n0 = (N - (n0 % N)) % N;
    int i0 = Lower_bound(Y, p0);
    vec ans(N);
    REP(i, N) ans[(n0 + i) % N] = Y[(i0 + i) % N];

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

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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

#define INF (1<<(4*4-1))
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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

   int T,X;
   cin>>T>>X;
   cout<<1.*T/X;
   return 0;
}


Measured memory_bytes: 256
import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.Set as S

import qualified Data.Array.IO as A
import qualified Control.Monad as C

newtype UnionFind = UnionFind { unwrap :: A.IOArray Int Int }

newUnionFindTree :: Int -> IO UnionFind
newUnionFindTree n = do
    tree <- A.newArray (1,n) 0 :: IO (A.IOArray Int Int)
    C.forM_ [1..n] $ \i -> A.writeArray tree i i
    return $ UnionFind tree

connectRoot :: UnionFind -> Int -> Int -> IO ()
connectRoot (UnionFind tree) a b = do
    a' <- traverseRoot (UnionFind tree) a
    b' <- traverseRoot (UnionFind tree) b
    A.writeArray tree b' a'
 
traverseRoot :: UnionFind -> Int -> IO Int
traverseRoot (UnionFind tree) i = do
    i' <- A.readArray tree i
    if i == i' then return i
               else do
        r <- traverseRoot (UnionFind tree) i'
        -- rootが分かるのでついでに経路圧縮を行う
        A.writeArray tree i r
        return r

main :: IO ()
main = do
    [n, m] <- map read . words <$> getLine :: IO [Int]
    edges <- replicateM m ((\[a,b]->(a,b)) . map (fst . fromJust . B.readInt) . B.words <$> B.getLine) :: IO [(Int, Int)]
    print . sum =<< forM [1..m] (\i -> do
        let edges' = map snd . filter ((i /=) . fst) $ zip [1..] edges
        tree <- newUnionFindTree n
        forM_ edges' $ \(a,b) -> do
            connectRoot tree a b
        s <- S.size <$> foldM (\s i -> (`S.insert` s) <$> traverseRoot tree i) S.empty [1..n]
        return $ if s == 1 then 0 else 1)


Measured memory_bytes: 1020
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::map;
using std::set;
using std::bitset;
using std::vector;
using std::string;
using std::multimap;
using std::multiset;
using std::deque;
using std::queue;
using std::stack;
using std::pair;
using std::iterator;

using std::sort;
using std::stable_sort;
using std::reverse;
using std::max_element;
using std::min_element;
using std::unique;
using std::ios_base;
using std::swap;
using std::fill;

using std::setprecision;
using std::fixed;

long long min(long long a, long long b) {return a < b ? a : b;}
long long min(int a, long long b) {return a < b ? a : b;}
long long min(long long a, int b) {return a < b ? a : b;}
long long min(int a, int b) {return a < b ? a : b;}

long long max(long long a, long long b) {return a > b ? a : b;}
long long max(int a, long long b) {return a > b ? a : b;}
long long max(long long a, int b) {return a > b ? a : b;}
long long max(int a, int b) {return a > b ? a : b;}

#define int long long

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

#define F(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define fi first
#define se second
#define re return
#define all(x) (x).begin(), (x).end()

const int N = 1522220;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const int K = 5;

ll inq(ll x, ll y)
{
    if (y == 0) return 1;
    ll l = inq(x, y / 2);
    if (y % 2) return l * l % MOD * x % MOD;
    return l * l % MOD;
}

ll n, h, d;
ll kek;
ll fact[N];
ll dp[N], s[N];

ll si(int p)
{
    if (p < 0) return 0;
    return s[p];
}

signed main()
{
    srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> h >> d;
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for (int i = 1; i <= n; i++) kek = (kek + fact[i]) % MOD;
    dp[0] = 1;
    s[0] = 1;
    for (int i = 1; i <= h; i++)
    {
        dp[i] = kek * (si(i - 1) + MOD - si(i - d - 1)) % MOD;
        s[i] = (s[i - 1] + dp[i]) % MOD;
    }
    cout << dp[h] * fact[n] % MOD * inq(kek, MOD - 2) % MOD;
}


Measured memory_bytes: 31872
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

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

  int ans = 0;
  rep(i, 0, n) {
    ans += b[a[i] - 1];
    if (i < n - 1 && a[i + 1] - a[i] == 1) ans += c[a[i] - 1];
  }

  cout << ans << endl;
}


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

struct Node {
  int key;
  Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int key) {
  Node *x, *y, *z;

  // initialize
  z = new Node;
  z->left = NIL;
  z->right = NIL;
  z->key = key;
  y = NIL;
  x = root;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }

  z->parent = y;
  if (y == NIL) root = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;
}

Node* find(int key) {
  Node *x;

  x = root;
  while (x != NIL && x->key != key) {
    if (key < x->key) x = x->left;
    else x = x->right;
  }

  return x;
}

// 次節点を求める
Node* next_node(Node *node) {
  Node *x;
  
  if (node->right != NIL) {
    x = node->right;
    while (x->left != NIL) {
      x = x->left;
    }    
  } else {    
    x = node;    
    while (x->parent != NIL && x == x->parent->right) {
      x = x->parent;
    }
    x = x->parent;
  }

  return x;
}

void delete_node(int key) {
  Node *x, *y, *z;

  z = find(key);  // 削除されるべきキーを持ったノード

  // yを決める
  if (z->left == NIL || z->right == NIL) {  // zが子を持たないor１個
    y = z;
    } else {  // zが子を２つ持つ
    y = next_node(z);  // 次節点
  }
  // xを決める
  if (y->left != NIL) x = y->left;
  else x = y->right;

  // ポインタつなぎ替え
  if (x != NIL) x->parent = y->parent;
  if (y->parent == NIL) root = x;
  else if (y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
  // zの子が２つの場合 yのキーをzに移す
  if (z != y) z->key = y->key;

  delete y;  // yのメモリを解放
}

void preorder(Node* node) {
  if (node == NIL) return;
  cout << " " << node->key;
  if (node->left != NIL) preorder(node->left);
  if (node->right != NIL) preorder(node->right);
}

void inorder(Node* node) {
  if (node == NIL) return;
  if (node->left != NIL) inorder(node->left);
  cout << " " << node->key;
  if (node->right != NIL) inorder(node->right);
}

void print() {
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      cin >> key;
      insert(key);
    } else if (command[0] == 'f') {
      cin >> key;
      if (find(key) != NIL) cout << "yes" << endl;
      else cout << "no" << endl;
    } else if (command[0] == 'd') {
      cin >> key;
      delete_node(key);
    } else {
      print();
    }
  }
    
  return 0;
}


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

int main(){
	int H, W;
	
	for(;;){
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		for(int i = 0; i < H; i++){
			if(i % 2 == 0){
				for(int j = 0; j < W; j++){
					if(j % 2 == 0){
						cout << '#';
					}else {
						cout << '.';
					}
				}
			}else {
				for(int j = 0; j < W; j++){
					if(j % 2 == 0){
						cout << '.';
					}else {
						cout << '#';
					}
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1152
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
int memo[31];
int f(int n){
  if(n<0) return 0;
  if(n<2) return 1;
  if(memo[n]!=-1) return memo[n];
  return (memo[n]=f(n-1)+f(n-2)+f(n-3));
}

int main(void){
  memset(memo,-1,sizeof(memo));
  int n;
  while(cin>>n){
    if(n==0)break;
    cout<<f(n)/3650+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int H = 1e4 + 5;
const int N = 1e3 + 5;
int h, n;
int a[N], b[N], dp[H];

int main()
{
	scanf("%d%d", &h, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", a + i, b + i);
	}
	for (int i = 0; i < h; i++) {
		dp[i] = 1e9;
	}
	int ans = 1e9;
	for (int i = 0; i < n; i++) {
		for (int j = h; j >= 0; j--) {
			dp[max(0, j - a[i])] = min(dp[max(0, j - a[i])], dp[j] + b[i]);
		}
		ans = min(ans, dp[0]);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
#define endl "\n"
using namespace std;
const ll N=100010;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n,k;
    cin>>n>>k;
    vector<pi> ar(n);
    for(ll i=0;i<k;++i){
        cin>>ar[i].first>>ar[i].second;
    }

    ll dp[n+2],pre[n+2];
    dp[n+1]=pre[n+1]=0;
    dp[n]=pre[n]=1;
    for(ll i=n-1;i>=1;--i){
        dp[i]=pre[i]=0;
        for(ll j=0;j<k;++j){
            ll x=i+ar[j].first;
            ll y=i+ar[j].second;
            x=min(x,n+1);
            y=min(y,n+1);
            dp[i]=(dp[i]+((pre[x]-pre[y]+mod)%mod+dp[y])%mod)%mod;
        }
        pre[i]=(pre[i+1]+dp[i]+mod)%mod;
    }
    cout<<dp[1];

    return (0);
}


Measured memory_bytes: 9532
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> v;
    for(int i=1;i*i<=m;i++){
        if(m%i==0){
            v.push_back(i);
            v.push_back(m/i);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    auto itr=upper_bound(v.begin(),v.end(),m/n);
    itr--;
    cout<<*itr<<endl;
    return 0;
}




Measured memory_bytes: 256
#pragma GCC optimize("O3")
        #pragma comment(linker, "/stack:200000000")
        #pragma GCC optimize("unroll-loops")
         
        #include <algorithm>
        #include <bitset>
        #include <cassert>
        #include <chrono>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <functional>
        #include <iomanip>
        #include <iostream>
        #include <iterator>
        #include <limits>
        #include <climits>
        #include <list>
        #include <map>
        #include <numeric>
        #include <queue>
        #include <random>
        #include <ratio>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <string>
        #include <unordered_map>
        #include <unordered_set>
        #include <utility>
        #include <vector>
        using namespace std;
         
        typedef long long ll;
        typedef long double LD;
        #define int ll
        #define double LD
        #define pb push_back
        #define mp make_pair
        #define REP(i,n) for (int i = 0; i < n; i++)
        #define loop(i,n) for (int i = 0; i < n; i++)
        #define FOR(i,a,b) for (int i = a; i < b; i++)
        #define REPD(i,n) for (int i = n-1; i >= 0; i--)
        #define FORD(i,a,b) for (int i = a; i >= b; i--)
        #define remax(a,b) a = max(a,b)
        #define remin(a,b) a = min(a,b)
        #define mem(a, b) memset(a, b, sizeof a)
        #define append push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define print(x) cout << (x) << endl
        #define PRECISION(x) cout << fixed << setprecision(x)
        #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
        #define N 1005
        #define pb push_back
        const double PI=acos(-1);
        const int MOD = 1000000007;
        const int FMOD = 998244353;
        const double eps = 1e-9;
         
        mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
  	
  		signed main()
  		{
  			int n;
  			cin>>n;
  			
  			int a[n+1];
  			int ans=0;
  			FOR(i,1,n+1)
  			{
  				cin>>a[i];
  				if(i%2 && a[i]%2)
  				ans++;
			  }
			  cout<<ans;
		}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

    int n;
    cin >> n;
    int ans = 0;
    for(int i=1;i < 10;i++){
        for(int j=1;j < 10;j++){

            if(i*j == n) {
                ans = 1;
                break;
            }            
            else continue;

        }
    }

    if(ans) cout << "Yes";
    else cout << "No";

    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i ++) 
static const int INF = 0x3f3f3f3f;

int main() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int> (m));
        rep(i, n) rep(j, m) {
                cin >> a[i][j];
                a[i][j] --;
        }
        vector<bool> valid(m, true);
        vector<int> cnt(m, 0);
        int ans = INF;
        rep(_, m) {
                cnt.clear();
                cnt.assign(m, 0);
                rep(i, n) {
                        rep(j, m) {
                                if (valid[a[i][j]]) { 
                                        cnt[a[i][j]] ++;
                                        break;
                                }
                        }
                }
                int ma = -1;
                int maxsport;
                rep(i, m) {
                        if (ma < cnt[i]) {
                                ma = cnt[i];
                                maxsport = i;
                        }
                }
                ans = min(ans, ma);
                valid[maxsport] = false;
        }
        cout << ans << endl;
        return 0;
}



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

ans = 0
L, R = 0, 114514

for i in range(m):
    l, r = map(int, input().split())
    L, R = max(L, l), min(R, r)

print(R - L + 1 if R - L + 1 >= 1 else 0)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#include <queue>
#define int long long
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i=0; i < n; i++){
        cin >> data[i];
    }
    int ans = 1, bad = 1;
    for (int i=0; i < n; i++){
        ans *= 3;
        if (data[i] % 2 == 0) bad *= 2;
    }
    cout << ans - bad << endl;
    return 0;
}



Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
k = ['R','U', 'D']
g = ['L', 'U', 'D']
isOK = True
i = 1
for t in s:
    if(i%2 == 0):
        isOK = t in g
    else:
        isOK = t in k
    if(isOK == False):
        break
    i += 1
print('Yes' if isOK else 'No')

Measured memory_bytes: 74260
#include <stdio.h>

int main(void){
  int N;
  double sum = 0.0,ans;
  int j;
  
  scanf("%d", &N);
  
  int A[N];
  
  for(j=1;j<=N;j++){
    scanf("%d", &A[j]);
    sum = sum + 1.0/A[j];
  }
  
  ans = 1.0/sum;
  
  printf("%f\n", ans);
  
  return 0;
}


Measured memory_bytes: 128