akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    map<int,vector<int>> MAP;
    rep(i,N - 1) {
        int num;
        cin >> num;
        MAP[num].push_back(i+2);
    }
    for (int i = 1; i <= N; i++) {
        cout << MAP[i].size() << endl;
    }
}

Measured memory_bytes: 25372
object Main {
  def is_prime(n: Int): Boolean = {
    if (n == 2)
      return true
    var i = 2
    while (i * i <= n){
      if (n%i == 0){
        return false
      }
      i += 1
    }
    return true
  }
  def main(args:Array[String]) = {
    val primes = for (i <- 2 to 999999 if is_prime(i)) yield i
    val sc = new java.util.Scanner(System.in)
    while (sc.hasNext){
      val n = sc.nextInt
      println(primes.count(i => i <=n))
    }
  }
}

Measured memory_bytes: 63248
#include<bits/stdc++.h>
using namespace  std;
#define ll long long
int main(){
ll a,b,c,d,e=0;
cin>>a>>b;
for(ll i=1;i<=b;i++)
{
cin>>c;
e+=c;
}
if(e<=a)cout<<a-e<<endl;
else cout<<"-1\n";
}

Measured memory_bytes: 3636
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n, m;
        cin >> n >> m;
        if(n == 0)
            return 0;

        string s(n, '#');
        for(int i=0; i<m; ++i){
            char c;
            cin >> c;
            if(c == 'A'){
                *find(s.begin(), s.end(), '#') = 'A';
            }else if(c == 'B'){
                bool ok = false;
                for(int j=n-1; j>=0; --j){
                    if(s[j] != '#')
                        continue;
                    if(j+1 < n && s[j+1] == 'A')
                        continue;
                    if(j-1 >= 0 && s[j-1] == 'A')
                        continue;
                    s[j] = 'B';
                    ok = true;
                    break;
                }
                if(!ok)
                    *find(s.begin(), s.end(), '#') = 'B';
            }else if(c == 'C'){
                if(i == 0){
                    s[n/2] = 'C';
                }else{
                    for(int j=0; j<n; ++j){
                        if(s[j] != '#'){
                            if(j+1 < n && s[j+1] == '#'){
                                s[j+1] = 'C';
                                break;
                            }else if(j-1 >= 0 && s[j-1] == '#'){
                                s[j-1] = 'C';
                                break;
                            }
                        }
                    }
                }
            }else{
                if(i == 0){
                    s[0] = 'D';
                }else{
                    vector<int> dist(n, INT_MAX);
                    for(int j=0; j<n; ++j){
                        if(s[j] == '#')
                            continue;
                        int k = j;
                        do{
                            dist[k] = min(dist[k], j - k);
                        }while(--k >= 0 && s[k] == '#');
                        k = j;
                        do{
                            dist[k] = min(dist[k], k - j);
                        }while(++ k < n && s[k] == '#');
                    }
                    s[max_element(dist.begin(), dist.end()) - dist.begin()] = 'D';
                }
            }
        }
        cout << s << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#pragma once
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
#define endn "\n"
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////

int n,m,a[1100], b[1100];bool c[1100][20]={};
int dp[10000];
signed main(){
  cin>>n>>m;
  rep(i,10000)dp[i] = INF;
  dp[0] = 0;
  rep(i,m){
    cin>>a[i]>>b[i];
    rep(j,b[i]){
      int cc;cin>>cc;cc--;
      c[i][cc] = true;
    }
  }
  rep(bit,1<<n){
    rep(i,m){
      int bb = bit;
      rep(j,n){
        if(c[i][j]){
          bb |= (1<<j);
        }
      }
      chmin(dp[bb], dp[bit] + a[i]);
    }
  }
  cout << (dp[(1<<n)-1] == INF ? -1 : dp[(1<<n)-1]) << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sort(a) sort(all(a))
using P = pair<int, int>;
using ll = long long;
using ld = long double;
typedef vector<int> vi;
int dx[4] = { 0, 1, 0,-1 };
int dy[4] = { 1, 0,-1, 0 };
const ll MOD = 1000000007;

signed main() {
  int a; cin >> a;
  cout << a+pow(a,2)+pow(a,3) << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const long long MOD = 998244353;

bool checkPalindrome(string s, int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++, j--;
    }
    return true;
}

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

    string s;
    cin >> s;
    int n = s.length();
    if (checkPalindrome(s, n) && checkPalindrome(s, (n - 1) / 2)) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string S;
    string F;
    cin >> S;
    cin >> F;
    
    int cont = 0;
    for(int i = 0; i < 3;i++){
        
        if(S[i]==F[i])cont++;
        
    }
    
    cout << cont << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import numpy as np
from decimal import Decimal

N = int(input())
A = [int(10**9*Decimal(input())) for _ in range(N)]

def count(a):
  n = a
  count2 = 0
  count5 = 0
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Measured memory_bytes: 34916
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> v(M - 1 + N);
    FOR(i, M - 1, v.size()) v[i] = 1;
    int ret = 0;
    vector<int> A(Q), B(Q), C(Q), D(Q);
    REP(i, Q) cin >> A[i] >> B[i] >> C[i] >> D[i];
    vector<int> arr(N + 1, 1);

    auto dfs = [&](auto &&f, int d) -> void {
        if (d == N)
        {
            int tmp = 0;
            REP(i, Q) tmp += (arr[B[i]] - arr[A[i]] == C[i]) * D[i];
            ret = max(ret, tmp);
            return;
        }
        for (int nxtv = arr[d]; nxtv <= M; nxtv++)
        {
            arr[d + 1] = nxtv;
            f(f, d + 1);
        }
    };
    dfs(dfs, 0);
    cout << ret << '\n';
}


