akhauriyash/Code-Regression huggingface dataset:
module mod_grouping
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer(8) :: f(0:1000), invf(0:1000)
contains
  subroutine init(n)
    implicit none
    integer, intent(in) :: n
    integer :: i
    f = 0_8
    invf = 0_8
    f(0) = 1_8
    invf(0) = 1_8
    do i = 1, n
      f(i) = mod(f(i-1)*int(i,8),md)
      invf(i) = inv(f(i))
    end do
    return
  end subroutine init
  integer(8) function perm(n,k)
    implicit none
    integer, intent(in) :: n, k
    perm = 0_8
    if (n.lt.0.or.k.gt.n) return
    perm = mod(f(n)*invf(n-k),md)
    return
  end function perm
  function inv(n) result(y)
    implicit none
    integer(8), intent(in) :: n
    integer(8) :: a, b, x, y, t, q
    a = mod(n,md)
    b = md
    x = 0
    y = 1
    do while(b.ne.0_8)
      q = a/b
      t = b
      b = mod(a,b)
      a = t
      t = y
      y = x
      x = t-q*x
    end do
    do while (y.lt.0_8)
      y = y+md
    end do
    y = mod(y,md)
    return
  end function inv
  recursive function pow(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a, b
    integer(8) :: r
    r = 1_8
    if (b.eq.0_8) return
    if (mod(b,2_8).eq.0_8) then
      r = pow(a,b/2_8)
      r = mod(r*r,md)
      return
    end if
    r = mod(a*pow(a,b-1_8),md)
    return
  end function pow
end module mod_grouping
program grouping
  use mod_grouping
  implicit none
  integer :: n, a, b, c, d, i, j, k
  integer(8) :: x, y, dp(0:1000,0:1000)
  read(*,*) n, a, b, c, d
  call init(n)
  dp = 0_8
  do i = 0, n
    dp(i,0) = 1_8
  end do
  do i = a, b
    do j = 1, n
      dp(i,j) = mod(dp(i-1,j)*perm(n-j,0),md)
      do k = c, d
        if (j-i*k.lt.0_8) exit
        x = mod(dp(i-1,j-i*k)*perm(n-j+i*k,i*k),md)
        y = mod(inv(pow(f(i),int(k,8)))*invf(k),md)
        dp(i,j) = mod(dp(i,j)+mod(x*y,md),md)
      end do
    end do
  end do
  write(*,'(i0)') dp(b,n)
  stop
end program grouping

Measured memory_bytes: 8064
/*
Sharif Hasan - CSE, PUST
Apr 24, 2020 02: 14 PM
*/
#include<bits/stdc++.h>
#define br cout<<"\n"
#define what(x) cout<<"in here var= "<<x<<"\n";

/*STL definations*/
#define pb push_back

#define FOR(i,n) for(int i=0;i<n;i++)
#define FROM(a,i,n) for(int i=a;i<n;i++)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
/*Main function*/
int main()
{
    int n;cin>>n;
    int lcm=(n*360)/__gcd(n,360);
    cout<<lcm/n;br;
    return 0;
}


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

int main(){
    std::ios::sync_with_stdio(0);
    int d,t,s;

    cin>>d>>t>>s;

    if(t*s>=d){
        cout<<"Yes";
    }
    else{cout<<"No";}

    return 0;}

    

        

Measured memory_bytes: 3624
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  switch(n%10){
    case 2:case 4:case 5:case 7:case 9:return "hon";
    case 3:return "bon";
  }
  return "pon";
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,1):0;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,1):0;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int N = nextInt();
  int M = nextInt();
  int K = nextInt();

  bool ans = false;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      int k = (N - i) * j + (M - j) * i;
      if (k == K) ans = true;
    }
  }
  cout << (ans ? "Yes":"No") << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int main()
{
	int a[maxn];
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int cnt=0;
	int ans=0;
	for(int i=n-1;i>=1;i--)
	{
		if(a[i]>=a[i+1])
			cnt++;
		else
		{
			ans=max(ans,cnt);
			cnt=0;
		}
	}
	ans=max(ans,cnt);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long MOD = 998244353;
const long long INF = 1LL << 60;
const int inf = pow(10, 9) + 7;
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;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int N;
  string S;
  cin >> N >> S;
  
  int ans = 0;
  int x = 0;
  for (int i = 0; i < N; i++)
  {
    if (S.at(i) == 'I') x++;
    else x--;
    chmax(ans, x);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int n,m,acc=0,wa=0,i,j;
	scanf("%d%d",&n,&m);
	int ac[n+2],p[m+1];
	char c[m+1];
	for(i=0;i<n+1;i++) ac[i]=0;
	for(i=0;i<m;i++){
		scanf("%d %c%c",&p[i],&c[i],&c[i]);
		if(c[i]=='C') ac[p[i]]=1;
	}
	for(i=0;i<m;i++){
		if(ac[p[i]]==1){
			if(c[i]=='A') wa++;
			else{
				acc++;
				ac[p[i]]=2;
			}
		}
	}
	printf("%d %d",acc,wa);
	return 0;
}

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

#define MAX 100000

vector<vector<int>> adj_list(MAX);
vector<int> visited(MAX, -1);
vector<int> init_visited(MAX, -1);

int group = 0;

void dfs(int node){
    // cout << "init node " << node << endl;
    visited.at(node) = group;
    
    for(int i = 0; ; i++){
        int next_node = adj_list.at(node).at(i);
        // cout << next_node << endl;

        if(next_node != -1 && visited.at(next_node) == -1){
            // cout << "called dfs with " << next_node << endl;
            dfs(next_node);
        }
        if(next_node == -1){
            break;
        }
    }
    // cout << "returned from " << node << endl;
}

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


    //　隣接リストの作成
    rep(i, m){
        int from, to;
        cin >> from >> to;
        adj_list.at(from).push_back(to);
        adj_list.at(to).push_back(from);
    }
    // 番兵の挿入
    rep(i, n){
        adj_list.at(i).push_back(-1);
    }

    for(int i = 0; i < n; i++){
        if(visited.at(i) == -1){
            dfs(i);
            group++;
        }
    }

    int q; cin >> q;
    rep(i, q){
        int from, to;
        cin >> from >> to;
        if(visited.at(from) == visited.at(to)){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }

    // cout << "=================" << endl;

    // for(int i = 0; i < m; i++){
    //     cout << "node " << i << " ";
    //     for(int j = 0; j < adj_list.at(i).size(); j++){
    //         cout << adj_list.at(i).at(j) << " ";
    //     }
    //     cout << endl;
    // }

    // rep(i, n){
    //     cout << "node " << i << " " << visited.at(i) << endl;
    // }
}


Measured memory_bytes: 13604
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>()> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const lint di[]{0, -1, 0, 1, -1, -1, 1, 1};
const lint dj[]{1, 0, -1, 0, 1, -1, -1, 1};

struct UnionFind
{
    vector<lint> data;
    UnionFind() {}

    // initialize
    UnionFind(lint size) : data(size, -1) {}

    void unite_set(lint x, lint y){
        x = root(x);
        y = root(y);
        bool is_unite = (x != y);
        
        if (is_unite){
            if (data[y] < data[x]){
                swap(x, y);
            }
            data[x] += data[y];
            data[y] = x;
        }
    }

    bool is_same(lint x, lint y){
        return root(x) == root(y);
    }

    lint root(lint x){
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }

    lint size(lint x){
        return -data[root(x)];
    }
};

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint n, m, a, b;
    lint ans;
    lint p, q;
    cin >> n >> m;
    struct UnionFind d(n);
    vector<pair<lint, lint>> query(m);
    for (lint i=1; i<=m; ++i){
        cin >> a >> b;
        a--;
        b--;
        query[m - i] = make_pair(a, b);
    }
    ans = (n * (n - 1)) / 2;
    vector<lint> answer(m);
    for (lint i=0; i<m; ++i){
        answer[m - i - 1] = ans;
        p = d.size(query[i].fst);
        q = d.size(query[i].snd);
        // cout << p << " " << q << endl;
        if(!d.is_same(query[i].fst, query[i].snd)){
            ans -= p * q;
        }
        d.unite_set(query[i].fst, query[i].snd);
    }
    for (lint i=0; i<m; ++i){
        if(answer[i] < 0){
            answer[i] = 0;
        }
        cout << answer[i] << endl;
    }
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x)  (x).begin(),(x).end()

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> mp;

