akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]
use std::io;

// "S1", "H2"などを数字の部分のみを比較して結果を返す関数。
// mx, nyに対して、x < yを返す
// なお、x,yは1..9であるとする。
fn cmp(s1: &str, s2: &str) -> bool {
    let d1: i32 = s1.chars().nth(1).unwrap().to_digit(10).unwrap() as i32;
    let d2: i32 = s2.chars().nth(1).unwrap().to_digit(10).unwrap() as i32;
    d1 < d2
}


/// バブルソート。
fn bubble_sort(a: &mut [&str]) {
    let n = a.len();
    for i in 0..n {
        for j in 1..(n-i) {
            if cmp(&a[j], &a[j-1]) {
                a.swap(j, j-1);
            }
        }
    }
}

// 挿入ソート。非安定
fn selection_sort(a: &mut [&str]) {
    let n = a.len();
    for i in 1..n {
        let mut min_idx = i-1;
        for j in i..n {
            if cmp(&a[j], &a[min_idx]) {
                min_idx = j;
            }
        }
        a.swap(min_idx, i-1);
    }
}

fn print_vec(a: &[&str]){
    let s = a.join(" ");
    println!("{}", s);
}

fn same_vec(a1: &[&str], a2: &[&str]) -> bool {
    let n = a1.len();
    if n != a2.len() {
        return false;
    } else {
        for i in 0..n {
            if a1[i] != a2[i] {
                return false;
            }
        }
    }
    true
}

fn main(){
    let sin = io::stdin();
    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let _n: i32 = buf.trim().parse().unwrap();

    let mut buf = String::new();
    sin.read_line(&mut buf).ok();
    let mut a1: Vec<&str> = buf.split_whitespace().collect();
    let mut a2 = a1.clone();

    // let mut a = vec!["H4", "C9", "S4", "D2", "C3"];
    // let mut a1: Vec<String> = a.iter().map(|&e| e.to_string()).collect();
    // let mut a2: Vec<String> = a1.clone();

    // print_vec(&a1);
    bubble_sort(&mut a1);
    print_vec(&a1);
    println!("Stable");     // バブルソートは常に安定

    selection_sort(&mut a2);
    print_vec(&a2);
    if same_vec(&a1, &a2) { // バブルソートと比較して、異なったら非安定とする
        println!("Stable");
    } else {
        println!("Not stable");
    }
}



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

using namespace std;

#define lp(i,n) for(int i = 0; i <n;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define SZ(v) ((int)((v).size()))
typedef long long ll;

const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;

void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    // int q;
    // scanf("%d",&q);
    // while (q--){
    //     ll n,k,a,b;
    //     scanf("%lld%lld%lld%lld",&k,&n,&a,&b);
    //     k-=a*n;
    //     if(k>0)printf("%d\n",n);
    //     else{
    //         k*=-1;
    //         ll diff = a-b;
    //         ll cant = (k+diff)/diff;
    //         if(cant>n)puts("-1");
    //         else printf("%lld\n",n-cant);
    //     }
    // }
    ll n;
    scanf("%lld",&n);
    printf("%lld",(n*(n-1))/2);
    
    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let (n, q) = (read::<usize>(), read::<usize>());

    let mut tree = vec![vec![]; n];
    for _i in 0..n-1 {
        let (a, b) = (read::<usize>(), read::<usize>());
        tree[a-1].push(b-1);
        tree[b-1].push(a-1);
    }

    let mut px = vec![0i64; n];
    for _i in 0..q {
        let (p, x) = (read::<usize>(), read::<i64>());
        px[p-1] += x
    }
    
    dfs(0, 0, &mut px, &tree);
    for i in 0..n {
        print!("{} ", px[i]);
    }
}

fn dfs(v: usize, par: usize, px: &mut Vec<i64>, tree: &Vec<Vec<usize>>) {
    for &w in tree[v].iter()  {
        if w == par {
            continue;
        }
        px[w] += px[v];
        dfs(w, v, px, tree);
    }
}

Measured memory_bytes: 33276
#include<bits/stdc++.h>
using namespace std;
int n,a[400001],b[400001],ta[400001],tb[400001],l=1,r=1;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),ta[a[i]]++;
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),tb[b[i]]++;
	for(int i=1;i<=n;i++)if(ta[i]+tb[i]>n)puts("No"),exit(0);
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=tb[i];j++)
		{
			while(b[l])++l;
			while(a[r]<=a[l]&&r<=n)++r;
			while(b[r])++r;
			if(a[l]!=i)b[l++]=i;
			else b[r++]=i;
		}
	}
	l=1;
	for(int i=n+1;b[i];i++)
	{
		while(b[l])++l;
		if(a[l]!=b[i])a[l]=b[i];
		else 
		{
			while(a[r=(rand()%n+1)]==b[i]||b[r]==a[l]);
			b[l]=b[r],b[r]=b[i];
		}
	}
	puts("Yes");
	for(int i=1;i<=n;i++)printf("%d ",b[i]);
	return 0;
}

Measured memory_bytes: 7700
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

