akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
//this cord is learned from beet
int main() {
    ll n,l;
    cin >> n >> l;
    vector<pair<ll,ll>> p(n);
    rep(i,n){
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin(),p.end());
    //左側(iが小さい側)に詰める
    // [0,i)
    vector<ll> dp(n+1,0);
    rep(i,n){
        ll dif = (i + 1) - p[i].first;//基本的には負になる
        dp[i+1] = dp[i] + dif*((p[i].second != 0) ? 1:-1);
    }
    //右側に詰める
    //[i,n)
    vector<ll> pd(n+1,0);
    per(i,n-1){
        ll dif = (l - n + i + 1) - p[i].first;//基本的には正
        pd[i] = pd[i+1] + dif*((p[i].second != 0) ? 1:-1);
    }
    ll res = 0;
    rep(i,n+1)chmax(res,dp[i]+pd[i]);
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 5868
import java.util.*;

class Main {
	Scanner sc;
	long H;
	
	private void calc() {
		sc = new Scanner(System.in);
		H = sc.nextLong();
		long a = 0;
		long b = 1;
		while (H > 0) {
			H = H >>> 1;
			a += b;
			b = b << 1;
		}
		
		System.out.println(a);
	}
	
	public static void main(String[] args) {
		new Main().calc();
	}
}


Measured memory_bytes: 23636
#include <iostream>
using namespace std;
int main(void){
    int n, R[200001];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> R[i];
    }
    int minv = R[0];
    int maxv = -1000000001;
    for(int j = 1; j < n; j++){
        if(R[j] - minv > maxv) maxv = R[j] - minv;
        if(R[j] < minv) minv = R[j];
    }
    
    cout << maxv << endl;
    
    return 0;
}



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

#define DEBUG(x...)

using namespace std;

string S;

bool canDo(int l);

int main(){
	cin>>S;
	int lo = 1;
	int hi = (int) S.size();
	//Inv: No values <lo or >hi are possible
	while (lo!=hi){
		int mid = (lo+hi+1)/2;
		if (canDo(mid)){
			lo = mid;
		} else{
			hi = mid-1;
		}
	}
	cout<<hi<<"\n";
}

bool canDo(int l){
	int f = 0;
	for (int i = 0; i<l; i++){
		int s = ((S[i]-'0')+f)%2;
		DEBUG("S[%d] = %d\n",i,s);
		if (s==1){
			if (i+l>(int)S.size()) return false;
			f++;
		}
	}
	return true;
}

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

using namespace std;

typedef long long ll;

int main(){
	int n;
	cin >> n;
	map<int, int> mp;
	ll suma = 0;
	for(int i = 0; i < n; i++){
		int cur;
		cin >> cur;
		mp[cur]++;
		suma += cur;
	}
	int q;
	cin >> q;
	while(q--){
		ll b, c;
		cin >> b >> c;
		ll antes_b = mp[b];
		mp[b] = 0;
		mp[c] += antes_b;
		suma -= antes_b * b;
		suma += antes_b * c;
		cout << suma << '\n';
	}
}


Measured memory_bytes: 8004
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF LONG_LONG_MAX
using namespace std;

signed main(){
    int n,x; cin>>n>>x;
    vector<int> a(n);
    rep(i,n) cin>>a.at(i);
    sort(all(a));
    int sum=0,ans=0;
    rep(i,n){
        sum+=a.at(i);
        if(sum>x){
            cout<<ans<<endl;
            return 0;
        }
        ans++;
    }
    if(sum==x) cout<<ans<<endl;
    else cout<<ans-1<<endl;
}

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

int main(int argc, const char * argv[]) {
    ll x, sum = 0, ans;
    cin >> x;
    for (int i = 0; i <= x; i++) {
        sum += i;
        if (sum >= x) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}


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

int main(){
  int n,m;
  cin >> n >> m;
  vector<pair<int,char>> sc(m);
  for(int i=0;i<m;i++){
    cin >> sc.at(i).first >> sc.at(i).second;
    if( sc.at(i).first > n ){
      cout << -1 << endl;
      return 0;
    }
    if( sc.at(i).first == 1 && sc.at(i).second == '0' && n != 1){
	  cout << -1 << endl;
      return 0;
    }
  }
  
  string s = "";
  for(int i=0;i<n;i++){
  	s.push_back('0');
  }
  for(int i=0;i<m;i++){
	s.at( sc.at(i).first-1 ) = sc.at(i).second;
  }
  
  for(int i=0;i<m;i++){
    if( s.at( sc.at(i).first-1 ) != sc.at(i).second ){
      cout << -1 << endl;
      return 0;
    }
  }
  if( s.size() != 1 && s.at(0) == '0' ){
    s.at(0) = '1';
  }
  if( stoi(s) < 0 ){
    cout << -1 << endl;
    return 0;
  }
  cout << stoi(s) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    string s;
    cin >> s;
    int N = s.size();
    cout << s[0];
    cout << N-2;
    cout << s[N-1] << endl;
}


Measured memory_bytes: 3568
n=int(input())
a=[[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]],[[],[],[],[],[],[],[],[],[]]]
for i in range(n):
    p=str(i+1)
    b,c=int(p[0]),int(p[-1])
    if c>0:
        a[b-1][c-1].append(p)
