akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static final Scanner sc  = new Scanner(System.in);
    static final int MOD = (int) 1E9 + 7;
    static final int INF = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        int N = nint();
        int M = nint();
        
        long sum = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < N; i++) {
            int a = nint();
            q.add(a);
            sum += a;
        }
        
        for (int i = 0; i < M; i++) {
            int p = q.poll();
            sum -= (p - p/2);
            q.add(p/2);
        }
        System.out.println(sum);
    }
    
    
    private static int nint() {
        return sc.nextInt();
    }

    private static int[] nints(int n) {
        return nints(n, 0, 0);
    }

    private static int[] nints(int n, int padL, int padR) {
        int[] a = new int[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nint();
        return a;
    }

    private static long nlong() {
        return sc.nextLong();
    }

    private static long[] nlongs(int n) {
        return nlongs(n, 0, 0);
    }

    private static long[] nlongs(int n, int padL, int padR) {
        long[] a = new long[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nlong();
        return a;
    }

    private static double ndouble() {
        return sc.nextDouble();
    }
    
    private static double[] ndoubles(int n) {
        return ndoubles(n, 0, 0);
    }
    
    private static double[] ndoubles(int n, int padL, int padR) {
        double[] d = new double[n + padL + padR];
        for (int i = 0; i < n; i++) {
            d[padL + i] = ndouble();
        }
        return d;
    }

    private static String nstr() {
        return sc.next();
    }

    private static char[] nchars() {
        return sc.next().toCharArray();
    }

    private static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }
    
    private static char[][] nchars2(int h, int w) {
        return nchars2(h, w, 0, 0);
    }

    private static char[][] nchars2(int h, int w, int padLU, int padRD) {
        char[][] a2 = new char[h + padLU + padRD][w + padLU + padRD];
        for (int i = 0; i < h; i++)
            System.arraycopy(nchars(), 0, a2[padLU + i], padLU, w);
        return a2;
    }
    
    private static long min(long... ls) {
        return Arrays.stream(ls).min().getAsLong();
    }
    
    private static long max(long... ls) {
        return Arrays.stream(ls).max().getAsLong();
    }
    
    private static long abs(long a, long b) {
        return Math.abs(a - b);
    }
}


Measured memory_bytes: 53172
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include <climits>
#include<set>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define M 1000000007
int main() {
    ll n;cin>>n;
    vector<ll> a(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<ll> b(n,0);
     b[n-1]=(a[n-1])%M;
    for(int i=n-2;i>=0;i--)
    {
        b[i]=((b[i+1]%M)+(a[i]%M))%M;
    }
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        ll k=((b[i]%M)-(a[i]%M)+M)%M;
        sum=((sum%M)+((a[i]%M)*(k%M))%M)%M;
   }
   cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 6052
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,make;
    cin>>a>>b>>c>>make;

    int res=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(i*500+j*100+k*50==make)
                    res++;
            }
        }
    }
    cout<<res<<endl;


    return 0;
}


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

using namespace std;

using ll = long long;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

#define input(...) __VA_ARGS__; in(__VA_ARGS__)

template<class T>
void print(vector<T> a) {
  cout << "[ ";
  REP(i, a.size()) cout << a[i] << " ";
  cout << "]" << endl;
}

void print() {
  std::cout << std::endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...);
}

void in() { }

template <class Head, class... Tail>
void in(Head&& head, Tail&&... tail) {
  cin >> head;
  in(std::forward<Tail>(tail)...);
}

ll n;
vector<ll> a;
vector<vector<ll>> table;

#define DP table[left][right]
ll dfs(ll left, ll right) {
  if (DP != -1) return DP;

  if (right - left <= 1) return DP = 0;
  ll maxv = 0;
  if (abs(a[left] - a[right - 1]) < 2) {
    ll value = dfs(left + 1, right - 1) + 2;
    if (value == right - left) maxv = value;
  }
  FOR(i, left + 1, right - 1) {
    maxv = max(maxv, dfs(left, i) + dfs(i, right));
  }

  return DP = maxv;
}

bool solve() {
  cin >> n;
  if (n == 0) return false;
  a = vector<ll>(n);
  REP(i, n) cin >> a[i];
  table = vector<vector<ll>>(n + 1, vector<ll>(n + 1, -1));

  cout << dfs(0, n) << endl;
  return true;
}

int main() {
  while(solve());
}



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

int SumDigit(int i) {
  int res=0;
  int tmp, digit;
  for (int n=4; n>=0; n--) {
    digit=pow(10,n);
    tmp=i/digit;
    i-=tmp*digit;
    res+=tmp;
  }
  return res;
}
int Calc(int i, int a, int b) {
  int x=SumDigit(i);
  if (a <= x && x <=b) return i;
  return 0;
}
int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int ans=0;
  for (int i=1; i<=N; i++) {
    ans+=Calc(i, A, B);
  }
  cout << ans << endl;
}