int main(){
    long long n,a,b;
    cin >> n >> a >> b;

    long long cnt=(n/(a+b))*a;
    if(n%(a+b)>a){
        cnt += a;
    }else{
        cnt += n%(a+b);
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0){
        printf("Possible\n");
    }else{
        printf("Impossible\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N, M;
    cin >> N >> M;
    long long INF = 1e9;
    vector<int> c(M, 0);
    vector<int> a(M);
    for(int i = 0; i < M; i++){
        int d;
        cin >> a[i] >> d;
        for(int j = 0; j < d; j++){
            int e;
            cin >> e;
            e--;
            c[i] += (1 << e);
        }
    }
    vector<vector<long long>> dp(M + 1, vector<long long> ((1 << N), INF));
    dp[0][0] = 0;
    for(int i = 0; i < M; i++){
        for(int j = 0; j < (1 << N); j++){
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
            if(dp[i][j] != INF) dp[i + 1][j | c[i]] = min(dp[i + 1][j | c[i]], dp[i][j] + a[i]);
        }
    }
    if(dp[M][(1 << N) - 1] == INF) cout << -1 << endl;
    else cout << dp[M][(1 << N) - 1] << endl;
}

Measured memory_bytes: 35296
#include <iostream>
using namespace std;
int main () {
	int N;
	cin >> N;
	if (N>=400 && N<=599) {
		cout << "8" << endl;
	}
	else if (N<=799) {
		cout << "7" << endl;
	}
	else if (N<=999) {
		cout << "6" << endl;
	}
	else if (N<=1199) {
		cout << "5" << endl;
	}
	else if (N<=1399) {
		cout << "4" << endl;
	}
	else if (N<=1599) {
		cout << "3" << endl;
	}
	else if (N<=1799) {
		cout << "2" << endl;
	}
	else {
		cout << "1" << endl;
	}
}

Measured memory_bytes: 3612
n = gets.to_i
as = gets.split.map(&:to_i)

ans = 1
if n == 1 || as[0] == as[1]
  increased = 0
else
  increased = as[0] < as[1] ? 1 : -1
end

1.upto(n - 1) do |i|
  l = as[i - 1]
  r = as[i]
  next if l == r

  if increased == 0
    increased = l < r ? 1 : -1
  elsif (r - l) * increased < 0
    ans += 1
    increased = 0
  end
end

puts ans


Measured memory_bytes: 8452
import io.StdIn._

object Main extends App {

  val strList = readLine.split(" ")
  val s = strList(0)
  val t = strList(1)

  val numList = readLine.split(" ")
  var numS = numList(0).toInt
  var numT = numList(1).toInt

  val u = readLine

  if (u == s) {
    numS = numS - 1
  } else {
    numT = numT - 1
  }

  println(s"$numS $numT")

}


Measured memory_bytes: 25384
# -*- coding: utf-8 -*-
import sys
from math import sqrt,floor
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    X = int(lines.pop(0))
    s = floor(sqrt(X))
    res = 1
    for c in range(s, 1, -1):
        n = 2
        while( c**n <= X ):
            res = max(res, c**n)
            n += 1

    print(res)
#
# main
#
lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

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

using namespace std;

#define MP 999983

bool is_prime[MP+1];

int s_prime[MP+1];

int count_prime(int l, int r) {
    if(l<=0) l=1;
    if(r>MP) r=MP;
    return s_prime[r] - s_prime[l-1];
}

int main() {
    fill(&is_prime[2], &is_prime[MP+1], true);
    for(int p=2; p*p<=MP; p++) {
        if(is_prime[p]) {
            for(int i=p*p; i<=MP; i+=p) {
                is_prime[i] = false;
            }
        }
    }
    for(int i=1; i<=MP; i++) s_prime[i] = s_prime[i-1] + (is_prime[i] ? 1 : 0);
    
    int n;
    while(cin>>n, n) {
        int res = 0;
        for(int i=0; i<n; i++) {
            int p, m;
            cin >> p >> m;
            res += count_prime(p-m, p+m) - 1;
        }
        cout << res << endl;
    }
    
    return 0;
}




Measured memory_bytes: 7904
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

def hoge():
    from collections import defaultdict
    n, m = map(int, input().split())

    ns = defaultdict(set)
    used = {}
    for _ in range(m):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)
        used[u-1,v-1] = False
        used[v-1,u-1] = False


    seen = [False] * n
    prev = [None] * n
    cs = []
    count = 0
    done = True
    
#     if not all(len(item)%2==0 and len(item)>0 for item in ns.values()):
#         print("No")
#         return


    for start in range(n):
        if seen[start]:
            continue
        q = [start]
        current_seen = [False] * n
        update = False
        while q:
            u = q.pop()
            current_seen[u] = True
            for v in ns[u]:
                if used[u,v] or prev[u]==v:
                    continue
                prev[v] = u
                if current_seen[v]:
                    # サイクル検出
                    count += 1
                    c = set()
                    tmp = v
                    while tmp not in c:
                        c.add(tmp)
                        used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                        tmp = prev[tmp]
                    cs.append(c)
                    for u in c:
                        seen[u] = True
                    update = True
                    break
                q.append(v)
            if update:
                break
        if not update:
            print("No")
            return 
    if sum(seen)<n:
        print("No")
        return
    def sub(cs):
        if len(cs)==1:
            return "No"
        elif len(cs)==2:
            if len(set(cs[0] & cs[1]))>=3:
                return "Yes"
            else:
                return "No"
        else :
            return "Yes"
    #     u2s = defaultdict(set)
    #     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    #     for i,s in enumerate(cs):
    #         for u in s:
    #             nns[i] |= u2s[u]
    #             u2s[u].add(i)
    #     for i,s in nns.items():
    #         for j in s:
    #             nns[j].add(i)
    #     count = 0
    # #     print(u2s)
    # #     print(nns)
    #     seen = [False] * len(cs)
    #     for start in range(len(cs)):
    #         if seen[start]:
    #             continue
    #         q = [start]
    #         seen[start] = True
    #         while q:
    #             u = q.pop()
    #             for v in nns[u]:
    #                 if not seen[v]:
    #                     q.append(v)
    #                     seen[v] = True
    #         count += 1
    #     if count<=3:
    #         return "Yes"
    #     else:
    #         return "No"
    if done:
        print(sub(cs))
    #     print("Yes")
hoge()

Measured memory_bytes: 129164
#include <stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a[3];
	scanf("%d %d %d",&a[0],&a[1],&a[2]);
	sort(a,a+3);
	
	if(!(a[0]%2)||!(a[1]%2)||!(a[2]%2)){
		printf("%d\n",0);
	}else{
		printf("%lld\n",(long long int)(a[0])*a[1]);
	}

}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int board[52][52];

