akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]
#![allow(unused_imports)]
 
use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;

#[fastout]
fn main() {
    input!{
        N:usize,
        K:usize,
        A: [usize; N],
    }
    let mut town_map: BTreeMap<usize, usize> = BTreeMap::new();
    let mut cnt_map: BTreeMap<usize, usize> = BTreeMap::new();
    
    let mut last_town: usize = 0;
    let mut start_town: usize = 1;
    let mut cnt: usize = 0;
    town_map.insert(1, 0);
    cnt_map.insert(0, 1);

    loop {
        if town_map.contains_key(&A[start_town-1]) {
            cnt_map.insert(cnt+1, A[start_town-1]);
            last_town = A[start_town-1];
            cnt += 1;
            break;
        } else {
            town_map.insert(A[start_town-1], cnt+1);
            cnt_map.insert(cnt+1, A[start_town-1]);
            start_town = A[start_town-1];
            cnt += 1;
        }
    }
    // println!("town_map: {:?}\n cnt_map: {:?}\n last_town: {}, cnt: {}", town_map, cnt_map, last_town, cnt);

    let cycele_lenght: usize = cnt - town_map.get(&last_town).unwrap();
    let mod_k: usize = (K - town_map.get(&last_town).unwrap()) % cycele_lenght;

    // println!("cl: {}, mod_k: {}", cycele_lenght, mod_k);

    let ans: usize = if K < *(town_map.get(&last_town).unwrap()) { *cnt_map.get(&K).unwrap() } else {*cnt_map.get(&(town_map.get(&last_town).unwrap() + mod_k)).unwrap()};
    println!("{}", ans)
    
}


Measured memory_bytes: 17900
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int N, K;

int main() {
    cin >> N >> K;

    string S;
    cin >> S;

    vi change(0);
    if(S[0]=='0') change.push_back(0);
    int last = 'x';
    for (int i = 0; i < N; i++) {
        if(S[i] == last) continue;
        change.push_back(i);
        last = S[i];
    }
    change.push_back(N);

    int ans = 0;
    for (int i = 0; i < change.size(); i+=2) {
        ans = max(ans, change[min(i+2*K+1, (int)(change.size()-1))]-change[i]);
    }
    
    if(change.size() == 2) ans = N;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1020
import java.util.*;

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();

        if((a==b && a!=c) || (a==c && a!=b) || (b==c && b!=a)){
            System.out.println(2);
        }
        else if(a==b && b==c){
            System.out.println(1);
        }
        else{
            System.out.println(3);
        }
    }
}

Measured memory_bytes: 21076
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