Measured memory_bytes: 4080
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        String a = sc.nextLine();
        int j = Integer.parseInt(a);
        long b[];
        b= new long[j];
        long sum = 0;
        
        for(int i = 0; i < j; i++){
            b[i] =sc.nextInt();
            sum = sum+b[i];
        }
        
        long max = b[0];
        long min = b[0];
        
        for(int i = 0; i < j; i++){
            if(max<b[i]){
                max = b[i];
            }
            if(min>b[i]){
                min = b[i];
            }
        }
        
        System.out.println(min + " " + max + " " + sum);
        
    }
}



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

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> p(n),c(n);
	rep(i,n) cin>>p[i];
	rep(i,n) cin>>c[i];
	rep(i,n) p[i]--;
	ll ans = -1e18;
	rep(si,n){
		int x = si;
		vector<int> s;
		ll tot = 0;
		while(1){
			x = p[x];
			s.push_back(c[x]);
			tot += c[x];
			if(x == si) break;
		}
		int l = s.size();
		ll t = 0;
		rep(i,l){
			t += s[i];
			if(i+1 > k) break;
			ll now = t;
			if(tot > 0){
				ll e = (k-(i+1))/l;
				now += tot*e;
			}
			ans = max(ans,now);
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3724
#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

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

// int solve(int n, int k) {
//     if (csum[n] < k) {
//         return 0;
//     }

//     if (n == 1 or csum[n] == k) {
//         return 1;
//     }

//     if (dp[n][k] != -1) {
//         return dp[n][k];
//     }

//     int ans = 0;
//     for (int x = 0; x <= min(a[n], k); x++) {
//         ans = (ans + solve(n - 1, k - x)) % MOD;
//     }

//     return dp[n][k] = ans;
// }

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

    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++) {
        vector<int> csum(dp[i - 1]);
        for (int j = 1; j <= k; j++) {
            csum[j] = (csum[j] + csum[j - 1]) % MOD;
        }
        for (int j = 1; j <= k; j++) {
            int l = max(0LL, j - a[i]), r = j;
            dp[i][j] = (csum[r] - (l ? csum[l - 1] : 0)) % MOD;
            dp[i][j] = (dp[i][j] + MOD) % MOD;
        }
    }

    cout << dp[n][k] << "\n";
}


Measured memory_bytes: 80256
import java.util.*;

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

    int n = sc.nextInt();//スイッチ
    int m = sc.nextInt();//電球
    int[] ak = new int[m];//電球に繋がっているスイッチの個数
    int[][] sw = new int[m][n];//電球mに接続しているスイッチの情報
    int[] ju = new int[m]; //電球に繋がっているスイッチ%2が配列内の値の時点灯
    int ans = 0;//条件合致数

    for(int i=0; i<m; i++){
      ak[i] = sc.nextInt();//電球i+1に繋がっているスイッチ個数
      for(int j=0; j<ak[i]; j++){
        sw[i][j] = sc.nextInt(); //繋がるスイッチ番号入力
      }
    }

    for(int k=0; k<m;k++){
      ju[k] = sc.nextInt();//1or0を入力
    }

    for(int i=0; i< (1<<n); i++){//スイッチの全ビット探索
      int[] swon = new int[m];//電球に繋がっているonの数
      for(int j=0; j<n;j++){//jビット左論理シフト

        if((1&i>>j)==1){//スイッチj+1がonかoffか
          for(int k=0; k<m;k++){//k+1=電球番号
            for(int l=0; l<ak[k];l++){
              if(sw[k][l]==j+1){
                swon[k] = swon[k] + 1;
              }
            }
          }

        }

      }
      // for(int p=0; p<m;p++){
      //   System.out.println("*"+swon[p]);
      // }
      //全ての電球が点灯したかの判定
      boolean judge = false;
      int count=0;
      for(int p=0;p<m;p++){
        if(swon[p]%2 == ju[p]){
          count +=1;
        }
      }
      if(count==m){
        ans += 1;
      }


    }

    System.out.println(ans);


  }
}

Measured memory_bytes: 22100
use std::io;

fn read_line()  -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).expect("Couldn't read standard input");
    buf.trim().to_owned()
}

fn main() {
    let input: Vec<i32> = read_line()
        .split_whitespace()
        .map(|n| n.parse().unwrap())
        .collect();

    println!("{}", input.iter().max().unwrap() - input.iter().min().unwrap());
}

Measured memory_bytes: 4352
lis = [int(x) for x in input().split()]
if lis[2]-lis[4] < 0 or lis[2]+lis[4] > lis[0] :
    print("No")
elif lis[3]-lis[4] < 0 or lis[3]+lis[4] > lis[1]:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 5604
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

int money(int x)
{
    if (x == 1)
        return 300000;
    else if (x == 2)
        return 200000;
    else if (x == 3)
        return 100000;
    else
        return 0;
}

int main()
{
    int x, y;
    cin >> x >> y;
    int res = money(x) + money(y);
    if (x == 1 and y == 1)
        res += 400000;
    cout << res << endl;
    return 0;
}

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

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

