akhauriyash/Code-Regression huggingface dataset:
def solve(n, a):
    ans = 1000
    for i in range(n-1):
        if a[i] < a[i+1]:
            ans += (ans // a[i]) * (a[i+1] - a[i])
    return ans

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Measured memory_bytes: 9128
use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::cmp::*;
use std::collections::HashSet;
use std::iter::Iterator;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
      n: usize,
      mut a:[i64;n],
    }

    a.sort();
    let a_max = a[n - 1];
    let mut cnt = 0;
    let mut dp = vec![true; (a_max+1) as usize];
    let mut countdp = vec![0; (a_max+1) as usize];

    for &x in a.iter() {
        countdp[x as usize] += 1;
        for i in 2..2000000 {
            if x * i <= a_max {
                if dp[(x * i) as usize] == false {
                    continue;
                }
                dp[(x * i) as usize] = false;
            }else{
                break;
            }
        }
    }

    if a.len() == 1 {
        println!("1");
        return;
    }


    for &i in a.iter() {
        if countdp[i as usize] <= 1 && dp[i as usize] == true {
            cnt +=1;
        }
    }

    println!("{}", cnt);
}


Measured memory_bytes: 9764
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    assert_eq!(v.len(), 2);
    (v[0], v[1])
}

fn main() {
    let n: usize = read();
    let mut i = 1;
    let mut ans = 1_000_000;
    while i * i <= n {
        if n % i == 0 {
            let a = count_digits(i);
            let b = count_digits(n / i);
            let v = std::cmp::max(a, b);
            ans = std::cmp::min(ans, v);
        }
        i += 1;
    }

    println!("{}", ans);
}

fn count_digits(n: usize) -> usize {
    let mut n = n;
    let mut ret = 0;
    while n > 0 {
        ret += 1;
        n /= 10;
    }

    ret
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[100010];
int main(){
    int n;
    string s;
    while(cin>>s){
    	n=s.size();
        ll ans=1;
        int m=n/2, m1, m2;
        if(n%2==0){
        	m1=m-1;
        	m2=m;
        }
        else{
        	m1=m-1;
        	m2=m+1;
        }
        for(int i=0; i<n; ++i){
        	if(s[i]!=s[n-1-i]){
        		ans=0;
        		break;
        	}
        	if(i<=m1){
        		if(s[i]!=s[m1-i]){
        			ans=0;
        			break;
        		}
        	}
        	// if(i>=m2){
        	// 	if(s[i]!=s[n-1-(i-m2)]){
        	// 		ans=0;
        	// 		break;
        	// 	}
        	// }
        }
        if(ans){
        	cout<<"Yes"<<endl;
        }
        else{
        	cout<<"No"<<endl;
        }
    }
  return 0;
}




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

int main(){
    using namespace std;
    unsigned long N, M;
    cin >> N >> M;
    vector<pair<unsigned long, pair<unsigned long, unsigned long>>> vt(N), hr(M);
    vector<unsigned long> xs, ys;
    constexpr unsigned long ofs = 1100000000;
    for(auto&& [i, j] : vt){
        long a, b, c;
        cin >> a >> b >> c;
        i = (c + ofs) * 2;
        ys.push_back(i);
        j = {(a + ofs) * 2, (b + ofs) * 2};
        xs.push_back(j.first);
        xs.push_back(j.second);
    }
    for(auto&& [i, j] : hr){
        long d, e, f;
        cin >> d >> e >> f;
        i = (d + ofs) * 2;
        xs.push_back(i);
        j = {(e + ofs) * 2, (f + ofs) * 2};
        ys.push_back(j.first);
        ys.push_back(j.second);
    }
    sort(vt.begin(), vt.end());
    sort(hr.begin(), hr.end());
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    const auto vt_locked = [&vt](unsigned long x, unsigned long y) -> bool {
        auto t = lower_bound(vt.begin(), vt.end(), pair<unsigned long, pair<unsigned long, unsigned long>>{y, pair<unsigned long, unsigned long>{0, 0}});
        unsigned long k = lower_bound(vt.begin(), vt.end(), pair<unsigned long, pair<unsigned long, unsigned long>>{y + 1, pair<unsigned long, unsigned long>{0, 0}}) - t;
        for(unsigned long i{0}; i < k; ++i)if(t[i].second.first <= x && x <= t[i].second.second)return true;
        return false;
    };
    const auto hr_locked = [&hr](unsigned long x, unsigned long y) -> bool {
        auto t = lower_bound(hr.begin(), hr.end(), pair<unsigned long, pair<unsigned long, unsigned long>>{x, pair<unsigned long, unsigned long>{0, 0}});
        unsigned long k = lower_bound(hr.begin(), hr.end(), pair<unsigned long, pair<unsigned long, unsigned long>>{x + 1, pair<unsigned long, unsigned long>{0, 0}}) - t;
        for(unsigned long i{0}; i < k; ++i)if(t[i].second.first <= y && y <= t[i].second.second)return true;
        return false;
    };
    deque visited(xs.size() + 1, deque(ys.size() + 1, false));
    queue<pair<unsigned long, unsigned long>> q;
    q.emplace(lower_bound(xs.begin(), xs.end(), 2 * ofs + 1) - xs.begin(), lower_bound(ys.begin(), ys.end(), 2 * ofs - 1) - ys.begin());
    unsigned long ans{0};
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        if(x == 0 || y == 0 || x == xs.size() || y == ys.size())return 0 & puts("INF");
        if(visited[x][y])continue;
        visited[x][y] = true;
        ans += (xs[x] - xs[x - 1]) * (ys[y] - ys[y - 1]) / 4;
        if(!hr_locked(xs[x], (ys[y] + ys[y - 1]) / 2) && !visited[x + 1][y])q.emplace(x + 1, y);
        if(!hr_locked(xs[x - 1], (ys[y] + ys[y - 1]) / 2) && !visited[x - 1][y])q.emplace(x - 1, y);
        if(!vt_locked((xs[x] + xs[x - 1]) / 2, ys[y]) && !visited[x][y + 1])q.emplace(x, y + 1);
        if(!vt_locked((xs[x] + xs[x - 1]) / 2, ys[y - 1]) && !visited[x][y - 1])q.emplace(x, y - 1);
    }
    cout << ans << endl;
    return 0;
}

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