int main(int argc, char *argv[]) {
	int H, W;
	cin >> H >> W;

	vector<string> S(H);

	for (int i = 1; i <= H; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= W; j++) {
			if (S[j-1] == '#') {
				board[i - 1][j - 1] ++;
				board[i][j - 1] ++;
				board[i + 1][j - 1] ++;
				board[i - 1][j] ++;
				board[i][j] += 9;
				board[i + 1][j] ++;
				board[i - 1][j + 1] ++;
				board[i][j + 1] ++;
				board[i + 1][j + 1] ++;
			}
		}
	}

	for (int y = 1; y <= H; y++) {
		for (int x = 1; x <= W; x++) {
			if (board[y][x] >= 9) cout << "#";
			else cout << board[y][x];
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int n;
  cin>>n;
    int sum = 0;
    rep(i, n)
    {
        int l, r;
        cin >> l >> r;
        sum += r - l + 1;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
def main():
    n, x = list(map(int, input().split()))
    ls = list(map(int, input().split()))

    count = 1
    d = 0
    for i in range(n):
        d = d + ls[i]
        if d > x:
            break
        else:
            count += 1

    print(count)


main()

Measured memory_bytes: 3060
fn main() {
    let (a, b, t) = {
        let s = {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            s.trim_right().to_owned()
        };
        let mut integers = s.split_whitespace();
        let a: i32 = integers.next().unwrap().parse().unwrap();
        let b: i32 = integers.next().unwrap().parse().unwrap();
        let t: i32 = integers.next().unwrap().parse().unwrap();
        (a, b, t)
    };
    let mut answer = 0;
    for i in 1..21 {
        if a*i > t {
            break;
        }
        answer += b;
    }
    println!("{}", answer);
}


Measured memory_bytes: 4352
N,A,B = (int(i) for i in input().split())
X = [int(i) for i in input().split()]
dp = [0]*N
for i in range(N-1):
    a = abs(X[i]-X[i+1])*A
    b = B
    dp[i+1] = min(a,b) + dp[i]
print(dp[-1])



Measured memory_bytes: 14252
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String []args){
	Scanner sc = new Scanner(System.in);
	int list[] = new int[3];
	for(int i = 0; i < 3; i++){
		list[i] = sc.nextInt();
	}

	Arrays.sort(list);

	for(int j = 0; j < 3; j++)
		if(j == 2)
		System.out.println(list[j]);
		else
		System.out.print(list[j] + " ");
	sc.close();
	}
}

Measured memory_bytes: 26288
#include <bits/stdc++.h>
using namespace std;
using ll =  long long;
const int INF = 0x3f3f3f3f;

int N, M;
vector<int> S[20];
int p[20];

void solve()
{
	int ans = 0;
	for(int st = 0; st <(1<<N) ; ++st){
		bool ok = true;
		for(int i=0;i<M;++i){
			int cnt = 0;
			for(int j : S[i])if(st>>j&1){
				cnt++;
			}
			if(cnt%2 != p[i]%2){
				ok = false;
				break;
			}
		}
		if(ok) ans++;
	}
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N >> M;
	int k,x;
	for(int i=0;i<M;++i){
		cin >> k;
		for(int j=0;j<k;++j){
			cin >> x;
			S[i].push_back(x-1);
		}
	}
	for(int i=0;i<M;++i){
		cin >> p[i];
	}
	solve();
	return 0;
}

Measured memory_bytes: 256
#include "iostream"

int main()
{
	int a, b;
	std::cin >> a >> b;

	const char* str = nullptr;

	if (a < b) str = "a < b";
	else if (a > b) str = "a > b";
	else str = "a == b";

	std::cout << str << std::endl;

    return 0;
}



Measured memory_bytes: 3076
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL


struct node {
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};

typedef struct node * Node;


Node root = NIL;

Node treeSearch(Node root, int k) {

  if (root == NIL) return NIL;
  if (root->key == k) return root;
  if (root->key > k) {

    if (root->l != NIL) return treeSearch(root->l, k);
    else return NIL;
  }
  else {
    if (root->r != NIL) return treeSearch(root->r, k);
    else return NIL;
  }
}

int find(Node root, int k) {
  if (root->key == k) return 1;

  if (root->key < k) {
    if (root->l != NIL) return find(root->l, k);
    else return 0;
  }
  else {
    if (root->r != NIL) return find(root->r, k);
    else return 0;
    
  }
}

void insert(int k) {
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->l = NIL;
  z->r = NIL;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->l;
    }
    else {
      x = x->r;
    }
  }
	
  z->p = y;
	
  if (y == NIL) {
    root = z;
  }
  else if (z->key < y->key) {
    y->l = z;
  }
  else {
    y->r = z;
  }
}

void inorder(Node u) {
  if (u == NIL) return;

  inorder(u->l);
  printf(" %d", u->key);
  inorder(u->r);
  return;
}

void preorder(Node u) {
  if (u == NIL) return;
  printf(" %d", u->key);
  preorder(u->l);
  preorder(u->r);
  return;
}

