akhauriyash/Code-Regression huggingface dataset:
import operator as O
c = {"N": (1, O.add), "E": (0, O.add), "W": (0, O.sub), "S": (1, O.sub)}
while True:
    N = int(input())
    if N == 0:
        break
    pos = [10, 10]
    nums = [tuple(map(int, input().split())) for _ in range(N)]
    M = int(input())
    ans = 0
    for _ in range(M):
        d, l = input().split()
        index = c[d][0]
        func = c[d][1]
        tx, ty = pos
        pos[index] = func(pos[index], int(l))
        x, y = pos
        if index:
            if d == "N":
                tmp = [(tx, i) for i in range(ty, y+1)][1:]
            elif d == "S":
                tmp = [(tx,  i) for i in range(y, ty+1)][:-1]
        else:
            if d == "E":
                tmp = [(i, ty) for i in range(tx, x+1)][1:]
            elif d == "W":
                tmp = [(i, ty) for i in range(x, tx+1)][:-1]
        hoge = list(filter(lambda n: n in tmp, nums))
        for h in hoge:
            nums.remove(h)
    print("No" if nums else "Yes")

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

int main(){
    int h, w; cin >> h >> w;
    int cnt = 0;
    rep(i, h)rep(j, w) {
        char g; cin >> g;
        if(g == '#') cnt++;
    }

    cout << ((cnt == h+w-1)?"Possible":"Impossible") << endl;

    return 0;
}

Measured memory_bytes: 3640
n=int(input())
R=[]
for i in range(n):
    a=int(input())
    R.append(a)


minv=R[0]
maxv=R[1]-R[0]
for i in range(1,n):

    maxv=max(maxv,R[i]-minv)
    minv=min(minv,R[i])

print(maxv)


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

int enumerate(int id){
        int sum=0;
        for(int i=id;i>0;i-=2){
                sum += 9*pow(10,i-1);
        }
        return sum;
}


int main(){
        string s;
        cin >> s;
        int a = atoi(s.c_str());
        int k = s.size();
        int l = a/pow(10,k-1);
        //cout << a << endl;
        //cout << k << endl;
        //cout << l << endl;
        int sum=0;
        if(k%2==0)  sum=enumerate(k-1);
        else{
                sum=enumerate(k-2);
                sum += (l-1)*pow(10,k-1);
                sum += a-l*pow(10,k-1)+1;
        }
        cout << sum << endl;
        return 0;
}
                           

Measured memory_bytes: 256
import itertools as t
N=int(input())
a,X=0,[]
for j in range(len(str(N))+1):X+=list(t.product((3,5,7),repeat=j))
for i in X:
    s=''
    for j in i:s+=str(j)
    if len(set(i))==3and int(s)<=N:a+=1
print(a)

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; }

template<class T> using PQ_G = priority_queue<T, vector<T>, greater<T>>;

typedef long long ll;
int const inf = 1<<29;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int main() {

  int H, W; cin>> W >> H;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  int N; cin >> N;
  map<pair<int, int>, int> mp;

  rep(i, N) {
    int x, y; cin >> x >> y;
    mp[{y, x}] = i + 1;
  }
  
  PQ_G<tuple<int, int, int>> q;
  q.emplace(0, 0, 0);

  static int dist[1001][1001];
  rep(i, 1001) rep(j, 1001) dist[i][j] = inf;

  dist[0][0] = 0;

  while(!q.empty()) {
    int cost, y, x; tie(cost, y, x) = q.top(); q.pop();

    if(dist[y][x] < cost) continue;

    if(G[y][x] == 't') {
      cout << cost << endl;
      exit(0);
    }

    rep(k, 4) {
      int ny = y + dy[k], nx = x + dx[k];
      if(!in_range(ny, nx, H, W)) continue;
      if(G[ny][nx] == '#') {
        if(mp.find({ny, nx}) != mp.end()) {
          int ncost = max(mp[{ny, nx}], cost);
          if(dist[ny][nx] <= ncost) continue;
          dist[ny][nx] = ncost;
          q.emplace(ncost, ny, nx);
        }
      }
      else {
        if(dist[ny][nx] <= cost) continue;
        dist[ny][nx] = cost;
        q.emplace(cost, ny, nx);
      }
    }
  }

  cout << -1 << endl;

  return 0;
}

Measured memory_bytes: 8212
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <random>

#include <fstream>
#include <vector>
#include <algorithm>

#define ll long long int

using namespace std;

int main(void)
{

    
    int n, k, tmp;
    vector<int> p;
    
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> tmp;
        p.push_back(tmp);
    }
    
    sort(p.begin(), p.end());
    
    tmp = 0;
    
    for(int i = 0; i < k; i++)
    {
        tmp += p[i];
    }
    
    cout << tmp;
    
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long 
int main()
{
	int n,we;
    cin>> n >> we ;
   	vector<ll int>dp(we+1,0),w(n),v(n);
    for(int i=0;i<n;i++){
        cin>> w[i]>>v[i];
    }
    for(int j=0;j<n;j++){
    	for(int i=we;i>0;i--){
            if(i>=w[j]){
                dp[i]=max(dp[i],v[j]+dp[i-w[j]]);
            }
        }
    }
    //for(auto i:dp)cout<<i<<" ";
   	cout<<dp[we]<<endl;
    return 0;
}