ll H, N, A[1000]={0}, B[1000]={0}, DP[20001];

signed main(){
    cin >> H >> N;
    for(int i=0;i<N;i++) cin >> A[i] >> B[i];
    for(int i=0;i<20001;i++) DP[i] = 1000000000;
    DP[0] = 0;
    for(int i=1;i<20001;i++) {
        for(int k=0;k<N;k++) {
            if(i-A[k]>=0) DP[i] = min(DP[i], DP[i-A[k]] + B[k]);
        }
    }
    ll ans = DP[H];
    for(int i=H;i<20001;i++) ans = min(ans, DP[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
s=input().split()
th=int(s[0])
ta=int(s[1])
ah=int(s[2])
aa=int(s[3])

while 1:
  ah=ah-ta
  if ah<1:
    print('Yes')
    break
  th=th-aa
  if th<1:
    print('No')
    break

Measured memory_bytes: 9188
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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 INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    int n;
    cin>>n;
    vi as(n);
    cin>>as;
    rep(i, n) as[i]--;
    
    int cur = 0;
    int cnt = 0;
    rep(i, n) {
        cur = as[cur];
        cnt++;
        if (cur == 1) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

using namespace std;

long long H, W;
string ban[25];

long long d[500][500];

long long toId(long long h, long long w) {
	return h * W + w;
}

int main(){
	cin >> H >> W;
	rep(i, H) cin >> ban[i];

	long long maxid = toId(H-1, W-1);

	rep(i, maxid+1){
		rep(j, maxid+1){
			d[i][j] = LONG_MAX/10;
		}
		d[i][i] = 0;
	}

	rep(i, H) {
		rep(j, W) {
			if(ban[i][j] == '#')continue;

			if(i > 0 && ban[i-1][j] == '.') {
				d[toId(i, j)][toId(i-1, j)] = 1;
				d[toId(i-1, j)][toId(i, j)] = 1;
			}

			if(i < H - 1 && ban[i+1][j] == '.') {
				d[toId(i, j)][toId(i+1, j)] = 1;
				d[toId(i+1, j)][toId(i, j)] = 1;
			}

			if(j > 0 && ban[i][j-1] == '.') {
				d[toId(i, j)][toId(i, j-1)] = 1;
				d[toId(i, j-1)][toId(i, j)] = 1;
			}

			if(j < W - 1 && ban[i][j+1] == '.') {
				d[toId(i, j)][toId(i, j+1)] = 1;
				d[toId(i, j+1)][toId(i, j)] = 1;
			}
		}
	}


	long long maxi = 0;
	for(int k = 0; k < maxid + 1; ++k){
		for(int i = 0; i < maxid + 1; ++i){
			for(int j = 0; j < maxid + 1; ++j){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	long long ans = 0;
	for(int i = 0; i < maxid + 1; i++){
		for(int j = 0; j < maxid + 1; j++){
			if(d[i][j] != LONG_MAX/10)
			ans = max(ans, d[i][j]);
		}
	}
	cout << ans << endl;



}


Measured memory_bytes: 5172
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int main() {
    //  freopen("test.in", "r", stdin);
    //  freopen("ac.txt", "w", stdout);
   int n;
   long long d;
   scanf("%d %lld",&n,&d);
   d*=d;
   long long x,y;
   int c = 0;
   while(n--){
       scanf("%lld %lld",&x,&y);
       x = x*x+y*y;
       c+=(x<=d);
   }
   printf("%d",c);
}


Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i = 0; i < (int)n; ++i)
 
bool isPrime(int num)
{
    if(num == 2) return true;
    if(num%2 == 0) return false;
 
    // +1 重要
    for(int i = 3; i < sqrt(num) + 1; i += 2) {
        if(num % i == 0) return false;
    }
    return true;
}
 
int main()
{
    int N;
    int count = 0;
    int num;
 
    cin >> N;
 
    REP(i, N) {
        cin >> num;
        if(isPrime(num)) ++count;
    }
 
    cout << count << endl;
 
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
string Yes[2] = {"Yes", "No"};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

using Graph = vector<vector<int>>;
Graph G;

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

    ll n; cin >> n;
    ll ans = 0;
    vector<ll> a(n), b(n), c(n), sum(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sum[0] = 0;

    rep(i, n){
        auto pos = lower_bound(a.begin(), a.end(), b[i]);
        int index = distance(a.begin(), pos);
        sum[i + 1] = sum[i] + index;
    }
    rep(i, n){
        auto pos = lower_bound(b.begin(), b.end(), c[i]);
        int index = distance(b.begin(), pos);
        ans += sum[index];
    }
    cout << ans << endl;
}


Measured memory_bytes: 6344
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define INF 1e12


int main()
{
	ll v,x,y,e,a,b,in=0;
	pll h;
	cin>>v>>e;
	vector<vl > grafo(v,vl(0));
	for(int i=0;i<e;i++)
    {
        cin>>x>>y;
        grafo[x-1].push_back(y-1);
    }
    cin>>a>>b;a--;b--;


    ll p=0,inicio=a;
	vector<vector<bool> > visitado(v,vector<bool>(4,false));
	vector<vector<ll> > dist(v,vector<ll>(4,INF));
    dist[inicio][p]=0;
    if(!visitado[inicio][p]){
    queue<pll> q;
    q.emplace(inicio,p);
    while(!q.empty()){

		    ll t=q.front().first,pos=q.front().second;
		    q.pop();
		    if(!visitado[t][pos%3]){

		        visitado[t][pos%3]=true;
		        for(ll i=0;i<grafo[t].size();i++){

		            if(!visitado[grafo[t][i]][(pos+1)%3])
					{
					    dist[grafo[t][i]][(pos+1)%3]=dist[t][pos%3]+1;
						q.emplace(grafo[t][i],(pos+1)%3);
					}
		        }
		    }
		}
		//u.

		}
    if(dist[b][0]!=INF)cout<<dist[b][0]/3<<"\n";
    else cout<<"-1\n";
	return 0;
}


Measured memory_bytes: 19840
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define all(x) begin((x)), end((x))
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    vector<vector<ll>> children(n);
    vector<ll> v(n);
    rep(i,n) {
        cin>>v[i];
        v[i]--;
    }
    rep(i,n-1) {
        ll a,b;cin>>a>>b;
        a--;b--;
        children[a].push_back(b);
        children[b].push_back(a);
    }
    ll lim = 1LL<<60; 
    vector<ll> dp(n,lim);
    vector<ll> res(n,-1);
    function<void(ll, ll)> dfs = [&] (ll num, ll par) {
        // cout << "num : " << num << endl;
        auto cur = lower_bound(all(dp), v[num]);
        ll idx = ll(cur-begin(dp)), val;
        val = dp[idx];
        dp[idx] = v[num];
        for (auto x:children[num]) {
            if (x == par) {
                continue;
            }
            dfs(x, num);
        }
        auto lis = lower_bound(all(dp), lim);
        res[num] = ll(lis - begin(dp));
        dp[idx] = val;
    };
    dfs(0, 0);
    rep(i,n) {
        cout << res[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 38780
#include<cstdio>
using namespace std;
int main(){
    while(1){
        int n;
        scanf("%d",&n);
        if(n == 0) break;
        int a[30] = {0};
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        int now = 32;
        for(int i = 0; now != 0; i++){
            if(i % 2 == 0) now -= (now-1)%5;
            else now -= a[(i/2)%n];
            now = (now < 0) ? 0:now;
            printf("%d\n",now);
        }
    }

    return 0;
}

Measured memory_bytes: 1028
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007; // 998244353;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const ld PI = acos((ld)-1);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
  return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
  os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  string s;cin>>s;
  ll tmp=0;
  rep(i,0,siz(s)){
    tmp+=s[i]-'0';
    tmp%=9;
  }

  if(tmp==0)cout<<"Yes"<<ENDL;
  else cout<<"No"<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

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

using namespace std;

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

int main() {
  long long a, b;
  cin >> a >> b;
  long long c = gcd(a, b);
  int ans = 1;
  for (long long i = 2; i * i <= c; i++) {
    if (c % i != 0) {
      continue;
    }
    ans++;
    while (c % i == 0) {
      c /= i;
    }
  }
  if (c != 1) {
    ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))
i = j = 0
b = [['.']*(w+1) for i in range(h+1)]

if a[0][0] == '.':
        print("Impossible")
        exit()
else:
        while i < h or j < w:
                b[i][j] = '#'
 
                if a[i][j] == a[i+1][j] == a[i][j+1] == a[i+1][j+1] == '#':
                        print("Impossible")
                        exit()

                if i == h-1 and j == w-1:
                        break
                elif a[i+1][j] == '#':
                        i += 1
                elif a[i][j+1] == '#':
                        j += 1
                else: 
                        print("Impossible")
                        exit()

        for i in range(h):
                for j in range(w):
                        if a[i][j] != b[i][j]:
                                print("Impossible")
                                exit()
        print("Possible")

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

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 10;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<ll> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

struct Item {
    int value;
    ll weight;
};

int main() {

    int n;
    ll w;
    cin >> n >> w;

    vector<Item> items;
    rep(i, n) {
        Item item;
        cin >> item.value >> item.weight;
        int m;
        cin >> m;

        int o = 1;
        while (o <= m) {
            Item item_o;

            int p = m - (o - 1);
            cmin(p, o);
            item_o.weight = item.weight * p;
            item_o.value = item.value * p;
            items.push_back(item_o);
            o *= 2;
        }
    }

    n = items.size();

    vector<vector<int>> dp(n + 1, vector<int>(w + 1, INT_MIN));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= w; j++) {
            if (dp[i][j] == INT_MIN) continue;
            {
                // 入れない
                cmax(dp[i + 1][j], dp[i][j]);
            }
            {
                // 入れる
                int next = j + items[i].weight;
                int now = dp[i][j];
                int next_value = now + items[i].value;
                if (next <= w) {
                    cmax(dp[i + 1][next], next_value);
                }
            }
        }
    }

    int ans = 0;
    for (int v : dp[n]) cmax(ans, v);
    cout << ans << endl;
}




Measured memory_bytes: 57712
#32 C - Otoshidama
N,Y = map(int,input().split())

for i in range(N+1):
    for j in range(N+1-i):
        tot = i*10000 + j*5000 + (N-i-j)*1000
        if tot == Y:
            ans = (i,j,N-i-j)
            break
    else:
        continue
    break
else:
    ans = (-1,-1,-1)
print(*ans)

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

int main() {
   int N,count=0;
   string S;
   cin >> N >> S;

   for(int i=0; i<N-2; i++) {
      string t = S.substr(i, 3);
      if(t == "ABC") count++;
   }
   cout << count << endl;
}

Measured memory_bytes: 3636
using System;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');


            int a = int.Parse(array[0]);

            int p = int.Parse(array[1]);

            int apple;

            apple = a * 3;

            apple += p;

            apple /= 2;

            Console.WriteLine(apple);
        }
    }
}


Measured memory_bytes: 13140
N, K = map(int, input().split())
S = input()

c = []
c_ap = c.append
cnt = 0

result = 0

for i in range(N - 1):
    if S[i] == S[i + 1]:
        result += 1
    if S[i] == "R":
        if S[i + 1] == "L":
            c_ap(cnt + 1)
            cnt = 0
        else:
            cnt += 1
            
            
if len(c) == 0 and "R" in S:
    result += 1
if len(c) >= K:
    result += K * 2
else:
    result = N - 1

print(result)


Measured memory_bytes: 3572
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    char a[600][600];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            scanf(" %c", &a[i][j]);
            a[i+n][j] = a[i][j+n] = a[i+n][j+n] = a[i][j];
        }
    int b[600][600], ans = 0;
    for (int d = -n+1; d < n; d++) { // d = A - B
        int a0 = max(0, d), b0 = max(0, -d), s = 2*n - abs(d);
        b[0][0] = 0;
        for (int i = 0; i < s; i++)
            for (int j = 0; j < s; j++) {
                b[i][j] = (a[i+a0][j+b0] != a[j+a0][i+b0]);
                if (i > 0) b[i][j] += b[i-1][j];
                if (j > 0) b[i][j] += b[i][j-1];
                if (i > 0 && j > 0) b[i][j] -= b[i-1][j-1];
            }
        for (int i = n-1; i < s-1; i++)
            if (b[i][i] - (i >= n ? b[i-n][i] + b[i][i-n] - b[i-n][i-n] : 0) == 0) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 2048
<?php
  
$x = trim(fgets(STDIN));
$a = trim(fgets(STDIN));
[$n, $k] = explode(' ', $x);
$a = explode(' ', $a);

$sum = 0;
$prev = 0;
$result = [];
foreach ($a as $i => $v) {
  $check = $sum;
  $sum += $v;

  if ($i >= $k) {
    $sum -= $a[$i - $k];
    $result[] = $sum > $check ? 'Yes' : 'No';
  }
}

echo implode(PHP_EOL, $result);

Measured memory_bytes: 41992
#include<iostream>
using namespace std;
#include<stdio.h>

int main(){
    int n,x,w;
    char ch;
    int list[4][13]={{}};
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> ch >> x ;
        if (ch =='S') w = 0;
        else if (ch =='H') w = 1;
        else if (ch == 'C') w = 2;
        else if (ch == 'D') w = 3;
        list[w][x-1]=1;
    }
    int k,t,y;
    char dh;
    for ( k = 0; k < 4; k++ ){
        for (t = 0; t < 13; t++){
            if (list[k][t]==0){
                if(k==0) dh='S';
                else if(k==1) dh='H';
                else if(k==2) dh='C';
                else if(k==3) dh='D';
                y=t+1;
                printf("%c %d", dh,y);
                cout << endl;
            }    
        }
    }
    return 0;
}



Measured memory_bytes: 3196
/*
ID: jerrywcy
TASK: AtCoder Beginner Contest 107 Problem B
LINK: https://abc107.contest.atcoder.jp/tasks/abc107_b
LANG: C++
*/
#include <bits/stdc++.h>

using namespace std;

int h,w;
int g[110][110];
bool mh[110],mw[110];

int main()
{
	cin>>h>>w;
	int i,j;
	for (i=1;i<=h;i++){
		string s;
		cin>>s;
		for (j=1;j<=w;j++){
			if (s[j-1]=='.')g[i][j]=0;
			else g[i][j]=1;
		}
	}
	
	for (i=1;i<=h;i++){
		for (j=1;j<=w;j++){
			mh[i]|=g[i][j];
			mw[j]|=g[i][j];
		}
	}
	
	for (i=1;i<=h;i++){
		if (!mh[i])continue;
		for (j=1;j<=w;j++){
			if (!mw[j])continue;
			if (g[i][j])cout<<'#';
			else cout<<'.';
		}
		cout<<endl;
	}

	return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

int main(){

    int a ,b;
    std::scanf("%d %d",&a,&b);

    int val[3];

    val[0] = a + b;
    val[1] = a - b;
    val[2] = a * b;

    int max;

    if(val[0] >= val[1] && val[0] >= val[2]) max = val[0];
    if(val[1] >= val[0] && val[1] >= val[2]) max = val[1];
    if(val[2] >= val[0] && val[2] >= val[1]) max = val[2];

    std::printf("%d",max);

}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007

using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	ll N, H; cin >> N >> H;
	vector<ll> a(N),b(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	ll cnt = 0, dmg = 0;
	for (int i = N - 1; i >= 0&&dmg<H; i--) {
		if (b[i] >= a[N - 1])cnt++, dmg += b[i];
		else break;
	}
	if (dmg < H) cnt += (H - dmg + a[N - 1] - 1) / a[N - 1];
	cout << cnt << endl;
}


Measured memory_bytes: 1792
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<Integer>();
        while(sc.hasNextInt()){
            int a=sc.nextInt();
            if(a==0){
                System.out.println(stack.pop());
            }else{
                stack.push(a);
            }
        }
    }
}

Measured memory_bytes: 25912
while True:
    try:
        x = map(float, raw_input().split(" "))
        a = (x[2]*x[4]-x[1]*x[5])/(x[0]*x[4]-x[1]*x[3])
        b = (-x[3]*x[2]+x[0]*x[5])/(x[0]*x[4]-x[1]*x[3])
        
        if a == -0: a = 0
        if b == -0: b = 0
        
        print "%.3f %.3f" % (a, b)
    
    except EOFError:
        break

Measured memory_bytes: 4260
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = std::max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = std::min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/


signed main() {
	int n; cin >> n;
	int k = n % 100, cnt = 0;
	for (int i = 5; i >= 1; i--) {
		cnt += k / i;
		k -= i * (k / i);
	}
	if (cnt > n / 100)cout << 0 << endl;
	else cout << 1 << endl;
}


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

using namespace std;

typedef long long ll;

typedef struct {
    int from;
    int to;
    ll cost;
} edge;


//負の閉路がない時にはtrueを返し、dにsからの最短距離を格納する
//負の経路が存在する時にはfalseを返す
bool bellman_ford(vector<edge> G, int n, int s, ll *d) {
    ll INF = -100000000000000;
    for (int i = 0; i < n; i++)
        d[i] = INF;
    d[s] = 0;

    for (int i = 0; i < n; i++) {
        bool check = false;
        for (int j = 0; j < G.size(); j++) {
            edge e = G[j];
            int u = e.from, v = e.to;
            ll c = e.cost;

            if (d[u] != INF && d[v] < d[u] + c) {
                d[v] = d[u] + c;
                if (v == n-1)
                    check = true;
            }
        }
        if (i == n - 1 && check)
            return false;
    }
    return true;
}

int main() {
    int n, m;   cin >> n >> m;
    vector<edge> G;

    for (int i = 0; i < m; i++) {
        int a, b;   ll c;
        cin >> a >> b >> c;

        edge es = {a-1, b-1, c};
        G.push_back(es);
    }


    ll *d = new ll[n];
    if (bellman_ford(G, n, 0, d)) {
        cout << d[n-1] << endl;
    }
    else 
        cout << "inf" << endl;

    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;

map <string,LL> mp;
LL n,cnt = 0;
string s;

int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	while(n --){
		cin >> s;
		if(mp.find(s) == mp.end()) cnt ++;
		mp[s] = 1;
	}
	cout << cnt << '\n';
	return 0;
}

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

int main() {
  long long n,d;
  cin >> n >> d;
  int ans=0;
  for(int i=0; i<n;i++){
    long long a,b;
    cin >> a >> b;
    if( (a*a)+(b*b) <= d*d )
      ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int cal(string s){
    if(s=="SUN")
        return 7;
    if(s=="MON")
    return 6;
    if(s=="TUE")
    return 5;
    if(s=="WED")
    return 4;
    if(s=="THU")
    return 3;
    if(s=="FRI")
    return 2;
    if(s=="SAT")
    return 1;
}
int main()
{
    string s;
    cin >>s;
    cout << cal(s) <<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Integer[] a = new Integer[n];
        for(int i = 0; i < n; i++) a[i] = scan.nextInt();
        Arrays.sort(a, Comparator.reverseOrder());
        int alice = 0;
        int bob = 0;
        for(int i = 0; i < n; i++){
            if(i % 2 == 0) alice += a[i];
            else bob += a[i];
        }
        System.out.println(alice - bob);
        scan.close();
    }
}

Measured memory_bytes: 26932
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
#define double long double
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
//typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-15;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int n,k,ind[26][301],dp[301][301][301];
string s;

int dfs(int l,int r,int x){
	if(dp[l][r][x] != -1) return dp[l][r][x];
	if(r == l) return 0;
	if(r - l == 1) return 1;
	if(s[l] == s[r - 1]) dp[l][r][x] = dfs(l + 1,r - 1,x) + 2;
	chmax(dp[l][r][x],max(dfs(l + 1,r,x),max(dfs(l,r - 1,x),(x ? dfs(l + 1,r - 1,x - 1) + 2 : 0))));
	return dp[l][r][x];
}

signed main(){
	cin >> s >> k;
	n = s.length();
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			for(int l = 0;l <= k;l++) dp[i][j][l] = -1;
		}
	}
	for(int i = 0;i < 26;i++) ind[i][0] = -1;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 26;j++){
			if(s[i] - 'a' == j) ind[j][i + 1] = i;
			else ind[j][i + 1] = ind[j][i];
		}
	}
	cout << dfs(0,n,k) << endl;
	return 0;
}