void treeDelete(Node z) {
  Node y;
  Node x;
  return;
}

int main(void) {
  int n, i, x;
  char com[20];
  Node t;
  scanf("%d", &n);

  for (i = 0; i < n; ++i) {

    scanf("%s", com);

    if ( com[0] == 'f' ) {
      scanf("%d", &x);
      t = treeSearch(root, x);

      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    }
    else if ( com[0] == 'i') {

      scanf("%d", &x);
      insert(x);
    }
    else if ( com[0] == 'p') {

      inorder(root);
      printf("\n");

      preorder(root);
      printf("\n");
    }
    else if ( com[0] == 'd') {

      scanf("%d", &x);

      treeDelete(treeSearch(root, x));
    } 
  }
	
  return 0;
}




  

 



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

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    vector<pair<ll, ll>> ps;
    rep(i, N){
        cin >> A[i] >> B[i];
        ps.push_back(make_pair(B[i], A[i]));
    }
    sort(ps.begin(), ps.end());

    ll sum = 0;
    rep(i, N){
        sum += ps[i].second;
        if (sum > ps[i].first){
            puts("No");
            return 0;
        }
    }

    puts("Yes");
    

    return 0;
}


Measured memory_bytes: 10588
#include<bits/stdc++.h>
using namespace std;
int  t;
long long a;
char c;
char s[200010];
int main(){
	gets(s);
	bool flag=false;
	 for(int i=0;i<strlen(s);i++){
	 	int c=s[i];
	 	if(flag) {
	 		flag=false;
	 		continue;
	 	}
	 	if(c=='A') t++;
	 	if(c=='B') {
	 		if(i+1<strlen(s)){
	 			c=s[i+1];
	 			flag=true;
	 		}
	 		else c='\n';
	 		if(c=='C'){
	 			a+=t;
	 			continue;
	 		}
	 		else{
				if(c=='A') t=1;
				else t=0;
			}
		}
		if(c=='C') t=0;
	}
	printf("%lld",a);
	return 0;
}

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

typedef long long ll;