int main() {
    int N;
    cin >> N;
    map <string, int> cnt;

    for (int i = 0; i < N; ++i) {
        string j;
        cin >> j;
        ++cnt[j];
    }

    cout << "AC x " << cnt["AC"] << endl;
    cout << "WA x " << cnt["WA"] << endl;
    cout << "TLE x " << cnt["TLE"] << endl;
    cout << "RE x " << cnt["RE"] << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>

using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
    
    int s, c;
    int v[3] = {-1, -1, -1};
    for (int i = 0; i < m; i++) {
        cin >> s >> c;
        s--;
        if (v[s] == -1 || v[s] == c) {
            v[s] = c;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }

    int ans = 0;
    if (n == 1) {
        if (v[0] == -1) {
            v[0] = 0;
        }
        ans = v[0];
    }

    if (n == 2) {
        if (v[0] == 0) {
            cout << -1 << endl;
            return 0;
        }
        if (v[0] == -1) v[0] = 1;
        ans = v[0] * 10 + max(v[1], 0);
    }

    if (n == 3) {
        if (v[0] == 0) {
            cout << -1 << endl;
            return 0;
        }
        if (v[0] == -1) v[0] = 1;
        ans = v[0] * 100 + max(v[1], 0) * 10 + max(v[2], 0);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.math;

void main() {
	int n = readln.chomp.to!int;

	long debt = 100000;
		foreach(i;0..n) {
		debt += debt * 0.05;
		debt = (((debt / 1000.0).ceil) * 1000).to!long;
	}
	debt.writeln;
}

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

typedef long long ll;

const int maxn=1e5+10;
const int inf=1e9+7;



int main()
{
	ll a;
	string b;
	cin>>a>>b;
	b.erase(1,1);
	ll c=stoll(b);
	ll ans=a*c/100;
	printf("%lld\n",ans);
}

Measured memory_bytes: 3636
#include<stdio.h>
#define N 2000
#define INF 10000
#define WHITE 0
#define BLACK 1
int G[N][N];
int n;

int prim(){
  int i,u,v,d[N],pi[N],color[N];
  int c,mincost;
  for(i=0;i<n;i++){
    d[i]=N;
    pi[i]=-1;
    color[i]=WHITE;
  }
  while(1){ 
    mincost = INF;
    for(i=0;i<n;i++){
      if (color[i] != BLACK && d[i] < mincost){
	mincost = d[i];
	u = i;
      }
    }
    if (mincost == INF)
      break;
    color[u] = BLACK;
    for (v=0;v<n;v++){
      if (color[v] != BLACK && G[u][v] < d[v] && G[u][v]!=-1){
	pi[v] = u;
	d[v] = G[u][v];
      }
    }
  }
  c=0;
  for(i=0;i<n;i++)
    c+=G[i][pi[i]];
  return c;
}
  
int main(){
  int i,j,pr;
  int d[N],pi[N],color[N];
  scanf("%d",&n);
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      scanf("%d",&G[i][j]);
  pr=prim();
  printf("%d\n",pr);
  return 0;
}

Measured memory_bytes: 1040
import math

A, B, H, M = map(int, input().split())


H_rad = (H * 30 + M * 0.5) % 360
M_rad = M * 6

rad = abs(M_rad-H_rad)

ans = (A ** 2) + (B ** 2) - (2 * A * B * math.cos(math.radians(rad)))

print(math.sqrt(ans))

Measured memory_bytes: 9508
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;
vector<int>G[maxn];
queue<int>q;
int in[maxn];
int main(){
	int  n,m;
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i = 1;i <= m;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		in[y]++;
	}
	for(int i = 1;i <= n;i++){
		if(in[i] == 0) q.push(i);
	}
	int ans = 0;
	while(!q.empty()){
		int cnt = q.size();
		//cout << cnt << endl;
		for(int i = 1;i <= cnt;i++){
		int cur = q.front();
		q.pop();
		int len = G[cur].size();
		for(int i = 0;i < len;i++){
			int tmp = G[cur][i];
			in[tmp]--;
			if(in[tmp] == 0) q.push(tmp);
		}
		}
		ans++;
	}
	ans--;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 9628
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using P = pair<int, int>;
constexpr int MX = 100005, INF = 2e9+5;
int n,x,l,a[MX];
P p[MX];
int main(){
	scanf("%d", &n);
	rep(i,n){
		scanf("%d%d", &x, &l);
		p[i] = {x+l,x-l};
	}
	sort(p,p+n);
	rep(i,n){
		l = p[i].second;
		auto it = lower_bound(p,p+n,P{l,INF});
		if(it != p) a[i] = a[it-1-p] + 1;
		else a[i] = 1;
		if(i) a[i] = max(a[i],a[i-1]);
	}
	printf("%d\n", a[n-1]);
}

Measured memory_bytes: 1408
import bisect
N = int(input())
L_array = list(map(int,input().split()))

L_array.sort()

# print(L_array)
ans = 0
for i in range(N):
    for j in range(i+1,N):
        max_len = L_array[i] + L_array[j] - 0.1
        max_index = bisect.bisect_left(L_array,max_len) - 1
        # print(i,j,max_len,max_index)
        if j < max_index:
            ans += (max_index - j)
print(ans)

Measured memory_bytes: 43372
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <unordered_map>

#define rep(i, a, b) for (ll i = a; i < b; i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef unordered_map<string, ll> u_map;

// input
void input() {}
template <class Head, class... Tail>
void input(Head &&a, Tail &&... b)
{
    cin >> a;
    input(forward<Tail>(b)...);
}

template <class V>
void input(vector<V> &v)
{
    for_each(v.begin(), v.end(), [](auto &i) { input(i); });
}

// output
template <class V>
void output(vector<V> &v)
{
    for_each(v.begin(), v.end(), [](auto &x) { cout << x << " "; });
    cout << endl;
}

// math functions
ll mpow(ll a, ll n, ll p)
{
    ll x = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            x = a * x % p;
        }
        a = a * a % p;
        n >>= 1;
    }

    return x;
}

ll mfact(ll n, ll p)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
    {
        res = res * i % p;
    }
    return res;
}

ll mcomb(ll n, ll r, ll p)
{
    if (n == 0 && r == 0)
    {
        return 1;
    }
    if (n < r || n < 0 || r < 0)
    {
        return 0;
    }

    ll a = mfact(n, p);
    ll b = mfact(n - r, p);
    ll c = mfact(r, p);
    return (((a * mpow(b, p - 2, p)) % p) * mpow(c, p - 2, p)) % p;
}

ll gcd(ll a, ll b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return b ? gcd(b, a % b) : a;
}

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