const int MOD = 1e9 + 7;


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

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

    bool f = true;
    if((a == b && b == c) || (a != b && b != c && a != c)) {
        f = false;
    }

    cout << (f ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int n;
int a[5005];
int A, B;
const long long inf = 1e16;
long long mem[5005][5005];

long long dp(int cur, int last) {
	if(cur == n + 1) return 0;
	long long &ans = mem[cur][last];
	if(ans != -1) return ans;
	ans = inf;
	if(last < a[cur]) {
		ans = min(ans, dp(cur + 1, a[cur]));
		ans = min(ans, dp(cur + 1, last) + A);
	} else {
		ans = min(ans, dp(cur + 1, last) + B);
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	scanf("%d %d %d", &n, &A, &B);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	memset(mem, -1, sizeof mem);
	printf("%lld\n", dp(1, 0));
	return 0;
}

Measured memory_bytes: 196096
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num_ball,num_color;
    cin>>num_ball>>num_color;
    long long int ans = 1;
    for(int i=0;i<num_ball;i++){
        if(i==0)
            ans*=num_color;
        else
            ans*=(num_color-1);
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;
#define rep(i, n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
typedef long double Double;

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif

using namespace std;


int p[101];
int c[101];

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

void solve(ll N) {
    for (int i = 2; i <= N; i++) {
        p[i] = pp(i);
        int w = N;
        while (w > 0) {
            c[i] += w / i;
            w /= i;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            for (int k = j + 1; k <= N; k++) {
                if (p[i] && p[j] && p[k]) {
                    if (c[i] >= 4 && c[j] >= 4 && c[k] >= 2) ans++;
                    if (c[i] >= 4 && c[j] >= 2 && c[k] >= 4) ans++;
                    if (c[i] >= 2 && c[j] >= 4 && c[k] >= 4) ans++;
                }
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int k = i + 1; k <= N; k++) {
            if (p[i] && p[k]) {
                if (c[i] >= 4 && c[k] >= 14) ans++;
                if (c[i] >= 14 && c[k] >= 4) ans++;
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int k = i + 1; k <= N; k++) {
            if (p[i] && p[k]) {
                if (c[i] >= 2 && c[k] >= 24) ans++;
                if (c[i] >= 24 && c[k] >= 2) ans++;
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (p[i]) {
            if (c[i] >= 74) ans++;
        }
    }
    cout << ans << endl;

}


void main_(istream &cin) {
    ll N;
    cin >> N;
    solve(N);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





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

#define ff              first
#define ss              second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii             map<ll,ll>
#define pqb             priority_queue<ll>
#define pqs             priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            ll x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mx 3000
ll n,m;
bool dp[100005];
string solve(vector<ll>& v,ll k){
   for(int i=1;i<=k;i++){
    for(ll move: v){
        if(move>i)
            continue;
        if(dp[i-move]==0)dp[i]=1;
    }
   }
   return dp[k]?"First":"Second";
}
int main()
{
    FIO;
    ll c,d,e,f=0,sum=0,ck,k,p,q,r,t,add=0,w,x,y,z;
    string ans;
    cin>>n>>k;
    memset(dp,0,sizeof dp);
    vector<ll>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    ans=solve(v,k);
    cout<<ans<<endl;

    return 0;
}




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

int main() {
  
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  
  if ((e - a) > k) {
    cout << ":(" << endl;
  } else {
    cout << "Yay!" << endl;
  }
  
}


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

typedef long long i64;
class no_solution: public std::exception
{
public:
	no_solution()
	{
	}

	const char * what() const noexcept
	{
		return "no solution under such constrains";
	}
};

const int MAXN = 100000 + 5;
const int MOD = 1e9 + 7;

int N;
i64 answer, dp[MAXN];
int degree[MAXN], lenCnt[MAXN];
int pre[MAXN], nxt[MAXN];
bool vis[MAXN];

void findCycle()
{
	for (int i = 1; i <= N; i++)
	{
		if (degree[i] > 2)
			throw no_solution();
		if (degree[i] != 2 || vis[i])
			continue;

		int cur = i;

		do
		{
			if (vis[cur])
				throw no_solution();
			vis[cur] = true;
			pre[nxt[cur]] = cur;
			cur = nxt[cur];
		} while (cur != i);
	}
}

void processCircleBasedTree()
{
	for(int i = 1; i <= N; i++)
	{
		if(degree[i])
			continue;

		int cur = i, footLen = 0, cycleLen = 0;

		while(!vis[cur])
		{
			vis[cur] = true;
			cur = nxt[cur];
			footLen++;
		}

		do
		{
			cur = pre[cur];
			cycleLen++;
		}while(degree[cur] == 1);

		if(footLen < cycleLen)
			answer = answer * 2 % MOD;
		if(footLen > cycleLen)
			throw no_solution();
	}
}

void countCycle()
{
	for(int i = 1; i <= N; i++)
	{
		if(vis[i])
			continue;

		int cur = i, len = 0;

		do
		{
			vis[cur] = true;
			cur = nxt[cur];
			len++;
		}while(cur != i);

		lenCnt[len]++;
	}
}

int main()
{
	answer = 1;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> nxt[i], degree[nxt[i]]++;

	try
	{
		findCycle();
		processCircleBasedTree();
		countCycle();

		for(int i = 1; i <= N; i++)
		{
			dp[0] = 1LL;
			for(int j = 1; j <= lenCnt[i]; j++)
			{
				dp[j] = dp[j-1] * (((i % 2 == 0) || i == 1) ? 1 : 2);
				if(j >= 2)
					dp[j] = (dp[j] + ((((dp[j-2] * (j-1)) % MOD) * i) % MOD)) % MOD;
			}

			answer = answer * dp[lenCnt[i]] % MOD;
		}

		cout << answer << endl ;
	} catch (const std::exception & x)
	{
		cout << "0" << endl;
		cerr << x.what() << endl;
	}
}



Measured memory_bytes: 1920
n=int(input())
axy=[]

for i in range(n):
    ai=int(input())
    axy.append([])
    for j in range(ai):
        axy[-1].append(list(map(int,input().split())))

ans=0
pat=2**n
#print(axy)
for p in range(pat):
    #i文字目は人iが正直者か日正直者か
    bin_p=list(map(int,bin(p)[2:].zfill(n)))

    flag=False
#    print(bin_p)
    for i in range(n):

        for axyi in axy[i]:
#            print(axyi)
            if(bin_p[i]==1 and bin_p[axyi[0]-1] != axyi[1]):
                flag=True
                break

#             if(bin_p[i]==0 and bin_p[axyi[0]-1] == axyi[1]):
#                 flag=True
#                 break


        if(flag):
            break
    else:
#        print(bin_p,flag)
        ans=max(ans,bin_p.count(1))
print(ans)


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

typedef long long lint;

#define fi first
#define se second

const int MAXN = 200010;

lint A[MAXN];
map<int, int> m;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, K;

	cin >> N >> K;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	lint ans = 0;
	m[A[0] = 0] = 1;
	for(int i = 1; i <= N; i++) {
		if(i >= K) m[A[i - K]]--; 
		A[i] = (A[i - 1] + A[i] + K - 1) % K;
		ans += m[A[i]]++;
		//printf("i = %d, A = %lld, m = %d, ans = %lld\n", i, A[i], m[A[i]], ans);
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
long long GCD_(long long a, long long b) {
    return b ? GCD_(b, a % b) : a;
}
int n,wi;
int v[105][2];
long long dp[105][100005];
long long solve(int i, int w){
   if(dp[i][w] != -1) return dp[i][w];
   if(i == n) return dp[i][w] =0;
   if(w<v[i][0]) return dp[i][w] = solve(i+1,w);
   return dp[i][w] = max(solve(i+1,w),solve(i+1,w-v[i][0])+v[i][1] );
}
int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n>>wi;
    for(int i=0;i<n;i++) cin>>v[i][0]>>v[i][1];
    cout<<solve(0,wi);
 return 0;
}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  int n, m; cin >> n >> m;
  vector<VI> adj(n + 1);
  while (m--) {
    int x, y; cin >> x >> y;
    adj[x].push_back(y);
  }

  VI dis(n + 1, -1);
  function<int(int)> get = [&](int u) {
    if (dis[u] != -1) return dis[u];
    dis[u] = 0;
    for (int v: adj[u]) {
      dis[u] = max(dis[u], 1 + get(v));
    }
    return dis[u];
  };

  int ans = 0;
  for (int u = 1; u <= n; u++) {
    ans = max(ans, get(u));
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define int      long long int
#define MOD      1000000007
#define pb       push_back
#define mp       make_pair
#define vi       vector<int>
#define mi  	 map<int,int>
#define umi		 unordered_map<int,int>
#define pii      pair<int,int>
#define ff 		 first
#define ss 		 second
#define inf		 1e18
#define case	int t;cin>>t;while(t--)
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void pre()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
int dp[100005];
vi adj[100005];
int dfs(int nd, int pr)
{	if (dp[nd] != -1)
		return dp[nd];
	if (adj[nd].size() == 0)
	{	dp[nd] = 0;
		return dp[nd];
	}
	for (auto i : adj[nd])
	{	if (nd != pr)
			dp[nd] = max(dp[nd], dfs(i, nd) + 1);
	}
	return dp[nd];
}
int32_t main()
{	//pre();
	//case
	{	int n, m;
		cin >> n >> m;
		for (int i = 0; i < m; i++)
		{	int x, y;
			cin >> x >> y;
			adj[x].pb(y);
		}
		for (int i = 0; i <= 100000; i++)
			dp[i] = -1;
		for (int i = 1; i <= n; i++)
		{	if (dp[i] == -1)
				dfs(i, 0);
		}

		int mx = 0;
		for (int i = 1; i <= n; i++)
			mx = max(mx, dp[i]);
		cout << mx;
	}
	return 0;
}

Measured memory_bytes: 8576
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

int main(){
  
  long long int X, A;
  scanf("%lld%lld", &X, &A);
  
  if(X < A){
    std::cout << 0 << std::endl;
  }
  else{
    std::cout << 10 << std::endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define Max 1000
int top;
int s[Max];
int isEnpty(int);
int isFull(int);
int pop();
void push(int);
void initialize();

int main(){
  char c[Max];
  int num1,num2,ans,x;

  initialize();
  
  while(scanf("%s",c)!=EOF){
    if(c[0] == '+'){
      num2=pop();
      num1=pop();
      ans=num1+num2;
      push(ans);
    }else if(c[0]=='-'){
      num2=pop();
      num1=pop();
      ans=num1-num2;
      push(ans);
    }else if(c[0]=='*'){
      num2=pop();
      num1=pop();
      ans=num1*num2;
      push(ans);
    }else{
      x=atoi(c);
      push(x);
    }
  }

  printf("%d\n",pop());
  
  return 0;
}

int isEnpty(int top){
  if(top==0){
    return 1;
  }else{
    return 0;
  }
}

int isFull(int top){
  if(top > Max){
    return 1;
  }else{
    return 0;
  }
}

void initialize(){
  top = 0;
}

int pop(){
  if(isEnpty(top)==1){
    fprintf(stderr,"stackOfEnpty");
    exit(1);
  }
  top--;
  return s[top+1];
}

void push(int x){
  if(isFull(top)==1){
    fprintf(stderr,"StackOfFull\n");
    exit(1);
  }else{
    top++;
    s[top]=x;
  }
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    int N,A;
    set<int> st;
    cin >> N;
    for(int i = 0;i < N;i++){
        cin >> A;
        if(!st.erase(A))st.insert(A);
    }
    cout << st.size() << endl;
}

Measured memory_bytes: 4864
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
static const double pi = 3.141592653589793;

int main() {
    double a, b, h, m;
    cin >> a >> b >> h >> m;

    double minutes = h * 60.0 + m;
    double theta = minutes / 720 - m / 60;
    theta = min(theta, 1 - theta);
    double x = a * a + b * b - 2 * a * b * cos(2 * pi * theta);
    printf("%.15f\n", sqrt(x));
}


Measured memory_bytes: 4164
/*


*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 111
#define mmp make_pair
using namespace std;
int read() {
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}

char s[M];

ll ans = (1ll << 40);

ll ab(ll x) {
	return x > 0 ? x : -x;
}

bool vis[M];
int n;


int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for(int i = 1; i + 2 <= n; i++) {
		ans = min(ans, ab(753 - (s[i] - '0') * 100 - (s[i + 1] - '0') * 10 - (s[i + 2] - '0')));
	}
	cout << ans<< "\n";
	return 0;
}




Measured memory_bytes: 256
import java.util.Scanner;

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

		if (N == K || N % K == 0) {
			System.out.println(0);
		} else {
			System.out.println(1);
		}

		sc.close();
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main(){

    ll n;
    cin>>n;

    ll cnt = 0;
    for(ll i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;

        if(a == b) cnt++;
        else cnt = 0;

        if(cnt == 3){ cout<<"Yes\n"; return 0;}
    }

    cout<<"No\n";


    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>

using namespace std;

int gcd(int p,int q){
    if(p % q == 0)return q;
    return gcd(q, p % q);
}

int main()
{ 
    int N;
    int sum = 0;
    cin >> N;
    for(int i = 1; i < N + 1; i++){
        for(int j = 1; j < N + 1; j++){
            for(int l = 1; l <N + 1; l++){
                sum += gcd(gcd(i,j),l);
            }
        }
    }
    cout << sum <<endl;
}

Measured memory_bytes: 3560
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const int MINF = -1e9;;


int main() {
	int n;
	cin >> n;
	for (int i = 1; i < 10; ++i) {
		for (int j = 1; j < 10; ++j) {
			if (n == i * j) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
<?php
$a=fgets(STDIN);
$b=fgets(STDIN);
$c=fgets(STDIN);
$x=fgets(STDIN);
$result=0;

for($i=0; $i<=$a; $i++){
	for($t=0; $t<=$b; $t++){
		for($r=0; $r<=$c; $r++){
			if(500*$i + 100*$t + 50*$r == $x){
			$result++;
			}
		}
	}
}
echo $result;
?>

Measured memory_bytes: 3576
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

vector<vector<int>> edges;

void getDist(int v, int prev, vector<int> &dist) {
    for(auto nei: edges[v]) {
        if (nei == prev) continue;
        dist[nei] = dist[v] + 1;
        getDist(nei, v, dist);
    }
}

int main(void)
{
    cin.sync_with_stdio(false);
    int N, u, v;
    cin >> N >> u >> v;
    --u; --v;

    edges.resize(N);
    REP(n, N-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        edges[a].pb(b);
        edges[b].pb(a);
    }

    vector<int> from_u(N);
    vector<int> from_v(N);
    getDist(u, -1, from_u);
    getDist(v, -1, from_v);

    int ans = 0;
    REP(i, N) {
        auto du = from_u[i];
        auto dv = from_v[i];
        if (du < dv) {
            int local_ans = du + (dv - du - 1);
            ans = max(ans, local_ans);
        }
    }
    cout << ans << endl;

    return 0;
}


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

template<typename T> struct Graph {
  struct Edge { int to; T cost; };
  vector<int> prev;
  vector<vector<Edge>> g;
  Graph(int n) : prev(n, -1), g(n) {}

  void addEdge(int u, int v, T w) {
    g[u].push_back({v, w});
    //g[v].push_back({u, w});
  }
  vector<T> dijkstra(int s) {
    vector<T> dist(g.size(), -1);
    using Node = pair<T, int>;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({dist[s] = 0, s});

    while (!pq.empty()) {
      auto d = pq.top().first;
      auto u = pq.top().second;
      pq.pop();
      if (dist[u] < d) continue;
      for (auto&& v : g[u]) {
        if (dist[v.to] < 0 || dist[v.to] > dist[u] + v.cost) {
          dist[v.to] = dist[u] + v.cost;
          prev[v.to] = u;
          pq.push({dist[v.to], v.to});
        }
      }
    }
    return dist;
  }
  vector<int> getPath(int t) {
    vector<int> path;
    for (; t != -1; t = prev[t]) path.push_back(t);
    reverse(begin(path), end(path));
    return path;
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  Graph<int> g(n);
  for (int i = 0; i < n; ++i) {
    int u, k; cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      int v, c; cin >> v >> c;
      g.addEdge(u, v, c);
    }
  }
  vector<int> d = g.dijkstra(0);
  for (int i = 0; i < n; ++i) {
    cout << i << ' ' << d[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 7884
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
double ans[100001];
int main(){
  ans[0]=0;
  ans[1]=1;
  for(int i=2;i<100001;i++){
    ans[i]=0;
    double a=1,b=1;
    for(int j=1;j<=min(i,50);j++){
      double c=j;
      if(i-j-1>=0)c+=ans[i-j-1];
      
      a*=0.5;
      if(j==i)a=0.0;
      ans[i]+=c*b*(1.0-a);
      b*=a;
    }

  }
  while(1){
    cin>>n;
    if(n==0)break;
    printf("%.8f\n",ans[n]);
  }
  return 0;
}

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()

int main() {
    string s;
    cin >> s;
    int x = -1;
    for(int i = 1;i < s.size();i++) {
        if(s[i] == s[i - 1]) {
            x = i;
            break;
        }
    }
    int y = -1;
    if(2 < s.size()) {
        for(int i = 2;i < s.size();i++) {
            if(s[i] == s[i - 2]) {
                y = i;
                break;
            }
        }
    }
    if(x != -1) {
        cout << x << " " << x + 1 << endl;
    }else if(y != -1){
        cout << y - 1 << " " << y + 1 << endl;
    }else{
        cout << -1 << " " << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
typedef long long LL;
typedef long double Lf;
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
//#define Rep(i,a,n)for(LL i=(LL)(a);i<(LL)(n);i++)
#define rep(i,n)Rep(i,0,n)
#define Repp(i,l,r,k)for(int i=(int)(l);i<(int)(r);i+=(int)(k))
//#define Repp(i,l,r,k)for(LL i=(LL)(l);i<(LL)(r);i+=(LL)(k))
#define Ma(x,y) ((x)>(y)?(x):(y))
#define mi(x,y) ((x)<(y)?(x):(y))
#define MOD 1000000007//998244353,1000000007,1000000009 
int upi(const void* a, const void* b) { return*(int*)a<*(int*)b ? -1 : *(int*)a> * (int*)b ? 1 : 0; }
int downi(const void* a, const void* b) { return*(int*)a<*(int*)b ? 1 : *(int*)a> * (int*)b ? -1 : 0; }
void sortupi(int* a, int n) { qsort(a, n, sizeof(int), upi); } //1,2,3,4,...
void sortdowni(int* a, int n) { qsort(a, n, sizeof(int), downi); }
int upLL(const void* a, const void* b) { return*(LL*)a<*(LL*)b ? -1 : *(LL*)a> * (LL*)b ? 1 : 0; }
int downLL(const void* a, const void* b) { return*(LL*)a<*(LL*)b ? 1 : *(LL*)a> * (LL*)b ? -1 : 0; }
void sortupLL(LL* a, int n) { qsort(a, n, sizeof(LL), upLL); }
void sortdownLL(LL* a, int n) { qsort(a, n, sizeof(LL), downLL); }
int cmp_char(const void* a, const void* b) { return *(char*)a - *(char*)b; } // a,b,c,d
int cmp_str(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); } // aaa,aab
LL gcd(LL p, LL q) { while (q) { LL t = p % q; p = q; q = t; }return p; }
LL modpow(LL a,LL n,int m){LL x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
#define invmodpow(b,p)modpow(b,p-2,p)// a/b≡a*b^{-1}(mod p)...return b^{-1}(mod p)
typedef struct fac { LL n, exp; }F;
LL fact(LL n,F*a){LL x,i,j,c=0;x=n;for(i=2;i*i<=x;i++){for(j=1;x%i==0;j++)x/=i;if(j>1){a[c].n=i;a[c++].exp=j-1;}}if(x-1){a[c].n=x;a[c++].exp=1;}return c;}
//snippet
//overflow...char 1e6

#define N 109

int main() {
	LL n, a[N];
	scanf("%lld", &n);
	rep(i, n) scanf("%lld", &a[i]);
	a[n] = 99;
	int b[N] = { 0 }, c = 0, m = a[0];
	rep(i, n + 1) {
		if (!i)continue;
		if (a[i] < m) {
			b[c]++;
			b[i - 1]--;
			c = i;
		}
		m = a[i];
	}
	
	LL ans = 1000, kb = 0;
	rep(i, n) {
		if (b[i] == 1) {
			kb = ans / a[i];
			ans -= a[i] * kb;
		}
		if (b[i] == -1) {
			ans += a[i] * kb;
			kb = 0;
		}
		if (i == n - 1 && kb)ans += a[i] * kb;
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1732
scra = []
scrb = []

for i in range(4):
  scr = int(input())
  scra.append(scr)

for i in range(2):
  scr = int(input())
  scrb.append(scr)

scra.sort()
scrb.sort()

total = sum(scra[1:]) +  scrb[1]
print(total)


Measured memory_bytes: 5596
#include <stdio.h>

int main(void)
{
   int N, i, j, tmp;
   int wa = 0;
   int A[100];

   scanf("%d", &N);
   for ( i = 0; i < N; i++ ) {
      scanf("%d", &A[ i ]);
   }

   for ( i = 0; i < N; i++ ) {
      for ( j = N - 1; j > 0; j-- ) {
         if ( A[ j ] < A[ j - 1 ] ) {
            tmp = A[ j ];
            A[ j ] = A[ j - 1 ];
            A[ j - 1 ] = tmp;
            wa = wa + 1;
         }
      }
   }

   for ( i = 0; i < N; i++ ) {
      if ( i > 0 ) {
         printf(" ");
      }
      printf("%d", A[ i ]);
   }
   printf("\n");

   printf("%d\n", wa);

   return 0;
}

Measured memory_bytes: 1852
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	while(kbd.hasNext()){
	    Man[] man = new Man[4000];
	    int n = kbd.nextInt();
	    if(n!=0) solve(n, man);
	}
    }

    static void solve(int n, Man[] man){
	int i=0, cnt=0;
	while(n>0){
	    i=0;
	    int m = kbd.nextInt();
	    long t = kbd.nextLong();
	    long c = kbd.nextLong();
	    while(i!=cnt && man[i].getM()!=m) i++;
	    if(i==cnt){
		man[i] = new Man(m, t*c);
		cnt++;
	    }
	    else{
		man[i].plus(t*c);
	    }
	    n--;
	}
	long a=0;
	for(i=0; i<cnt; i++){
	    if(man[i].getP() >= 1000000){
		System.out.println(man[i].getM());
		a++;
	    }
	}
	if(a==0){
	    System.out.println("NA");
	}
    }
}

class Man{
    int m;
    long p;
    public Man(int num, long pt){
	m = num;
	p = pt;
    }
    public void plus(long pt){
	p += pt;
    }
    public long getP(){
	return p;
    }
    public long getM(){
	return m;
    }
}

Measured memory_bytes: 25284
#include <iostream>

using namespace std;

static const int N = 100;

int main () {
  int M[N][N];
  int n, u, k, v;
  
  cin>>n;
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          M[i][j] = 0;
      }
  }
  
  for (int i = 0; i < n; i++) {
      cin >> u >> k;
      u--;
      for (int j = 0; j < k; j++) {
          cin >> v;
          v--;
          M[u][v] = 1; //在u和v之间画出一条边
      }
  }
  
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
          if (j) cout << " ";
          cout << M[i][j];
      }
      cout << endl;
  }

    
    
    
    return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
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;}


int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    ll sum = 0;
    int cnt = 0;
    ll minv = ll(1e18)+1;
    rep(i,n) {
        cin >> a[i];
        sum += abs(a[i]);
        if(a[i]<0) cnt++;
        minv = min(minv,abs(ll(a[i])));
    }
    if(!(cnt%2)) {
        cout << sum << endl;
        return 0;
    } else {
        cout << sum - 2*minv << endl;
    }

}

Measured memory_bytes: 3768
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint ungigned
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define y1 wzpakking 
#define fi first
#define se second
#define BG begin
#define ED end
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?(x)-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define sqr(x) (1ll*x*x)
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
#define INF (1<<30)
using namespace std;

const int N=100005;
int fl[N],pri[N],n,ans;
ll a[N],b[N];
map<ll,int> s,vis;
int main(){
	For(i,2,N-1){	
		if (!fl[i]) pri[++*pri]=i;
		For(j,1,*pri){
			if (i*pri[j]>=N) break;
			fl[i*pri[j]]=1;
			if (i%pri[j]==0) break;
		}
	}
	scanf("%d",&n);
	For(i,1,n){
		scanf("%lld",&a[i]);
		ll k=a[i]; a[i]=b[i]=1;
		For(j,2,2200){
			if (k==1) break;
			if (fl[j]) continue;
			ll t=1ll*j*j*j;
			for (;k%t==0;k/=t);
			if (k%(j*j)==0) a[i]*=j*j,b[i]*=j;
			else if (k%j==0) a[i]*=j,b[i]*=j*j;
			for (;k%j==0;k/=j);
		}
		if (k>1){
			ll t=(ll)(sqrt(k));
			if (1ll*t*t==k) a[i]*=k,b[i]*=t;
			else a[i]*=k,b[i]*=k*k;
		}
	}
	For(i,1,n) s[a[i]]++;
	For(i,1,n) if (!vis[a[i]]){
		vis[a[i]]=1;
		if (a[i]==b[i]) ans++;
		else ans+=max(s[a[i]],s[b[i]]),vis[b[i]]=1;
	}
	printf("%d",ans);
}

Measured memory_bytes: 27264
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect

for i in range(n):
    for j in range(i + 1,n):
        a = l[i]
        b = l[j]
        ans += bisect.bisect_left(l,a + b) - j - 1

print(ans)

Measured memory_bytes: 43756
s = list(input())
t = list(input())
bag = []
for i in range(len(s)-len(t)+1):
  st = False
  for j in range(len(t)):
    if j==0 and (s[i+j]==t[j] or s[i+j]=='?'):
      st = True 
    elif st==True and (s[i+j]==t[j] or s[i+j]=='?'):
      pass 
    elif st==True and (s[i+j]!=t[j] and s[i+j]!='?'):
      st = False 
      break 

  if st:
    bag += [i]

if len(bag)==0:
  print('UNRESTORABLE')
  exit()
else:
  idx = max(bag)
  s[idx:idx+len(t)] = t 

for i in range(len(s)):
  if s[i] == '?':
    s[i] = 'a' 

print(''.join(s))


  


Measured memory_bytes: 3064
#include <cstdio>

int a, b ,c;
int da[] = {1, 0, 1, 0, 0};
int db[] = {0, 1, 1, 0, 0};
int dc[] = {0, 0, 0, 1, 0};
bool ans[] = {0, 0, 1, 1, 0};


int main(){
    scanf("%d %d %d", &a, &b, &c);

    for(int i = 0; i < 5; i++){
        if(a == da[i] && b == db[i] && c == dc[i]){
            if(ans[i]) printf("Open\n");
            else printf("Close\n");
        }
    }


    return 0;
}

Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> cnt(100001);
	rep(i,n){
		int a;
		cin >> a;
		cnt[a]++;
	}
	int ans=0;
	rep(i,100001){
		if(cnt[i]) ans++;
	}
	if(ans%2==0) cout << ans-1 << endl;
	else cout << ans << endl;
}

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

int main(void){
    int n,c=0;
    cin >> n ;
    for (int i=0; i<n; i++){
        int x ;
        cin >> x ;
        if (x!=i+1){
            c++ ;
        }
    }
    if (c==0 || c==2){
        cout << "YES" << endl ;
    } else {
        cout << "NO" << endl ;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
int main()
{
    long N;
    std::cin >> N;
    long x,y;

    long center = long(std::sqrt(N));    
    for (int i = center; i > 0; i--)
    {
      if (N % i == 0) {
        y = ((long) N / i ) - 1;
        x = i - 1;
        // std::cout << "x:" << x << "y:" << y << std::endl;
        std::cout << x + y << std::endl;
        break;
      }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define dump(a) cout << (a) << endl;
typedef long long ll;

int main() {
    int h, w;
    cin >> h >> w;
    int edge[10][10] = {};
    for( int i = 0; i < 10; i++ ) for( int j = 0; j < 10; j++ ) cin >> edge[i][j];
    for( int k = 0; k < 10; k++ ) {
        for( int i = 0; i < 10; i++ ) {
            for( int j = 0; j < 10; j++ ) {
                edge[i][j] = min( edge[i][j], edge[i][k] + edge[k][j] );
            }
        }
    }
    int res = 0;
    for( int i = 0; i < h*w; i++ ) {
        int x;
        cin >> x;
        if( x >= 0 ) res += edge[x][1];
    }
    dump( res );
    return 0;  
}

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

int main() {
  int n, m = INT_MAX, o = 0;
  cin >> n;
  vector<int> p(n);
  for(int i = 0; i < n; i++) {
    cin >> p.at(i);
    if(m > p.at(i))
      o++;
    m = min(m, p.at(i));
  }
  cout << o << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  for (int i = 0; i < a+b+1; i++){
    if ((i<a || i>a) && s[i]>='0' && s[i]<='9'){
      
      continue;
    }else if(i == a && s[i] == '-'){
      
      continue;
    }else{
      cout << "No" << "\n";
      return 0;
    }
  }
  cout << "Yes" << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/math/common_factor_rt.hpp>

#define rep_ui(k,n)      for(ui  i = (k); i < (n); ++i)
#define rep_si(k,n)      for(int i = (k); i < (n); ++i)
#define rep_ul(k,n)      for(ul  i = (k); i < (n); ++i)
#define rep_sl(k,n)      for(ll  i = (k); i < (n); ++i)
#define rep_ui_down(k,n) for(ui  i = (k); i > (n); --i)
#define rep_si_down(k,n) for(int i = (k); i > (n); --i)
#define rep_ul_down(k,n) for(ul  i = (k); i > (n); --i)
#define rep_sl_down(k,n) for(ll  i = (k); i > (n); --i)

#define rep_uj(k,n)      for(ui  j = (k); j < (n); ++j)
#define rep_sj(k,n)      for(int j = (k); j < (n); ++j)
#define rep_uj_down(k,n) for(ui  j = (k); j > (n); --j)
#define rep_sj_down(k,n) for(int j = (k); j > (n); --j)

#define rep(k,n)         rep_ui(k,n)

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vc)
{
  for (auto it = vc.begin(); it != vc.end(); ++it)
  {
    if (std::next(it) == vc.end())
      os << *it;
    else
      os << *it << ' ';
  }
  return os;
}

template<class T1, class T2>
inline
std::ostream & operator<<(std::ostream & os, const std::pair<T1, T2> & p)
{
  return os << p.first << ' ' << p.second;
}

void solve(void)
{
  using std::string;
  using std::vector;
  using std::map;
  using std::pair;
  using std::cin;
  using std::cout;
  ui N{}; std::cin >> N;
  vector<ui> L(N);
  rep(0, L.size()) cin >> L[i];

  auto M = boost::max_element(L);

  auto ans = boost::accumulate(L, 0) - *M > *M;

  cout << (ans ? "Yes" : "No" ) << '\n';
  return;
}

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

  solve();

  return 0;
}


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

int main()
{
ll n ;
cin >> n ;
vector<ll> a(n);
rep(i, n){
  cin >> a[i];
}
ll b=0,c=0;
rep(i,n){
  if(a[i]%4==0)b++;
  if(a[i]%2==1)c++;
}
bool ok=1;
if(b==0&&c>0)ok=0;
else if(b<c-1)ok=0;
else if(b==c-1 && n!=b+c)ok=0;
cout << (ok? "Yes" :"No") << endl;
return 0;
}

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

int main(int argc, char const *argv[])
{
    string s, t; cin >> s >> t;
    int n = s.size(), ans = 0;
    rep(i,n) if (s[i] != t[i]) ans++;
    cout << ans << endl;
    
    return 0;
}


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

int main()
{
    ll N,K;
    cin >> N >> K;
    ll count = 0;

    for(ll i = K; i <= N+1; i++)
    {
        count += ((i * (N - (i - 1)) + 1));
        count %= 1000000007;
    }
    cout << count << endl;
}

Measured memory_bytes: 3636
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
    static final int MODULUS = 1_000_000_007;

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

        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(solve(N, K));

        sc.close();
    }

    static String solve(int N, int K) {
        int[][] wayNums = new int[N + 2][N + 1];
        wayNums[0][0] = 1;
        for (int i = 1; i <= N + 1; ++i) {
            wayNums[i][0] = wayNums[i - 1][0];
            for (int j = 1; j <= N; ++j) {
                wayNums[i][j] = addMod(wayNums[i][j - 1], wayNums[i - 1][j]);
            }
        }

        int[] result = new int[K];
        for (int i = 0; i < result.length; ++i) {
            result[i] = multiplyMod(getWayNum(wayNums, i + 1, K - (i + 1)), getWayNum(wayNums, i + 2, N - K - i));
        }

        return Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining("\n"));
    }

    static int getWayNum(int[][] wayNums, int partNum, int sum) {
        return (sum < 0) ? 0 : wayNums[partNum][sum];
    }

    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }

    static int multiplyMod(int x, int y) {
        return (int) ((long) x * y % MODULUS);
    }
}

Measured memory_bytes: 68152
n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
b = [int(input()) for _ in range(m)]
for ni in range(n):
    ans = 0
    for mi in range(m):
        ans += A[ni][mi] * b[mi]
    print(ans)

Measured memory_bytes: 8016
import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math, std.container, std.typecons;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

void main() {
	int n;
	scanf("%d", &n);
	long[] d = new long[n];
	foreach (i; 0..n) {
		scanf("%lld", &d[i]);
	}
	alias Tuple!(long,int) P;
	P[] raw_p = new P[n];
	foreach (i; 0..n) {
		raw_p[i][0] = d[i];
		raw_p[i][1] = i;
	}
	auto p = raw_p.sort.assumeSorted;
	int[] sz = new int[n];
	P[] ans;
	foreach_reverse (i; 1..n) {
		int v = p[i][1];
		sz[v]++;
		int diff = (n-sz[v]) - sz[v];
		int pi = p.lowerBound(P(d[v]-diff,-1)).length.to!int;
		if (pi == n || p[pi][0] != d[v]-diff) {
			writeln(-1);
			return;
		}
		int par = p[pi][1];
		sz[par] += sz[v];
		ans ~= P(v+1, par+1);
	}

	int[][] to = new int[][](n);
	foreach (edge; ans) {
		int a = edge[0].to!int-1, b = edge[1]-1;
		if (d[a] > d[b]) swap(a,b);
		to[a] ~= b;
	}
	int root = p[0][1];
	long dfs(int v, int depth) {
		long ret = depth;
		foreach (int u; to[v]) ret += dfs(u,depth+1);
		return ret;
	}
	if (dfs(root, 0) != d[root]) {
		writeln(-1);
		return;
	}

	foreach (edge; ans) {
		writeln(edge[0], ' ', edge[1]);
	}
}

Measured memory_bytes: 15836