int main(){
int n;
cin>>n;
vector<int>a(n),b(n),c(n);
ll ans;
rep(i,n)cin>>a[i];
rep(i,n)cin>>b[i];
rep(i,n)cin>>c[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());

rep(j,n){
  ll na=lower_bound(a.begin(),a.end(),b[j])-a.begin();  
  ll nc=upper_bound(c.begin(),c.end(),b[j])-c.begin();
  ans+=na*(n-nc);
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 1536
s = input()
n = int(input())

for _ in range(n):
    line = input().split()
    command = line[0]

    if command == 'replace':
        start, end  = int(line[1]), int(line[2])
        s = s[:start] + line[3] + s[end+1:]
    elif command == 'reverse':
        start, end  = int(line[1]), int(line[2])
        s = s[:start] + s[start:end+1][::-1] + s[end+1:]
    elif command == 'print':
        start, end  = int(line[1]), int(line[2])
        print(f"{s[start:end+1]}")





Measured memory_bytes: 5628
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<iostream>
#include<cmath>
#define INF 1000001LL
#define INF2 100000001000000LL
using namespace std;

typedef long long ll;

struct cord{
  int d,k;
  vector<ll> c;
  cord(void){d = k = 0;c.clear();}
  cord(vector<ll> v){d = v.size(); k = 0; c = v;}
  bool operator<(const cord a)const{return c[k]<a.c[k];}
  bool operator==(const cord a)const{return c==a.c;}
};

ll dis(cord a, cord b){
  if(a.d != b.d)return INF;
  ll res = 0;
  for(int i=0;i<a.d;i++)res += (a.c[i]-b.c[i]) * (a.c[i]-b.c[i]);
  return res;
}

struct KDTree{
  int n,d,root;
  vector<cord> v;

  KDTree(void){n = d = root = 0;v.clear();}

  KDTree(vector<cord> x){
    n = x.size();
    if(!n)return;
    d = x[0].c.size();
    if(!d)return;
    v = x;
    compose(0,n,0);
  }

  void compose(int l, int r, int depth){
    if(r-l<=1)return;
    for(int i=l;i<r;i++)v[i].k = depth;
    sort(v.begin()+l,v.begin()+r);

    compose(l,(l+r)/2,(depth+1)%d);
    compose((l+r)/2+1,r,(depth+1)%d);
  }

  inline void search(int l,int r,vector<ll> &rng, cord p, int depth, ll &dist){
    if(r-l<1)return;

    int mid = (l+r)/2;
    dist = min(dist,dis(p,v[mid]));
    for(int i=0;i<d;i++){
      if(rng[2*i]>p.c[i] && (rng[2*i]-p.c[i])*(rng[2*i]-p.c[i]) >= dist)return;
      else if(rng[2*i+1]<p.c[i] && (rng[2*i+1]-p.c[i])*(rng[2*i+1]-p.c[i]) >= dist)return;
    }

    ll tmp,nxt[4],st[] = {0,1},d1,d2;
    nxt[0] = mid+1; nxt[1] = r; nxt[2] = l; nxt[3] = mid;

    if(p.c[depth]<v[mid].c[depth]){
      swap(nxt[0],nxt[2]);
      swap(nxt[1],nxt[3]);
      swap(st[0],st[1]);
    }
    
    for(int i=0;i<2;i++){
      tmp = rng[2*depth+st[i]];
      rng[2*depth+st[i]] = v[mid].c[depth]; 
      search(nxt[2*i],nxt[2*i+1],rng,p,(depth+1)%d,dist);
      rng[2*depth+st[i]] = tmp;
    }
  }
};

int n,q,m;
vector<cord> v;
cord p,r;
vector<ll> tmp;   

int main(){
  vector<ll> range;
  for(int i=0;i<3;i++){
    range.push_back(-INF); 
    range.push_back(INF);
  }

  while(scanf("%d%d",&n,&q)!=EOF,n||q){
    v.resize(n); tmp.resize(3);

    for(int i=0;i<n;i++){
      for(int j=0;j<3;j++)scanf("%lld",&tmp[j]);
      v[i] = cord(tmp);
    }

    KDTree kd(v);

    for(int i=0;i<q;i++){
      scanf("%d",&m);
      double ans = 0;
      ll now, prv;

      for(int j=0;j<3;j++)scanf("%lld",&tmp[j]);
      p = cord(tmp); prv = INF2;
      kd.search(0,n,range,p,0,prv);
      for(int j=1;j<m;j++){
	for(int k=0;k<3;k++)scanf("%lld",&tmp[k]);

	r = cord(tmp); now = INF2;
	kd.search(0,n,range,r,0,now);
	ans += min(sqrt(prv) + sqrt(now), sqrt(dis(p,r)) );
	prv = now; p = r;
      }
      printf("%.9lf\n",ans);
    }
  }
}

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

int n, s=1, a[100005];
bool v=1;
int main() {
	int i, t;
	cin >> n;
	for(i=0; i<n; i++) {
		scanf("%d", &t);
		a[t/2]++;
	}
	if(n%2) {
		if(a[0] != 1) v = 0;
		for(i=1; i<=n/2; i++) if(a[i] != 2) v = 0;
	} else {
		for(i=0; i<n/2; i++) if(a[i] != 2) v = 0;
	}
	for(i=0; i<n/2; i++) s = s*2 % 1000000007;
	printf("%d", v ? s:0);
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<typename Monoid>
struct Segment_Tree{
    vector<Monoid> seg;
    const Monoid unit;
    const int n;

    Monoid f(Monoid a, Monoid b) const {return max(a, b);}
    
    Segment_Tree(int N, const Monoid &unit) : unit(unit), n(1<<(32-__builtin_clz(N-1))){
        seg.assign(2*n, unit);
    }
    
    void change(int i, const Monoid &x){
        i += n;
        seg[i] = x;
        while(i > 0){
            i /= 2;
            seg[i] = f(seg[2*i], seg[2*i+1]);
        }
    }

    Monoid query(int a, int b, int i = 1, int l = 0, int r = -1) const{
        if(r < 0) r = n;
        if(a >= r || b <= l) return unit;
        if(a <= l && r <= b) return seg[i];
        Monoid vl = query(a, b, 2*i, l, (l+r)/2);
        Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);
        return f(vl, vr);
    }
    
    Monoid operator [] (int i) const {return seg[n+i];}

    int find_first(int a, const Monoid &x, int i = 1, int l = 0, int r = -1) const{
        if(r < 0) r = n;
        if(seg[i] < x) return -1;
        if(r-l == 1) return l;
        int m = (l+r)/2;
        if(a < m){
            int tmp = find_first(a, x, 2*i, l, m);
            return (tmp == -1? find_first(m, x, 2*i+1, m, r) : tmp);
        }
        return find_first(a, x, 2*i+1, m, r);
    }
    
    void clear(){
        fill(all(seg), unit);
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    Segment_Tree<int> seg(N, -inf);
    rep(i, N){
        int A; cin >> A;
        seg.change(i, A);
    }
    while(Q--){
        int q, a, b; cin >> q >> a >> b; a--;
        if(q == 1) seg.change(a, b);
        if(q == 2) cout << seg.query(a, b) << endl;
        if(q == 3){
            int ans = seg.find_first(a, b);
            cout << (ans == -1? N+1 : ans+1) << endl;
        }
    }
}

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

int main() {
    int N;
    cin >> N;
    vector<int> B(N);
   
    rep(i, N-1) cin >> B[i+1];
    B[0] = B[1];

    int res = 0;
    for(int i=1; i<N; i++) {
        res += min(B[i], B[i-1]);
    }
    res += B[N-1];
    cout << res << endl;
    

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		int m = s.nextInt();
		int l = s.nextInt();
		int gyouretuA[][] = new int [n][m];
		int gyouretuB[][] = new int [m][l];
		long gyouretuC[][] = new long [n][l];
		
		for(int i = 0;i < n; i++){
			for(int j = 0;j < m; j++){
				gyouretuA[i][j] = s.nextInt();
			}
		}
		
		for(int i = 0;i < m; i++){
			for(int j =0; j < l; j++){
				gyouretuB[i][j] = s.nextInt();
			}
		}
		
		for(int i = 0;i < n; i++){
			for(int j = 0; j < l; j++){
				for(int k = 0; k < m; k++){
					gyouretuC[i][j] += gyouretuA[i][k] * gyouretuB[k][j];
				}
			}
		}
		
		for(int i =0;i < n; i++){
			for(int j =0;j < l; j++){
				System.out.print(gyouretuC[i][j]);
				if(j < l - 1)
					System.out.print(" ");
			}
			System.out.println();
			s.close();
		}
	}
}



Measured memory_bytes: 52880
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

using namespace std;
using ll = long long int;
using vec = vector<int>;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define Sort(a)    sort(a.begin(), a.end())
#define gSort(a)   sort(a.begin(), a.end())
const int INF = 2147483647;
const ll  MOD = 1000000007;

int main() {
    ll h, w; cin >> h >> w;

    if((h == 1) || (w == 1)) {
        cout << 1;
        return 0;
    }

    ll ans = h * w;
    ll num = ans / 2.0;
    ans -= num;

    cout << ans;
}

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


public class Main {
    public static BigInteger[][] memo = new BigInteger[3000][3000];

    public static BigInteger choose(BigInteger n, BigInteger k) {

        if (n.intValue() == 0 && k.intValue() > 0) {
            return BigInteger.ZERO;
        } else if (k.intValue() == 0 && n.intValue() >= 0) {
            return BigInteger.ONE;
        } else if (memo[n.intValue()][k.intValue()] != null) {
            return memo[n.intValue()][k.intValue()];
        } else {
            memo[n.intValue()][k.intValue()] = choose(n.subtract(BigInteger.ONE), k.subtract(BigInteger.ONE)).add(choose(n.subtract(BigInteger.ONE), k));
        }
        return memo[n.intValue()][k.intValue()];

    }



    public static void main(String[] args) throws NumberFormatException, IOException {
       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
       String[] line = reader.readLine().split(" ");
       int n = Integer.parseInt(line[0]);
       int p = Integer.parseInt(line[1]);
       line = reader.readLine().split(" ");
       int[] arr = new int[line.length];
       int par = 0, nepar = 0;
       for (int i = 0; i < arr.length; ++i) {
           arr[i] = Integer.parseInt(line[i]);
           if (arr[i]%2 == 0) {
               par++;
           } else {
               nepar++;
           }
       }
        BigInteger N = BigInteger.valueOf(nepar);
       if (p == 0) {
            BigInteger res = BigInteger.valueOf(2L).pow(par);
            BigInteger count = BigInteger.ZERO;
            for (int i = 0; i <= nepar; i+=2) {
                count = count.add(choose(N, BigInteger.valueOf(i)));
            }
           System.out.println(res.multiply(count));
       } else {
           BigInteger res = BigInteger.valueOf(2L).pow(par);
           BigInteger count = BigInteger.ZERO;
           for (int i = 1; i <= nepar; i+=2) {
               count = count.add(choose(N, BigInteger.valueOf(i)));
           }
           System.out.println(res.multiply(count));
       }

    }

}


Measured memory_bytes: 79828
s = input()
if len(s) % 2 == 1:
    print('No')
else:
    f = True
    for i in range(len(s) // 2):
        if s[i * 2: i * 2 + 2] != 'hi':
            f = False

    if f:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;

int match[10][10];
int ans = 0, n, win_max, lose_max, win[10], lose[10];

void dfs(int k, int l) {
    if (k == n) {
        if (win_max == lose_max) ans++;
        //cout << "OK" << endl;
    }
    else if (l == n) dfs(k + 1, 0);
    else if (k < l && !match[k][l]) {
        //cout << "(" << k << ", " << l << ")" << endl;
        win[k]++;  lose[l]++;
        match[k][l] = 1;
        match[l][k] = -1;
        int t1 = win_max, t2 = lose_max;
        win_max = max(win[k], win_max);
        lose_max = max(lose[l], lose_max);
        /*cout << win_max << " " << lose_max << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) cout << "\\";
                else if (match[i][j] == -1) cout << "X";
                else if (match[i][j] == 0) cout << "-";
                else cout << "O";
            }
            cout << " " << win[i] << " " << lose[i];
            cout << endl;
        }*/
        if (max(win_max, lose_max) <= n / 2) dfs(k, l + 1);
        win[k]--;  lose[l]--;
        
        
        match[k][l] = 0;
        match[l][k] = 0;
        
        //cout << "(" << k << ", " << l << ")" << endl;
        win[l]++;  lose[k]++;
        match[k][l] = -1;
        match[l][k] = 1;
        win_max = t1;
        lose_max = t2;
        win_max = max(win[l], win_max);
        lose_max = max(lose[k], lose_max);
        /*
        cout << win_max << " " << lose_max << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) cout << "\\";
                else if (match[i][j] == -1) cout << "X";
                else if (match[i][j] == 0) cout << "-";
                else cout << "O";
            }
            cout << " " << win[i] << " " << lose[i];
            cout << endl;
        }*/
        if (max(win_max, lose_max) <= n / 2) dfs(k, l + 1);
        win[l]--;  lose[k]--;
        match[k][l] = 0;
        match[l][k] = 0;
        
    }
    else dfs(k, l + 1);
}


int main(void){
    while (cin >> n) {
        if (!n) return 0;
        
        int m;
        cin >> m;
        ans = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) match[i][j] = false;
            win[i] = lose[i] = 0;
        }
        win_max = lose_max = 0;
        
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            match[x-1][y-1] = 1;
            match[y-1][x-1] = -1;
            win[x-1]++;  lose[y-1]++;
            win_max = max(win_max, win[x - 1]);
            lose_max = max(lose_max, lose[y-1]);
        }
        
        dfs(0, 1);
        
        cout << ans << endl;
        
    }
}



