akhauriyash/Code-Regression huggingface dataset:
/**
 * C - HonestOrUnkind2
 * https://atcoder.jp/contests/abc147/tasks/abc147_c
 * 
 * 方針1 全探索
 * 正直な人の組み合わせを仮定し、全パターンで
 * 証言に矛盾が発生しないかを検証する
 **/
#include<iostream>
#include<vector>


using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<pair<int, int>>> X(N);
    for(int i=0; i<N; i++) {
        int ai;
        cin >> ai;
        for(int j=0; j<ai; j++) {
            int xii, yii;
            cin >> xii >> yii;
            X[i].push_back(pair<int, int>(xii, yii));
        }
    }

    int ans = 0;
    for(int bit=0; bit<(1<<N); ++bit) {
        // 全bit探索
        bool flag = false;
        for(int i=0; i<N; i++) {
            if(bit & 1<<(N-i-1)) {
                // i番目の人が正直物だと仮定して進める
                for(auto p:X[i]) {
                    if(p.second) {
                        // p.first は正直者
                        if((1<<(N-p.first) & bit) == 0) {
                            // 矛盾してる
                            flag = true;
                            break;
                        }
                    } else {
                        // 嘘つき
                        if(1<<(N-p.first) & bit) {
                            // 矛盾してる
                            flag = true;
                            break;
                        }
                    }
                }
            }
            if(flag) {
                break;
            }            
        }
        if(!flag) {
            int count = 0;
            // bitの1の数を数える
            int q = bit;
            int r;
            while(q!=0) {
                r = q % 2;
                q = q / 2;
                if(r==1) {
                    count++;
                }
            }
            ans = max(count, ans);
        }
    }

    cout << ans << endl;

    return 0;
}


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

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int result = 0;
        if (a < b){
            result += a;
        }else{
            result += b;
        }
        if (c < d){
            result += c;
        }else{
            result += d;
        }
        System.out.println(result);
        sc.close();
    }
}

Measured memory_bytes: 20820
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

int main() 
{
	int N,K,X,Y;
	cin >> N>>K>>X>>Y;

	int ans = 0;
	for (int i = 0; i < N; i++)
	{ 
		if (i < K)
		{
			ans += X;
		}
		else if (i >= K)
		{
			ans += Y;
		}
		
	}
	cout << ans << endl;
	
	return 0;
	
}

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

int a[100005];

bool cmp(int p, int q)
{
	return p>q;
}

int main()
{
	int n;
	cin >> n;
	memset(a, 0, sizeof(a));
	while(n--)
	{
		int x;
		cin >> x;
		a[x+2]++;
		a[x+1]++;
		a[x]++;
	}
	sort(a, a+100005, cmp);
	cout << a[0] << endl;
}

Measured memory_bytes: 640
#a=int(input())
#b,c=int(input()),int(input())
# c=[]
#  for i in b:
#     c.append(i)
A,B,T = map(int,input().split())
# f = list(map(int,input().split()))
# j = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split()))

s=T//A 
print(s*B)



Measured memory_bytes: 81080
n=int(input())
a=list(map(int, input().split()))
from fractions import gcd
gcd_all=gcd(a[0],a[1])
gcd_eli=[a[0],a[1]]
for i in range(2,n):
    temp0=gcd(gcd_eli[0],a[i])
    temp1=gcd(gcd_eli[1],a[i])
    gcd_eli=sorted([temp0,temp1,gcd_all])[1:]
    gcd_all=gcd(gcd_all,a[i])
print(max(gcd_all,max(gcd_eli)))

Measured memory_bytes: 14584
#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;i<n;i++)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%I64d",&x)
#define ss(s)	scanf("%s",s)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const int mod = 1000000007;
const int N = 4004;
vi g[N];
int a[N];
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i,n,k,j;
	cin>>n;
	fo(i, 2*n) cin>>a[i];
	sort(a, a+2*n);
	int ans = 0;
	Fo(i, 0, 2*n-1) ans += a[i++];
	cout<<ans<<endl;


	return 0;
} 

int mpow(int base, int exp) {
base %= mod;
int result = 1;
while (exp > 0) {
if (exp & 1) result = ((ll)result * base) % mod;
base = ((ll)base * base) % mod;
exp >>= 1;
}
return result;
}

void ipgraph(int n, int m){
int i, u, v;
while(m--){
	cin>>u>>v;
	g[u-1].pb(v-1);
	g[v-1].pb(u-1);
}
}

void dfs(int u, int par){
for(int v:g[u]){
	if (v == par) continue;
	dfs(v, u);
}
}

Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static long INF = Long.MAX_VALUE >> 1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tokens = br.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int M = Integer.parseInt(tokens[1]);
		int P = Integer.parseInt(tokens[2]);
		Edge[] edges = new Edge[M];
		for (int i = 0; i < M; i++) {
			tokens = br.readLine().split(" ");
			int src = Integer.parseInt(tokens[0]) - 1;
			int dest = Integer.parseInt(tokens[1]) - 1;
			int weight = Integer.parseInt(tokens[2]) - P;
			edges[i] = new Edge(src, dest, weight);
		}
		long[] dist = new long[N];
		Arrays.fill(dist, -INF);
		dist[0] = 0;
		boolean done = true;
		for (int i = 1; i < N; i++) {
			done = true;
			for (Edge e : edges) {
				if (dist[e.u] != -INF && dist[e.v] < dist[e.u] + e.w) {
					dist[e.v] = dist[e.u] + e.w;
					done = false;
				}
			}
			if (done)
				break;
		}
		long max = dist[N - 1];
		if (!done)
			for (int i = 0; i < N; i++)
				for (Edge e : edges) {
					if (dist[e.u] != -INF && dist[e.v] < dist[e.u] + e.w) {
						dist[e.v] = INF;
					}
				}