Measured memory_bytes: 213376
from fractions import gcd
import math

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n =int(input())
    a = map(float, input().split())
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
main()


Measured memory_bytes: 5588
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	int N, K;
	cin >> N >> K;
	vl V(N);
	ll ans = -pow(10, 18);
	rep(i, N)
		cin >> V[i];
	rep(i, N + 1) {
		rep(j, N + 1) {
			if (i + j > N)
				continue;
			if (i + j > K)
				continue;
			vl Vget;
			int VgetN = 0;
			rep(p, N) {
				if (p < i || (N -  j) <= p) {
					Vget.push_back(V[p]);
					VgetN++;
				}
			}
			sort(Vget.begin(), Vget.end(), less <ll>());
			int k = 0;
			while (1) {
				if (i + j + k >= K)
					break;
				if (k >= VgetN)
					break;
				if (Vget[k] > 0)
					break;
				k++;
			}
			ll anstmp = 0;
			rep(p, VgetN) {
				if (p >= k)
					anstmp += Vget[p];
			}
			ans = max(ans, anstmp);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

int main() {
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ll cnt = 0,cnt2 = 0;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i] > a[j]) cnt++;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if(a[i] > a[j]) cnt2++;
        }
    }
    ll ans = 0,tmp;
    ans = (k)*cnt;
    ans = (ans%mod);
    tmp = k*(k-1)/2;
    tmp = (tmp%mod);
    tmp = tmp*cnt2;
    ans += tmp;
    ans = (ans%mod);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[616][616];