Measured memory_bytes: 3056
def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    visited = [0] * N
    cycles = []

    for i in range(N):
        if visited[i]:
            continue
        score = []
        v = i
        visited[v] = True
        score.append(C[v])
        while not visited[P[v]]:
            v = P[v]
            visited[v] = True
            score.append(C[v])
        cycles.append(score)

    ans = -INF
    for cy in cycles:
        length = len(cy)
        c_num = max(0, (K - 1) // length - 1)
        total = max(0, sum(cy) * c_num)
        rest = K - (c_num * length)
        l_cy = cy + cy + cy
        for l in range(length):
            total_rest = 0
            for diff in range(rest):
                total_rest += l_cy[l + diff]
                ans = max(ans, total + total_rest)

    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 69060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const ll MOD = 1e9+7;


#define REP(i, N) for (ll i = 0; i < (N); i++)
#define REPP(i, a, b) for (ll i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((ll)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<ll>>

using namespace std;
// 変数初期化
vector<ll> bsv; // binary_search用のvector
ll a,b,c,n,m;
typedef pair<ll, ll> Pll;
vector<Pll> facts; // 素因数分解の結果格納用(基数:乗数)
vector<vector<ll> > bit_search_v; //nit全探索の結果格納用

// index が条件を満たすかどうか
bool isOK(ll index, ll key) {
    if (bsv[index] >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
ll binary_search(int key) {
    int ng = -1;
    int ok = (ll)bsv.size();

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key)) ok = mid;
        else ng = mid;
    }
    // OK(key以上となる)のindex番号を返す
    return ok;
}