int main()
{
    int A, B, C;
    input(A, B, C);

    set<int> s;
    s.insert(A);
    s.insert(B);
    s.insert(C);

    if (s.size() == 2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
    #include <string.h>
     
    int main(void)
    {
        int a;
        int b;
        int c;
        scanf("%d",&a);    
     
        int e = a;
     
        while(a){
        b = a % 10;
        c = c + b;
        a = a / 10;
      }
     
    int d = e % c;
    if(d == 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
       return 0;
    }

Measured memory_bytes: 128
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let _n : i32 = s.trim().parse().ok().unwrap();
    let mut t = String::new();
    std::io::stdin().read_line(&mut t).ok();
    let k : i32 = t.trim().parse().ok().unwrap();
    let mut u = String::new();
    std::io::stdin().read_line(&mut u).ok();
    let xs : Vec<i32> = u.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();

    let mut ans = 0;
    for x in xs {
        //println!("{}", x);
        ans += std::cmp::min(x,(k-x).abs()) * 2;
    }
    println!("{}", ans);

}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

long long n,k,f[N];

ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	ll ans=0;
	for(int i=k;i>=1;i--){
		f[i]=power(k/i,n);
		for(int j=2*i;j<=k;j+=i) f[i]-=f[j];
		ans=(ans+i*f[i]%mod)%mod;//大小×个数才是该数所有的和
	}
	cout<<(ans+mod)%mod<<'\n';
	return 0;
}


Measured memory_bytes: 4368
//F5で実行 Shift+F5で停止
//F9でブレークポイント
#include<cmath>
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
//Shift+PageUpで上部の大半を選択できる
// 1e18 = 10の18乗

int N;
int A[100];
string S;

void _main() {
	cin >> S;

	string x = "x";

	rep(i, 0, S.length()) {
		S[i] = x[0];
	}

	cout << S << endl;
}

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

typedef long long ll;

int n,p,q,ans,as,bs;
int dp[41][500][500];

int main(){
    cin>>n>>p>>q;
    ans=4001;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
        as+=a[i];
        bs+=b[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=400;j++){
            for(int k=0;k<=400;k++){
                dp[i][j][k]=4001;
            }
        }
    }
    dp[0][0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=400;j++){
            for(int k=0;k<=400;k++){
                if((j-a[i]<0)||(k-b[i]<0))dp[i+1][j][k]=dp[i][j][k];
                else dp[i+1][j][k]=min({dp[i+1][j][k],dp[i][j][k],dp[i][j-a[i]][k-b[i]]+c[i]});
            }
        }
    }

    //cout << dp[n][3][3] << endl;

    for(int i=1;(i*p<=400)&&(i*q<=400);i++){
        ans=min(ans,dp[n][i*p][i*q]);
        //printf("%d %d\n",ans,i);
    }

    if(ans==4001)cout<<-1<<endl;
    else cout<<ans<<endl;
}


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


int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int N,M; cin >> N >> M;
    vector<int> count(M,0);
    for(int i = 0; i < N; i++){
        int K; cin >> K;
        for(int j = 0; j < K; j++){
            int A; cin >> A; A--;
            count[A]++;
        }
    }
    int ans = 0;
    for(int i = 0; i < M ; i++){
        if(count[i] == N) ans++;
    }
    cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

vs input(string& s)
{
	int t = s.find('-');
	string l = s.substr(0, t);
	string r = s.substr(t + 1);
	vs res;
	res.push_back(l); res.push_back(r);
	return res;
}