Measured memory_bytes: 3632
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let ss = sc.chars();
    let mut cnts = vec![false; 10];
    let mut cnts1 = vec![false; 100];
    let mut results = vec![false; 1000];
    for &c in ss.iter() {
        let num = c as usize - 48;
        for (idx, x) in cnts1.iter().enumerate() {
            if *x == true {
                results[idx * 10 + num] = true;
            }
        }
        for (idx, x) in cnts.iter().enumerate() {
            if *x == true {
                cnts1[idx * 10 + num] = true;
            }
        }
        cnts[num] = true;
    }
    let mut result = 0;
    for x in results.iter() {
        if *x == true {
            result += 1;
        }
    }
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}
pub mod utils {
    const DYX: [(isize, isize); 8] = [
        (0, 1),   //right
        (1, 0),   //down
        (0, -1),  //left
        (-1, 0),  //top
        (1, 1),   //down right
        (-1, 1),  //top right
        (1, -1),  //down left
        (-1, -1), //top left
    ];

    pub fn try_adj(y: usize, x: usize, dir: usize, h: usize, w: usize) -> Option<(usize, usize)> {
        let ny = y as isize + DYX[dir].0;
        let nx = x as isize + DYX[dir].1;
        if ny >= 0 && nx >= 0 {
            let ny = ny as usize;
            let nx = nx as usize;
            if ny < h && nx < w {
                Some((ny, nx))
            } else {
                None
            }
        } else {
            None
        }
    }
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n;
string s[101010];
void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s[i];
		sort(s[i].begin(),s[i].end());
	}
	sort(s,s+n);
	i64 ans = 0;
	for(int i = 0; i < n; i++){
		i64 cnt = 0;
		for(int j = i+1; j < n; j++){
			if(s[i] != s[j]){
				ans += cnt*(cnt+1)/2;
				i = j-1;
				break;
			}
			cnt++;
			if(j == n-1){
				ans += cnt*(cnt+1)/2;
				i = j;
				break;
			}
		}
	}
	cout << ans << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD (1e9+7)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    int n,m;
    cin >> n >> m;
    vector<bool> a(n+1,true);
    vector<ll> dp(n+1,0);
    REP(i, m){
        int b;
        cin >> b;
        a[b]=false;
    }

    dp[0]=1;
    Rep(i, 0, n){
        if(i + 1 <= n)
            if(a[i+1]){
                dp[i+1] += dp[i];
                dp[i+1] %= 1'000'000'007;
            }

        if(i + 2 <= n)
            if(a[i+2]){
                dp[i+2] += dp[i];
                dp[i+2] %= 1'000'000'007;
            }
    }
    // DEBUG_VEC(dp);
    pr(dp[n]);
}

Measured memory_bytes: 1024
k,n = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i)
a_arr << k + a_arr[0]

max = 0
a_arr.each_cons(2) do |a1, a2|
  diff = a2 - a1
  max = diff if diff > max
end

puts k - max