// 最大公約数
int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

// 最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

//　素因数分解
void prime_fact(ll target){
    ll base=2, exp=0;
    while (base*base<=target) {
        while (target%base==0) {
            target /= base; exp++;
        }
        if (exp>0) {
            facts.push_back(make_pair(base, exp));
        }
        base++; exp=0;
    }
    if (target>1) facts.push_back(make_pair(target,1));
}
// prime_factの結果の確認用
void print_facts(){
    for (int i=0; i<facts.size(); i++) {
        cout << facts[i].first << " " << facts[i].second << endl;
    }
}

// bit全探索
void bit_search(ll target){
    for (ll i=0; i<(1<<target); ++i) {
        if (i==0) continue;
        vector<ll> v;
        for (ll j=0; j<target; ++j) {
            if (i&(1<<j)) v.push_back(j);
            if (i&(1<<j)) cout << i << "  :  " << j << endl;
        }
        bit_search_v.push_back(v);
    }
}
// bit全探索の結果確認用
void print_bit_search(){
    for (ll i=0; i<bit_search_v.size(); ++i) {
        for (ll j=0; j<bit_search_v[i].size(); ++j) {
            cout << bit_search_v[i][j] << " ";
        }
        cout << endl;
    }
}



int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    a=0;
    while(1){
        for(ll i = -a; i < a;i++){
            for(ll l = -120; l < 120;l++){
                if(pow(i,5)-pow(l,5) == x){
                    cout << i << " " << l << endl;
                    return 0;
                }
            }
        }
        a++;
    }
    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
#define endl "\n"
 