q=0
for i in range(9):
    for j in range(9):
        q+=len(a[i][j])*len(a[j][i])
print(q)

Measured memory_bytes: 15092
#include<iostream>
using namespace std;
const long long m=1e9+7;
long long n,k,x,jc[200005];
void init()
{
	jc[0]=1;
	for(long long i=1;i<=n;i++)
	jc[i]=(jc[i-1]*i)%m;
}
long long qpow(long long a,long long n)
{
	long long ans=1;
	while(n)
	{
		if(n&1) ans=(ans*a)%m;
		a=(a*a)%m;
		n>>=1;
	}
	return ans;
}
long long c(long long n,long long r)
{
	long long ans=1,ans1=1;
	ans1=qpow(jc[n-r],m-2);
	ans=qpow(jc[r],m-2);
	ans=(jc[n]*((ans1*ans)%m))%m;
	return ans;
}
int main()
{
	long long ans3=0;
	cin>>n>>k;
	init();
	if(k>=n)  k=n-1;
	for(long long i=0;i<=k;i++)
	{
		ans3+=(c(n,i)*c(n-1,i))%m;
		ans3%=m;
	}
	ans3=(ans3+m)%m;
	cout<<ans3<<endl;
	return 0;
} 

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int N, L;
	cin >> N >> L;
	string s;
	vector<string> v;
	for (int i = 1; i <= N; i ++) cin >> s, v.push_back(s);
	sort(v.begin(), v.end());
	for (int i = 0; i < N; i ++) cout << v[i];
	cout << endl;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