int main()
{
    int n, ans = 1;
    scanf("%d", &n);

    int tmp0, tmp1 = 1;
    rep(i, n-1){
        tmp0 = tmp1;
        tmp1 = ans;
        ans = tmp0 + tmp1; 
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 2712
#include<iostream>
#include<string>
using namespace std;
int main(){
    string ptr;
    while(cin>>ptr){
        int f=0;
        for(int i=0;i<ptr.length();i++){
            for(int j=i+1;j<ptr.length();j++){
                if(ptr[i]==ptr[j]){
                    f=1;
                    break;
                }
            }
        }
        if(f==1){
            cout<<"no"<<endl;
        }else{
            cout<<"yes"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#define rnt register int
using namespace std;
int d[100001];
int n,x;
int main()
{
	scanf("%d",&n);
	for(rnt i=0;i<100001;i=-~i)
		d[i]=-1;
	for(rnt i=0;i<n;i=-~i)
	{
		scanf("%d",&x);
		for(rnt j=0;;j=-~j)
			if(x>d[j])
			{
				d[j]=x;
				break;
			}
	}
	for(rnt i=0;i<=n;i++)
		if(d[i]==-1)
		{
			printf("%d\n",i);
			return 0; 
		}
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
using namespace std;
const int maxn=100+10;
int n,a[maxn],s1,s2,s,flag;
int main(){
	scanf("%d",&n);
	REP(i,1,n)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	DREP(i,n,1){
		if(flag%2==0)s1+=a[i];
		else s2+=a[i];
		flag++;
	}
	cout<<s1-s2<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

int N, M;

void solve()
{
	if(M == N) cout << "Yes\n";
	else cout << "No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N >> M;
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
using namespace std;
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    queue<int> lane[15];
    int n,m;
    cin>>n>>m;
    int info,nam,minx=0;
    for(int i=0;i<m;i++){
        cin>>info>>nam;
        if(info==1){
            for(int j=0;j<n;j++){
                if(lane[minx].size()>lane[j].size()){
                    minx=j;
                } 
            }
            lane[minx].push(nam);
            minx=0;
        }else{
            cout<<lane[nam-1].front()<<"\n";
            lane[nam-1].pop();
        }
    }
    return(0);
}


Measured memory_bytes: 3236
/* #region template */
#![allow(unused_imports)]
use std::cmp::{max, min};
use std::io::{stdin, stdout, Bytes, Read, Stdin, StdinLock, Stdout, StdoutLock, Write};
use std::iter::{repeat, repeat_with};
use std::mem::swap;
use std::str::FromStr;
#[allow(dead_code)]
struct Io<'a> {
    reader: Bytes<StdinLock<'a>>,
    writer: StdoutLock<'a>,
    in_buf: [u8; BUF_SIZE],
}
#[allow(dead_code)]
impl<'a> Io<'a> {
    fn new(stdin: &'a Stdin, stdout: &'a Stdout) -> Io<'a> {
        Io {
            reader: stdin.lock().bytes(),
            writer: stdout.lock(),
            in_buf: [0; BUF_SIZE],
        }
    }
    fn r<T: FromStr>(&mut self) -> T {
        let mut count = 0;
        loop {
            match self.reader.next() {
                Some(Ok(b' ')) | Some(Ok(b'\n')) => break,
                Some(Ok(c)) => self.in_buf[count] = c,
                _ => panic!(),
            }
            count += 1;
        }

        let s = unsafe { std::str::from_utf8_unchecked(&self.in_buf[0..count]) };
        s.parse().unwrap_or_else(|_| panic!())
    }
    fn ru(&mut self) -> usize {
        self.r()
    }
    fn iter<'b, T>(&'b mut self) -> IoIter<'a, 'b, T> {
        IoIter::new(self)
    }
    fn c<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        self.iter().take(n).collect()
    }
    fn cu(&mut self, n: usize) -> Vec<usize> {
        self.c(n)
    }
    fn w<T: std::fmt::Display>(&mut self, v: T) {
        writeln!(self.writer, "{}", v).unwrap();
    }
    fn wn<T: std::fmt::Display>(&mut self, v: T) {
        write!(self.writer, "{}", v).unwrap();
    }
}
#[allow(dead_code)]
struct IoIter<'a: 'b, 'b, T> {
    io: &'b mut Io<'a>,
    m: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<'a: 'b, 'b, T> IoIter<'a, 'b, T> {
    fn new(io: &'b mut Io<'a>) -> IoIter<'a, 'b, T> {
        IoIter {
            io,
            m: std::marker::PhantomData,
        }
    }
}
impl<'a, 'b, T: FromStr> Iterator for IoIter<'a, 'b, T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        Some(self.io.r())
    }
}
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    let mut io = Io::new(&stdin, &stdout);
    unsafe {
        solve(&mut io);
    }
}
/* #endregion */

const BUF_SIZE: usize = 1024;

unsafe fn solve(io: &mut Io) {
    let n = io.ru();
    let k = io.ru();

    let mut t = vec![false; n];

    for _ in 0..k {
        let d = io.ru();
        for a in io.iter::<usize>().take(d) {
            t[a - 1] = true;
        }
    }

    io.w(t.iter().filter(|i| !*i).count())
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl a[n];
    map<intl,intl> m;
    cin(i,a);
    rep(i,n){
        m[a[i]] = 0;
    }
    rep(i,n){
        m[a[i]]++;
    }
    intl cnt = 0;
    for(auto i: m){
        cnt += (i.first > i.second ? i.second : i.second - i.first);
    }
    cout << cnt << endl;
    return 0;
}

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