Measured memory_bytes: 28852
#include<iostream>
#include <algorithm>
#include<string>
using namespace std;
int main()
{
	//int h, w,   q, D, ax[90001], ay[90001], l[100000], r[100000];
	int  a,b, c, d, e,ans=0;
	//string a, b, c;

	cin >> a>>b;
	for ( c = a; c < b+1; c++)
	{
		d = c;
		/*cout << "aaaaaaaaaaaaa" << endl;
		cout << d << endl;
		cout << d / 10000 << endl;
		cout << d % 10 << endl;
		cout << (d / 1000) - (d / 10000) * 10 << endl;
		cout << (d % 100) - (d % 10) << endl;*/
		if (d/10000==d%10&& (d / 1000)-(d/10000)*10==((d%100)-(d%10))/10)
		{
			

			ans++;
		}
	}
	//	cout << a[0]<<b[1]<<c[2] << endl;
		cout << ans << endl;
		
	

	



	// 出力
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        int x = 500;
        int y = 5;
        long happy = (a/x)*1000+(a%x/y)*y;
        System.out.println(happy);
    }
}

Measured memory_bytes: 21972
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    sort(l.begin(), l.end());
    reverse(l.begin(), l.end());
    int ans = 0;
    rep(i, k) {
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! flush {
    () => {
        std::io::stdout().flush().unwrap();
    };
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let mut n: u64 = sc.cin();
    let a: u64 = sc.cin();
    let b: u64 = sc.cin();
    let k = n / (a + b);
    n %= a + b;
    let mut aa = a * k;
    let mut ab = b * k;
    aa += min!(n, a);
    if n > a {
        ab += n - a
    }
    put!(aa);
}

use std::collections::VecDeque;
use std::io::{self, Write};
use std::str::FromStr;

struct Scanner {
    stdin: io::Stdin,
    buffer: VecDeque<String>,
}
impl Scanner {
    fn new() -> Self {
        Scanner {
            stdin: io::stdin(),
            buffer: VecDeque::new(),
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.is_empty() {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.cin::<String>().chars().collect()
    }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.cin()).collect()
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    ll n, x; cin >> n >> x;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans = 0;
    if (a[0]>x) {
        ans += a[0]-x;
        a[0] -= a[0]-x;
    }
    repf(i,1,n) {
        ll tmp = max(0ll, a[i]+a[i-1]-x);
        ans += tmp;
        a[i] -= tmp;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    // get a integer
    char c;
    cin >> c ;

    char vowels[] = {'a', 'i', 'u', 'e', 'o'};

    for (auto&& i = 0; i < 5; ++i ) {
        if( vowels[i] == c )
        {
            cout << "vowel" << endl; 
            return 0;
        }
    }

    cout << "consonant" << endl;
}



Measured memory_bytes: 256
N, X = map(int, input().split())
L = list(map(int, input().split()))
d = 0

# ans = 1

# for i in range(N):
#     d += L[i]
#     if d <= X:
#         ans += 1

e = 1


for i in L:
    if d + i <= X:
        d += i
        e += 1
    else:
        break

# for i in l:
print(e)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1001001001;

int H, W;
int dp[1410][1410];

int main(){
  cin >> H >> W;

  memset(dp, INF, sizeof(dp));
  rep(h, H+1) dp[h][0] = 0;
  rep(w, W+1) dp[0][w] = 0;
  REP(h, 1, H){
    REP(w, 1, W){
      char c; cin >> c;
      if(c == '1') dp[h][w] = 0;
    }
  }

  int ml = 0;
  REP(h, 1, H){
    REP(w, 1, W){
      if(dp[h][w] == 0) continue;
      chmin(dp[h][w], dp[h-1][w] + 1);
      chmin(dp[h][w], dp[h][w-1] + 1);
      chmin(dp[h][w], dp[h-1][w-1] + 1);
      chmax(ml, dp[h][w]);
    }
  }

  cout << ml * ml << endl;

  return 0;

}





Measured memory_bytes: 10876
#include<stdio.h>
int main(void){
 
  int S,h,m,s;
 
  scanf("%d",&S);
 
  h = S / 3600;
  m = S / 60 % 60;
  s = S % 60;
 
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

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


Measured memory_bytes: 3916
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        int n = sc.nextInt();
        int W = sc.nextInt();

        int[][] mono = new int[n][2];
        for (int i = 0; i < n; i++) {
            mono[i][0] = sc.nextInt();
            mono[i][1] = sc.nextInt();
        }

        long[][] dp = new long[n][W + 1];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < W + 1; k++) {
                int weight = mono[i][0];
                if (i == 0) {
                    if (k < weight) {
                        dp[i][k] = 0;
                    } else {
                        dp[i][k] = mono[i][1];
                    }
                } else {
                    if (k < weight) {
                        dp[i][k] = dp[i - 1][k];
                    } else {
                        dp[i][k] = Math.max(dp[i - 1][k], dp[i - 1][k - weight] + mono[i][1]);
                    }
                }
            }
        }

        out.println(dp[n - 1][W]);
        out.flush();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

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

int main() {
int64_t X;
  cin >> X;
  int64_t t = 100;
  int count = 0;
  for (int i = 0; i < 3770; i++){
  	t *= 1.01;
    if(t >= X){
    	cout << i+1 << endl;
      break;
    }
  }
  
}

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

typedef pair<int,int> P;

int n, used[105];
vector<P> A, B;

int main(){

  cin>>n;

  for(int i=0;i<n;i++){
    int a, b;
    cin>>a>>b;
    A.push_back(P(a, b));
  }

  for(int i=0;i<n;i++){
    int a, b;
    cin>>a>>b;
    B.push_back(P(a, b));
  }

  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  int ans=0;
  
  for(int i=0;i<B.size();i++){
    
    int ymax = -1, idx = -1;
    
    for(int j=0;j<A.size();j++){

      if(used[j]) continue;
      
      if(A[j].first>=B[i].first) continue;
      
      if(B[i].second>A[j].second && A[j].second>ymax){
	ymax = A[j].second;
	idx = j;
      }
    }
    
    if(idx!=-1){
      ans++;
      used[idx]=1;
    }

  }

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


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

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int dp[100001] = {};
  dp[0] = 0;
  for(int i = 1; i <= 100000; i++) {
    int res = dp[i - 1] + 1;
    int t = 6;
    while(1) {
      if(i < t) break;
      res = min(res, dp[i - t] + 1);
      t *= 6;
    }
    t = 9;
    while(1) {
      if(i < t) break;
      res = min(res, dp[i - t] + 1);
      t *= 9;
    }
    dp[i] = res;
  }
  int n; cin >> n;
  cout << dp[n] << endl;
}



Measured memory_bytes: 640
<?php
fscanf(STDIN, "%d %d", $n, $k);
$aArray = explode(" ", fgets(STDIN));
$ret = 0;
$ans = 0;
for($i = 40; $i >= 0; $i--){
    $mask = 1 << $i;
    $cnt = 0;
    foreach($aArray as $a){
        if($a & $mask)++$cnt;
    }
    if($cnt >= $n - $cnt){
        $ans+=$mask*$cnt;
    }else{
        if($mask+$ret<=$k){
            $ans+=($n-$cnt)*$mask;
            $ret+=$mask;
        }else{
            $ans+=$mask*$cnt;
        }
    }
}
printf("%d", $ans);

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

struct UnionFind{
    vector<int32> par;
    UnionFind(int32 n){
        REP(i,n)par.pb(i);
    }
    int32 root(int32 x){
        if(par[x] == x)return x;
        return par[x] = root(par[x]);
    }
    void unite(int32 a, int32 b){
        a = root(a);
        b = root(b);
        if(a == b)return;
        par[a] = b;
    }
    bool same(int32 a, int32 b){
        return root(a) == root(b);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    vector<tuple<int32,int32,int32>> xy(n);
    REP(i,n){
        int32 x,y;
        cin >> x >> y;
        xy[i] = make_tuple(x,y,i);
    }
    sort(ALL(xy));
    vector<tuple<int32,int32,int32>> pq;   //dist, v, w
    REP(i,n-1){
        int32 vx,vy,v,wx,wy,w;
        tie(vx, vy, v) = xy[i];
        tie(wx, wy, w) = xy[i+1];
        pq.pb(make_tuple(min(abs(vx-wx), abs(vy-wy)), v, w));
    }
    REP(i,n)xy[i] = make_tuple(get<1>(xy[i]), get<0>(xy[i]), get<2>(xy[i]));
    sort(ALL(xy));
    REP(i,n-1){
        int32 vx,vy,v,wx,wy,w;
        tie(vy, vx, v) = xy[i];
        tie(wy, wx, w) = xy[i+1];
        pq.pb(make_tuple(min(abs(vx-wx), abs(vy-wy)), v, w));
    }
    UnionFind uf(n);
    int64 cost = 0;
    int32 edgeCnt = 0;
    sort(ALL(pq));
    REP(i,pq.size()){
        int32 dist, v, w;
        tie(dist, v, w) = pq[i];
        if(!uf.same(v,w)){
            cost += dist;
            uf.unite(v,w);
            // cout << v << " " << w << endl;
            edgeCnt++;
        }
        if(edgeCnt >= n-1)break;
    }
    ANS(cost);
    return 0;
}

Measured memory_bytes: 10736
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() throws IOException{

		int n = Integer.parseInt(br.readLine());

		outer:
		while (n-- > 0) {
			String str = br.readLine();
			String[] s = str.split(" ");

			for (int a=1; a<26; a++) {
				if (gcd(a,26) != 1) continue;

				for (int b=0; b<26; b++) {
					for (int i=0; i<s.length; i++) {
						if (s[i].length() != 4) continue;
						if (isThat(s[i],a,b) || isThis(s[i],a,b)) {
							print(str,a,b);
							continue outer;
						}
					}
				}
			}

		}
	}

	static int gcd(int a, int b) {
		return a == 0 ? b : gcd(b%a, a);
	}

	static boolean isThat(String s, int a, int b) {
		if ((a*('t'-'a')+b)%26 + 'a' != s.charAt(0)) return false;
		if ((a*('h'-'a')+b)%26 + 'a' != s.charAt(1)) return false;
		if ((a*('a'-'a')+b)%26 + 'a' != s.charAt(2)) return false;
		if ((a*('t'-'a')+b)%26 + 'a' != s.charAt(3)) return false;
		return true;
	}

	static boolean isThis(String s, int a, int b) {
		if ((a*('t'-'a')+b)%26 + 'a' != s.charAt(0)) return false;
		if ((a*('h'-'a')+b)%26 + 'a' != s.charAt(1)) return false;
		if ((a*('i'-'a')+b)%26 + 'a' != s.charAt(2)) return false;
		if ((a*('s'-'a')+b)%26 + 'a' != s.charAt(3)) return false;
		return true;
	}

	static void print(String s, int a, int b) {
		for (int i=0; i<s.length(); i++) {
			if (s.charAt(i) == ' ') {
				out.print(' ');
			} else {
				int c = (s.charAt(i) - 'a' - b + 26)%26;
				while (c%a != 0) c += 26;
				out.print((char)(c/a + 'a'));
			}
		}
		out.println();
	}

	public static void main(String[] args) throws Exception {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		br.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 25092
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int d[50][50];
void floryd()
{
    for(int k=0;k<=n;k++)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
               d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int w,ma;
int main()
{
    while(scanf("%d",&w)&&w)
    {
        for(int i=0;i<=46;i++)
        {
            for(int j=0;j<=46;j++)
            {
                d[i][j]=0x3f3f3f3f;
            }
        }
        ma=-1;
        int a,b,c;
        for(int i=0;i<w;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            ma=max(max(a,b),ma);
            d[a][b]=d[b][a]=c;
        }
        n=ma;
        int q,s;
        floryd();
        int mi=0x3f3f3f3f;
        for(int i=0;i<=ma;i++)
        {
            s=0;
            for(int j=0;j<=ma;j++)
            {
                if(i!=j)
                {
                    s=s+d[i][j];
                }
            }
            if(s<mi)
            {
                mi=s;
                q=i;
            }
        }
        printf("%d %d\n",q,mi);
    }

    return 0;
}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	bool n,a,sum;
  string s;
  	cin>>s;
  int b,c;
  	a=0;b=0;c=0;
  if(s.at(0)=='A')
    a=1;
  
  for(int i=2;i<s.size()-1;i++){
  	if(s.at(i)=='C'){
    b++;
    }
  }
  
  for(int i=0;i<s.size();i++){
  	if(s.at(i)>'z'||s.at(i)<'a')
      c++;
  }
  
    if(a==1&&b==1&&c==2)
      cout<<"AC"<<endl;
  else
    cout<<"WA"<<endl;
    
    
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
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 dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};        
int main(){
  ll n,m;
  cin>>n>>m;
  vvll ta(n,vll(n,INF));
  vll a(m),b(m),c(m);
  rep(i,m){
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
    ta[a[i]][b[i]]=c[i];
    ta[b[i]][a[i]]=c[i];
  }
  rep(i,n) ta[i][i]=0;
  rep(k,n)rep(i,n)rep(j,n){
    ta[i][j]=min(ta[i][j],ta[i][k]+ta[k][j]);
  }
  vll ch(m,false);
  rep(i,n){
    rep(j,n){
      rep(z,m){
        if(ta[i][j]==ta[i][a[z]]+c[z]+ta[b[z]][j]){
          ch[z]=true;
        }
      }
    }
  }
  ll ans=0;
  rep(i,m){
    if(!ch[i])ans++;
  }
  COUT(ans);
}

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

int main() {
	int N, K;
	cin >> N >> K;
	vector<ll> h(N);
	for (int i = 0; i < N; ++i) { cin >> h[i]; }
	sort(h.begin(), h.end());

	ll res = 1e18;
	for (int i = 0; i < N; ++i) {
		if (i + K - 1 >= N) { break; }
		ll tmp = h[i + K - 1] - h[i];
		res = min(res, tmp);
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long


void solve(long long N, long long A, long long B, std::vector<long long> X){
    int res = 0;
    for (int i = 0; i < N - 1; ++i) {
        if (A * (X[i + 1] - X[i]) < B) {
            res += A * (X[i + 1] - X[i]);
        } else {
            res += B;
        }
    }
    cout << res << endl;
}

signed main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    std::vector<long long> X(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&X[i]);
    }
    solve(N, A, B, std::move(X));
    return 0;
}

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

int main() {
	ll k, a, b;
	cin >> k >> a >> b;
	if (k == 1) cout << 2 << endl;
	else if (k <= a) cout << k+1 << endl;
	else {
		if (a + 3 <= b) {
			k -= a - 1;
			if (k % 2 == 0)cout << a + (k / 2) * (b - a) << endl;
			else cout << a + (k / 2) * (b - a) + 1 << endl;
		}
		else cout << k+1 << endl;
	}
}

Measured memory_bytes: 256
#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 RGBTriplets | diff RGBTriplets.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address RGBTriplets.cpp && ./a.out

/*
 
 4/12/2020
 
 5:10-5:25 AC
 
 https://img.atcoder.jp/abc162/editorial.pdf
 
 */

//const int MAX_N=4000+1;
int N;
string S;

vector<char> C={'R','G','B'};
void solve() {
  map<char,LL> cnt;
  LL res=0;
  REP(i,N) {
    FOR(j,i+1,N) if(S[j]!=S[i]) {
      int k=i-(j-i);
      if(k>=0)cnt[S[k]]--;
      FORR(c,C) if(c!=S[i]&&c!=S[j]) {
        res+=cnt[c];
//        dump(i,j,S[i],S[j],c,cnt[c]);
      }
      if(k>=0)cnt[S[k]]++;
    }
    cnt[S[i]]++;
  }
  cout<<res<<endl;
}

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

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...) 0
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> a(h);
    rep(i, 0, h) cin >> a[i];
    vector<vector<char>> red(h, vector<char>(w, '.'));
    vector<vector<char>> blue(h, vector<char>(w, '.'));
    rep(i, 0, h) rep(j, 0, w) {
        if (a[i][j] == '#') {
            red[i][j] = blue[i][j] = '#';
        }
        if (j % 2 == 1) red[i][j] = '#';
        if (j % 2 == 0) blue[i][j] = '#';
    }
    rep(j, 0, w) {
        red[0][j] = blue[h - 1][j] = '#';
        blue[0][j] = red[h - 1][j] = '.';
    }
    rep(i, 0, h) {
        rep(j, 0, w) cout << red[i][j];
        cout << endl;
    }
    cout << endl;
    rep(i, 0, h) {
        rep(j, 0, w) cout << blue[i][j];
        cout << endl;
    }
    return 0;
}


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

int C[10][10];

int main(void) {
	int H, W;
	cin >> H >> W;

	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++) {
			cin >> C[i][j];
		}
	}

	int cnt[10] = {0};
	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			int A;
			cin >> A;
			if (A != -1) cnt[A]++;
		}
	}

	int minpath[10];
	bool calc[10];
	for (int i = 0; i <= 9; i++) {
		minpath[i] = 100000;
		calc[i] = false;
	}

	minpath[1] = 0;
	calc[1] = true;
	int calcnum = 1;

	int from = 1;
	while (calcnum < 10) {
		int mincost = 100000;
		int next = -1;
		for (int to = 0; to <= 9; to++) {
			if (to[calc]) continue;
			int tmppath =  minpath[from] + C[to][from];
			if (minpath[to] > tmppath) {
				minpath[to] = tmppath;
			}
			if (minpath[to] < mincost) {
				mincost = minpath[to];
				next = to;
			}
		}
		calc[next] = true;
		from = next;
		calcnum++;
	}

	long long ans = 0;
	for (int i = 0; i <= 9; i++) {
		ans += (long long)minpath[i] * cnt[i];
	}
	cout << ans << endl;

	return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> order_p, order_q,order;
  int cnt, cnt_p, cnt_q;
  cnt = cnt_p = cnt_q =0;
  order.resize(n);
  order_p.resize(n);
  order_q.resize(n);
  rep(i,n) order[i] = i+1;
  rep(i,n) cin >> order_p[i];
  rep(i,n) cin >> order_q[i];

  do{
    cnt++;
    if(order == order_p) cnt_p = cnt;
    if(order == order_q) cnt_q = cnt;
  }while(next_permutation(order.begin(),order.end()));
  cout << abs(cnt_p - cnt_q) << endl;


  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