Measured memory_bytes: 4016
import java.util.*;
     
    public class Main{
      public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int h[] = new int[n];
        int count = 0;
        for(int i = 0; i < n; i++){
          h[i] = sc.nextInt();
          if(h[i] >= k){
            count++;
          }
        }
        System.out.println(count);
      }
    }

Measured memory_bytes: 49124
#include <iostream>
#include <math.h>
#include <string>

#define MIN(x, y) (x < y ? x : y)
#define MAX(x, y) (x > y ? x : y)

using namespace std;

int main(){
	long x;
	cin >> x;

	long max = 1;
	for(int b = 2; b <= x; ++b){
		for(int p = 2; pow(b, p) <= x; ++p){
			int tmp = pow(b, p);
			max = MAX(pow(b, p), max);
		}
	}

	cout << max << endl;
}



Measured memory_bytes: 512
/*
 ID: bradyawn
 PROG: contest
 LANG: C++11
 */

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <utility>
#include <set>
#include <unordered_set>
#include <ctime>
#include <queue>
#include <stack>
#include <bitset>
#include <random>
#include <cstring>
#include <functional>

using namespace std;

typedef long long ll;
typedef pair<int,int> i2;
typedef pair<ll,ll> ll2;

int main()
{
    //ifstream inf("");
    //ofstream outf("");
    //cout << setprecision(10);
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    
    
    
    multiset<int> s;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    
    int ret = 0;
    
    ret += *s.begin(); s.erase(s.begin());
    ret += *s.begin(); s.erase(s.begin());
    int x = *s.begin();
    
    while (k--) x *= 2;
    
    ret += x;
    
    cout << ret << '\n';
    
    return 0;
    
}




Measured memory_bytes: 256
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<fstream>       //ファイルストリーム（標準入力変更用）
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;

//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;

//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in1(x1) cin >> x1
#define in2(x1, x2) cin >> x1 >> x2
#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3
#define inN(x, N) rep(i, N) in1(x[i])
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl 

//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

    //標準入力をファイルに変更
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());

    int N;
    in1(N);

    vll h(N);
    inN(h, N);

    ll ans = h[0];

    reps(i, 1, N)
    {
        ans += h[i] > h[i - 1] ? h[i] - h[i - 1] : 0;
    }

    outl(ans);

    return 0;
}


Measured memory_bytes: 3608
#include <iostream>

using namespace std;

typedef long long ll;
#define x first
#define y second
#define mp make_pair

int n, k;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
int br = 0;
while(n > 0){
	n /= k;
	br++;
}
cout << br << endl;