struct Edge {int to, id;};

vector<vector<Edge>> g;
vector<int> ans;

void dfs(int v, int c = -1, int p = -1) {
    int k = 1;
    rep(i,g[v].size()) {
        int u = g[v][i].to, ei = g[v][i].id;
        if (u == p) continue;
        if (k == c) k++;
        ans[ei] = k; k++;
        dfs(u,ans[ei],v);
    }
}

int main() {
    int n;
    cin >> n;
    g.resize(n);
    ans.resize(n-1);
    rep(i,n-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back((Edge){b,i});
        g[b].push_back((Edge){a,i});
    }
    dfs(0);
    int mx = 0;
    rep(i,n) mx = max(mx, int(g[i].size()));
    cout << mx << endl;
    rep(i,n-1) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 8320
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

enum FACE { TOP, BOTTOM, FRONT, BACK, LEFT, RIGHT };
int dy[]={0,0,1,-1,0,0};
int dx[]={0,0,0,0,1,-1};

class dice {
	private:
		int num[6];

		void roll(FACE a, FACE b, FACE c, FACE d) {
			int tmp = num[a];
			num[a] = num[b];
			num[b] = num[c];
			num[c] = num[d];
			num[d] = tmp;
		}

	public:
		dice() {
			num[TOP] = 1;
			num[BOTTOM] = 6;
			num[FRONT] = 3;
			num[BACK] = 4;
			num[RIGHT] = 5;
			num[LEFT] = 2;
		}

		void set(int top, int front) {
			if(num[RIGHT] == top || num[LEFT] == top)
				west();

			while(num[TOP] != top)
				north();

			while(num[FRONT] != front)
				right();
		}

		int operator[] (FACE f) const { return num[f]; }

		//?????¬???????????¨???????????¢
		void north() { roll(TOP, BACK, BOTTOM, FRONT); }
		void east() { roll(TOP, LEFT, BOTTOM, RIGHT); }
		void west() { roll(TOP, RIGHT, BOTTOM, LEFT); }
		void south() { roll(TOP, FRONT, BOTTOM, BACK); }
		void right() { roll(BACK, RIGHT, FRONT, LEFT); }
		void left() { roll(BACK, LEFT, FRONT, RIGHT); }
};

/*
int main(){
	dice d;
	d.set(1,3);
	d.north();
	cout << d[TOP] << endl;//?????§??????
}
*/

const int MAX = 200;

pair<int, dice> field[MAX][MAX];

void show(){
	cout << endl;
	for(int i=95;i<105;i++){
		for(int j=95;j<105;j++){
			cout << field[i][j].first;
		}
		cout << endl;

	}
}

void solve(dice d,int x,int y) {
	int number=0;
	vector<pair<int, int>> plan; //?????????????????°?????¨??????
	number=d[RIGHT];
	plan.push_back(make_pair(number, RIGHT));
	number=d[LEFT];
	plan.push_back(make_pair(number, LEFT));
	number=d[FRONT];
	plan.push_back(make_pair(number, FRONT));
	number=d[BACK];
	plan.push_back(make_pair(number, BACK));

	sort(ALL(plan));

	int n = plan.size() - 1;
	bool flag = false;	
	for(int i = n; i >= 0; --i) {
		if(plan[i].first>=4 && field[y+dy[plan[i].second]][x+dx[plan[i].second]].first<field[y][x].first){	
			if(plan[i].second == FRONT){ d.north(); }
			else if(plan[i].second == BACK){ d.south(); } 
			else if(plan[i].second == RIGHT){ d.east();}
			else if(plan[i].second == LEFT){d.west();}
			flag = true;
			y+=dy[plan[i].second];
			x+=dx[plan[i].second];
			break;
		}
	}
	if(!flag){
		field[y][x].first++;
		field[y][x].second=d;
		return;
	}
	solve(d,x,y);
}

int main() {
	int n;
	while(cin >> n, n) {
		fill_n((pair<int, dice>*)field, MAX*MAX, make_pair(0, dice()));
		int t, f;
		rep(i, n) {
			cin >> t >> f;
			dice d;
			d.set(t, f);
			
			solve(d, 100, 100);
		}
		vector<int> ans(7, 0);
		rep(i,MAX){
			rep(j,MAX){
				if(field[i][j].first>0){
					++ans[field[i][j].second[TOP]];
				}
			}
		}
		
		for(int i = 1; i <= 6; ++i)	{
			cout << ans[i];
			if(i<6) cout << " ";
		}cout << endl;
	}
	return 0;
}

Measured memory_bytes: 2288
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b;
    cin>>a>>b;
    cout<<(a+b-1)/b<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000
#define N -1

struct Node{int p,l,r;};
struct Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int u,int d){
  if(u==N)return;
  D[u]=d;
  setDepth(T[u].l, d+1);

  setDepth(T[u].r, d+1);
}