int dp[3][616][616];
const int C = 301;
const int C2 = 605;
bool isvalid(int x, int y)
{
	return (x>=0&&x<C2&&y>=0&&y<C2);
}

int sub(int id, int x1, int y1, int x2, int y2)
{
	x2=min(x2,C2-1); y2=min(y2,C2-1); x1=max(x1,0); y1=max(y1,0);
	if(x1>x2||y1>y2) return 0;
	int ans=dp[id][x2][y2];
	if(x1) ans-=dp[id][x1-1][y2];
	if(y1) ans-=dp[id][x2][y1-1];
	if(x1&&y1) ans+=dp[id][x1-1][y1-1];
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		string s; cin>>s;
		for(int j=0;j<m;j++)
		{
			if(s[j]=='#') 
			{
				//cerr<<i+j<<' '<<i-j+C<<'\n';
				a[i+j][i-j+C]=1;
			}
		}
	}
	ll ans=0;
	for(int D=1;D<400;D++)
	{
		for(int i=0;i<C2;i++)
		{
			for(int j=0;j<C2;j++)
			{
				dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=0;
				if(a[i][j])
				{
					dp[0][i][j]=1;
					if(isvalid(i,j-D)&&a[i][j-D]) dp[1][i][j]=1;
					if(isvalid(i-D,j)&&a[i-D][j]) dp[2][i][j]=1;
				}
				/*
				for(int id=0;id<3;id++)
				{
					if(id>0&&dp[id][i][j]>0)
					{
						cerr<<D<<' '<<id<<' '<<i<<' '<<j<<' '<<dp[id][i][j]<<'\n';
					}
				}
				*/
			}
		}
		for(int id=0;id<3;id++)
		{
			for(int i=0;i<C2;i++)
			{
				for(int j=0;j<C2;j++)
				{
					if(i) dp[id][i][j]+=dp[id][i-1][j];
					if(j) dp[id][i][j]+=dp[id][i][j-1];
					if(i&&j) dp[id][i][j]-=dp[id][i-1][j-1];
					//if(D<=3&&i<=3&&j-C<=3&&j-C>=-3) cerr<<D<<' '<<id<<' '<<i<<' '<<j<<' '<<dp[id][i][j]<<'\n';
				}
			}
		}
		for(int i=0;i<C2;i++)
		{
			for(int j=D;j<C2;j++)
			{
				if(a[i][j])
				{
					//ans+=sub(1,i-D,j+1,i-D,j+D-1);
					//ans+=sub(1,i+D,j+1,i+D,j+D-1);
					ans+=sub(2,i+1,j-D,i+D-1,j-D);
					//ans+=sub(2,i+1,j+D,i+D-1,j+D);
					/*
					if(isvalid(i,j+D)&&a[i][j+D])
					{
						ans+=sub(0,i-D,j+1,i-D,j+D);
						ans+=sub(0,i+D,j+1,i+D,j+D);
					}
					*/
					if(isvalid(i,j-D)&&a[i][j-D])
					{
						ans+=sub(0,i-D,j-D,i-D,j-1);
						ans+=sub(0,i+D,j-D,i+D,j-1);
					}
					if(isvalid(i-D,j)&&a[i-D][j])
					{
						ans+=sub(0,i-D,j-D,i-1,j-D);
						//ans+=sub(0,i-D,j+D,i-1,j+D);
					}
					/*
					if(isvalid(i+D,j)&&a[i+D][j])
					{
						ans+=sub(0,i+1,j-D,i+D,j-D);
						ans+=sub(0,i+1,j+D,i+D,j+D);
					}
					*/
					/*
					if(isvalid(i,j+D)&&isvalid(i-D,j)&&a[i][j+D]&&a[i-D][j])
					{
						ans++;
					}
					*/
					if(isvalid(i,j-D)&&isvalid(i-D,j)&&a[i][j-D]&&a[i-D][j])
					{
						ans++;
					}	
					/*
					if(isvalid(i,j+D)&&isvalid(i+D,j)&&a[i][j+D]&&a[i+D][j])
					{
						ans++;
					}
					if(isvalid(i,j-D)&&isvalid(i+D,j)&&a[i][j-D]&&a[i+D][j])
					{
						ans++;
					}
					*/
				}
			}
		}
	}
	cout<<ans<<'\n';
	//cout<<ans/3<<'\n';
}