div = sorted(make_divisors(M))
import bisect
ind = bisect.bisect_right(div,M/N)
print(div[ind-1])

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define ll long long
ll Q, H, S, D, N;
int main(){
	scanf("%lld%lld%lld%lld", &Q, &H, &S, &D);
	scanf("%lld", &N);
	Q*=4;
	H*=2;
	S = min(min(S, H), Q);
	if (2*S < D){
		printf("%lld\n", N*S);
	} else {
		if (N % 2 == 0){
			printf("%lld\n", (N*D)/2);
		} else {
			printf("%lld\n", ((N - 1)*D)/2 + S);
		}
	}
	
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long
#define PINT pair<int,int>
#define f1 first
#define s2 second
const int INF = 1e9 + 7;

using namespace std;

int main(){
    cin.tie(0), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<PINT> red(n),blue(n);
    REP(i,n) cin >> red[i].f1 >> red[i].s2;
    REP(i,n) cin >> blue[i].f1 >> blue[i].s2;
    sort(red.begin(),red.end());
    sort(blue.begin(),blue.end());
    vector<bool> jud(n,false);
    int ans=0;
    REP(i,n){
        int max;
        bool flg=false;
        for(int j=0;red[j].f1<blue[i].f1&&j<n;j++){
            if(jud[j]) continue;
            if(red[j].s2 < blue[i].s2){
                if(!flg){
                    max=j;
                    flg=true;
                }
                if(red[max].s2 < red[j].s2) max = j;
            }
        }
        if(flg){
            jud[max] = true;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import math
 
S = int(input())
 
first_half = math.floor(S / 100)
second_half = S - first_half * 100
 
if 1 <= second_half <= 12 and 1 <= first_half <= 12 :
  print("AMBIGUOUS")
elif 1 <= second_half <= 12 :
   		print("YYMM")
elif 1 <= first_half <= 12 :
    	print("MMYY")
else: 
        print("NA")


Measured memory_bytes: 2940
#include <stdio.h>
int main(){
  int w,h,n,x,y,a;
  scanf("%d%d%d",&w,&h,&n);
  int r1=0,r2=w,r3=0,r4=h;
  for(int i=0;i<n;i++){
    scanf("%d%d%d",&x,&y,&a);
    switch(a){
      case 1:
        if(x>r1)r1=x;
        break;
      case 2:
        if(x<r2)r2=x;
        break;
      case 3:
        if(y>r3)r3=y;
        break;
      case 4:
        if(y<r4)r4=y;
        break;
    }
  }
  if(r2>r1&&r4>r3)printf("%d",(r2-r1)*(r4-r3));
  else puts("0");
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
bool D[10];
bool check(int x)
{
    while(x)
    {
        if(D[x%10])
            return 0;
        x /= 10;
    }
    return 1;
}
int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k))
    {

        memset(D, 0, sizeof(D));
        for(int i = 0; i < k; i++)
        {
            int d;
            scanf("%d", &d);
            D[d] = 1;
        }
        for(int i = n; i < 1e7; i++)
        {
            if(check(i))
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}


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

int main()
{	
	int r,c,b;
	cin >> r >> c;
	int arr_r[100] = {};
	int arr_c[100] = {};
	int sum=0;
	for(int i=0; i<r ;i++){
		cin >> b;
		cout << b;
		arr_r[i] += b;
		arr_c[0] +=b;
		for(int j=1; j<c ;j++){
			cin >> b;
			cout << " " << b;
			arr_r[i] += b;
			arr_c[j] +=b;
		}
		sum += arr_r[i]; 
		cout << " " << arr_r[i] << endl;
	}
	cout << arr_c[0];
	for(int i=1 ; i<c ;i++){
		cout << " " << arr_c[i];  
	}
	cout << " " << sum << endl;

	


    return 0;
}



Measured memory_bytes: 3100
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
4
"""
import sys


def solve():
    dp = [[0] * (W + 1) for _ in range(H + 1)]

    for i in range(H):
        for j in range(W):
            if not int(carpet_info[i][j]):
                dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1

    cand = (max(each) for each in dp)
    return pow(max(cand), 2)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    print(solve())

Measured memory_bytes: 60288
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz size()
#define ll long long

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	int ans = 0;
	ans += n * (n - 1) / 2;
	ans += m * (m - 1) / 2;
	cout << ans;
	return 0;
}


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

/* short names and const
using ll = long long;
using vll = vector<long long>;
using df = vector<vll>;
df data(n, vll(m));
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
*/


/* Boost!
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/range/algorithm.hpp> // boost::sort(arr)
using boost::algorithm::split; // split(result, s, boost::is_any_of(","));
using boost::algorithm::join; // string s = join(arr, "");
using boost::algorithm::replace_all; // replace_all(s, "AtCoder", "A");
*/

/* print(arr)
template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}
*/

/* fast cin and precise cout
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  getline(cin, s);
  cout << fixed << setprecision(15);
*/

#include <boost/range/algorithm.hpp> // boost::sort(arr)

int sum(vector<int> &arr) {
  int res = accumulate(arr.begin(), arr.end(), 0);
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  rep(i, n) cin >> arr[i];
  boost::sort(arr);
  cout << sum(arr) - arr.back() / 2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <set>
using namespace  std;

#define int long long int

constexpr int INF = std::numeric_limits<int>::max();

int one[64];

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;

    cout << A * B / 2 << endl;
}

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

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());

		StringTokenizer st1 = new StringTokenizer(br.readLine());
		int si = Integer.parseInt(st1.nextToken());
		int sj = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int ei = Integer.parseInt(st2.nextToken());
		int ej = Integer.parseInt(st2.nextToken());

		char[][] a = new char[h][w];

		for (int i = 0; i < h; i++) {
			String str = br.readLine();
			for (int j = 0; j < w; j++) {
				a[i][j] = str.charAt(j);
			}
		}

		bfs(a, si - 1, sj - 1, ei - 1, ej - 1, h, w);
		out.close();
	}

	static class Pair {
		int x;
		int y;
		int cst;

		Pair(int x, int y, int cst) {
			this.x = x;
			this.y = y;
			this.cst = cst;
		}
	}

	static int[] walkH = { 0, 1, 0, -1 };
	static int[] walkW = { 1, 0, -1, 0 };
	static int[] warpH = { 1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1 };
	static int[] warpW = { 1, -1, 1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2 };

	static void bfs(char[][] a, int si, int sj, int ei, int ej, int h, int w) {
		LinkedList<Pair> q = new LinkedList<>();
		q.add(new Pair(si, sj, 0));

		

		while (!q.isEmpty()) {
			Pair rem = q.poll();

			if (rem.x == ei && rem.y == ej) {
				System.out.println(rem.cst);
				return;
			}
			if(a[rem.x][rem.y]=='#') continue;

			a[rem.x][rem.y] = '#';


			for (int k = 0; k < 4; k++) {
				int nx = walkH[k] + rem.x;
				int ny = walkW[k] + rem.y;
				if (nx >= 0 && ny >= 0 && nx < h && ny < w && a[nx][ny] == '.' ) {
					q.addFirst(new Pair(nx, ny, rem.cst));	
				}
			}

			for (int k = 0; k < warpH.length; k++) {
				int nx = warpH[k] + rem.x;
				int ny = warpW[k] + rem.y;
				if (nx >= 0 && ny >= 0 && nx < h && ny < w && a[nx][ny] == '.') {
					q.addLast(new Pair(nx, ny, rem.cst + 1));
				}
			}
		}

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

Measured memory_bytes: 58576
import java.util.Scanner

object Main extends App  {
  val sc = new Scanner(System.in)
  val w = sc.next.split("(?<=.)")

  val ac = new Array[Int](26)
  val alphabets = "abcdefghijklmnopqrstuvwxyz"

  val tArr =
    w.foldLeft(ac){case (arr, c) =>
      val i = alphabets.indexOf(c)
      val x = arr(i)
      arr.update(i, x + 1)
      arr
    }

  val res = if(tArr.forall(_ % 2 == 0)) "Yes" else "No"

  println(res)
}


Measured memory_bytes: 27316
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long k = sc.nextLong();
		long num = sc.nextLong();
		List<Long> primes = primeFactor(num);
		List<Long> oks = new ArrayList<Long>();
//		System.out.println(Arrays.toString(primes.toArray()));
		for(int i=0;i<primes.size();i++) {
			int ind =primes.lastIndexOf(primes.get(i));

			if(ind - i  +1 >= k) {
				for(int be = 0; be<(ind-i+1)/k ; be++)oks.add(primes.get(i));
//				System.out.println("get:"+primes.get(i));
			}
			i = ind;
		}
		long ans=1;
		for(long pr:oks) {
			ans*=pr;
		}
		System.out.println(ans);
	}

	/**<h1>素因数分解のリストを作る</h1>
	 * @param num ： 素因数分解する値 (>=0)
	 * @return<b>List<Long></b> ： 素因数分解のリスト
	 */
	public static final List<Long> primeFactor(long num) {
		final List<Long> list = new ArrayList<Long>();
		if (num < 2) {    //n が2以上とわかっていれば、ここは不要
			return list;
		}

//		long fin = num/2+1;

		while (num != 1 && num % 2 == 0) {    //2で割り切れるだけ割る
			list.add(2l);
			num /= 2 ;        //÷2 の代わり
		}

		for (long i = 3; i * i <= num; i += 2) {    //奇数のみ [O(√n[/2])で可]
			while (num % i == 0) {
				list.add(i);
				num /= i;
			}
		}

		if (num != 1) {
			list.add(num);
		}
		return list;
	}


}


Measured memory_bytes: 23124
#include <cstdio>
const int Mod=1e9+7,N=2005;
int f[N][N],n,k;
int main (){
	scanf ("%d%d",&n,&k);
    for (int i=2;i<=n;i++) f[1][i]=1;
    for (int i=1;i<k-1;i++){
        int sum=f[i][n-i+1];
        for(int j=n-i;j>=2;j--){
            sum=(sum+f[i][j])%Mod;
            f[i+1][j]=(f[i+1][j]+sum)%Mod;
        }
    }
    int ans=0;
    for (int j=2;j<=n-k+2;j++) ans=(ans+f[k-1][j])%Mod;
    if (k==1) ans=1;
    for (int i=1;i<=n-1-k;i++) ans=ans*2%Mod;
    printf ("%d",ans);
	return 0;
}


Measured memory_bytes: 15232
import sys
input = lambda: sys.stdin.readline().rstrip()

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

A = list(map(int, input().split()))

gcd_front = gcd(A[0], A[1])
gcd_front_list = [A[0],gcd_front, ]
for i in range(2, N):
    gcd_front = gcd(gcd_front, A[i])
    gcd_front_list.append(gcd_front)

gcd_rear = gcd(A[N-1], A[N-2])
gcd_rear_list = [A[N-1], gcd_rear, ]

for i in range(N-3, -1, -1):
    gcd_rear = gcd(gcd_rear, A[i])
    gcd_rear_list.append(gcd_rear)

ans = 0

for i in range(N):
    if i == 0:
        ans = max(ans, gcd_rear_list[-2])
    if i == N-1:
        ans = max(ans, gcd_front_list[-2])   

    ans = max(ans, gcd(gcd_front_list[i-1],gcd_rear_list[N-2-i]))
    
print(ans)

Measured memory_bytes: 16144
#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    match = set()

    while True:
        if totalGame == 0:
            for i in range(N):
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1
        else:
            if totalGame == MAXGAME:
                break

            check_needed = list(match)
            # 既にこのターンでマッチしたインデックスを保持
            match = set()

            for i in check_needed:
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 35568
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
#include <bits/stdc++.h>
using namespace std;
 
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cout_precision cout.setf(ios::fixed); cout.precision(32);
 
using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;
using ld = long double;
 
// ------------------------------------------------------------------------------------------------

const ll N_MAX = 50, A_MAX = 50;
ll n, a, ans;
ll dp[N_MAX][N_MAX + 1][A_MAX * N_MAX + 1] = {0};
vll x;

ll dp_f(ll i, ll j, ll k) {    
    if (j == 0 && k == 0) {
        return 1;
    }
    if (j > i + 1) {
        return 0;
    }
    if (i < 0 || i >= N_MAX || j < 0 || j > N_MAX + 1 || k < 0 || k > A_MAX * N_MAX) {
        return 0;
    }
    if (dp[i][j][k] == -1) {
        dp[i][j][k] = dp_f(i - 1, j, k) + dp_f(i - 1, j - 1, k - x[i]);
    }
    return dp[i][j][k];
}

int main() {
    fast_io; cout_precision;
    cin >> n >> a;
    x.resize(n);
    for (ll i = 0; i < n; i++) {
        cin >> x[i];
    }
    ans = 0;
    for (ll i = 0; i < N_MAX; i++) {
        for (ll j = 0; j <= N_MAX; j++) {
            for (ll k = 0; k <= A_MAX * N_MAX; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    for (ll i = 1; i <= n; i++) {
        ans += dp_f(n - 1, i, a * i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 50048
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
const ll MOD=998244353;
const ll MAX_N=500010;
const ll INF=4448283280358331064;
ll dp[110][200100];

/*
int main(){
    int n;
    cin>>n;
    ll k;
    cin>>k;
    vector<ll> pos(0), neg(0);
    int zero=0;
    for(int i=0;i<n;i++){
        ll a;
        cin>>a;
        if(a>0) pos.push_back(a);
        if(a==0) zero++;
        if(a<0) neg.push_back(-a);
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    ll ub=INF;
    ll lb=-INF;
    while(ub-lb>1){
        ll m=(ub+lb)/2;
        ll num=0;
        //cout<<m<<endl;
        if(m<=0){
            for(ll u:neg){
                num+=pos.end()-upper_bound(pos.begin(),pos.end(),-m/u);
            }
        }else{
            num+=neg.size()*pos.size();
            num+=zero*(neg.size()+pos.size());
            num+=zero*(zero-1)/2;
            for(int i=0;i<pos.size();i++){
                num+=lower_bound(pos.begin()+i, pos.end(), m/pos[i])-(pos.begin()+i);
            }
            for(int i=0;i<neg.size();i++){
                num+=lower_bound(neg.begin()+i, neg.end(), m/neg[i])-(neg.begin()+i);
            }
        }
        if(num<=k){
            lb=m;
        }else{
            ub=m;
        }
    }
    cout<<ub<<endl;
}

*/

int main(){
    int n,cap;
    cin>>n>>cap;
    vector<int> W(n+1);
    vector<ll> V(n+1);
    for(int i=1;i<=n;i++){
        int w;
        ll v;
        cin>>w>>v;
        W[i]=w;
        V[i]=v;
    }

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

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

int main(){
    int N,M;
    cin >> N;
    int sum,A[2][N];
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < N; j++){
			cin >> A[i][j];
		}
	}
    for (int i=0; i<N; ++i){
        sum=0;
        for (int j=0; j<N; ++j){
	    if(j == i) sum += A[0][j] + A[1][j];
            else if(j > i) sum += A[1][j]; 
	    else sum += A[0][j];
        }
        M=max(M,sum);
    }
    cout << M  << endl;
}


Measured memory_bytes: 256
n,a,b=map(int,input().split())
mod=10**9+7

def comb(n,r):
    P=1
    R=1
    for i in range(r):
        P=P*(n-i)%mod
        R=R*(r-i)%mod
    return P*pow(R,mod-2,mod)%mod

combN=pow(2,n,mod)-1
print((combN-comb(n,a)-comb(n,b))%mod)

Measured memory_bytes: 3064
import java.util.*;

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

	public Main(){
		new AOJ1135().doIt();
	}
	
	class AOJ1135{
		int n,m;
		
		void solve(){
			int taro[] = new int[n];
			int hana[] = new int[m];
			for(int i=0;i<n;i++)taro[i] = in.nextInt();
			for(int i=0;i<m;i++)hana[i] = in.nextInt();
			Arrays.sort(taro);Arrays.sort(hana);
			int tsum = 0,hsum = 0;
			for(int i=0;i<n;i++)tsum += taro[i];
			for(int i=0;i<m;i++)hsum += hana[i];
			int a=-1,b=-1;
			for(int i=0;i<n;i++)for(int s=0;s<m;s++){
				int c = tsum-taro[i]+hana[s];
				int d = hsum-hana[s]+taro[i];
//				System.out.println(c+" "+d);
				if(c==d&&a==-1){
					a=taro[i];b=hana[s];break;
				}
			}
			if(a==-1||b==-1)System.out.println(-1);
			else System.out.println(a+" "+b);
		}
		
		void doIt(){
			while(in.hasNext()){
				n = in.nextInt(); 
				m = in.nextInt();
				if(n+m==0)break;
				solve();
			}
		}
	}
	
}

Measured memory_bytes: 21756
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
//#pragma GCC target("popcnt")
//#pragma GCC target("sse4")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(),a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;













#define int long long

signed main(){
    int n, p;
    map<int,int> mp;
    cin >> n >> p;
    string s;
    cin >> s;
    int a[n];
    for (int i = 0; i < n; i++) a[i] = s[i] - '0';
    mp[0]++;
    int x = 0;
    int r = 1;
    if (p == 2 || p == 5){
        int ans = 0;
        for (int i = 0; i < n; i++){
            if (a[i]%p == 0) ans += (i + 1);
        }
        cout << ans;
        return 0;
    }
    for (int i = n - 1; i >= 0; i--){
        x = (x + a[i]*r)%p;
        mp[x]++;
        r = (r * 10)%p;
    }
    int ans = 0;
    for (auto x : mp){
        ans += x.se * (x.se - 1) / 2;
    }
    cout << ans;
}


Measured memory_bytes: 2564
from itertools import product

A, B, C, D = input()
for op1, op2, op3 in product("+-", repeat=3):
    expr = "{}{}{}{}{}{}{}".format(A, op1, B, op2, C, op3, D)
    if eval(expr) == 7:
        print("{}{}{}{}{}{}{}=7".format(A, op1, B, op2, C, op3, D))
        break


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
    int a,b,c;

    cin >> a >> b >> c;

    int x = max(a,max(b,c)) * 9;
    cout << a + b + c + x;
    return 0;
}


Measured memory_bytes: 256
def main() -> None:
    N = int(input())
    S = input()
    m = 0
    for i in range(N):
        same_num = len(set(sorted(S[0:i])) & set(sorted(S[i:])))
        m = same_num if m < same_num else m
    
    print(m)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<stdio.h>
#include<string.h>
char ch[205][11],str[11];
int s[205];
int main()
{
	int a,b,k=0;
	scanf("%d",&a);
	getchar();
	for(int i=0;i<a;i++)
	{
		scanf("%s",str);
		int flag=0;
		for(int j=0;j<k;j++)
		{
			if(strcmp(ch[j],str)==0)
			{
				flag=1;
				s[j]++;
				break;
			}
		}
		if(flag==0)
		{
			strcpy(ch[k],str);
			s[k]++;
			k++;
		}
	}
	scanf("%d",&b);
	getchar();
	for(int i=0;i<b;i++)
	{
		scanf("%s",str);
		int flag=0;
		for(int j=0;j<k;j++)
		{
			if(strcmp(ch[j],str)==0)
			{
				flag=1;
				s[j]--;
				break;
			}
		}
		if(flag==0)
		{
			strcpy(ch[k],str);
			s[k]--;
			k++;
		}
	}
	int max=0;
	for(int i=0;i<k;i++)if(s[i]>max)max=s[i];
	printf("%d\n",max);
}

Measured memory_bytes: 888
S = input()

a, b = int(S[:2]), int(S[2:])

if 0 < a < 13:
    if 0 < b < 13:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 0 < b < 13:
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  vector<string> abcs = {"abc", "acb", "bac", "bca", "cab", "cba"};
  for (int i = 0; i < 6; i++) {
    if (S == abcs.at(i)) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
N, x = map(int, input().split())
if x == 1 or x == 2 * N - 1:
    print("No")
else:
    if x <= N:
        ans = list(range(1, x - 1) ) +  list(range(x + 2, N + 2)) + [x - 1, x, x + 1] + list(range(N + 2,  2 * N))
    else:
        ans = list(range(1, N  - 1)) + [x - 1, x, x + 1] + list(range(N - 1, x - 1)) + list(range(x + 2, 2 * N))
    print("Yes")
    for a in ans:
        print(a)

Measured memory_bytes: 13268
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int N = sc.nextInt();
        double[] p = new double[N + 1];
        double[][] f = new double[N + 1][N + 1];
        for(int i = 1; i <= N;  i++)p[i] = sc.nextDouble();

//        f[i][j] = f[i - 1][j - 1] * p[i] + f[i][j - 1] * p[i];
        f[0][0] = 1;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j ++){
                f[0][j] = f[0][j - 1] * (1 - p[j]);
                f[i][j] = f[i - 1][j - 1] * p[j] + f[i][j - 1] * (1 - p[j]);
            }
        }
        double res = 0.0;
        for(int i = 0; i <= N; i ++){
            if(i > (N - i))res += f[i][N];
        }
        System.out.println(res);
    }
}

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

int main(void) {
	int n, r;

	scanf("%d %d", &n, &r);
	if (n >= 10) printf("%d", r);
	else printf("%d", r + 100 * (10 - n));
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m,sum=0;
    cin>>n>>m;
    long long a[m];
    for(int i=1; i<=m; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum>n)
        cout<<-1;
    else
        cout<<n-sum;

}


Measured memory_bytes: 3648
N,M = map(int,input().split())

if M % N == 0:    print(M//N)
elif M//N > 100000:
    for i in range(N,M//2+1):
        if M % i == 0:
            print(M//i)
            break
    else:
        print(1)
else:
    m = M//N
    for i in range(2,m)[::-1]:
        if M % i == 0:
            print(i)
            break
    else:
        print(1)

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

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var a = Console.ReadLine().ToArray();
            int cnt = 0;
            foreach (char c in a)
            {
                if (c == 'o') cnt++;
            }
            Console.WriteLine(700 + cnt * 100);
        }
    }
}



Measured memory_bytes: 13268
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

string S;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> S;
  int c = 0;
  rep(i, 16) {
    if ("CODEFESTIVAL2016"[i] != S[i]) c++;
  }
  cout <<c<<"\n";
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

    if (p % 2 == 0) {
        long long t = pow_mod(n, p / 2, m);
        return t * t % m;
    }
    return n * pow_mod(n, p - 1, m) % mod;
}

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

bool is_prime(long long n)
{
    if (n == 1) {
        return false;
    }

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main()
{
    long long n, t;
    std::cin >> n >> t;

    std::vector<long long> times(n);
    for (int i = 0; i < n; i++) {
        std::cin >> times[i];
    }

    long long ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += std::min(t, times[i + 1] - times[i]);
    }

    std::cout << ans + t << std::endl;
}


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

#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcd(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

  int n, m;
  cin >> n >> m;
  vt<int> imos(n + 2, 0);
  rep(i, 0, m) {
    int l, r;
    cin >> l >> r;
    imos[l]++;
    imos[r + 1]--;
  }

  rep(i, 1, n + 1) {
    imos[i] += imos[i - 1];
  }

  int ans = 0;
  rep(i, 1, n + 1) {
    if(imos[i] == m) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<61);

using namespace std;

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string s; cin >> s;
    if(count(all(s), 'A') == 0 || count(all(s), 'B') == 0){
      cout <<"No\n";
    }else cout <<"Yes\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}


int main(){
	ll int mae,ato,kin;
	while(1){
		cin >> mae >> ato >> kin;
		if(mae==0&&ato==0&&kin==0) break;
		ll int ans = -1;
		FOR(i,1,kin){
			FOR(j,1,kin){
				if(i*(mae+100)/100+j*(mae+100)/100==kin){
					ans = max(ans,i*(100+ato)/100+j*(100+ato)/100);
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1156
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H1, M1, H2, M2, K = lr()
start = H1 * 60 + M1
end = H2 * 60 + M2
answer = end - start - K
print(answer)


Measured memory_bytes: 9044
from sys import stdin

input = stdin.readline
MOD = 998244353


def solve():
    N,X,M = map(int,input().split())
    cur = X
    res = [0]
    d = {}

    for i in range(N):
        res.append(cur+res[-1])
        if d.get(cur,-1) != -1:
            #d[cur]----i cycle
            pos = d[cur]
            m,r = divmod(N - pos,i-pos)
            s  = (res[i] - res[pos])*m + res[pos+r]
            print(s)
            return
        d[cur] = i
        cur =  (cur**2)%M

    print(res[-1])


if __name__ == '__main__':
    solve()


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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

signed main() {
    int r;
    cin >> r;
    cout << 3 * r * r << endl;

    return 0;
}


Measured memory_bytes: 256
def manyformula(S):
    T=int(S)
    if len(S)==1:
        return int(S)
    else:
        m=0
        for i in range(1,len(S)):
            a=T%(10**i)
            b=T//(10**i)
            m=m+b*(2**(len(str(a))-1))+manyformula(str(a))
        return T+m

S=input()
print(manyformula(S))


Measured memory_bytes: 3060
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for (int i = 0; i < (int)c; i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int,int>;
const int inf = 1000000000; //10^9
const ll MOD = 1e9 + 7;
//加算代入演算子は+=！！！！！
//int 2^31 10^9まで
// 5! = 120。約数の数は、16。
// 5! = 5 * 3 * (2^3)
int main() {
    int n, count = 0;
    cin >> n;
    map<int, int> count_prime; // mapを用いると「特定の値に、ある値が紐付いている」ようなデータを扱うことができる。

    // N,N-1,N-2,..について各素数の個数を求める。
    for (int i = 2; i <= n; i++) { // 階乗の整数(i)分繰り返す。1は除外してるので2からスタート。
        int temp = i; // iが変化しないように
        for (int j = 2; j <= temp; j++) { // 階乗の各整数(temp)をさらに素数に分解
            while (temp % j == 0) {
                temp /= j;
                count_prime[j]++; //分解できたらその素数をキーに値+1する。
            }
        }
    }

    // (素数aの数+1) * (素数bの数+1) * (素数cの数+1)...
    // +1はその素数を選ぶか選ばないか
    ll ans = 1;
    for (auto p : count_prime) { //pair<int, int> p : count_primeと同義。count_primeのキーの値が小さい順にループ
        ans = ((ans % MOD) * (p.second + 1) % MOD) % MOD; //p.secondは素数の個数
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include<queue>

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int gcd(int a, int b){return b ? gcd(b, a%b) : a;}


int main(){
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;

    int foreigh = 0;
    int throuth = 0;
    bool flag = true;
    for(int i = 0; i < n; i++){
        if(s[i] == 'a'){
            if(a+b<=throuth) cout << "No" << endl;
            else {
                cout << "Yes" << endl;
                throuth++;
            }
        }
        else if(s[i] == 'b'){
            if(a+b<=throuth || foreigh==b) cout << "No" << endl;
            else {
                cout << "Yes" << endl;
                throuth++;
                foreigh++;
            }
        }
        else cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define siz(v) (ll)(v).size()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repn(i, n) for (ll i = 0; i <= (ll)(n); i++)
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
//cin.tie(0);
//ios::sync_with_stdio(false);
vector<ll> finddivisor(ll x)
{ //整数xの約数が入ったvectorを返すよ(xを含む)
    vector<ll> divisor;
    for (ll i = 1; (i * i) <= x; i++)
    {
        if (x % i == 0)
        {
            divisor.push_back(i);
            if (i * i != x)
            {
                divisor.push_back(x / i);
            } //約数はペアを持つことを利用
        }
    }
    sort(divisor.begin(), divisor.end());
    //divisor.push_back(x);
    return divisor;
}

signed main()
{
    ll sum = 0, n, k, ans = 1;
    cin >> n >> k;
    vector<ll> v(n);

    rep(i, n)
    {
        cin >> v[i];
        sum += v[i];
    }
    vector<ll> y = finddivisor(sum);

    for (int i = 0; i < siz(y); i++)
    {
        ll cost = 0, zure = 0;
        vector<PL> u(0);
        for (int j = 0; j < n; j++)
        {
            ll r = v[j] % y[i], r2 = y[i] - (v[j] % y[i]);
            cost += r;
            zure += r;
            u.pb({r2 - r, -r});

        }
        if (zure % y[i] != 0)
        {
            continue;
        }

        sort(all(u));

        for (int l = 0; l < (zure / y[i]); l++)
        {
            cost += u.at(l).se;
        }
        if (cost <= k)
        {
            ans = y[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 1e9 + 7;

int n, a[N];

bool vis[N];

int pre[N], tot;

bool see[N];

void init(int up) {

    rep(i, 2, up) {

        if(!vis[i]) pre[++tot] = i;

        rep(j, 1, tot) {

            if(i * pre[j] > up) break;

            vis[i * pre[j]] = 1;

            if(i % pre[j] == 0) break;

        }

    }
    
    return ;
    
}

bool judge1() {

    rep(i, 1, n) {

        for(int j = 1; pre[j] * pre[j] <= a[i]; j++) {

            if(a[i] % pre[j] == 0) {

                if(see[pre[j]]) return 0;

                see[pre[j]] = 1;

                while(a[i] % pre[j] == 0) {

                    a[i] /= pre[j];

                }

            }

        }

        if(a[i] != 1) {

            if(see[a[i]]) return 0;

            see[a[i]] = 1;

        }

    }

    return 1;

}

void solve() {

    scanf("%d", &n);

    int ma = 0;

    rep(i, 1, n) scanf("%d", &a[i]), ma = max(ma, a[i]);
    
    if(ma == 1) {
        
        puts("pairwise coprime");
        
        return ;
        
    }
    
    init(ma);
    
    int G = a[1];

    rep(i, 2, n) G = __gcd(G, a[i]);

    if(judge1()) puts("pairwise coprime");

    else if(G == 1) puts("setwise coprime");

    else puts("not coprime");
    
    return ;
    
}


int main() {



//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}


Measured memory_bytes: 8856
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
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; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion


void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    ll N, M, X;
    cin >> N >> M >> X;
    vec<int> cost(101);
    REP(i, M){
        int A;
        cin >> A;
        cost[A] = 1;
    }
    int s1 = 0, s2 = 0;
    for(int i=X; i<N; i++){
        s1 += cost[i];
    }
    for(int i=X;i>=0; i--){
        s2 += cost[i];
    }
    cout << min(s1, s2) << el;
}



Measured memory_bytes: 256