//const (
//	MaxIntValue = int(^uint(0) >> 1)
//)

func main() {
	N := readLineInt()[0]
	posX, posY := 1, N
	for i := 1; i <= sqrt(N); i++ {
		if (N % i) == 0 {
			if abs(posY-posX) > abs(i-(N/i)) {
				posX, posY = i, N/i
			}
		}
	}
	fmt.Println(posX + posY - 2)
}

/////////////////////////////////////////
var scanner = bufio.NewScanner(os.Stdin)

func init() {
	//scanner.Split(bufio.ScanWords)
}
func readLine() string {
	scanner.Scan()
	return scanner.Text()
}

func Loop(start, end int, f func(i int)) {
	for i := start; i < end; i++ {
		f(i)
	}
}

func readLineInt() []int {
	result := make([]int, 0)
	for _, v := range strings.Split(readLine(), " ") {
		r, _ := strconv.Atoi(v)
		result = append(result, r)
	}
	return result
}

func abs(i int) int {
	if i >= 0 {
		return i
	} else {
		return i * -1
	}
}

func sqrt(i int) int {
	t := math.Sqrt(float64(i))
	return int(t) + 1
}


Measured memory_bytes: 640
import itertools
N = int(input())
S = []
for i in range(N):
    S.append(input())

count = [0]*5
countType = 0
    