Measured memory_bytes: 6144
#include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <complex>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <numeric>
    #include <utility>
    #include <iostream>
    #include <algorithm>
    #include <functional>
     
    using namespace std;
     
    #define INF (1 << 30)
    #define INFL (1LL << 62)
    #define MOD7 1000000007
    #define MOD9 1000000009
    #define EPS 1e-10
     
    #define ll long long
    #define ull unsigned long long
    #define pii pair<int, int>
    #define pll pair<ll, ll>
    #define pul pair<ull, ull>
    #define all(a) (a).begin(), (a).end()
    #define mp make_pair
    #define pb push_back
    #define FOR(i,a,b) for (int i=(a);i<(b);++i)
    #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
    #define REP(i,n) for (int i=0;i<(n);++i)
    #define RREP(i,n) for (int i=(n)-1;i>=0;--i)
     
    void YES() { cout << "YES" << endl; }
    void NO() { cout << "NO" << endl; }
    void Yes() { cout << "Yes" << endl; }
    void No() { cout << "No" << endl; }
    void yes() { cout << "yes" << endl; }
    void no() { cout << "no" << endl; }
    void Taka() { cout << "Takahashi" << endl; }
    void Aoki() { cout << "Aoki" << endl; }
    void digit(int d) { cout << fixed << setprecision(d); }
    void IOup() { cin.tie(0); ios::sync_with_stdio(false); }
     
    int main() {
    	string s;
    	cin >> s;
    	int ans = 0;
    	for (int i = 0; i < 3; ++i) {
    		if (s[i] == '1')
    			ans++;
    	}
    	cout << ans << 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;

void solve(int N) {
  int i = 1;
  for (; i <= N; i*= 2) {}
  cout << i / 2 << endl;
}

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

  int N;
  cin >> N;
  solve(N);
  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)