int setHeight(int u){
  int h1 =0,h2=0;
  if(T[u].l!=N)h1=setHeight(T[u].l)+1;
  if(T[u].r!=N)h2=setHeight(T[u].r)+1;
  return H[u] = (h1>h2?h1:h2);
}

int getSibling(int u){
  if(T[u].p==N)return N;
  if(T[T[u].p].l!=u&&T[T[u].p].l!=N)
    return T[T[u].p].l;
  if(T[T[u].p].r!=u&&T[T[u].p].l!=N)
    return T[T[u].p].r;
  return N;
}

void print(int u){
  printf("node %d: parent = %d, sibling = %d, ",u,T[u].p,getSibling(u));
  int deg = 0;
  if(T[u].l!=N)deg++;
  if(T[u].r!=N)deg++;
  printf("degree = %d, depth = %d, height = %d, ",deg,D[u],H[u]);

  if(T[u].p==N){
    printf("root\n");
  }else if(T[u].l==N&&T[u].r==N){
    printf("leaf\n");
  }else {
    printf("internal node\n");
  }
}

int main(){
  int i,v,l,r,root=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)T[i].p=N;
  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    if(l!=N)T[l].p=v;
    if(r!=N)T[r].p=v;
  }

  for(i=0;i<n;i++)if(T[i].p==N)root=i;
 
  setDepth(root,0);
  setHeight(root);

 
  for(i=0;i<n;i++)print(i);
  return 0;
}

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

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

    ll *arr = new ll[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);

    ll ans = 0;

    if (n % 2 == 0)
    {
        int mid = n / 2;
        int idx = mid;
        while (idx < n - 1)
        {
            ans += (2 * arr[idx]);
            idx++;
        }
        ans += arr[idx];
        cout << ans << endl;
    }
    else
    {
        int mid = n / 2;
        ans = arr[mid];
        int idx = mid + 1;
        while (idx < n - 1)
        {
            ans += (2 * arr[idx]);
            idx++;
        }
        ans += arr[idx];
        cout << ans << endl;
    }
}

Measured memory_bytes: 5212
#!/bin/sh

while true;
do
        read line1
        read line2

        if [ -z "$line1" ]; then
                break
        fi

        halfStr=`echo $line2 | awk -v strlen=$line1 'halfN=strlen/2{print substr($0,halfN+1)}'`
        repeatStr=$halfStr$halfStr
        if [ $line2 = $repeatStr ]; then
                echo "Yes"
        else
                echo "No"
        fi