const ll INF = 1e15;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int& x : a)
        cin >> x;

    ll ans = 0;
    int maxx = a[0];
    for (int i = 0; i < n; ++i) {
        maxx = max(maxx, a[i]);
        ans += maxx - a[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 3984
#include <stdio.h>
int main(void){
  int A,B,C;
  scanf("%d%d%d", &A,&B,&C);
  if(A == 5 && B== 5 && C ==7){
	  printf("YES\n");
  }else if(A == 5 && B== 7 && C == 5){
	  printf("YES\n");
  }else if(A == 7 && B== 5 && C == 5){
	  printf("YES\n");
  }else{
	  printf("NO\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>

using namespace std;

int main()
{
	string s, ans = "";
	vector<string> sub;
	long long K, count=0;
	cin >> s >> K;

	for (int i = 0; i < s.size(); i++) {
		for (int j = i + 1; j < s.size() + 1; j++) {
			if(j-i<=K)sub.push_back(s.substr(i, j - i));
		}
	}

	sort(sub.begin(), sub.end());

	for (int i = 0; i < sub.size(); i++) {
		if (ans != sub[i]) {
			ans = sub[i];
			count++;
			if (K == count) break;
		}
	}

	cout << ans;

	char qq;
	cin >> qq;
	return 0;
}

Measured memory_bytes: 1660
n = gets.to_i
ary = []
n.times do
  ary << gets.chomp.to_s
end

if ary.uniq != ary
	puts "No"
	exit
end

(n-1).times do |i|
	if ary[i][-1] != ary[i+1][0]
		puts "No"
		exit
	end
end

puts "Yes"


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

typedef long long int LLI;
const int N_MAX = 200000;

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

  int N;
  int a[N_MAX];
  bool u[N_MAX];
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }
  sort(a, a + N);

  for (int i = 0; i < N; ++i) {
    u[i] = false;
  }

  LLI m = 2;
  while (a[N - 1] * 2 >= m) {
    m <<= 1;
  }
  m >>= 1;

  int s = 0;
  while (m >= 2) {
    int r = N - 1;
    int l = 0;
    while (l < r) {
      if (a[l] + a[r] > m) {
        --r;
        continue;
      }
      if (a[l] + a[r] < m) {
        ++l;
        continue;
      }
      if (u[r]) {
        --r;
        continue;
      }
      if (u[l]) {
        ++l;
        continue;
      }
      u[l] = true;
      u[r] = true;
      ++s;
      ++l;
      --r;
    }
    m >>= 1;
  }
  cout << s << endl;

  return 0;
}

Measured memory_bytes: 1280
s = input()
nums = []

f = "0"+str(len(s)-1)+"b"

for i in range(2**(len(s)-1)):
    m = format(i, f)

    l = 0
    r = 0
    while r < len(m):
        if m[r] == "1":
            nums.append(s[l:r+1])
            l = r+1
        r += 1

    nums.append(s[l:r+1])

print(sum(map(int, nums)))

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll mod=1000000007;
int main()
{
    ll n;
    cin>>n;
    bool flag=true;
    for(ll i=1;i<=9;i++)
    {
        for(ll j=1;j<=9;j++)
        {
            if(i*j==n)
            {
                cout<<"Yes"<<endl;
                flag=false;
                break;
            }
        }
        if(!flag)
            break;
    }
    if(flag)
        cout<<"No"<<endl;
}


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

    using namespace std;
     
    int main(){
    	int n;
    	scanf("%d", &n);
    	for (int i = 1; i < 10; ++i){
    		if (n%i==0){
    			if(n/i<10){
    				printf("Yes");
    				return 0;
    			}
    		}
    	}
    	printf("No");
    	return 0;
    }

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

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

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    vector<ll> h(N);
    rep(i,N) cin >> h[i];

    sort(all(h));
    
    ll ans = h[K-1] - h[0];
    rep(i,N-K+1)
    {
        if( h[i+K-1] - h[i] < ans )
        {
            ans = h[i+K-1] - h[i];
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <cstring>
#define MAX_N 1000 + 16
 
using namespace std;
 
int N, H, W;
int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N];
int fld[2 * MAX_N][2 * MAX_N], // 填充遍?用，代表坐?(i, j)?是否空白（??后）
dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
 
// ??坐?，将坐?的??成“?是第几??”，返回一共有几?坐?
int compress(int *x1, int *x2, int w)
{
	vector<int>xs;
 
	for (int i = 0; i < N; ++i)
	{
		int tx1 = x1[i], tx2 = x2[i];
		if (1 <= tx1 && tx1 < w) xs.push_back(tx1);
		if (1 <= tx2 && tx2 < w) xs.push_back(tx2);
	}
	xs.push_back(0);
	xs.push_back(w);
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	for (int i = 0; i < N; ++i)
	{
		x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
		x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
	}
	return xs.size() - 1;
}
 
int bfs()
{
	int ans = 0;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			if (fld[i][j]) continue;
			++ans;
			queue<pair<int, int> >que;
			que.push(make_pair(j, i));
			while (!que.empty())
			{
				int nx = que.front().first, ny = que.front().second;
				que.pop();
 
				for (int i = 0; i < 4; ++i)
				{
					int tx = nx + dx[i], ty = ny + dy[i];
					if (tx < 0 || W < tx || ty < 0 || H< ty || fld[ty][tx] > 0) continue;
					que.push(make_pair(tx, ty));
					fld[ty][tx] = 1;
				}
			}
		}
	}
	return ans;
}
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	while (cin >> W >> H, W | H)
	{
		cin >> N;
		for (int i = 0; i < N; ++i)
		{
			cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
		}
 
		memset(fld, 0, sizeof(fld));
 
		W = compress(X1, X2, W);
		H = compress(Y1, Y2, H);
 
		// imos-法
		for (int i = 0; i < N; i++)
		{
			fld[Y1[i]][X1[i]]++;
			fld[Y1[i]][X2[i]]--;
			fld[Y2[i]][X1[i]]--;
			fld[Y2[i]][X2[i]]++;
		}
		// 横向累?
		for (int i = 0; i < H; i++)
		{
			for (int j = 1; j < W; j++)
			{
				fld[i][j] += fld[i][j - 1];
			}
		}
		// ?向累?
		for (int i = 1; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				fld[i][j] += fld[i - 1][j];
			}
		}// 累?完后，fld中非0部分表示有?板
		cout << bfs() << endl;
	}
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

Measured memory_bytes: 17128
#include <stdio.h>
int main ()
{
	int panjang, index;
	scanf ("%d %d\n", &panjang, &index);
	char karakter [panjang+10];
	scanf ("%s", &karakter);
	karakter[--index]+= 32;
	printf ("%s\n", karakter);
return (0);	
}

Measured memory_bytes: 1572
import math


n, k = list(map(int, input().split()))
que = list(map(int, input().split()))

ans = 0
max_pop_cnt = min(n, k)
for pop_cnt in range(max_pop_cnt+1):
#  pop_cnt+1にしないと、pop_cntが0の場合は消えてしまう。
    for right in range(pop_cnt+1):
        for push_cnt in range((k - pop_cnt)+1):
            ans = max(ans, sum(sorted(que[:pop_cnt-right] + list(reversed(que))[:right])[push_cnt:]))
# reverseにした方がいい。-1で後ろからスライスをとると、0の場合に全部になってしまう。
print(ans)

Measured memory_bytes: 3064
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int a, b;
    cin >> a >> b;
    cout << a*b;
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    string s;
    cin >> s;
    int K;
    cin >> K;
    rep(i, s.size()){
        if(i == s.size() - 1){
            int a = s[i] - 'a';
            (a += K) %= 26;
            s[i] = 'a' + a;
            break;
        }
        if(K == 0){
            break;
        }
        if(s[i] == 'a') continue;
        if(26 - (s[i] - 'a') <= K){
        
            K -= 26 - (s[i] - 'a');
            s[i] = 'a';
//            cout << i << ":" << K << endl;
        }
        
        
    }
    
    output(s);
    
    return 0;
}

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

typedef long long int lli;
const int inf = 1<<30;

int main(){
  string str;
  cin>>str;
  int n=0,w=0,s=0,e=0;
  for(int i=0;i<str.size();++i){
    if(str[i] == 'N') n++;
    if(str[i] == 'W') w++;
    if(str[i] == 'S') s++;
    if(str[i] == 'E') e++;
  }
  bool ans = true;
  if(n+s != 0 && n*s == 0) ans = false;
  if(e+w != 0 && e*w == 0) ans = false;
  if(ans) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
//#include<boost/multi_array.hpp>
//#include<boost/optional.hpp>
//#include<boost/range/irange.hpp>
//#include<boost/range/algorithm.hpp>
//#include<boost/range/adaptors.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();

void Main() {
    int x;
    cin >> x;
    if (x) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
}

int main() {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3612