s = sum(A)
nord = [0]*(10**5 +1)

for a in A:
    nord[a] += 1

for b,c in zip(B,C):
    s +=  (c-b)*nord[b]
    nord[c] += nord[b]
    nord[b] = 0
    print(s)


Measured memory_bytes: 22052
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
ll ksm(ll a,ll b){
    ll res=1,t=a;
    while(b){
        if(b&1)res=(res*t)%mod;
        t=(t*t)%mod;
        b>>=1;
    }
    return res;
}
int n;
int arr[maxn],jl[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]),jl[arr[i]]++;
    if(n%2==0){
        int flag=0;
        for(int i=1;i<=n&&!flag;i+=2){
            if(jl[i]!=2)flag=1;
        }
        if(flag){puts("0");return 0;}
    }
    else{
        int flag=0;
        if(jl[0]!=1)flag=1;
        for(int i=2;i<=n;i+=2){
            if(jl[i]!=2)flag=1;
        }
        if(flag){puts("0");return 0;}
    }
    printf("%lld\n",ksm(2,n/2));
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<cctype>
using namespace std;

#define REP(i,a,n) for(int i = a ; i < n ;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

class State{
public:
  int x,y,d,memory;

  State(int _x,int _y,int _d,int _memory){
    x = _x;
    y = _y;
    d = _d;
    memory = _memory;
  }
};