//		System.out.println(Arrays.toString(dist));
		System.out.println(Math.abs(dist[N - 1]) >= (5e10) ? -1 : Math.max(0, max));
	}

	static class Edge {
		int u;
		int v;
		int w;

		Edge(int src, int dest, int w) {
			u = src;
			v = dest;
			this.w = w;
		}

		Edge(Edge e) {
			u = e.u;
			v = e.v;
			w = e.w;
		}

		@Override
		public String toString() {
			return String.format("[%d, %d, %d]", u, v, w);
		}

	}
}

Measured memory_bytes: 27052
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll=long long;
int main(){
int n;
  cin>>n;
  vector<int>a(n);
  int ans=0;
  rep(i,n) cin>>a.at(i);
  rep(i,n) rep(j,n)rep(k,n){
  	if(i<j && j<k){
    	if(a.at(i)==a.at(j)) continue;
      if(a.at(j)==a.at(k)) continue;
      if(a.at(i)==a.at(k)) continue;
       if(((ll) a.at(i)+a.at(j)+a.at(k) )   <=max({a.at(i),a.at(j),a.at(k)})*2) continue;
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3572
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int a,b,c,k,ans=0; cin>>a>>b>>c>>k;
    if(k<a) cout<<k<<endl;
    else if(k<a+b) cout<<k<<endl;
    else{
        k-=(a+b);
        cout<<a-k<<endl;
    }
}

Measured memory_bytes: 3624
#include <stdio.h>
int main(){
    int n,ans;
    while(scanf("%d",&n)!=EOF){
        ans=0;
    for(int a=0;a<=9;a++){
        for(int b=0;b<=9;b++){
            for(int c=0;c<=9;c++){
                for(int d=0;d<=9;d++){
                    if(a+b+c+d==n)ans++;
                }
            }
        }
    }
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 2704
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int N,K,i,a;
  cin>>N>>K;
  a=(int)pow(2,N);
  for(i=0;i<=N;i++){
    a=min(a,(int)pow(2,i)+(N-i)*K);
  }
  cout<<a;
}

Measured memory_bytes: 384
using System;
using static System.Console;
using static System.Convert;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var figs = Array.ConvertAll(ReadLine().Split(' '), ulong.Parse);
        var result = 0;
        var isFinish = false;
        while (!isFinish)
        {
            for (var i = 0; i < num; i++)
            {
                if (!(figs[i] / 2 == (double)figs[i] / 2)) { isFinish = true;break; }
                figs[i] /= 2;
            }
            if (!isFinish) result++;
        }

        WriteLine(result);
    }
}



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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n, k;
double a[maxn];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cout << fixed << setprecision(12);

  cin>>n>>k;
  for (int i=1; i<=n; i++) {
    cin>>a[i];
    double x = a[i];
    x = x*(x+1)/2;
    x = x/a[i];
    a[i] = x;

    a[i] += a[i-1];
  }

  double res = 0;

  for (int i=k; i<=n; i++) {
    res = max(res, a[i] - a[i-k]);
  }

  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 1792
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
dis_list = []
dis_list.append(abs(a-b))
dis_list.append(abs(a-c))
dis_list.append(abs(a-d))
dis_list.append(abs(a-e))
dis_list.append(abs(b-c))
dis_list.append(abs(b-d))
dis_list.append(abs(b-e))
dis_list.append(abs(c-d))
dis_list.append(abs(c-e))
dis_list.append(abs(d-e))
if max(dis_list) > k:
    print(':(')
else:
    print('Yay!')

Measured memory_bytes: 3064
#! /usr/bin/env python3
import math

def main():
    N, A, B = map(int, input().split())
    v = sorted(map(int, input().split()))[::-1]
    L = [[sum(v[:A]) / A, v[:A]]]
    for i in range(A+1, B+1):
        if sum(v[:i]) / i == L[0][0] : L += [[sum(v[:i]) / i, v[:i]]]
    ans = 0
    for i in L:
        a = 1
        for j in set(i[1]):
            if i[1].count(j) == 1:
                a *= v.count(j)
            else:
                x = v.count(j)
                y = i[1].count(j)
                a *= (math.factorial(x) // math.factorial(x-y)) // math.factorial(y)
        ans += a
    print(L[0][0])
    print(ans)

if __name__ == '__main__':
    main()

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

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

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s,z;
	int k;
	cin >> s >> k;
	int n = s.size();
	int cnta = 0,cntb = 0;
	if(n == 1){
		cout << k / 2 << '\n';
		return 0;
	}
	if(n == 2){
		cout << ((s[0] == s[1]) ? k : 0 ) << '\n';
		return 0;
	}
	if(s[0] == s[n-1] && k > 1){
		cnta = 1;
		rep(i,n-1){
			if(s[i] == s[i+1]) ++cnta;
			else break;
		}
		cntb = 1;
		for(int i = n-1;i > 0;--i){
			if(s[i] == s[i-1]) ++cntb;
			else break;
		}
		if(cnta == n) cntb = 0;
		z = s.substr(0,cnta) + s.substr(n-cntb);
	}
	int x = z.size() / 2 * (k-1);
	if(z.size() == n){
		cout << n * k / 2 << '\n';
		return 0;
	}
	int cnt = 0;
	bool flg;
	int cntx = 0;
	for(int i = cnta;i < n - cntb;++i){
		if(s[i] == s[i+1]){
			++cntx;
			flg = true;
		}
		else if(flg){
			++cntx;
			cnt += cntx / 2;
			cntx = 0;
			flg = false;
		}
	}
	if(cnt == 0){
		cout << x + cnta / 2 + cntb / 2<< '\n';
	}
	else{
		cout << cnt * k + x + cnta / 2 + cntb / 2 << '\n';
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    long A,B; cin>>A>>B;
    long AA = A,BB = B;
    long ex = 1;
    long i = 2;
    while(1){
        while(1){
            if(A%i==0&&B%i==0){
                A /= i;
                B /= i;
                ex *= i;
                break;
            }
            if(i>AA/2||i>BB/2)break;
            i++;
        }
        if(i>AA/2||i>BB/2)break;
    }
    
    long ans = ex*A;
    ans *= B;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 764
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_Garden {
    class Program {
        static void Main(string[] args) {
            string param = Console.ReadLine();
            string[] items = param.Split(' ');
            int a = Convert.ToInt32( items[0]);
            int b = Convert.ToInt32(items[1]);
            int ans = a * b - (a + b - 1);
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define mod 1000000007
using ll = long long;
using namespace std; 

int main(){
    int n,m; cin >> n >> m;
    int sum=0;
    int ans=0;
    vector<int> A(n);
    for (int i=0;i<n;i++){
        int a; cin >> a;
        A[i]=a;
        sum+=a;
    }
    for (auto val : A){
        if (val*4*m>=sum){
            ans++;
        }
    }
    if (ans>=m) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}



Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<typename T> inline istream& operator>>(istream &i, vector<T> &v) {rep(j, size(v)) i >> v[j]; return i;}
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 T> T gcd(T a, T b) {if(b==0)return a; else return gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return a/gcd(a,b)*b;}
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n & 1) {
        No();
    }else{
        if(s.substr(0, n/2) == s.substr(n/2, n/2)) Yes();
        else No();
    }
}


Measured memory_bytes: 3644
fun main(args: Array<String>) {

    val inputCount = readLine()!!.split(" ").map { it.toInt() }

    val observatoryCount = inputCount[0]
    val pathCount = inputCount[1]

    val observatories = readLine()!!.split(" ").map { it.toInt() }.map{ Observatory(it) }

    repeat(pathCount) {
        val pathInput = readLine()!!.split(" ").map { it.toInt() }
        val a = pathInput[0]
        val b = pathInput[1]

        observatories[a-1].addPath(observatories[b-1])
        observatories[b-1].addPath(observatories[a-1])
    }

    print(observatories.count { it.isGoodObservatory() })
}

class Observatory(val elevation: Int) {
    var neighbors = mutableListOf<Observatory>()

    fun addPath(obs: Observatory) {
        neighbors.add(obs)
    }

    fun isGoodObservatory(): Boolean {
        if(neighbors.size == 0) {
            return true
        }
        neighbors.forEach {
            if(elevation <= it.elevation) {
                return false
            }
        }
        return true
    }
}

Measured memory_bytes: 72900
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long ll;
//
vector<int> primes = {2, 3, 5, 7, 11 , 13, 17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
vector<int> cnt(25);
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < 25; i++){
        int cur = primes[i];
        int div = cur;
        while(true){
            if(div > n) break;
            cnt[i] += n / div;
            div *= cur;
        }
    }
    int ans = 0;
    for(int i = 0; i < 25; i++) if(cnt[i] >= 74) ans++;
    for(int i = 0; i < 25; i++){
        for(int j = i + 1; j < 25; j++){
            if(cnt[i] >= 24 && cnt[j] >= 2) ans++;
            if(cnt[j] >= 24 && cnt[i] >= 2) ans++;
            if(cnt[i] >= 14 && cnt[j] >= 4) ans++;
            if(cnt[i] >= 4 && cnt[j] >= 14) ans++;
        }
    }
    for(int i = 0; i < 25; i++){
        for(int j = i + 1; j < 25; j++){
            for(int k = j + 1; k < 25; k++){
                if(cnt[i] >= 4 && cnt[j] >= 4 && cnt[k] >= 2) ans++;
                if(cnt[i] >= 4 && cnt[j] >= 2 && cnt[k] >= 4) ans++;
                if(cnt[i] >= 2 && cnt[j] >= 4 && cnt[k] >= 4) ans++;
            }
        }
    }
    cout << ans;
}

/*⠀⠀⠀⠀⠀⢀⣀⣀⣀    
⠀⠀⠀⠰⡿⠿⠛⠛⠻⠿⣷
⠀⠀⠀⠀⠀⠀⣀⣄⡀⠀⠀⠀⠀⢀⣀⣀⣤⣄⣀⡀
⠀⠀⠀⠀⠀⢸⣿⣿⣷⠀⠀⠀⠀⠛⠛⣿⣿⣿⡛⠿⠷
⠀⠀⠀⠀⠀⠘⠿⠿⠋⠀⠀⠀⠀⠀⠀⣿⣿⣿⠇
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠁

⠀⠀⠀⠀⣿⣷⣄⠀⢶⣶⣷⣶⣶⣤⣀
⠀⠀⠀⠀⣿⣿⣿⠀⠀⠀⠀⠀⠈⠙⠻⠗
⠀⠀⠀⣰⣿⣿⣿⠀⠀⠀⠀⢀⣀⣠⣤⣴⣶⡄
⠀⣠⣾⣿⣿⣿⣥⣶⣶⣿⣿⣿⣿⣿⠿⠿⠛⠃
⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡁
⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁
⠀⠀⠛⢿⣿⣿⣿⣿⣿⣿⡿⠟
⠀⠀⠀⠀⠀⠉⠉⠉
*/

//library//
ll mod_fact(ll a, ll mod){
    ll ans = 1;
    while(a > 1){
        ans = ans * a % mod;
        a--;
    }
    return ans; 
}
ll mod_pow(ll a, ll b, ll mod){
    ll ans = 1;
    while(b > 0){
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll mod_inv(ll a, ll mod){
    return mod_pow(a, mod - 2, mod);
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static class Card {
        public String type;
        public int num;

        public Card(String cardString) {
            type = cardString.substring(0, 1);
            num = Integer.parseInt(cardString.substring(1, 2));
        }
        
        public String toString() {
            return type + num;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int N = readInt(r);
        String[] numStrings = r.readLine().split(" ");
        Card[] A1 = new Card[N];
        Card[] A2 = new Card[N];
        for (int i = 0;i < N;i++) {
            A1[i] = new Card(numStrings[i]);
            A2[i] = new Card(numStrings[i]);
        }
        bubbleSort(A1, N);
        selectionSort(A2, N);
    }
    
    public static void bubbleSort(Card[] A, int N) {
        boolean stable = true;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int j = N - 1;j >= 1;j--) {
                if (A[j].num < A[j - 1].num) {
                    stable &= swapInt(A, j, j - 1);
                    flag = true;
                }
            }
        }
        System.out.println(dump(A, N));
        System.out.println(stable ? "Stable" : "Not stable");
    }
    
    public static void selectionSort(Card[] A, int N) {
        boolean stable = true;
        for (int i = 0;i < N;i++) {
            int minj = i;
            for (int j = i;j < N;j++) {
                if (A[j].num < A[minj].num) {
                    minj = j;
                }
            }
            //if (A[i].num != A[minj].num) {
                stable &= swapInt(A, i, minj);
            //}
        }
        System.out.println(dump(A, N));
        System.out.println(stable ? "Stable" : "Not stable");
    }
    
    // Stable: true
    // Unstable: false
    public static boolean swapInt(Card[] A, int j, int k) {
        Card v = A[j];
        A[j] = A[k];
        A[k] = v;

        int min = Math.min(j, k);
        int max = Math.max(j, k);
        for (int i = min + 1;i < max;i++) {
            if (A[j].num == A[i].num || A[k].num == A[i].num || A[j].num == A[k].num) {
                return false;
            }
        }
        return true;
    }
    
    public static String dump(Card[] A, int N) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < N;i++) {
            if (i != 0) {
                builder.append(" ");
            }
            builder.append(A[i]);
        }
        return builder.toString();
    }
    
    public static int readInt(BufferedReader r) throws Exception {
        return Integer.parseInt(r.readLine());
    }
}

Measured memory_bytes: 24216
#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;

#define watch(x) cout<<(#x)<<"="<<(x)<<endl
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF 2e14
#define MOD 1000000007
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 2005

ll n,k;
ll arr[MAXN];
ll cnt[MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	mset(cnt,0);
	
	cin>>n>>k;
	forn(i,0,n){
		cin>>arr[i];
		cnt[arr[i]]++;
	}
	
	fore(i,2,2003){
		cnt[i]+=cnt[i-1];
	}
	
	ll ans=0;
	
	forn(i,0,n){
		forn(j,i+1,n){
			if(arr[i]>arr[j]){
				ans++;
				ans%=MOD;
			}
		}
	}
	
	ans*=k;
	ans%=MOD;
	
	forn(i,0,n){
		ll k1=k*(k-1)/2; k1%=MOD;
		ll c1=cnt[arr[i]-1]*k1; c1%=MOD;
		ans+=c1;
		ans%=MOD;
	}
	
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long x = Long.parseLong(sc.next());
        Long[] a = new Long[n];
        Arrays.setAll(a, i -> Long.parseLong(sc.next()));
        sc.close();

        // 主処理
        int result = 0;
        long sum = Arrays.stream(a).mapToLong(i -> i).sum();
        if (x < sum) {
            Arrays.sort(a);
            long num = 0;
            for (int i = 0; i < a.length; i++) {
                num += a[i];
                if (num <= x) {
                    result++;
                }
            }
        } else if (sum < x) {
            result = n - 1;
        } else {
            result = n;
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 27600
#include<iostream>
#include<algorithm>
#include<queue>
#define MAX 101
using namespace std;
int n,d[MAX],color[MAX],A[MAX][MAX];
queue<int> Number_of_vertices;
void input(void){
    cin >> n;
    for(int i=0;i<n;i++){
        d[i] = -1;
        color[i] = 0;
        A[i][i] = 0;
    }
    for(int i=0;i<n;i++){
        int id,adj;
        cin >> id >> adj;
        id--;
        if(i==0){
            Number_of_vertices.push(id);
            d[id] = 0;
            color[id] = 1;
        }
        for(int j=0;j<adj;j++){
            int k;
            cin >> k;
            A[id][--k] = 1;
        }
    }
}
void Breadth_First_Search(void){
    while(!Number_of_vertices.empty()){
        int u = Number_of_vertices.front();
        Number_of_vertices.pop();
        for(int i=0;i<n;i++){
            if(color[i]==0 && A[u][i]==1){
                d[i] = d[u] + 1;
                color[i] = 1;
                Number_of_vertices.push(i);
            }
        }
    }
}
void print(void){
    for(int i=0;i<n;i++){
        cout << i + 1 << ' ' << d[i] << endl;
    }
}
int main(void){
    input();
    Breadth_First_Search();
    print();
    return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
int A, B;

int main(int argc, char ** argv) {
	scanf("%d%d", &A, &B);
	int x = (A+B)/2;
	if(abs(A-x)==abs(B-x)) printf("%d\n", x);
	else puts("IMPOSSIBLE");
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
const int S=200030;
int n,k,su=0,res=0,c[S],f[S],nx[S][26],pre[S],id=1;
char y[S];
inline int mi(int a,int b){return a<b?a:b;}
int main()
{
	scanf("%s",y+1);
	n=strlen(y+1);
	for (int i=0;i<26;i++) nx[n+1][i]=n+1;f[n+1]=1;
	for (int j=n;j;--j)
	{
		for (int i=0;i<26;i++) nx[j][i]=nx[j+1][i];
		nx[j][y[j]-'a']=j;
	}
//	for (int j=n;j;--j)
//	{
//		for (int i=0;i<26;i++) printf("%d ",nx[j][i]);
//		puts("");
//	}
	for (int i=n;i;i--)
	{
		f[i]=1<<30;
		for (int j=0;j<26;j++)
			f[i]=mi(f[i],f[nx[i][j]+1]+1);
//		printf("%d ",f[i]);
	}
	for (int i=1;i<=n;)
	{
		int j;
		for (j=0;j<26;j++)
			if (f[i]==f[nx[i][j]+1]+1)
				break;
		printf("%c",j+'a');
		i=nx[i][j]+1;
	}
	return 0;
}


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

int main()
{
	int m[30];
	int number;
	for(int i=0;i<30 ;i++){
		m[i]=0;
	}

	for(int i=0 ;i<28 ;i++){
		cin >> number;
		for(int j=0 ;j<30 ;j++){
			if(number-1 == j)
				m[number-1]++;
		}
		
	}
	for(int i=0 ;i<30 ;i++){
		if(m[i] == 0)
			cout << i+1 << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
using namespace std;
using ll = long long;

int main(){
  string s;
  cin >> s;
  long long x;
  cin >> x;
  
  ll cnt = 0;
  if(s[0] == '1'){cnt++;}
  for(int i = 0; i < s.size()-1; i++){
    if(s[i] == '1' && s[i+1] == '1'){cnt++;}
    else{break;}
  }
  //cout << cnt << endl;
  if(x <= cnt || cnt == s.size()){cout << 1 << endl;}
  else{cout << s[cnt] << endl;}
}


Measured memory_bytes: 256
# ABC119D - Lazy Faith
from bisect import bisect_right as bsr


def dist(x: int) -> int:
    i, j = bsr(S, x), bsr(T, x)
    ret = min(
        min(abs(s - x) + abs(t - s), abs(t - x) + abs(s - t))
        for s in (S[i - 1], S[i])
        for t in (T[j - 1], T[j])
    )
    return ret


def main():
    global S, T
    A, B, Q, *STX = map(int, open(0).read().split())
    INF = 1 << 60
    S, T, X = [-INF] + STX[:A] + [INF], [-INF] + STX[A : A + B] + [INF], STX[A + B :]
    ans = [dist(x) for x in X]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 40188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset
 
using namespace std;
 
typedef long long Lint;
typedef pair<Lint,Lint> ii;
typedef pair<int,char> ic;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;
 
const int maxn = 1020;
const int maxm = 10000020;
const int MOd = 998244353;

int a;
string s, s2;

void solve() {
	cin >> s >> s2;
	int ans = s2.size();
	for(int i=0;i+s2.size()<=s.size();i++) {
		int cnt = 0;
		for(int j=i;j<i+s2.size() && j < s.size();j++)
			if( s[j] != s2[j-i] ) cnt++;
		umin( ans, cnt );
	}
	cout << ans << endl;
}
 
int main() {
	int n = 1;
	// scanf("%d",&n);
	while( n-- ) solve();
 
	return 0;
}

Measured memory_bytes: 3620
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, A: "List[int]", B: "List[int]"):
    count = 0
    for i in range(N):
        b = min(A[i], B[i])
        count += b
        if A[i] < B[i]:
            c = min(B[i]-A[i], A[i+1])
            count += c
            A[i+1] -= c
    print(count)
    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)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19452
#include<stdio.h>
char code[]={'I','V','X','L','C','D','M'};
int value[]={1,5,10,50,100,500,1000};
int main(){
  int i,j,sum,prev;
  char str[101];
  while(scanf("%s",str)!=EOF){
    for(i=0,sum=0,prev=1000;str[i];i++){
      for(j=0;j<7;j++)
	if(code[j]==str[i]) break;
      if(prev<value[j]){
	sum+=value[j]-prev*2;
      }else{
	sum+=value[j];
      }
      prev=value[j];
    }
    printf("%d\n",sum);
  }
  return 0;
}

Measured memory_bytes: 0
/*
 * @Author: Kaizyn
 * @Date: 2020-03-17 15:19:46
 * @LastEditors: Kaizyn
 * @LastEditTime: 2020-03-17 15:38:23
 * @FilePath: \Code\atcoder\panasonic2020E_3.cpp
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const int N = 2e3+7;

char a[N], b[N], c[N];
bool buf[3][N<<2];
bool *ab = buf[0]+(N<<1), *ac = buf[1]+(N<<1), *bc = buf[2]+(N<<1);

bool cmp(const char &c1, const char &c2)
{
    return c1 == '?' || c2 == '?' || c1 == c2;
}

signed main()
{
    scanf("%s %s %s", a, b, c);
    int la = strlen(a), lb = strlen(b), lc = strlen(c), res = la+lb+lc;
    for (int i = 0; i < la; ++i) for (int j = 0; j < lb; ++j) ab[i-j] |= !cmp(a[i], b[j]);
    for (int i = 0; i < la; ++i) for (int j = 0; j < lc; ++j) ac[i-j] |= !cmp(a[i], c[j]);
    for (int i = 0; i < lb; ++i) for (int j = 0; j < lc; ++j) bc[i-j] |= !cmp(b[i], c[j]);
    for (int i = -(lb+lc); i <= la+max(lb, lc); ++i) {
        for (int j = -(lb+lc); j <= la+max(lb, lc); ++j) {
            if (!ab[i] && !ac[j] && !bc[j-i]) {
                int l = min({0, i, j}),
                    r = max({la, i+lb, j+lc});
                res = min(res, r-l);
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define pb push_back
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int ans= 0;
	if(k>=a)
	{
		k -= a;
		ans += a;
	}
	else if(a>=k)
	{
		ans += k;
		k = 0;
	}
	if(k>=b)
	{
		k -= b;
	}
	else if(b>=k)
	{
		k = 0;
	}
	if(k>=c)
	{
		ans -= c;
		k -= c;
	}
	else if(k<c)
	{
		ans -= k;
		k = 0;
	}
	cout<<ans<<endl;
	return 0;
}

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

const int MAXA = 1.01e6;
const int MAXN = 2.01e5;
int ar[MAXN], c[MAXA];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n; cin >> n;
  memset(c, 0, sizeof c);

  for(int i = 0; i < n; ++i) {
    cin >> ar[i];
    c[ar[i]]++;
  }
 
  int res = 0;
  for(int i = 0; i < n; ++i) {
    c[ar[i]]--;
    bool ok = true;
    for(int x = 1; x <= ar[i] / x; ++x) {
      if(ar[i] % x) continue;
      if(c[x]) ok = false;
      if(ar[i] / x != x && c[ar[i] / x]) ok = false; 
    }
    res += int(ok);
    c[ar[i]]++;
  }

  cout << res << '\n';

  return 0;
}


Measured memory_bytes: 8332
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
P dp[101][50001];

void Max(P &a,P b){a=max(a,b);}

int main(){
  int n,p[101];
  while(cin>>n,n){
    for(int i=0;i<n;i++)cin>>p[i];
  
    memset(dp,-1,sizeof(dp));
    dp[0][0]=P(0,0);
  
    for(int i=0;i<n;i++)
      for(int j=0;j<50000;j++){
	if(dp[i][j]==P(-1,-1))continue;
	int coin=dp[i][j].first;
	int ncost=dp[i][j].second-p[i];
	Max(dp[i+1][j],dp[i][j]);
	if(p[i]%1000<500&&p[i]%1000)Max(dp[i+1][j+(500-p[i]%500)],P(coin+1,ncost));
	if(p[i]%1000==0&&j>=500) Max(dp[i+1][j-500],P(coin+1,ncost));
	
	if(p[i]%1000>=500) {
	  if(j>=p[i]%500)Max(dp[i+1][j-p[i]%500],P(coin+1,ncost));
	  else Max(dp[i+1][j+(500-p[i]%500)],P(coin,ncost));
	}
      }
    
    P ans=P(0,0);
    for(int i=0;i<50000;i++)Max(ans,dp[n][i]);
    cout <<ans.first<<" "<<-ans.second<<endl;
    
  }	
  return 0;
}

Measured memory_bytes: 42500
x = int(input())

a = b = -1
con = True
while con:
  a += 1
  b5 = a**5 - x
  b1 = int(abs(b5**0.2))
  if b1**5 == b5:
    b = b1 
    con = False
  elif b1**5 == -1*b5:
    b = -1*b1
    con = False
print(str(a)+' '+str(b))

Measured memory_bytes: 9436
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N, M;
  cin >> N >> M;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }

  map<ll, ll> mp;
  ll S = 0;
  for (ll i = 0; i < N; i++)
  {
    S += A.at(i);
    mp[S % M]++;
  }

  ll ans = 0;
  for (auto mx : mp)
  {
    ll m = mx.first, x = mx.second;
    ans += x * (x - 1) / 2;
    if (m == 0)
      ans += x;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4992
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 500010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define db double
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
	char c; ll x,f=1;
	for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
	for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

map<char,int>mp;
int n;
char cz[110];
ll a[10];

int main()
{
	n=r();
	mp['M']=1;
	mp['A']=2;
	mp['R']=3;
	mp['C']=4;
	mp['H']=5;
	rep(i,1,n)
	{
		scanf("%s",cz);
		a[mp[cz[0]]]++;
	}
	ll ans=0;
	rep(i,1,5) rep(j,i+1,5) rep(k,j+1,5)  ans+=1ll*a[i]*a[j]*a[k];
	cout<<ans<<endl;
	return 0;
}

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

int main(){
	int n,a,b;
	string s,t;
	char c;
	cin>>n>>s;
	b=s.size();
	for(int i=0; i<b; i++){
		c=s[i];
		a=(int)c;
		a=(a-65+n)%26+65;
		t+=(char)a;
	}
	cout<<t<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll dat[100005];
pair<ll,ll> p[100005];
ll sz[100005];
ll from[100005];
ll to[100005];
ll n;
int main() {
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>dat[i];
		p[i]=make_pair(dat[i],i);
	}
	sort(p,p+n);
	ll id=0;
	ll sum=0;
	for(int i=0;i<n;i++){
		sz[i]=1;
	}
	for(ll i=n-1;i>=1;i--){
		ll curid=p[i].second;
		ll tmp=p[i].first;
		ll nx=n-2*sz[curid];
		if(nx<=0){
			cout<<-1<<endl;
			return 0;
		}
		ll pos=lower_bound(p,p+n,make_pair(tmp-nx,0LL))-p;
		if(p[pos].first!=tmp-nx){
			cout<<-1<<endl;
			return 0;
		}
		from[id]=p[i].second;
		to[id++]=p[pos].second;
		sum+=sz[curid]*(n-sz[curid])*2;
		sz[p[pos].second]+=sz[curid];
	}
	ll ans=0;
	for(ll i=0;i<n;i++){
		ans+=dat[i];
	}
	if(sum!=ans) {
		cout<<-1<<endl;
		return 0;
	}
	for(ll i=0;i<id;i++){
		cout<<from[i]+1<<" "<<to[i]+1<<endl;
	}
	return 0;
}


Measured memory_bytes: 6144
n, m, k = list(map(int, input().split()))

# 二項係数を 10^9+7 で割った余りを求める
# https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#5-%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0-ncr
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
# https://www.hamayanhamayan.com/entry/2018/06/06/210256

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = n * m #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
	factori_table[i] = factori_table[i-1] * (i) % mod

# 	factori_inv_table[i] = modinv(factori_table[i])
#	↑が遅いので、使うところだけ逆元を計算する↓
for i in [k-2, n*m-k]:
	factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
	# n! / (k! * (n-k)! )
	return factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]

ans_1 = 0
for i in range(n):
	ans_1 += i * m**2 * (n-i) % mod
for i in range(m):
	ans_1 += i * n**2 * (m-i) % mod

print(binomial_coefficients(n*m-2, k-2) * ans_1 % mod)


Measured memory_bytes: 12532
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  int a,b;
  cin>>a>>b;


  cout << a*b << endl;

}

Measured memory_bytes: 3488
a, b = map(int, input().split())
consume = 0
count = 0
mini = 1000
for i in range(a):
    mi = int(input())
    consume += mi
    count += 1
    if(mi <= mini):
        mini = mi
while(consume + mini <= b):
    consume += mini
    count += 1
print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <math.h> 
#include <iomanip>
#include <string.h>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI 3.14159265358979323846264338327950L

#define INF 0x3f3f3f3f
//const int N = 2e5 + 5;
   
int sum(int l, int r) {

	return (l + r)*(r - l + 1) / 2;

}

int gcd(int a, int b) {

	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a%b);
	}

}

int32_t  main() {

	IOS;

	int K;

	cin >> K;

	queue<int> q;

	vector<int> ans;
	for (int i = 1; i <= 9; i++) {
		q.push(i);
		ans.push_back(i);
	}

	if (K <= ans.size()) {

		cout << ans[K - 1] << endl;
		return 0;
	}

	while (true) {

		if (ans.size() >= K) {
			cout << ans[K - 1] << endl;
			break;
		}

		int tmp = q.front();

		q.pop();

		for (int i = -1; i <= 1; i++) {

			int curr = tmp % 10;

			curr += i;
			if (curr < 0 || curr > 9)
				continue;
			int newN = tmp * 10 + curr;

			q.push(newN);

			ans.push_back(newN);


		}


	}



}


Measured memory_bytes: 4204
(n, k) = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]

s = 0
sums = [0]
for i in p:
  	s += i
  	sums.append(s)

maxNum = -1
maxIndex = [0, 0]
for i in range(len(sums)-k):
  if sums[i+k] - sums[i] > maxNum:
    maxNum = sums[i+k] - sums[i]
    maxIndex = [i, i+k-1]

dices = p[maxIndex[0]:maxIndex[1]+1]
e = 0
for dice in dices:
  e += sum(list(range(1, dice+1))) / dice
print(e)



Measured memory_bytes: 80992
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
constexpr int MAX = 5000000;

vector<int> bfs(int start, vector<vector<int>>& g) {
	vector<int> d(g.size(), inf);
	d[start] = 0;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int next : g[cur]) {
			if (chmin(d[next], d[cur] + 1)) {
				q.push(next);
			}
		}
	}
	return d;
}
int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, x, y; cin >> n >> x >> y; x--; y--;
	vector<vector<int>> dist(n, vector<int>(n, inf));
	vector<vector<int>> g(n); g[x].emplace_back(y), g[y].emplace_back(x);
	for (int i = 0; i + 1 < n; i++) {
		g[i].emplace_back(i + 1);
		g[i + 1].emplace_back(i);
	}
	for (int i = 0; i < n; i++) dist[i] = move(bfs(i, g));
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			res[dist[i][j]]++;
		}
	}

	for (int i = 1; i < n; i++) cout << res[i] << "\n";
	return 0;
}

Measured memory_bytes: 19396
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
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; }
typedef pair <ll,ll> P;

int main()
{
    ll N, K;
    cin >> N >> K;
    ll t = N % K;
    print(t);
    return 0;
}

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

int H, n, A;

int main()
{
    scanf("%d %d", &H, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A);
        H -= A;
    }
    if (H <= 0) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

ll gcd(ll a, ll b) {
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main()
{
    ll a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
}

Measured memory_bytes: 3600
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) { return a * b * gcd(a, b); }

bool compareP(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

int main() {
    int n, ans = 0;
    cin >> n;
    char c;
    int s[n];
    rep(i, n) {
        cin >> c;
        s[i] = c - '0';
    }
    // size_t size = s.length();
    // cout << size << endl;
    //    rep(i, n) s[i] = s[i];
    bool seen3[10][10][10] = {}, seen2[10][10] = {}, seen[10] = {};
    rep(i, n - 2) {
        if (seen[s[i]])
            continue;
        seen[s[i]] = true;
        for (int j = i + 1; j < n - 1; j++) {
            if (seen2[s[i]][s[j]])
                continue;
            seen2[s[i]][s[j]] = true;
            for (int k = j + 1; k < n; k++) {
                if (seen3[s[i]][s[j]][s[k]])
                    continue;
                ans++;
                seen3[s[i]][s[j]][s[k]] = true;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
from fractions import gcd


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


gcd_l = [0] * n
gcd_r = [0] * n
for i in range(n):
    if i == 0:
        gcd_l[i] = A[i]
        gcd_r[-i-1] = A[-i-1]
    else:
        gcd_l[i] = gcd(gcd_l[i-1], A[i])
        gcd_r[-i-1] = gcd(gcd_r[-i], A[-i-1])

ans = [0] * n
ans[0] = gcd_r[1]
ans[n-1] = gcd_l[n-2]
for i in range(1, n-1):
    ans[i] = gcd(gcd_l[i-1], gcd_r[i+1])
print(max(ans))


Measured memory_bytes: 16152
#include <stdio.h>

int main() {
	double x1, y1, x2, y2, x3, y3, xp, yp;
	double s, t;

	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp) != EOF) {
		s = ((xp - x1) * (y3 - y1) - (yp - y1) * (x3 - x1)) /
				((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));

		t = ((xp - x1) * (y2 - y1) - (yp - y1) * (x2 - x1)) /
				((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1));

		if(s > 0 && t > 0 && s + t < 1)
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 1040
#include <stdio.h>
#include <math.h>

int main(void){
	int N;
	int T,A;
	int i;
	int H[1000];
	double y = 0.006;
	double min=11111111,temp;
	int ans=1;
	scanf("%d",&N);
	scanf("%d %d",&T,&A);
	for(i=0;i<N;i++){
		scanf("%d",&H[i]);
		temp = (double)A - ((double)T - 0.006 * (double)H[i]);//tempは気温の差
		temp = fabs(temp);
		if ( temp < min ){
			min = temp;
			ans = i;
		}
	}
	printf("%d",ans+1);
	return 0;
}

Measured memory_bytes: 128