return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    string S;
    cin >> S;
    if(N % 2 == 1){
        cout << "No" << endl;
        return 0;
    }
    if(S.substr(0,N / 2) == S.substr(N / 2,N / 2)){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3652
#include<stdio.h>


 
int main() {

	char s[100001];
	int i,cnt1=0,cnt0=0;

	scanf("%s", s);

	for (i = 0;s[i]!='\0' ; i++) {
		if (s[i] == '0')cnt0++;
		if (s[i] == '1')cnt1++;
	}
	printf("%d", (cnt1 < cnt0) ? cnt1*2 : cnt0*2);


	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
DATA = """
sippuu
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = get_line()

if N[2] == N[3] and N[4] == N[5]:
	print("Yes")
else:
	print("No")


Measured memory_bytes: 2940
import java.util.*;

class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		String[] line =sc.nextLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		
		int[][] a = new int[n][m];
		int[] b   = new int[m];
		int[] c   = new int[n];
	//a	
		for(int i=0;i<n;i++){
			String[] input=sc.nextLine().split(" ");
			for(int j=0;j<m;j++){
				a[i][j]=Integer.parseInt(input[j]);
			}
		}	
	//b	
		for(int i=0;i<m;i++){
			b[i]=sc.nextInt();
		}
	//c	
		for(int i=0;i<n;i++){
			int sum=0;
			for(int j=0;j<m;j++){
				sum=sum+a[i][j]*b[j];
			}
			c[i]=sum;
		}
	//output
		for(int i=0;i<n;i++){
			System.out.println(c[i]);
		}
	}
}

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

int main() {
    int n,m;
    cin>>n>>m;
    pair<ll,ll> p[n];
    for (int i=0;i<n;i++) {
        ll a,b;
        cin>>a>>b;
        p[i]={a,b};
    }
    sort(p,p+n);
    ll ans=0;
    for (auto q:p) {
        if (q.second<m) {
            m-=q.second;
            ans+=q.first*q.second;
        } else {
            ans+=q.first*m;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
const ll MOD=1e9+7;
ll a[300005];
int main()
{
    int n;
    cin>>n;
    ll ans=0;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<60;i++)
    {
        ll t=0;
        for(int j=0;j<n;j++)
        {
            if(a[j]&(1LL<<i)) t++;
        }
        ans=(ans+(((t*(n-t))%MOD)*((1LL<<i)%MOD)))%MOD;
    }
    cout<<ans<<'\n';
}


Measured memory_bytes: 2560
N = input()
l = len(N)

ans = int(N)

for i in range(1,l):
    for j in range(l+1-i):
        if j == 0 or j == l-i:
            t = l - i - 1
        else:
            t = l - i - 2
        ans += int(N[j:j+i]) * (2 ** t)

print(ans)

Measured memory_bytes: 3060
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000003;

int main(){
    ll a, b, c, d; cin >> a >> b >> c >> d;
    prtl(d == 1);
}


Measured memory_bytes: 3616
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <map>
#include <ctime>
#include <cstdlib>
#include <random>
using namespace std;

int main(){
	int n;
	cin >> n;
	cout << (n + 1)/2 << endl;
	return 0;
}

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

template <typename T>
void print(const T &v);

vector<int> grid[200000];
ll score[200000];
bool seen[200000];

void dps(int now)
{
    for (auto next : grid[now])
    {
        if (seen[next])
        {
            continue;
        }
        score[next] += score[now];
        seen[next] = true;
        dps(next);
    }
}

int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        grid[a].push_back(b);
        grid[b].push_back(a);
    }
    for (int i = 0; i < q; i++)
    {
        int p, x;
        cin >> p >> x;
        --p;
        score[p] += x;
    }
    seen[0] = true;
    dps(0);
    for (int i = 0; i < n; i++)
    {
        if (i)
        {
            cout << ' ';
        }
        cout << score[i];
    }
    cout << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

Measured memory_bytes: 25668
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<57;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

class Graph{
	private:
	int V;
	vvi List;
	vvb dp;
	vi a;
	void Update(int v,int d){
		for(int i=d;i>=0;i--){
			if(dp[v][i]) break;
			dp[v][i]=1;
		}
	}
	void dfs(int v,int d,int c){
		Update(v,d);
		if(!a[v]) a[v]=c;
		if(!d) return;
		for(int i=0;i<List[v].size();i++){
			int u=List[v][i];
			if(!dp[u][d-1]) dfs(u,d-1,c);
		}
	}
	public:
	Graph(int v){
		V=v;
		List=vvi(v);
		dp=vvb(v,vb(11,0));
		a=vi(v);
	}
	void add_edge(int s,int t){
		List[s].push_back(t);
		List[t].push_back(s);
	}
	void solve(){
		int q;
		cin>>q;
		vi v,d,c;
		v=d=c=vi(q);
		for(int i=0;i<q;i++) cin>>v[i]>>d[i]>>c[i];
		for(int i=q-1;i>=0;i--) if(!dp[v[i]-1][d[i]]) dfs(v[i]-1,d[i],c[i]);
		for(int i=0;i<V;i++) cout<<a[i]<<endl;
	}
};

int n,m;

int main(){
	cin>>n>>m;
	Graph g(n);
	for(int i=0;i<m;i++){
		int s,t;
		cin>>s>>t;
		g.add_edge(s-1,t-1);
	}
	g.solve();
}

Measured memory_bytes: 15096
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();
        if(b % a == 0) {
            System.out.println(a + b);
        }else {
            System.out.println(b - a);
        }
    }
}


Measured memory_bytes: 23124
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp00=[0]*(s+1)
dp01=[0]*(s+1)
dp10=[0]*(s+1)
dp11=[0]*(s+1)
dp20=[0]*(s+1)
dp21=[0]*(s+1)
dp00[0]=1
for i in range(n):
  for j in range(s+1):
    if i%2==0:
      if j>=a[i]:
        dp11[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j]+dp20[j])%mod
      else:
        dp01[j]=dp00[j]%mod
        dp11[j]=(dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j]+dp10[j]+dp20[j])%mod
    else:
      if j>=a[i]:
        dp10[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j]+dp21[j])%mod
      else:
        dp00[j]=dp01[j]%mod
        dp10[j]=(dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j]+dp11[j]+dp21[j])%mod
if n%2==1:
  print(dp21[s])
else:
  print(dp20[s])

Measured memory_bytes: 44720
from fractions import gcd


def prime_factorize(n):
    ret = []
    while n % 2 == 0:
        ret.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ret.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ret.append(n)
    return ret


def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    lst_prime_numbers = prime_factorize(g)
    ans = 1 + len(set(lst_prime_numbers))
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 5596
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

A,B=two_int()

data = list(set(make_divisors(A)) & set(make_divisors(B)))

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

count=1
data.sort()
for i in data[1:]:
    if is_prime(i):
        count+=1
print(count)

Measured memory_bytes: 5068
//
//  main.cpp
//  Atcoder66
//
//  Created by GaoY on 16/12/18.
//  Copyright (c) 2016年 GaoY. All rights reserved.
//

#include <bits/stdc++.h>

using namespace::std;

void solve(){
    int n;
    cin>>n;
    if(n==0){
        cout<<0<<endl;
        return;
    }
    int f=0;
    int modi=pow(10,9)+7;
    
    if(n%2==1) f=1;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin>>a[i];
    }
    if(n==1&&a[0]==0){
        cout<< 1<<endl;
        return;
    }
    if(n==1&&a[0]!=0){
        cout<< 0<<endl;
        return;
    }
    sort(a.begin(), a.end());
    if(f==1){
        if(a[0]==0&&a[1]==0){
            cout<<0<<endl;
            return;
        }
    }else{
        if (a[0]==0) {
            cout<<0<<endl;
            return;
        }
    }
    for (int j=f; j<a.size()-1; j=j+2) {
        if(a[j]!=a[j+1]){
            cout<<0<<endl;
            return;
        }
    }
    long long ret=1;
    for(int i=0;i<(n-f)/2;i++){
        ret=ret*2%modi;
    }
    cout<<ret<<endl;
    return;
}



int main(int argc, const char * argv[]) {
    // insert code here...
    //freopen("data", "r",stdin );
    solve();
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#define llint long long
#define inf 1000000000
#define mod 998244353

using namespace std;

llint n;
string s;
llint dp[200005][2];
vector<llint> vec[200005];
llint num[200005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	cin >> s;
	s = "#" + s;
	
	dp[0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++){
				if(j == 0 && s[i+1] == '0' && k == 1) continue;
				int nj = j;
				if(s[i+1] == '1' && k == 0) nj = 1;
				dp[i+1][nj] += dp[i][j], dp[i+1][nj] %= mod;
			}
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; i*j <= n; j++) vec[i*j].push_back(i);
	}
	
	llint ans = 0, rem = 1;
	llint mul = 1;
	for(int i = 0; i < n; i++){
		rem += (s[n-i] -'0') * mul % mod, rem %= mod;
		mul *= 2, mul %= mod;
	}
	//cout << rem << endl;
	for(int i = n; i >= 3; i--){
		if(i % 2 == 0 || n % i) continue;
		llint x = n/i, can;
		can = dp[x][1];
		bool flag = true;
		for(int i = 1; i <= n; i++){
			int p = (i-1)/x;
			int z = (i-1)%x+1;
			if(p % 2 == 0){
				if(s[i] == '1' && s[z] == '0') break;
				if(s[i] == '0' && s[z] == '1'){
					flag = false;
					break;
				}
			}
			else{
				if(s[i] == '1' && s[z] == '1') break;
				if(s[i] == '0' && s[z] == '0'){
					flag = false;
					break;
				}
			}
		}
		if(flag) can++, can %= mod;
		for(int j = 0; j < vec[x].size(); j++){
			if(vec[x][j] == x) continue;
			can += mod - num[vec[x][j]], can %= mod;
		}
		
		//cout << x << " " << can << " " << flag << endl;
		ans += can * (2*x) % mod, ans %= mod;
		rem += mod - can, rem %= mod;
		num[x] = can;
	}
	//cout <<rem << endl;
	ans += rem * (2*n) % mod, ans %= mod;
	cout << ans << endl;
	
	/*for(int i = 0; i < (1<<21); i++){
		llint cnt = 0, k = i;
		do{
			cnt++;
			if(k % 2) k >>= 1;
			else k >>= 1, k += (1<<20);
		}while(k != i);
		if(cnt != 42) cout << i << " : " << cnt << endl;
	}*/
	
	return 0;
}

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

const int maxn = 405;
const ll inf = 1e18;
ll a[maxn];
ll DP[maxn][maxn];
ll sum[maxn];
int N;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for(int i = 1; i <= N; ++i){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for(int len = 2; len <= N; ++len){
        for(int i = 1; i + len - 1 <= N; ++i){
            int j = i + len - 1;
            DP[i][j] = sum[j] - sum[i - 1];
            ll min_val = inf;
            for(int k = i; k < j; ++k){
                min_val = min(min_val , DP[i][k] + DP[k + 1][j]);
            }
            DP[i][j] += min_val;
        }
    }
    cout << DP[1][N] << endl;
}


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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string str;

    map<string, int> mp;
    map<string, int> :: iterator itr;
    mp["SUN"]=7;
    mp["MON"]=6;
    mp["TUE"]=5;
    mp["WED"]=4;
    mp["THU"]=3;
    mp["FRI"]=2;
    mp["SAT"]=1;
    cin >> str;
    itr = mp.find(str);
    if(itr != mp.end()){
        cout<< itr->second ;
    }

    return 0;
}


Measured memory_bytes: 256
N, D = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for _ in range(N)]

count = 0
for i, xi in enumerate(X):
    for j, xj in enumerate(X):
        if i >= j:
            continue
        t = 0
        for k in range(D):
            t += (xi[k] - xj[k]) ** 2
        if int(t ** 0.5) ** 2 == t:
            count += 1

print(count)

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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

void check(vector<int> x) {
  for (int i = 0; i < (int)x.size(); i++) {
    if (i)
      cout << ' ';
    cout << x[i];
  }
  cout << endl;
}

int main() {
  int N;
  cin >> N;
  vector<int> a(N), b(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> b[i];
  }
  long long cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a[i] - b[i] < 0) {
      long long tmp = (b[i] - a[i]) / 2 + (b[i] - a[i]) % 2;
      cnt += tmp;
      a[i] += tmp * 2;
    }
  }
  for (int i = 0; i < N; i++) {
    if (cnt <= 0)
      break;
    if (a[i] - b[i] > 0) {
      long long tmp = a[i] - b[i];
      if (cnt < tmp)
        b[i] += cnt;
      else
        b[i] = a[i];
      cnt -= min(cnt, tmp);
    }
  }
  for (int i = 0; i < N; i++) {
    if (a[i] != b[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 384
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		for(int i=0;i<n;i++){
			list.add(sc.nextInt());
		}
		int count = 0;

		boolean isAllZero =false;
		for(int i=0;i<101;i++){
			count++;
			boolean flag =false;
			isAllZero =true;
			boolean isAfterSecondZero =false;
			for(int j =0;j<n;j++){
				int height = list.get(j);
				if(height == 0 ){
					if(isAfterSecondZero){
						flag =true;
						// isAfterSecondZero =false;
					}
				}else{
					isAfterSecondZero =true;
					isAllZero =false;
					list.set(j,height-1);
					if(flag){
						count++;
					}
					flag =false;
				}
				// System.out.print("j"+j);
				// System.out.print(" height"+height);
				// System.out.println(" count"+count);
			}
			if(isAllZero){
				break;
			}
			// if(i >50){
			// 	System.out.print(i + " ");
			// 	System.out.print(count);
			// 	System.out.println(" end oneLine");

			// }

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

	}
}



Measured memory_bytes: 22612
#include <iostream>
#include <string>

int main(){
  int a,b;
  std::string s;
  std::cin>>a>>b>>s;
  bool f=true;
  for(int i=0;i<s.size();++i){
    if(i!=a){
      if(s[i]>'9' || s[i]<'0'){
        f=false;
        break;
      }
    }else{
      if(s[i]!='-'){
        f=false;
        break;
      }
    }
  }
  if(f)std::cout<<"Yes"<<std::endl;
  else std::cout<<"No"<<std::endl;
  return 0;
}



Measured memory_bytes: 256
import math
x = int(input())
cnt = 10**5
res = 0,0
for b in range(cnt):
    val = x+int(pow(b,5))
    if (int(val**0.2))**5 == val:
        res = int(val**0.2),b
        break
    val = x-b**5
    if val < 0:
        continue
    if (int(val**0.2))**5 == val:
        res = int(val**0.2),-b
        break
print(*res)

Measured memory_bytes: 9356
#include<bits/stdc++.h>
//#include<iostream>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define gap ' '
#define abs(x) ((x)>0?(x):-(x))
#define INF 1e18
#define mod  10000007
int main()
{
 ios::sync_with_stdio(0);
    cin.tie(0);
    string s,t;
    cin>>s>>t;
    int lens=s.size();
    int lent=t.size();
    int dp[lens+1][lent+1];
    for(int i=0;i<=lens;i++)
        for(int j=0;j<=lent;j++)
        dp[i][j]=0;
    for(int i=1;i<=lens;i++ )
        for(int j=1;j<=lent;j++)
    {
        if(t[j-1]==s[i-1]) dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
        else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
    }
    string ans;
    int te=lens;
    int te2=lent;
    //int ttt=0;
   while(te && te2)
   {
       if(dp[te][te2]!=dp[te-1][te2] && dp[te][te2]!=dp[te][te2-1])
           {
               ans+=s[te-1];
               te--;
               te2--;
           }
        else if(dp[te][te2]==dp[te-1][te2]) te--;
        else if(dp[te][te2]==dp[te][te2-1]) te2--;


   }
   reverse(ans.begin(),ans.end());
cout<<ans;

}


Measured memory_bytes: 35456
#include<stdio.h>

int main(){
   int h, w;
   for(int i=0; ;i++){
      scanf("%d %d", &h, &w);
      if(h == 0 & w == 0)break;
      for(int j=0; j<h; j++){
         for(int k=0; k<w; k++){
           printf("#");
        }
        printf("\n");
      }
      printf("\n");
    }
}


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

int main(){
    ll n,m;
    cin >> n >> m;
    vector<ll> friends(n,1);
    vector<ll> samewith(n);
    for(ll i=0;i<n;i++){
      samewith[i]=i;
    }
    for(ll i=0;i<m;i++){
      ll _a,_b;
      cin >> _a >> _b;
      ll a = _a-1; ll b = _b-1;
      ll ga = a;
      while(true){
        if(samewith[ga]==ga) break;
        else ga = samewith[ga];
      }
      ll gb = b;
      while(true){
        if(samewith[gb]==gb) break;
        else gb = samewith[gb];
      }
      if(ga == gb) continue;
      ll sum = friends[ga]+friends[gb];
      ll gab = min(ga,gb);
      friends[gab] = sum;
      samewith[a] = gab;
      samewith[b] = gab;
      samewith[ga] = gab;
      samewith[gb] = gab;
    }
    ll maxfriend = 0;
    for(ll i=0;i<n;i++){
      maxfriend = max(friends[i],maxfriend);
    }
    cout << maxfriend;
}

Measured memory_bytes: 6384
#include <stdio.h>

int main(void){

int N,A,B;

scanf("%d %d %d", &N,&A,&B);

if(
    1<=N && N<=20,
    1<=A && A<=50,
    1<=B && B<=50
){
    
}else{
    printf("error");
}

int NA = N*A;
if(NA < B){
    printf("%d\n" ,NA);
    
}else if(NA>B){
    printf("%d\n",B);
}else{
    printf("%d\n",NA);
}

}

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

#define INF (ll)1e+18

int main(){

	  int V,E; cin >> V >> E;

	  AdjMat G(V,vector<ll>(V,INF));
	  for(int i=0; i<E; i++){
			ll s,t,d; cin >> s >> t >> d;
			G[s][t] = d;
	  }
	  for(int i=0; i<V; i++) G[i][i] = 0;

	  for(int k=0; k<V; k++)
			for(int j=0; j<V; j++)
				  for(int i=0; i<V; i++)
						G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

	  for(int i=0; i<V; i++)
			if(G[i][i] != 0){	  cout << "NEGATIVE CYCLE" << endl;	  return 0;			}

	  for(int i=0; i<V; i++){
			for(int j=0; j<V; j++){
				  if(G[i][j] >= INF/10) cout << "INF";
				  else cout << G[i][j];
				  if(j==V-1) cout << endl;
				  else cout << " ";
			}
	  }
}
			
	  
			   

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

int main() {

    int N, K;
    cin >> N >> K;

    double p = 0;
    int x = 1;
    for (int i = N; i > 0; i--) {
        while (x < 1.0*K/i) {
            x *= 2;
        }
        p += 1.0 / x;
    }

    cout << setprecision(15) << 1.0 * p / N << endl;

    return 0;
}


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

int main(void){
    
    unsigned long H,W;
    cin >> H >> W;
    
    if(H%2 == 1 && W%2 == 1){
        if(H == 1 || W == 1){
            cout << 1 << endl;
        }
        else{
            cout<< H*W/2 + 1 <<endl;
        }
        
    }
    else{
        if(H == 1 || W == 1){
            cout << 1 << endl;
        }
        else{
            cout<< H*W/2 <<endl;
        }
        
    }
   
}

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

long long min(long long a, long long b){
	if(a > b){
		return b;
	}else{
		return a;
	}
}


int main(){
	long long a, b, c;
	cin >> a >> b >> c ;
	if(a%2 == 0 || b%2 == 0 || c%2 == 0){
		cout << 0 << endl;
		return 0;
	}

	long long ans = min(a*b, min(b*c, c*a));
	cout << ans << endl;

}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import math
a, b, h, m = map(int, input().split())
dh = float(360/12)*(h+m/60)
dm = float(360/60)*m
t = max(dh,dm)-min(dh,dm)
theta = t if t<=180 else 360-t

c = math.sqrt(a**2+b**2 - 2*a*b*math.cos(math.radians(theta)))
print("{:.10f}".format(c))

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

int main() {
	string s;
	cin >> s;
	ll sum = 0;
	for (char c : s) {
		sum += c - '0';
	}
	if (sum % 9 == 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 3744
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> p;

int main()
{
    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    vector<int> tmp = p;
    int ans = 0;
    sort(tmp.begin(), tmp.end());
    for(int i = 0; i < n; ++i) {
        if (p[i] != tmp[i]) ++ans;
    }

    if (ans <= 2) printf("YES\n");
    else printf("NO\n");

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define ll long long
#define debug(x) cout << "debug: " << x << endl
#define MOD 1e9 + 7
#define INF 1e9

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

//const double pi = 3.1415926535;

int main(){
    int n;
    cin>>n;
    vector<int> a(n + 1);
    vector<int> k(n + 1, 0);
    repk(i, 2, n + 2) {
        cin >> a[i];
        k[a[i]]++;
    }

    repk(i, 1, n+1) cout << k[i] << endl;

}

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

int main()
{
    int n, r, ans;
    cin >> n >> r;
    if (n >= 10)
        ans = r;
    else
        ans = r + 100 * (10 - n);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

#ここから書き始める
x, y, z = map(int, input().split())
print(z, x, y)

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

typedef long long ll;
typedef long long LL;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#ifdef DEBUG
    #define cek(x) cout<<x
#else
    #define cek(x) if(false){}
#endif // DEBUG

#define fi first
#define se second
#define INF 1000000000
#define INFLL 1000000000000000000LL
#define EPS 1e-9
#define PI acos(-1.0)
#define pb push_back
#define TC() while(tc--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORN(i,n) for(int i=0;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REPN(i,a,b) for(int i=a;i<=b;i++)
#define reset(a,b) memset(a,b,sizeof(a))
#define sc(x) scanf("%d",&x)

char str[200010];

int main(void){
    #ifdef ccsnoopy
        freopen("D:/Code/in.txt","r",stdin);
    #endif

    scanf("%s", str);
    int len = strlen(str);
    stack<char> st;
    FOR(i,len){
        if(str[i] == 'T'){
            if(!st.empty() && st.top() == 'S'){
                st.pop();
            }else st.push(str[i]);
        }else st.push(str[i]);
    }

    printf("%d\n", (int)st.size());


    return 0;
}





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

#define ll long long
ll N , M , P;

void BF(){
	static bool vis[10000007]; vis[1] = 1;
	for(int i = 2 ; i <= M ; ++i)
		if(M % i == 0){
			int tms = P; while(!vis[tms]){vis[tms] = 1; tms = 1ll * tms * P % M;}
			for(int j = 1 ; j <= M / i ; ++j) vis[i * j] = 1;
			vector < int > ans; for(int i = 1 ; ans.size() < N && i < M ; ++i) if(!vis[i]) ans.push_back(i);
			if(ans.size() < N) puts("-1"); else for(auto t : ans) printf("%d " , t);
			break;
		}
}

ll FM(ll A , ll B , ll P){ll C = A * B - (ll)((long double)A / P * B + 0.5) * P; return C < 0 ? C + P : C;}
ll PW(ll A , ll B , ll P){ll T = 1; while(B){if(B & 1) T = FM(T , A , P); A = FM(A , A , P); B >>= 1;} return T;}

mt19937_64 rnd(time(0));
const int prm[] = {2,3,5,7,11,13,19,29,31,37,61,24251,998244353,19260817} , SZ = 14;
bool MR(ll P){
	for(int i = 0 ; i < SZ ; ++i)
		if(P == prm[i]) return 1;
		else if(P % prm[i] == 0) return 0;
		else if(PW(prm[i] , P - 1 , P) != 1) return 0;
	ll tms = P - 1; while(!(tms & 1)) tms >>= 1;
	for(int i = 0 ; i < SZ ; ++i){
		ll val = PW(prm[i] , tms , P); if(val == 1) continue;
		while(val != P - 1 && val != 1) val = FM(val , val , P);
		if(val == 1) return 0;
	}
	return 1;
}

ll PR(ll P){
	ll x0 = 0 , c = rnd() % (P - 1) + 1 , x = 0;
	for(int i = 1 ; ; i <<= 1 , x0 = x){
		ll tms = 1;
		for(int j = 1 ; j <= i ; ++j){
			x = (FM(x , x , P) + c) % P; tms = FM(tms , abs(x - x0) , P);
			if(j % 128 == 0 && __gcd(tms , P) != 1) return __gcd(tms , P);
		}
		if(__gcd(tms , P) != 1) return __gcd(tms , P);
	}
	return P;
}

vector < ll > pot;
void find(ll P , int tms){
	if(P == 1) return;
	if(MR(P)) return (void)pot.insert(pot.end() , tms , P);
	ll t = PR(P); while(t == P) t = PR(P);
	int cnt = 0; while(P % t == 0){P /= t; ++cnt;}
	find(t , tms * cnt); find(P , tms);
}

map < ll , int > cnt; map < ll , ll > anti;

int main(){
	int N; cin >> N;
	for(int i = 1 ; i <= N ; ++i){
		ll s; cin >> s; pot.clear(); find(s , 1); sort(pot.begin() , pot.end()); int p = 0; long double tms1 = 1 , tms2 = 1;
		while(p < pot.size()){
			int pos = p; while(pos < pot.size() && pot[p] == pot[pos]) ++pos;
			int num = (pos - p) % 3; for(int i = 0 ; i < num ; ++i) tms1 *= pot[p];
			for(int i = 0 ; i < (3 - num) % 3 ; ++i) tms2 *= pot[p];
			p = pos;
		}
		++cnt[tms1]; anti[tms1] = tms2;
	}
	int sum = 0;
	while(!cnt.empty()){
		ll t = cnt.begin()->first; sum += t == 1 ? 1 : (max(cnt[t] , cnt[anti[t]]));
		cnt.erase(t); cnt.erase(anti[t]);
	}
	cout << sum;
	return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

s64 N;

s64 dfs(s64 x)
{
    s64 ret = 0;
    if (x > N) return ret;

    bool flag[3] = {false, false, false};
    s64 temp = x;
    while (temp > 0)
    {
        flag[(temp % 10) % 3] = true;
        temp /= 10;
    }
    if (flag[0] && flag[1] && flag[2]) ++ret;

    static s64 l[] = {3, 5, 7};
    rep (i, 3)
    {
        ret += dfs(x * 10 + l[i]);
    }
    return ret;
}

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

    cin >> N;

    s64 ans = dfs(0);

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N,M;cin>>N>>M;
  vector<vector<long>>A(8,vector<long>(N));
  for(long j=0;j<N;j++){
    long x,y,z;cin>>x>>y>>z;  
    for(long i=0;i<8;i++){
      long a=(i%2)*2-1,b=((i/2)%2)*2-1,c=((i/4)%2)*2-1;
      A[i][j]=a*x+b*y+c*z;
    }
  }
  vector<long>B(8,0);
  for(long i=0;i<8;i++){
    sort(A[i].begin(),A[i].end(),greater<long>());
    for(long j=0;j<M;j++)B[i]+=A[i][j];
    B[i]=abs(B[i]);
  }
  sort(B.begin(),B.end(),greater<long>());
  cout<<B[0];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define mod 1000000007
#define ALL(a) a.begin(),a.end()
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

bool IsPrime(ll num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
const int INF = 1000000000;
const int MOD = 1000000007;

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

int main() {
  ull x;
  cin >> x;
  int n = 1000;
  vector<ull> a(n), b(n);
  for(ull i = 0; i < n; ++i){
    a[i] = i * i * i * i * i;
    b[i] = i * i * i * i * i;
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i] - b[j] == x){
        cout << i << " " << j << endl;
        return 0;
      }
      else if (a[i] + b[j] == x){
        cout << i << " " << -j << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3644
#include <stdio.h>
#include <stdlib.h>

#define N 4
#define N2 16
#define LIMIT 100

int H[N2][N2];//マンハッタン距離の組み合わせの集合
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0}; //方向

void swap(int *x,int *y){
  int tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

typedef struct puzzle
{
  int f[N2];//どの場所になんの数字が入っているか
  int space;//空マス
  int MD;//マンハッタン距離
}Puzzle;

Puzzle state;//現在の状態
int limit;//深さの制限
int path[LIMIT];

int getAllMD(Puzzle pz){
  int sum = 0;
  int i;
  for(i=0; i<N2; i++){
    if(pz.f[i] == N2)continue; //正しい位置にあればそのまま
    sum += H[i][pz.f[i] - 1];//マンハッタン距離を加える
  }
  //printf("getALLMD\n");
  return sum;
}

int isSolved(){
  int i;
  for (int i = 0; i < N2; ++i)if(state.f[i] != i+1)return 0;
  return 1;
}

int dfs(int depth, int prev){
  //printf("dfs start\n");
  if(state.MD == 0)return 1; //終了
  if(depth + state.MD > limit)return 0;

  int sx = state.space / N; //空のマスのx座標;
  int sy = state.space % N; //空のマスのy座標;

  Puzzle tmp;
  int r;
  for(r = 0;r < 4;r++){
    int tx = sx + dx[r]; //空のマスの次の位置
    int ty = sy + dy[r];
    if(tx < 0|| ty <0||tx >= N||ty >= N)continue; //行けないマスはスルー
    if((prev - r == 2)||(prev - r == -2))continue;//一個前の状態に戻る操作はスルー
    tmp = state;
    state.MD -= H[tx * N + ty][state.f[tx * N + ty]-1];//入れ替わった分のマンハッタンん距離の増減を加算
    state.MD += H[sx * N + sy][state.f[tx * N + ty]-1];
    swap(&state.f[tx * N + ty],&state.f[sx * N + sy]);
    state.space = tx * N + ty;
    if(dfs(depth+1,r) != 0){path[depth] = r; return 1;}
    state = tmp;
  }
  return 0;
}

int iterative_deepening(Puzzle in){
  in.MD = getAllMD(in);

  for(limit = in.MD;limit <= LIMIT; limit++){//limit = c
    state = in;
    if(dfs(0,-100) != 0){
      //pathに入っている文字数を数えたい
      int count = 0,l;
      for(l=0;l<limit;l++){
        if(path[l] != ' ')count++;
      }
      //printf("\n");
      //printf("return count\n");
      return count;

    }
  }
  return -1;
}

int main(void){
  int i,j;
  for(i=0;i<N2;i++){
    for(j=0;j<N2;j++){
      H[i][j] = abs(i/N - j/N) + abs(i%N -j%N);//マンハッタン距離の組み合わせの初期化
    }
  }

  Puzzle in;//初期のパズル

  for(i=0;i<N2;i++){
    scanf("%d", &in.f[i]);
    if(in.f[i]==0){
      in.f[i] = N2;
      in.space = i;
    }
  }

  int ans = iterative_deepening(in);
  printf("%d\n",ans);
  return 0;

}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using vec_b = vector<bool>;
using vec_str = vector<string>;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back


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

int main()
{
    ll N, M;
    cin >> N >> M;
    vec A(N);
    REP(i,0,N) cin >> A[i];
    vector<pair<ll,ll>> P(M);
    ll b, c;
    REP(i,0,M) {
        cin >> b >> c;
        P[i] = make_pair(b, c);
    }

    sort(ALL(A));
    sort(ALL(P), compare_by_second);
    
    vec D(N, 0);
    ll k = 0;
    REP(i,0,M) {
        b = P[i].first;
        c = P[i].second;
        REP(j,k,MIN(k+b,N)) D[j] = c;
        k += b;
        if(k >= N) break;
    }

    ll sum = 0;
    REP(i,0,N) sum += MAX(D[i],A[i]);
    _PR(sum);

    return 0;
}

/*



*/

Measured memory_bytes: 3328