int h,w;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
char t[22][22];
bool closed[22][22][4][16];

void solve(){
  queue<State> open;
  memset(closed,false,sizeof(closed));
  open.push(State(0,0,1,0));

  while(!open.empty()){
    State st = open.front(); open.pop();
    if(closed[st.y][st.x][st.d][st.memory]) continue;
    closed[st.y][st.x][st.d][st.memory] = true;

    if(t[st.y][st.x] == '@'){
      cout<<"YES\n";
      return;
    }

    bool flg = false;

    switch(t[st.y][st.x]){
    case '<': st.d = 3; break;
    case '>': st.d = 1; break;
    case '^': st.d = 0; break;
    case 'v': st.d = 2; break;
    case '_': st.d = (st.memory==0 ? 1 : 3); break;
    case '|': st.d = (st.memory==0 ? 2 : 0); break;
    case '?': flg = true; break;
    case '+': st.memory = (st.memory+1)%16; break;
    case '-': st.memory = (st.memory+15)%16; break;
    }

    if(isdigit(t[st.y][st.x])){
      st.memory = t[st.y][st.x] - '0';
    }

    if(flg){
      rep(i,4){
        int nx = (st.x + dx[i] + w) % w;
        int ny = (st.y + dy[i] + h) % h;
        open.push(State(nx,ny,i,st.memory));
      }
    }
    else{
      int nx = (st.x + dx[st.d] + w) % w;
      int ny = (st.y + dy[st.d] + h) % h;
      open.push(State(nx,ny,st.d,st.memory));
    }
  }

  cout<<"NO\n";
}