for i in range(N):
    if S[i][0]  =='M':
        count[0]  = count[0] + 1
        if count[0] == 1:
            countType = countType+1
    elif S[i][0]  =='A':
        count[1]  = count[1] + 1
        if count[1] == 1:
            countType = countType+1
    elif S[i][0]  =='R':
        count[2]  = count[2] + 1
        if count[2] == 1:
            countType = countType+1
    elif S[i][0]  =='C':
        count[3]  = count[3] + 1
        if count[3] == 1:
            countType = countType+1
    elif S[i][0]  =='H':
        count[4]  = count[4] + 1
        if count[4] == 1:
            countType = countType+1
            
if countType<3:
    print(0)
else:
    ans = 1
    buf =  0
    LIST = list(itertools.combinations([0,1,2,3,4],3))
    for i in range(len(LIST)):
        for j in range(len(LIST[i])):
            ans = ans*count[LIST[i][j]]
        buf = buf + ans
        ans = 1
    print(buf)
    
            


Measured memory_bytes: 9796
package main

import (
	"bufio"
	"fmt"
	"os"
)

var H, W int
var grid [][]int

func main() {
	H, W = ReadInt(), ReadInt()
	grid = make([][]int, H)
	for i := 0; i < H; i++ {
		grid[i] = ReadInts(W)
	}

	paths := []string{}
	prefix := [][]int{}
	for y := 0; y < H; y++ {
		for i := 0; i < W; i++ {
			x := i
			if y%2 == 1 {
				x = W - i - 1
			}
			if len(prefix) > 0 {
				// tracing
				prefix = append(prefix, []int{y, x})
			}
			if grid[y][x]%2 == 1 {
				if len(prefix) == 0 {
					// start trace
					prefix = append(prefix, []int{y, x})
					continue
				}
				// found goal
				for i := 0; i < len(prefix)-1; i++ {
					paths = append(paths,
						fmt.Sprintf("%d %d %d %d",
							prefix[i][0]+1,   // y
							prefix[i][1]+1,   // x
							prefix[i+1][0]+1, // next y
							prefix[i+1][1]+1, // next x
						),
					)
				}
				prefix = nil
			}
		}
	}

	fmt.Println(len(paths))
	for _, path := range paths {
		fmt.Println(path)
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 16964
H, W = map(int,input().split())
table = []
for h in range(H):
    table.append(input())

dp=[[1000 for i in range(W+1)] for j in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(
            dp[h][w+1] + (table[h][w]=='#' and (h==0 or table[h-1][w]=='.')),
            dp[h+1][w] + (table[h][w]=='#' and (w==0 or table[h][w-1]=='.'))
        )

print (dp[-1][-1])

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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define fr(i,k,n) for (int i = k; i < n; ++i)
#define fri(i,k,n) for (int i = k; i >= n; --i)
#define INF (int)1e9
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define all(arr) arr.begin(),arr.end()

void boost(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N=1e6+4;
ll spf[N];
void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<N; i++) 
        spf[i] = i; 
    for (ll i=4; i<N; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i<N; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (ll j=i*i; j<N; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}

bool vis[N];

void solve(){
	int n;
	cin>>n;
	vi arr(n);
	int gc;
	fr(i,0,n){
		cin>>arr[i];
		if(i==0)
			gc=arr[i];
		else
			gc=__gcd(gc,arr[i]);
	}
	bool poss=true;
	fr(i,0,n){
		while(arr[i]>1){
			int x=spf[arr[i]];
			// cout<<x<<endl;
			if(vis[x]){
				poss=false;
				break;
			}
			vis[x]=true;
			while(arr[i]>1 && arr[i]%x==0)
				arr[i]=arr[i]/x;
		}
	}
	if(poss){
		cout<<"pairwise coprime"<<endl;
	}
	else if(gc==1){
		cout<<"setwise coprime"<<endl;
	}
	else{
		cout<<"not coprime"<<endl;
	}
	return;
}

int main()
{
	boost();
	sieve();
	int tc=1;
	//cin>>tc;
	while(tc--)
		solve();
	return 0;
}

Measured memory_bytes: 15972
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

class UF_pop{
    public:
    int sz;
    int sm;
    vector<int>par,nrank;
    vector<int> extra;
    vector<vector<int> > hist;
    UF_pop(int node_size) : sm(0),sz(node_size),par(sz),nrank(sz,0),extra(sz,0){
        rep(i,sz){
            par[i] = i;
        }
    }
    int find(int x){
        return (par[x] == x)?(x):find(par[x]);
    }
    void pop(){
        sm = 0;
        while(!hist.empty()){
            auto & a = hist.back();
            par[a[0]] = a[0],nrank[a[0]] = a[1],par[a[2]] = a[2];
            extra[a[0]] = 0;
            extra[a[2]] = 0;

            hist.pop_back();
        }
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        hist.push_back({x,nrank[x],y});
        if(x==y){
            if(extra[x]==0){
                extra[x]++;
                sm++;
            }else{
                extra[x]++;
            }
            return ;
        }
        //
        if(extra[x]==0||extra[y]==0){
            sm++;
        }
        if(nrank[x] < nrank[y]){
            par[x] = y;
            extra[y] += extra[x];
        }else{
            nrank[x] += (nrank[x]==nrank[y]);
            par[y] = x;
            extra[x] += extra[y];
        }
    }
    
};

int n,k;
vector<vector<int> > g;
vector<int> h;
vector<int> res;
vector<int> c;
vector<int> d;

int precalc(int id,int pre){
    int mx = -1;
    int sm = 0;
    for(int x:g[id]){
        if(x!=pre){
            int k = precalc(x,id);
            sm += k;
            if(mx<k){
                h[id] = x;
                mx = k;
            }
        }
    }
    sm++;
    return sm;
}
void dfs2(int id,int pre,UF_pop &uf){
    uf.unite(c[id],d[id]);
    for(auto x:g[id]){
        if(x!=pre){
            dfs2(x,id,uf);
        }
    }
    return;
}

void dfs(int id,int pre,UF_pop &uf){
    for(auto x:g[id]){
        if(x!=pre&&x!=h[id]){
            dfs(x,id,uf);
        }
        uf.pop();
    }
    if(h[id]!=-1)dfs(h[id],id,uf);
    uf.unite(c[id],d[id]);
    for(auto x:g[id]){
        if(x!=pre&&x!=h[id]){
            dfs2(x,id,uf);
        }
    }
    res[id] = uf.sm;
    return ;
}

int main(){
    cin >> n >> k;
    g.resize(n);
    h.resize(n,-1);
    res.resize(n);
    c.resize(n);
    d.resize(n);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    rep(i,n){
        cin >> c[i] >> d[i];
        c[i]--;d[i]--;
    }
    precalc(0,-1);
    // rep(i,n){
    //     cerr << h[i] << endl;
    // }
    UF_pop uf(k);
    dfs(0,-1,uf);
    rep(i,n){
        cout << res[i] << endl;
    }
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  
  int Alice = 0, Bob = 0;
  
  for (int i = 0; i < n; i++) {
    int max = 1;
    int maxnumber = 0;
    for (int j = 0; j < n; j++) {
      if (a.at(j) >= max) {
        max = a.at(j);
        maxnumber = j;
      }
    }
    if (i % 2 == 0)
      Alice += max;
	else
      Bob += max;
    
    a.at(maxnumber) = 0;
  }
  
  cout << Alice - Bob << endl;
}

Measured memory_bytes: 256