done

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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    sort(d.begin(), d.end());

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int k = lower_bound(d.begin() + j + 1, d.end(), d[i] + d[j]) - d.begin();
            ans += max(k - j - 1, 0);
        }
    }

    cout << ans << endl;

    return 0;
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    bool zeroFlag = false;
    int countMinus = 0;
    REP(i, N) 
    {
        cin >> A[i];
        if (A[i] == 0) zeroFlag = true; 
        if (A[i] < 0) countMinus++;
    }
    ll sumA = 0;
    ll minA = INT32_MAX;
    REP(i, N)
    {
        sumA += abs(A[i]);
        minA = min(minA, abs(A[i]));
    }
    ll ans;
    if (zeroFlag) 
    {
        ans = sumA;
    }
    else 
    {
        if (countMinus % 2 == 0) ans = sumA;
        else ans = sumA - 2 * minA;
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch MaximumVolume | diff MaximumVolume.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address MaximumVolume.cpp && ./a.out

/*
 
 3/22/2020
 
 5:10-
 
 */

int L;

void solve() {
  double good=0,bad=1000;
  REP(_,100) {
    double mid=(good+bad)/2;
    (mid*3<=L?good:bad)=mid;
  }
//  dump(good);
  cout<<pow(good,3)<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>L;
  solve();
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;

int power2(int n){
    int res = 1;
    REP(i, n) res *= 2;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int ans = 1001001001;
    REP(i, power2(n)){
        int val = 1;
        REP(j, n){
            if((i >> j) & 0x1) val *= 2;
            else val += k;
        }
        ans = min(val, ans);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;
const int maxn=2e5+7;
int fa[3][maxn];
int Find(int tp,int x)
{
	return x==fa[tp][x]?x:fa[tp][x]=Find(tp,fa[tp][x]);
}
void Union(int tp,int x,int y)
{
	x=Find(tp,x);y=Find(tp,y);
	fa[tp][x]=y;
}
map<PII,int> cnt;
int main()
{
	int n,k,l;
	cin>>n>>k>>l;
	for(int i=0;i<=n;i++) fa[0][i]=fa[1][i]=i;
	for(int i=0,p,q;i<k;i++)
	{
		cin>>p>>q;
		Union(0,p,q);
	}
	for(int i=0,r,s;i<l;i++)
	{
		cin>>r>>s;
		Union(1,r,s);
	}
	for(int i=1;i<=n;i++)
	{
		int u=Find(0,i),v=Find(1,i);
		cnt[make_pair(u,v)]++;
	}
	for(int i=1;i<=n;i++)
	{
		int u=Find(0,i),v=Find(1,i);
		cout<<cnt[make_pair(u,v)]<<" ";
	}
	cout<<'\n';
}


Measured memory_bytes: 13568
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;

struct UnionFind
{
    vector< int > data;
    
    UnionFind(int sz)
    {
        data.assign(sz, -1);
    }
    
    bool unite(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return(false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return(true);
    }
    
    int find(int k)
    {
        if(data[k] < 0) return(k);
        return(data[k] = find(data[k]));
    }
    
    int size(int k)
    {
        return(-data[find(k)]);
    }
};

struct Bipartite_Graph : UnionFind
{
    vector< int > color;
    
    Bipartite_Graph(int v) : color(v + v, -1), UnionFind(v + v) {}
    
    bool bipartite_graph_coloring()
    {
        for(int i = 0; i < color.size() / 2; i++) {
            int a = find(i);
            int b = find(i + (int) color.size() / 2);
            if(a == b) return (false);
            if(color[a] < 0) color[a] = 0, color[b] = 1;
        }
        return (true);
    }
    
    bool operator[](int k)
    {
        return (bool(color[find(k)]));
    }
};

int main(){
    long N, M;
    cin >> N >> M;
    Bipartite_Graph roads(N);
    for(int i = 0; i < M; i++){
        int A, B;
        cin >> A >> B;
        roads.unite(A - 1, B - 1 + N);
        roads.unite(A - 1 + N, B - 1);
    }
    if(roads.bipartite_graph_coloring()){
        long counter = 0;
        for(int i = 0; i < N; i++){
            counter += roads[i];
        }
        cout << counter * (N - counter) - M << endl;
    }else{
        cout << N * (N - 1) / 2 - M << endl;
    }
}


Measured memory_bytes: 1792
input()
nlist = list(map(int, input().split()))
denied = False
for n in nlist:
  if n % 2 == 1:
    continue
  else:
    if n%5 ==0 or n%3==0:
      continue
    else:
      denied =True
      break
if denied:
  print("DENIED")
else:
  print("APPROVED")
  

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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

void hawawa()
{
  int n;
  cin >> n;
  int ans = 1;
  while (ans <= n) {
    ans *= 2;
  }
  ans /= 2;
  cout << ans << "\n";
}

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


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

int main() {
  int A, B, C, N;
  cin >> A >> B >> C >> N;
  int pat = 0;
  int lima = N/A;
  for (int i = 0; i <= lima; i++) {
    int rest = N-i*A;
    int limb = rest/B;
    for (int j = 0; j <= limb; j++) {
      int r = rest-j*B;
      if (r%C == 0) pat+= 1;
    }
  }
  
  cout << pat << endl;
}

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

struct E{
	int x, y, d;
	bool operator<(const E &oth) const {
		return d > oth.d;
	}
};

int n, m;
map<int, vector<E>> e[200010];
map<int, int> md[200010];
priority_queue<E> pq;

void add(int ax, int ay, int bx, int by, int c){
	e[ax][ay].push_back({bx, by, c});
	e[bx][by].push_back({ax, ay, c});
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0, x, y, c; i < m; i++){
		scanf("%d%d%d", &x, &y, &c);
		add(x, c, y, c, 0);
		add(x, c, x, 0, 1);
		add(y, c, y, 0, 1);
	}
	md[1][0] = 0;
	pq.push({1, 0, 0});
	while(!pq.empty()){
		E c = pq.top(); pq.pop();
		for(auto &i : e[c.x][c.y]){
			if(md[i.x].find(i.y) == md[i.x].end() || md[i.x][i.y] > c.d + i.d){
				md[i.x][i.y] = c.d + i.d;
				pq.push({i.x, i.y, c.d + i.d});
			}
		}
	}
	printf("%d\n", (md[n].find(0) == md[n].end()) ? (-1) : (md[n][0] / 2));
}

Measured memory_bytes: 102452
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const ll MOD = 1e9+7;
const double EPS = 1e-9;


int main(int argc, const char * argv[]) {
  int A, B; cin >> A >> B;
  vector<vector<char>> grid(100, vector<char>(100, 'a'));
  
  int a = 0, b = 0;
  for(int i=0; i<50; i++){
    for(int j=0; j<100; j++){
      if(i==0){
        grid[i][j] = '.';
        grid[i+50][j] = '#';
      } else {
        grid[i][j] = '.';
        grid[i+50][j] = '#';
        if(i%2==0 && j%2==0) {
          if(b < B-1) {
            grid[i][j] = '#';
            b++;
          }if(a < A-1) {
            grid[i+50][j] = '.';
            a++;
          }
        }
      }
    }
  }

  cout << 100 << " " << 100 << endl;
  for(auto gi: grid){
    for(auto c: gi)
      cout << c;
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>

using namespace std;

int main(){
   int x,a,b;
   cin>>x>>a>>b;
   int ans=0;
   ans=x-a-(x-a)/b*b;
   cout<<ans<<endl;
}

Measured memory_bytes: 256
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353


N = int(input())
s = defaultdict(int)

for i in range(N):
    s[input()] += 1

M = int(input())
t = defaultdict(int)
for i in range(M):
    t[input()] += 1

m = 0
for p in list(s.keys()):
    m = max(m, s[p] - t[p])
print(m)


Measured memory_bytes: 72388
s=int(input())

mod = 10**9 + 7
ans = 0

m = 10**5 +1 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

for i in range(s//3):
    ans += comb(s-3*(i+1)+i,i)
    ans %= mod

print(ans)

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

int main(){
  int n;
  cin >> n;
  if ( n % 2 == 0){
    cout << 0.50000 << endl;
  } else {
    cout << (n/2 + 1 )/ (double)n << endl;
  }

  return 0;
}

Measured memory_bytes: 256
while True:
    N, T, L, B = map(int, input().split())
    if N | T | L | B == 0:
        break

    lose = set([int(input()) for i in range(L)])
    back = set([int(input()) for i in range(B)])
    dp = [[0] * (T + 1) for j in range(N + 1)]
    dp[0][0] = 1

    for t in range(T):
        for n in range(N):
            for d in range(1, 7):
                step = 0
                if n + d <= N:
                    step = n + d
                else:
                    step = 2 * N - (n + d)

                if step in lose:
                    if t + 2 <= T:
                        dp[step][t + 2] += dp[n][t] / 6
                elif step in back:
                    dp[0][t + 1] += dp[n][t] / 6
                else:
                    dp[step][t + 1] += dp[n][t] / 6

    print(format(sum(dp[-1]), "0.6f"))


Measured memory_bytes: 5992
#include <stdio.h>

const int MAX_V = 1000000;
int prime[MAX_V+1];

void init(){
    int i, k, v;
    for(i=2; i<MAX_V; i++){
        prime[i] = 1;
    }
    for(i=2; i*i<=MAX_V; i++){
        if(prime[i]){
            for(k=2*i; k<=MAX_V; k+=i){
                prime[k]=0;
            }
        }
    }
}

int isprime(int n){
    return prime[n];
}

int main(){
    init();
    int num;
    while(scanf("%d", &num) != EOF){
        int count=0;
        for(int i=2; i<=num; i++){
            if(isprime(i)==1)
                count++;
        }
    printf("%d\n", count);
    }
    return 0;
}

Measured memory_bytes: 6584
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <random>
using namespace std;

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

template <typename T, int size0>
void fill(T (&a)[size0], T value)
{
	fill_n(a, size0, value);
}
template <typename T, int size0, int size1>
void fill(T (&a)[size0][size1], T value)
{
	fill_n(a[0], size0 * size1, value);
}
template <typename T, int size0, int size1, int size2>
void fill(T (&a)[size0][size1][size2], T value)
{
	fill_n(a[0][0], size0 * size1 * size2, value);
}

const int MAX_N = 100;
const int MAX_W = 1e+9;
const int MAX_V = 1e+3 * MAX_N;
int N;
int W;
int w[MAX_N];
int v[MAX_N];
llong dp[MAX_N+1][MAX_V + 1];

llong solve (int n, int rest_value)
{
	if (n == N) return 0 == rest_value ? 0 : W+1;
	if (dp[n][rest_value] != -1LL) return dp[n][rest_value];

	llong min_weight = solve(n+1, rest_value);
	min_weight = min(min_weight, solve(n+1, rest_value - v[n]) + w[n]);

	return dp[n][rest_value] = min_weight;
}

int main ()
{
	cin >> N;
	cin >> W;
	rep(i, N)
	{
		cin >> w[i];
		cin >> v[i];
	}

	int V = 0;
	rep(i, N)
	{
		V += v[i];
	}

	fill(dp, -1LL);

	for (int rest_value = V; rest_value >= 0; --rest_value)
	{
		if (solve(0, rest_value) <= W)
		{
			cout << rest_value << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll MOD = 1000000007;

int main() {
    int n; cin >> n;
    vector<ll> a(n), b(n), c(n);
    REP(i,n) cin >> a[i];
    REP(i,n) cin >> b[i];
    REP(i,n) cin >> c[i];
    sort(ALL(a)); sort(ALL(b)); sort(ALL(c));
    ll ans = 0;
    REP(i,n) {
        ll ab = lower_bound(ALL(a), b[i]) - a.begin();
        ll bc = c.end() - upper_bound(ALL(c), b[i]);
        ans += ab*bc;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
from itertools import product

a, b, c, d = [int(i) for i in list(input())]
for i, j in zip(product([1, -1], repeat=3), product(["+", "-"], repeat=3)):
    if a + b * i[0] + c * i[1] + d * i[2] == 7:
        print(f"{a}{j[0]}{b}{j[1]}{c}{j[2]}{d}=7")
        break

Measured memory_bytes: 9040
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int dp[1100][1100];

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();

    rep(i,n+1){
        rep(j,m+1){
            if(i == 0){
                dp[i][j] = j;
            }else if(j == 0){
                dp[i][j] = i;
            }else{
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
    }
    /*
    rep(i,n+1){
        rep(j,m+1){
            cout << dp[i][j];
        }
        cout << endl;
    }
    */
    cout << dp[n][m] << endl;
    return 0;
}
 
 



Measured memory_bytes: 7496
S = input() + '#'

pressed = []

prev = S[0]
count = 0
for s in S:
    if s == prev:
        count += 1
    else:
        prev = s
        pressed.append(count)
        count = 1

left_cumsum = []
right_cumsum = []

cumsum = 0
for count in pressed:
    cumsum += count
    left_cumsum.append(cumsum)

cumsum = 0
for count in pressed[::-1]:
    cumsum += count
    right_cumsum.append(cumsum)

length = len(left_cumsum)

if length == 1:
    print(len(S)-1)
    exit()

change_k = [0] * length

for idx in range(1, length):
    k = right_cumsum[-idx-1]
    change_k[idx-1] = k

for idx in range(1, length):
    k = left_cumsum[-idx-1]
    change_k[-idx] = max(change_k[-idx], k)

ans1 = min(change_k[::2])
ans2 = min(change_k[1::2])
print(max(ans1, ans2))

Measured memory_bytes: 8052
#include<bits/stdc++.h>
#define MAXN 1e6
using namespace std;

int main()
{
	//freopen("t.txt","r",stdin);
	int n,Max=0,kq=0;
	cin>>n;
	for (int i=1;i<=n;i++){
		
		int a=i,d=0;
		while (a%2==0){
			d++;
			a/=2;
			//cout<<a<<endl;
		}
		if (d>Max) {
			Max=d;
			kq=i;
		}
		
	}
	if (n==1){
		cout<<1; return 0;
	}
	else cout<<kq;
}

Measured memory_bytes: 256
N = int(input())
A_n = list(map(int, input().split(' ')))
zero = 0 in A_n
if zero:
    total = 0
else:
    total = 1
    for i in A_n:
        total *= i
        if total > 10 ** 18:
            total = -1
            break
print(total)


Measured memory_bytes: 21656
#include<bits/stdc++.h>
using namespace std;
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; }
const long long INF = 1LL<<60;
const int MAX_N = 110;
const int MAX_V = 100100;

int N;

long long W, weight[MAX_N], value[MAX_N];
long long dp[MAX_N][MAX_V];
int main(){
    cin >> N >> W;
    
    for (int i=0; i< N; ++i) cin >> weight[i] >> value[i];
    
    for (int i=0; i< MAX_N; ++i)
        for (int j=0; j< MAX_V; ++j) dp[i][j] = INF;
        
        
    dp[0][0] = 0;
    
    for(int i=0; i< N; ++i){
        for(int j=0; j<= MAX_V; ++j){
            if(j - value[i] >= 0){
                chmin(dp[i+1][j], dp[i][j-value[i]] + weight[i]);
            }
            chmin(dp[i+1][j], dp[i][j]);
        }
    }
    long long res = 0;
    for(int i=0; i< MAX_V; ++i){
        if(dp[N][i] <= W) res = i;
    }
    
    cout << res << endl;
    
    return 0;
}

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

int main()
{  
  int s;
  int p=0;
  cin >> s;
  if(100<=s&&s<1300){
    p+=2;
  }
  if(1<=s%100&&s%100<13){
    p+=1;
  }
  switch(p){
    case 0:
      cout << "NA";
      break;
    case 1:
      cout << "YYMM";
      break;
    case 2:
      cout << "MMYY";
      break;
    case 3:
      cout << "AMBIGUOUS";
      break;
  }
  return 0;
}

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

int n, MAX = 100000;
int a[101000], b[101000], c[101000], dp[101000][3];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i] >> c[i];
	}
	dp[2][0] = a[1];
	dp[2][1] = b[1];
	dp[2][2] = c[1];
	for (int i = 1; i <= n; i++)
	{
		dp[i + 1][0] = max(dp[i][1], dp[i][2]) + a[i];
		dp[i + 1][1] = max(dp[i][0], dp[i][2]) + b[i];
		dp[i + 1][2] = max(dp[i][0], dp[i][1]) + c[i];
	}
	cout << max({dp[n + 1][0], dp[n + 1][1], dp[n + 1][2]}) << endl;
}


Measured memory_bytes: 2560
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int N; cin >> N;
    double T, A; cin >> T >> A;
    vector<double> abss, cp;
    rep(i, 0, N) {
        int h; cin >> h;
        abss.push_back(abs(A - (T - h * 0.006)));
    }

    copy(abss.begin(), abss.end(), back_inserter(cp));
    sort(abss.begin(), abss.end());
    vector<double >::iterator iter = find(cp.begin(), cp.end(), abss[0]);
    size_t index = distance(cp.begin(), iter);
    cout << index+1 << endl;
}

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

int main() {
	int count=0;
	int num=1;
	int N;
	cin>>N;
	
	vector<int> a(N);
	
	for(int i=0;i<N;i++){
		cin>>a.at(i);
	}
	for(int i=0;i<N;i++){
		if(num==a.at(i)){
			num++;
		}
		else{
			count++;
		}
		
	}
	if(num==1){
			printf("-1");
		}
	else{
		printf("%d",count);
	}
	return 0;
}

Measured memory_bytes: 1024