int main()
{
	cin.sync_with_stdio(false);
	int n;
	while (cin >> n, n)
	{
		vector<vs> v(n);
		map<string, int> mp;
		REP(i, n)
		{
			string s; cin >> s;
			v[i] = input(s);
		}
		int p = 0;
		REP(i, n)REP(j, 2)
		{
			string tmp = v[i][j];
			if (mp.count(tmp)) continue;
			mp[tmp] = p;
			p++;
		}
		Graph g(p);
		Matrix dist(p, Array(p));
		REP(i, n)
		{
			int l = mp[v[i][0]], r = mp[v[i][1]];
			add_edge(g, l, r, 1);
			add_edge(g, r, l, 1);
			dist[r][l] = 1;
		}
		vector<pii> same;
		REP(i, p)REP(j, i)
		{
			bool f1 = false, f2 = true;
			REP(k, p)
			{
				if ((dist[i][k] || dist[k][i]) && (dist[j][k] || dist[k][j])) f1 = true;
				if ((dist[i][k] && dist[k][j]) || (dist[k][i] && dist[j][k])) f2 = false;
			}
			if (f1&&f2) same.emplace_back(i, j);
		}
		for (auto i : same)
		{
			dist[i.first][i.second] = 1;
			dist[i.second][i.first] = 1;
		}
		REP(k, p)REP(i, p)REP(j, p)
		{
			if (dist[i][k] && dist[k][j]) dist[i][j] = 1;
		}
		vi color(p);
		int col = 1;
		REP(i, p)
		{
			if (color[i]) continue;
			queue<int> que;
			que.push(i);
			int c = col, d = -col;
			color[i] = c;
			while (que.size())
			{
				int t = que.front();
				que.pop();
				int nx = (color[t] == c ? d : c);
				REP(j, g[t].size())
				{
					if (color[g[t][j].to]) continue;
					color[g[t][j].to] = nx;
					que.push(g[t][j].to);
				}
			}
			col++;
		}
		cout << p << endl;
		int q;
		cin >> q;
		REP(i, q)
		{
			string s; cin >> s;
			vs t = input(s);
			if (!mp.count(t[0]) || !mp.count(t[1]))
			{
				cout << "NO" << endl;
				continue;
			}
			int l = mp[t[0]], r = mp[t[1]];
			if (color[l] == -color[r] && dist[r][l])
			{
				cout << "YES" << endl;
			}
			else
			{
				cout << "NO" << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3508
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793
 

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

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define ii pair<int,int>
#define st first
#define nd second
#define N 200005
#define inf 1000000000
#define MOD 998244353
#define sz(x) ((int)x.size())
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
using namespace std;

int n,m;
string s,t;
vector<int> pos[26];

int main(int arg,char* argv[]) {

	cin>>s>>t;

	n=sz(s);
	m=sz(t);

	s=s+s;

	for(int i=0;i<n+n;i++) {

		pos[s[i]-'a'].pb(i);

	}	

	ll cur=1;
	int cpos=-1;

	for(int i=0;i<m;i++) {

		auto nxt=lower_bound(pos[t[i]-'a'].begin(),pos[t[i]-'a'].end(),cpos+1);

		if(nxt==pos[t[i]-'a'].end()) {

			cur=-1;

			break ;

		}

		if(*nxt>=n) cur++;

		cpos=*nxt%n;

	}

	if(cur!=-1) cout<<(cur-1)*n+cpos+1;
	else cout<<-1;

}

Measured memory_bytes: 1788
alpha='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alpha2='DEFGHIJKLMNOPQRSTUVWXYZABC'
caesar=list(input())
for i in range(len(caesar)):
    for j in range(len(alpha2)):
        if caesar[i]==alpha2[j]:
            caesar[i]=alpha[j]
            print(caesar[i],end='')
            break
print('')


Measured memory_bytes: 5716
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
public class PG {
    public static void Main() {
        char[] r = Console.ReadLine().ToCharArray();
        char[] o = r.Length==2 ? r : r.AsEnumerable().Reverse().ToArray();
        Console.WriteLine(o);
    }
}

Measured memory_bytes: 13268
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};

int main(){
    int a,p;
    cin>>a>>p;
    cout<<(a*3+p)/2;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x;
    for (int i=0; i<m; i++) {
        int tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    sort(x.begin(), x.end());    

    vector<int> diff;
    for (int i=0; i<m-1; i++) {
        diff.push_back(x[i+1] - x[i]);
    }
    sort(diff.begin(), diff.end());

    int ans = 0;   
    for (int i=0; i<m-n; i++) {
        ans += diff[i];
    }
    if (n >= m) cout << 0 << endl;
    else cout << ans << endl;
}


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

#define endl '\n'

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

    int n; cin >> n;
    int a[n]; for (int i=0; i<n; i++) cin >> a[i];

    int ans = 0;
    for (int k=1; k<=100; k++){
        int cur = 0;
        for (int i=0; i<n; i++){
            cur += (k - a[i])*(k - a[i]);
        }
        if (k == 1) ans = cur;
        else ans = min(ans, cur);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll pow(ll x,ll y){
  if(y==0) return 1;
  ll res=pow(x,y/2);
  res*=res;
  res%=mod;
  if(y%2==1) res*=x;
  return res%mod;
}
ll gyaku(ll x){
  return pow(x,mod-2);
}
vector<ll> frac,gfrac;
void set_frac(ll n){
  frac.push_back(1);
  gfrac.push_back(1);
  for(ll i=1;i<=n;i++){
    frac.push_back(frac[i-1]*i%mod);
    gfrac.push_back(gyaku(frac[i]));
  }
}
ll nCr(ll n,ll r){
  ll res=frac[n]*gfrac[r]%mod;
  res*=gfrac[n-r];
  return res%mod;
}
ll cnt[1000005]={0};
int main(){
  ll n;
  cin>>n;
  vector<ll> vec;
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    vec.push_back(a);

    for(ll k=2;k*k<=a;k++){
      ll kn=0;
      while(a%k==0){
        a/=k;
        kn++;
      }
      cnt[k]=max(cnt[k],kn);
    }
    if(a!=1){
      cnt[a]=max(cnt[a],(ll)1);
    }
  }
  ll lcm=1;
  for(ll i=1;i<1000005;i++){
    lcm*=pow(i,cnt[i]);
    lcm%=mod;
  }
  ll ans=0;
  for(int i=0;i<n;i++){
    ans+=(lcm*gyaku(vec[i]))%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 6784
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()

using namespace std;

int main(){

    int n;
    cin >> n;

    if(n == 1){
        cout << "Hello World" << endl;
    }else{
        int a,b;
        cin >> a >> b;

        cout << a + b << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import scala.annotation.tailrec
import scala.io.StdIn._
object Main extends App {


  solve()
  @tailrec def solve(): Unit = {
    val n = readInt()
    if (n == 0) return
    val top = Array.fill(21){Array.fill(21){0}}
    val height = Array.fill(21){Array.fill(21){0}}
    for (_ ← 0 until n ){
      val Array(t, f) = readLine.trim.split(' ').map(_.toInt)
      var dice = Dice(t, f)
      var pos = Point(10, 10)
      while (Direction.all.exists(dir ⇒ dice.valueAt(dir) > 3 && height(pos.x)(pos.y) > height(pos.move(dir).x)(pos.move(dir).y))) {
        val dir = Direction.all.filter(dir ⇒ dice.valueAt(dir) > 3 && height(pos.x)(pos.y) > height(pos.move(dir).x)(pos.move(dir).y)).maxBy(dir ⇒ dice.valueAt(dir))
        dice = dice.rotate(dir)
        pos = pos.move(dir)
      }
      top(pos.x)(pos.y) = dice.top
      height(pos.x)(pos.y) += 1
      //println(top.map(_.mkString(" ")).mkString("\n"))
    }
    val counts = Array.fill(6){0}
    for (line ← top; cell ← line if cell != 0) counts(cell - 1) += 1
    println(counts.mkString(" "))
    solve()
  }
}
case class Point(x: Int, y: Int) {
  def +(that: Point): Point = Point(x + that.x, y + that.y)
  def move(direction: Direction): Point = {
    direction match {
      case Up ⇒ Point(x, y - 1)
      case Right ⇒ Point(x + 1, y)
      case Down ⇒ Point(x, y + 1)
      case Left ⇒ Point(x - 1, y)
    }
  }
}
object Dice {
  def apply(top: Int, front: Int): Dice = {
    var dice = new Dice(1, 3, 5)
    while (dice.front != front) {
      dice = if (dice.front == 3) dice.rotateRight.rotateUp else dice.rotateUp
    }
    while (dice.top != top) {
      dice = dice.rotateRight
    }
    dice
  }
}
class Dice(val top: Int, val front: Int, val right: Int) {
  def rotateRight: Dice = new Dice(7 - right, front, top)
  def rotateLeft: Dice = new Dice(right, front, 7 - top)
  def rotateUp: Dice = new Dice(front, 7 - top, right)
  def rotateDown: Dice = new Dice(7 - front, top, right)
  def rotate(direction: Direction): Dice = {
    direction match {
      case Up ⇒ rotateUp
      case Right ⇒ rotateRight
      case Down ⇒ rotateDown
      case Left ⇒ rotateLeft
    }
  }
  def valueAt(direction: Direction): Int = {
    direction match {
      case Up ⇒ 7 - front
      case Right ⇒ right
      case Down ⇒ front
      case Left ⇒ 7 - right
    }
  }
}
object Direction {
  val all = List(Up, Right, Down, Left)
}
sealed trait Direction
case object Up extends Direction
case object Right extends Direction
case object Down extends Direction
case object Left extends Direction


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

int main() {
	long long a,b;
	while (cin >> a >> b) {
		long long gcd,lcm;
		// ??????????????????????????????
		long q = max (a,b);
		long r = min (a,b);
		for (;;) {
			if (r == 0) break;
			long new_r;
			new_r = q % r;
			q = r;
			r = new_r;
		}
		gcd = q;
		lcm = a * b / gcd;
		cout << gcd << " " << lcm << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#define REP(i,a,b) \
for(int i=int(a);i<=int(b);i++)
#define DEP(i,a,b) \
for(int i=int(a);i>=int(b);i--)
#define TR(c, it) \
for (auto it = (c).begin(); it != (c).end(); it++)

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a,b;
  cin>>a>>b;
  cout<<a*b;
	return 0;
}


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

using namespace std;

int all[1000001];
int odd[1000001];

int const INF = 1<<29;

int main() {
  
  fill(all, all+1000001, INF);
  fill(odd, odd+1000001, INF);
  
  all[0] = odd[0] = 0;
  
  for(int i=1; ; i++) {
    int n = i*(i+1)*(i+2)/6;
    if(n > 1000000) break;
    for(int j=n; j<=1000000; j++) {
      all[j] = min(all[j-n]+1, all[j]);
      if(n % 2) {
	odd[j] = min(odd[j-n]+1, odd[j]);
      }
    }
  }
  
  int N;
  while(cin >> N && N) {
    cout << all[N] << ' ' << odd[N] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 8972
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

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

int main(){
	ll n,m; cin >> n >> m;
  set<int> st;
	int a=1,b=n;
	rep(i,m){
		cout << a << " " << b << endl;
    st.insert(b-a);
    st.insert(n-(b-a));
		a++; b--;
    if(b-a==n-(b-a)||st.count(b-a)) b--;
  }
	
}

Measured memory_bytes: 11844
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

bool su(int a, int b, int k){
    int sum = 0;
    string ii = to_string(k);
    for(int i = 0;i<ii.length();i++){
        sum += (ii[i] - 48);
    }
    if(a<=sum&&b>=sum){
        return true;
    }
    else return false;
}

int main(){
    int n, a, b, sum = 0;
    cin >> n >> a >> b;
    for(int i = 1;i<=n;i++){
        if(su(a,b,i)){
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions 
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
#endif


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

    int N, X; cin >> N >> X;
    vi x(N); REP(i, N) cin >> x[i];

    x.push_back(X);

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

    vi d(N);    
    FOR(i, 1, N+1) d[i-1] = x[i] - x[i - 1];

    int ans = d[0];
    FOR(i, 1, N) ans = gcd(ans, d[i]);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
const int INFTY = 1001001001;

void djkstra(int N, vector<vector<int> >& edges, vector<int>& state, vector<int>& dist){
    dist[1] = 0;
    while(1){
        int min_i = -1, min_v = INFTY;
        for(int i=0;i<N;++i){
            if(state[i] == 0 && min_v > dist[i]){
                min_i = i;
                min_v = dist[i];
            }
        }
        if(min_i == -1) break;
        state[min_i] = 1;
        for(int e =0;e<N;++e){
            if(state[e] == 0 && dist[e] > dist[min_i] + edges[e][min_i]){
                dist[e] = dist[min_i] + edges[e][min_i];
            }
        }
    }
}

int main()
{
    int H, W;
    cin >> H >> W;
    vector< vector<int> > cost(10, vector<int>(10)), A(H, vector<int>(W));
    vector<int> dist(10, INFTY), state(10, 0);
    for(int i=0;i<10;++i){
        for(int j=0;j<10;++j){
            cin >> cost[i][j];
        }
    }

    djkstra(10, cost, state, dist);

    int a, ans=0;
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            cin >> a;
            if(a != -1)
                ans += dist[a];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;
    if (A < C && C < B || A > C && C > B) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define X first;
#define Y second;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const ll INF = 2e18;
const int inf = 1e9+10;
const int maxN = 2e5 + 10;
const int maxK = 1e4+10;
const int maxD = 15;
const int maxH = 100; 
const int MOD = 1e9+7;

int n;
char s[maxN];
int main()
{
	cin>>n;
	scanf("%s",s+1);
	int cnt = 0;
	queue<int> Q;
	for(int i=1;i<=n;i++)
	{
		if(s[i] == 'R')
		{
			cnt++;
			Q.push(i);
		}
	}
	while(!Q.empty())
	{
		int x = Q.front();
		if(x <= cnt)
		{
			Q.pop();
		}
		else
		{
			break;
		}
	}
	int ans = 0;
	for(int i=1;i<=cnt;i++)
	{
		if(s[i] == 'W')
		{
			if(!Q.empty())
			{
				int x = Q.front();
				swap(s[i],s[x]);
				Q.pop();
				ans++;
			}	
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4292
import java.util.*;
class Main{
	public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
      	int[] numbers = new int[5];
      	int lastdish = 0;
      	for(int i=0;i<5;i++){
        	numbers[i] = scan.nextInt();
        }
      	for(int i=0;i<5;i++){
        	if(numbers[i]%10 !=0 && resi(numbers[i]) < resi(numbers[lastdish])){
            	lastdish = i;
            }
        }
      	int time = 0;
      	for(int i = 0;i<5;i++){
        	if(i != lastdish){
            	time += kuriage(numbers[i]);
            }
        }
      	time+= numbers[lastdish];
        System.out.println(time);
    }
  	public static int resi(int n){
    	    int r=0;
          	if(n%10 == 0){
            	r = 10;
            } else {
            	r = n%10;
            }
      	return r;
    }
  	public static int kuriage(int n){
    	int a = 0;
      	if(n%10 == 0){
        	return n;
        } else {
        	return n + (10-n%10);
        }
    }
  
}

Measured memory_bytes: 22868
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>
//#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,s,n) for(int i=(s);i<(n);++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define REPR(i,s,n) for(int i=(s);i>=(n);--(i))
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
typedef vector<P> vP;
using Edge = pair<int, ll>;
using Graph = vector<vector<Edge> >;
const ll mod = 1e9 + 7;
ll dx[4] = { 1,0,-1,0 };
ll dy[4] = { 0,1,0,-1 };

void printvll(vll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) cout << v[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}
void printvvll(vvll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) {
		rep(j, v[i].size()) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void prints(string s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) cout << s[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}

void printvs(vs s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) {
		rep(j, s[i].size()) {
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void Yes(bool x) {
	if (x) cout << "Yes\n";
	else cout << "No\n";
}

void YES(bool x) {
	if (x) cout << "YES\n";
	else cout << "NO\n";
}

void yes(bool x) {
	if (x) cout << "yes\n";
	else cout << "no\n";
}

void Yay(bool x) {
	if (x) cout << "Yay!\n";
	else cout << ":(\n";
}
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}



ll  d, n, r, l, k, ans = 0, ret = M;
bool flag = false, flag2 = false, flag3 = false;
string s, t;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	vll v(n);
	rep(i, n) cin >> v[i];
	vll a(n+1,0), b(n+1,0);
	REP(i, 1, n+1) {
		a[i] = gcd(a[i - 1], v[i - 1]);
		b[i] = gcd(b[i - 1], v[n - i]);
	}
	//printvll(a);
	//printvll(b);
	ans = max(a[n-1], b[n-1]);
	REP(i, 1, n - 1) ans = max(ans, gcd(a[i], b[n - i - 1]));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2560
N = int(input())
ans = {}
for i in range(N):
    A = input()
    if  A in ans:
        ans[A] += 1
    else:
        ans[A] = 1
c = 0
for i in ans:
    if ans[i] % 2 == 1:
        c += 1
print(c)

Measured memory_bytes: 21604
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
ll sq(ll x) {return (x * x) % MOD;}
ll modP(ll a, ll b) {return (!b ? 1 : (sq(modP(a, b / 2)) * (b % 2 ? a : 1)) % MOD);}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int A, B, T;
	cin >> A >> B >> T;
	cout << (T / A) * B << endl;
	return 0;
}



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

public class Main {

	
	public static void main(String[] args) throws IOException {
		
		int[] a = new int[10];
		
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		for(int i = 0; i < 10; i++) {
			String s = r.readLine();
			a[i] = Integer.parseInt(s);
		}
		
		Arrays.sort(a);
		System.out.printf("%d\n", a[9]);
		System.out.printf("%d\n", a[8]);
		System.out.printf("%d\n", a[7]);
		
//		for(int x = 1; x < 10; x++) {
//			for(int y = 1; y < 10; y++) {
//				System.out.printf("%dx%d=%d\n", x, y, x * y);
//			}
//		}
	}
}

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

int main()
{
    int N;
    string S;

    cin >> N >> S;

    long long num_r = 0, num_g = 0, num_b = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == 'R')
        {
            num_r++;
        }
        else if (S[i] == 'G')
        {
            num_g++;
        }
        else
        {
            num_b++;
        }
    }

    long long all = num_r * num_g * num_b;
    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < j; i++)
        {
            int d = j - i;
            if (j + d >= N || S[i] == S[j])
            {
                continue;
            }

            if (S[i] != S[j + d] && S[j] != S[j + d])
            {
                all--;
            }
        }
    }

    cout << all << endl;
}


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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解説AC]
一回の操作で行うことは動く人を1人決める+動き先を1つ決める
⇒0人の部屋は選べない
⇒0人の部屋を固定して考える.
0人の部屋をm個作る場合(0 <= m <= min(n-1,k))
nCm(n個のうちm個選ぶ)(移動元) * n-mHm(n-m個のうち重複ありでm個選ぶ)(移動先)
"""
def C(n,r):
    return fact[n] * pow(fact[n-r],mod-2,mod) * pow(fact[r],mod-2,mod) % mod


n,k = LI()

fact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

ans = 0

for i in range(min(n,k+1)):
    ans += C(n,i) * C(n-1,n-i-1)
    ans %= mod
print(ans)

Measured memory_bytes: 42732
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll r,g,b,n;
	cin >> r >> g >> b >> n;
	ll count = 0;
	for (int x=0;x<=n;x++){
		if (x*r > n) break;
		for (int y=0;y<=n;y++){
			if (x*r + y*g > n) break;
			ll z = (n-x*r-y*g)/b;
			if (x*r+y*g+z*b == n) count++;	
		}
	}
	cout << count << endl;
	cin >> r;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    
using namespace std;
    
#define endl "\n"
#define ll unsigned long long
#define int long long int
#define vi vector <int >
#define vii vector < pii >
#define vll vector <ll >
#define pii pair <int, int>
#define pdd pair< double, double>
#define piii pair < pii, int > 
#define pll pair<ll, ll >
#define umap unordered_map
#define pb push_back
#define pq priority_queue
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define rep(i,b,c) for(int i = (int)b; i < (int)c; i++)
#define double long double
#define a first
#define b second

const int N = 100010;
int n, x;
vi arr(105);
int dp[N][2];


int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);	
    
    cin >> n >> x;
    forn(i, n)
        cin >> arr[i];
    dp[0][0] = 1;
    dp[0][1] = 0;

    rep(i, 1, x + 1){
        dp[i][0] = 1;
        dp[i][1] = 0;
        forn(k, n){
            if(i - arr[k] >= 0){
                if(dp[i - arr[k]][0] == 1){
                    dp[i][0] = 0;
                    dp[i][1] = 1;
                    break;
                }
            }
        }
    }

    if(dp[x][0] == 0)
        cout << "First\n";
    else cout << "Second\n";



    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;
typedef tuple<ll,ll,ll> T;
long long euclid(long long x,long long y){
    long long a=max(x,y);
    long long b=min(x,y);
    if(a%b==0)return b;
    else{
        return euclid(b,a%b);
    }
}
long long ruijou(long long x, long long y){
    if(y==0) return 1;
    else if(y%2==0) return ruijou(x*x%mod,y/2);
    else return x*ruijou(x,y-1)%mod;
}


ll i,j,k;

int main(){
   ll N;
   cin>>N;
   V A(N);
   rep(i,N)cin>>A[i];
   map<ll,ll> hitotuni;
   rep(i,N){
       if(hitotuni.count(A[i]))hitotuni[A[i]]++;
       else hitotuni[A[i]]=1;
   }
   V kaburinasi;
   for(auto itr=hitotuni.begin();itr!=hitotuni.end();itr++){
       kaburinasi.push_back(itr->first);
   }

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

   ll ans=0;
   rep(i,kaburinasi.size()){
       if(hitotuni[kaburinasi[i]]>1)continue;
       else{
           if(i==0){
               ans++;
               continue;
           }
           else{
               bool jud=true;
               for(ll j=1;j*j<=kaburinasi[i];j++){
                   if(kaburinasi[i]%j==0){
                       if(j!=1&&hitotuni.count(kaburinasi[i]/j)){
                           jud=false;
                           break;
                       }
                       if(hitotuni.count(j)){
                           jud=false;
                           break;
                       }
                   }
               }
               if(jud)ans++;
           }
       }
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 19380
#include<cstdio>
#include<bitset>
using namespace std;
bitset<1<<21> s;
int sum;
int main()
{
    int n;
    s[0]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        s|=s<<x;
        sum+=x;
    }
    for(int i=(sum+1)>>1;i<=sum;++i)
    {
        if(s[i])
        {
            printf("%d",i);
            break;
        }
    }
}

Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/math/common_factor_rt.hpp>

template <class... Args>
struct tuple_input_impl;
template <std::size_t i, std::size_t... tail>
struct tuple_input_impl<std::index_sequence<i, tail...>>
{
    template <class... Args>
    static void f(std::tuple<Args...>& x)
    {
        std::cin >> std::get<i>(x);
        tuple_input_impl<std::index_sequence<tail...>>::f(x);
    }
};
template <>
struct tuple_input_impl<std::index_sequence<>>
{
    static void f(...) {}
};

template <class... Args>
std::istream& operator>>(std::istream& in, std::tuple<Args...>& x)
{
    tuple_input_impl<std::index_sequence_for<Args...>>::f(x);
    return in;
}

template <class T>
T read()
{
    T res;
    std::cin >> res;
    return res;
}
template <class T>
std::vector<T> read(std::size_t n)
{
    std::vector<T> res(n);
    for (std::size_t i = 0; i < n; ++i) std::cin >> res[i];
    return res;
}

template <class T, class... Args>
void out_impl(T&& v, Args&&... args)
{
    std::cout << std::forward<T>(v) << ' ';
    impl(std::forward<Args>(args)...);
}
template <class T>
void out_impl(T&& v) { std::cout << std::forward<T>(v); }
template <class... Args>
void out(Args&&... args)
{
    out_impl(std::forward<Args>(args)...);
    std::cout << '\n';
}
template <class... Args>
void out_noreturn(Args&&... args) { out_impl(std::forward<Args>(args)...); }

template <class T>
void print(const T& container)
{
    bool first = true;
    for (auto&& x : container) {
        if (!first) std::cout << ' ';
        std::cout << x;
        first = false;
    }
    std::cout << '\n';
}

void prog()
{
    int n, m, c;
    std::cin >> n >> m >> c;
    auto b = read<int>(m);
    int res = 0;
    for (auto i : boost::irange(0, n)) {
        auto a = read<int>(m);
        int x = c;
        for (auto j : boost::irange(0, m)) {
            x += a[j] * b[j];
        }
        if (x > 0) ++res;
    }
    out(res);
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>
#include<stack>
#include<time.h>



#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ALL(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define getmid ((l+r)>>1)
#define mst(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) x&(-x)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
//#define ls rt<<1
//#define rs rt<<1|1
using namespace std;
#ifdef local
#define dbg(args...) cout << #args << " -> ", err(args);
void err(){ cout << endl; }
template<typename T, typename... Args>
void err(T a, Args... args){ cout << a << ' '; err(args...); }
#else
#define dbg(args...)
#endif // local

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-8;
const int mod=1e9+7;
const int maxn=3e5+100;
const int N=2e5+100;
const int M=500+10;
const ll mm=(1LL<<32);

template <class T>
inline void read(T &x)
{
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}


int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local
    IOS;//cout.tie(0);
    int x;cin>>x;
    if(x<30) puts("No");
    else puts("Yes");
    return 0;
}



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


int main()
{
	int n, x, d, y[100000], z[100000];
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> y[i];
	}
	y[n] = x;
	sort(y, y + (n + 1));
	for (int i = 0; i <n; i++)
	{
		z[i] = y[i + 1] - y[i];
		if (i == 0)d = z[i];
		if (i > 0)d = __gcd(d, z[i]);
	}
	cout << d << endl;
    return 0;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int ni[4], max = 0, min = 10, mid, a, b;

	scanf("%d%d%d", &ni[0], &ni[1], &ni[2]);
	for (int i = 0; i < 3; i++) {
		if (max < ni[i]) {
			max = ni[i];
			a = i;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (min > ni[i]) {
			min = ni[i];
			b = i;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (i != a && i != b)
			mid = ni[i];
	}

	printf("%d\n", (max * 10) + mid + min);
	
	return 0;
}


Measured memory_bytes: 128
k = gets.to_i
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
p list[k-1]

Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;bool ok;
int main()
{
	cin>>n;
	while(n)
	{
		if(n%10==9){
			ok=1;cout<<"Yes";break;
		}
		n=n/10;
	}
	if(ok==0)cout<<"No";
	return 0;
 } 

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

int main(void) {
  string s;
  cin >> s;
  if(s[s.length()-1] == 's') {
    cout << s << "es"<<  endl;
  } else {
    cout << s << "s" << endl;
  }
}

Measured memory_bytes: 3616