int main(){
  while(cin>>h>>w){
    rep(i,h){
      cin>>t[i];
    }
    solve();
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
int main()
{
  int a, b ;
  char op ;

  while(op != '?'){
    scanf("%d %c %d",&a,&op,&b);
    if(op == '+'){
      printf("%d\n", a+b);
    }
    if(op == '-'){
      printf("%d\n", a-b);
    }
    if(op == '*'){
      printf("%d\n", a*b);
    }
    if(op == '/'){
      printf("%d\n", a/b);
    }
  }

  return 0;
}


Measured memory_bytes: 2032
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n;
  cin>>n;
  vector<pair<int,int>> vec;
  int a;
  REP(i,n){
    cin>>a;
    vec.push_back(make_pair(a,i));
  }
  sort(ALL(vec));
  REP(i,n){
    int student = vec[i].second + 1;
    cout<<student<<' ';
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 1780
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                long tmp1 = i * j;
                if(tmp1 >= n) {
                    break;
                }else if(tmp1 < n) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35768
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;

#define ll long long
#define forn(i,n)for(i=0;i<n;i++)
#define forc(i,c,n)for(i=c;i<=n;i++)
typedef list<ll> LST;
typedef vector<ll> VEC;
typedef map<ll, ll> MAP;

int main() {
	ifstream fin("Text.txt");
	ios_base::sync_with_stdio(false); cin.tie(0);

	ll i, j, q;
	ll n, m, p, k, t;
	ll a, b, c, d;
	ll x, y, z, l, r;
	ll one = 1, zero = 0, ans = 0;
	ll mod = 1000000007;
	string st1, st2, st3;
	char ch1, ch2, ch3;

	VEC primes(100007, 1);
	forc(i,2,1000) {
		if (primes[i]) {
			for(j= i + i; j<=100000;j+=i)
				primes[j] = 0;
		}

	}
	VEC cnt(1000007);
	primes[1] = 0;
	forc(i, 1, 100000) {
		if (i & 1 && primes[i] && primes[(i + 1) / 2])
			cnt[i]++;
		cnt[i] += cnt[i - 1];
	}
	cin >> q;
	forn(i, q) {
		cin >> l >> r;
		cout << cnt[r] - cnt[l - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 9216
A = ["* = ****",
     "* =* ***",
     "* =** **",
     "* =*** *",
     "* =**** ",
     " *= ****",
     " *=* ***",
     " *=** **",
     " *=*** *",
     " *=**** "]

n = map(int,list(raw_input()))
while True:
    if len(n) < 5:
        n = [0]*(5-len(n)) + n
    print "\n".join("".join(s) for s in zip(*[A[i] for i in n]))
    try:
        n=map(int,list(raw_input()))
    except EOFError:
        break
    print

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

//flag を用いたバブルソート

int bubbleSort(int A[],int N){
  int sw = 0;
  bool flag = 1;
  for (int i = 0; flag; i++){
    flag = 0;
    for( int j = N - 1; j >= i + 1; j--){
      if( A[j] < A[j - 1]){
	//隣接要素を交換する。
	swap(A[j],A[j - 1]);
	flag = 1;
	sw++;
      }
    }
  }
  return sw;
}

int main(){
  int A[100],N,sw;
  cin >> N;
  for(int i =0;i < N; i++)cin >> A[i];

  sw = bubbleSort(A,N);

  for(int i =0; i < N; i++){
    if(i) cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << sw << endl;

  return 0;

}




Measured memory_bytes: 3096