akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	char s[15];
	int len, judge = 0;
	scanf("%s", s);
	if (s[0] != 'A')
	{
		printf("WA");
		return 0;
	}
	if (s[1] < 'a' || s[1] > 'z')
	{
		printf("WA");
		return 0;
	}
	len = strlen(s);
	for (int i = 2; i < len; i++)
	{
		if (s[i] >= 'a' && s[i] <= 'z')
		{
			continue;
		}
		if (s[i] >= 'A' && s[i] <= 'Z')
		{
			if (s[i] == 'C' && s[i+1] != '\0')
			judge++;
			else
			judge = 2;
		}
	}
	if (judge == 1)
	{
		printf("AC");
	}
	else
	{
		printf("WA");
	}
	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
int main(void){
    int a, b;
    char s[11+3];
    scanf("%d %d", &a, &b);
    scanf("%s", s);
    for(int i=0; i<a; i++){
        if(s[i]=='-'){
            printf("No\n");
            return 0;
        }
    }
    if(s[a]!='-'){
        printf("No\n");
        return 0;
    }
    for(int i=a+1; i<a+b+1; i++){
        if(s[i]=='-'){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 1648
#include <stdio.h>

int main(){
  int y, m, d;
  while(~scanf("%d%d%d", &y, &m, &d)){
    if(y > 1989 || (y == 1989 && (m > 1 || m == 1 && d >= 8)))
      printf("heisei %d %d %d\n", y - 1988, m, d);
    else if(y > 1926 || (y == 1926 && m == 12 && d >= 25))
      printf("showa %d %d %d\n", y - 1925, m, d);
    else if(y > 1912 || (y == 1912 && (m > 7 || m == 7 && d >= 30)))
      printf("taisho %d %d %d\n", y - 1911, m, d);
    else if(y > 1868 || (y == 1868 && (m > 9 || m == 9 && d >= 8)))
      printf("meiji %d %d %d\n", y - 1867, m, d);
    else
      printf("pre-meiji\n");
  }
  return 0;
}

Measured memory_bytes: 608
// https://atcoder.jp/contests/abc107/tasks/abc107_a
#include <bits/stdc++.h>
using namespace std;
using P = pair<double, int>;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a - b + 1 << endl;

    return 0;
}


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

int main() {
  int N, D, result;
  double dis;
  result = 0;
  cin >> N >> D;
  vector<vector<int> > vec(N, vector<int>(2));
  for(int i = 0; i < N; i++){
    for(int j = 0; j < 2; j++){
      cin >> vec.at(i).at(j);
    }
  }
  for(int i = 0; i < N; i++){
    dis = sqrt(std::pow(vec.at(i).at(0),2) + std::pow(vec.at(i).at(1),2));
    if(dis <= D){
      result = result + 1;
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 14036
#include <stdio.h>

int main(void)
{
  int x,n;
  int p[100];
  int flag1 = 0;
  int flag2 = 0;
  scanf("%d %d", &x, &n);
  if(n==0){
    printf("%d\n", x);
  } else {
    for(int i=1;i<=n;i++){
      scanf("%d", &p[i]);
    }
    for(int i=1;i<=200;i++){
      if(i%2==0){
	for(int j=1;j<=n;j++){
	  if(x+((i-1)/2)!=p[j]){
	    flag1 += 1;
	    if(flag1==n){
	      printf("%d\n", x+((i-1)/2));
	      flag2 = 1;
	      break;
	    }
	  }
	}
      } else {
	for(int j=1;j<=n;j++){
	  if(x-(i/2)!=p[j]){
	    flag1 += 1;
	    if(flag1==n){
	      printf("%d\n", x-(i/2));
	      flag2 = 1;
	      break;
	    }
	  }
	}
      }
      if(flag2==1){
	break;
      }
      flag1 = 0;
    }
  }
  return 0;
}


Measured memory_bytes: 1720
type Triangle = (Int,Int,Int)
isRightTriangle :: Triangle -> Bool
isRightTriangle (x,y,z) = let
    d = maximum [x,y,z]
    in
        x^2+y^2+z^2 == 2* d^2

readTriangle :: String -> Triangle
readTriangle s = let [p,q,r] = map read $ words s in (p,q,r)

main = do
    _ <- getLine
    getContents >>=
        mapM_ (putStrLn . (\b -> if b then "YES" else "NO") . isRightTriangle
                                    . readTriangle) . lines

Measured memory_bytes: 4280
def main(n,v,c):
    sumVal = 0
    for i in range(n):
        if v[i] > c[i]:
            sumVal += v[i] - c[i]
    return sumVal

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
print(main(n,v,c))

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

int main() {
  int A;
  int B;
  
  cin >> A;
  cin >> B;
  
  if (A == 1 && B == 2 || A == 2 && B == 1 ) {
    cout << 3 << endl;
  }
  if (A == 2 && B == 3 || A == 3 && B == 2 ) {
    cout << 1 << endl;
  }
  if (A == 3 && B == 1 || A == 1 && B == 3 ) {
    cout << 2 << endl;
  }
  
}




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

int h, w;
char input[2001][2003];
int rl[2001][2000];
struct Rect{
    int h, w;
    Rect() {}
    Rect(int x, int y)
        : h(x), w(y)
    {}
}s[1999];


int main()
{
    int front, rear, pos, w_now, ans(0), t;
    
    scanf("%d%d", &h, &w);
    for (int i = 1; i <= h; ++i)
        scanf("%s", input[i] + 1);
    if (h == 1 || w == 1) {
        printf("%d\n", h * w);
        return 0;
    }
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j < w; ++j) {
            input[i][j] = input[i][j] != input[i][j + 1];
            input[i][j] ^= input[i - 1][j];
        }
    for (int i = h; i > 2; --i)
        for (int j = 1; j < w; ++j)
            input[i][j] ^= input[i - 2][j];
    for (int i = 2; i <= h; ++i) {
        front = rear = 1;
        while (rear < w) {
            while (rear < w && !input[i][rear])
                ++rear;
            while (front < rear) {
                rl[i][front] = rear - front;
                ++front;
            }
            ++rear, ++front;
        }
    }
    for (int j = 1; j < w; ++j) {
        pos = 0;
        s[pos++] = Rect(rl[2][j], 1);
        for (int i = 3; i <= h; ++i) {
            if (rl[i][j] > s[pos - 1].h)
                s[pos++] = Rect(rl[i][j], 1);
            else {
                w_now = 0;
                while (pos && rl[i][j] <= s[pos - 1].h) {
                    w_now += s[pos - 1].w;
                    ans < (t = (s[pos - 1].h + 1) * (w_now + 1)) && (ans = t);
                    --pos;
                }
                s[pos++] = Rect(rl[i][j], w_now + 1);
            }
        }
        w_now = 0;
        while (pos) {
            w_now += s[pos - 1].w;
            ans < (t = (s[pos - 1].h + 1) * (w_now + 1)) && (ans = t);
            --pos;
        }
    }
    ans < h && (ans = h);
    ans < w && (ans = w);
    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 19840
import java.util.Scanner;
public class Main
{
	static int base[][];
	static int ans;
	static int H,W;
	public static void main(String arg[])
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			String str;
			H=in.nextInt();
			W=in.nextInt();
			if((H|W)==0)
				return;
			base=new int[H][W];
			for(int i=0;i<H;i++)
			{
				str=in.next();
				for(int j=0;j<W;j++)
				{
					if(str.charAt(j)=='@')
						base[i][j]=1;
					else if(str.charAt(j)=='#')
						base[i][j]=2;
					else if(str.charAt(j)=='*')
						base[i][j]=3;
				}
			}
			int one=base[0][0];
			int ju=0;
			for(int i=0;i<H;i++)
			{
				for(int j=0;j<W;j++)
				{
					if(one==base[i][j])
						ju=1;
					else
					{
						ju=0;
						break;
					}	
				}
				if(ju==0)
					break;
			}
			ans=0;
			if(ju==1)
				System.out.println(1);
			else
			{
				for(int i=0;i<H;i++)
					for(int j=0;j<W;j++)
					{
						if(base[i][j]==1)
						{
							solve1(i,j);
							ans++;
						}
						else if(base[i][j]==2)
						{
							solve2(i,j);
							ans++;
						}
						else if(base[i][j]==3)
						{
							solve3(i,j);
							ans++;
						}
					}
				System.out.println(ans);
			}
		}
	}
	public static void solve1(int m, int n)
	{
		if(base[m][n]==1)
		{
			base[m][n]=0;
			if(m-1>=0&&base[m-1][n]==1)
				solve1(m-1,n);
			if(m+1<H&&base[m+1][n]==1)
				solve1(m+1,n);
			if(n-1>=0&&base[m][n-1]==1)
				solve1(m,n-1);
			if(n+1<W&&base[m][n+1]==1)
				solve1(m,n+1);
		}
	}
	public static void solve2(int m, int n)
	{
		if(base[m][n]==2)
		{
			base[m][n]=0;
			if(m-1>=0&&base[m-1][n]==2)
				solve2(m-1,n);
			if(m+1<H&&base[m+1][n]==2)
				solve2(m+1,n);
			if(n-1>=0&&base[m][n-1]==2)
				solve2(m,n-1);
			if(n+1<W&&base[m][n+1]==2)
				solve2(m,n+1);
		}
	}
	public static void solve3(int m, int n)
	{
		if(base[m][n]==3)
		{
			base[m][n]=0;
			if(m-1>=0&&base[m-1][n]==3)
				solve3(m-1,n);
			if(m+1<H&&base[m+1][n]==3)
				solve3(m+1,n);
			if(n-1>=0&&base[m][n-1]==3)
				solve3(m,n-1);
			if(n+1<W&&base[m][n+1]==3)
				solve3(m,n+1);
		}
	}
}

Measured memory_bytes: 12000
N,Q=map(int,input().split())
arr_ab = [[] for j in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    arr_ab[a-1].extend([b])
arr_px = [0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    arr_px[p-1]+=x

ans = [0]*N

for i in range(N-1):
    for j in arr_ab[i]:
        arr_px[j-1]+=arr_px[i]
print(' '.join(list(map(str, arr_px))))

Measured memory_bytes: 109388
class String
    def to_sec
        h, m, s = self.split(":").map(&:to_i)
        h * 60 * 60 + m * 60 + s
    end
end
loop do
    n = gets.to_i
    break if n == 0
    log = n.times.map{gets.split.map(&:to_sec)}
    h = Hash.new(0)
    log.each do |l|
        h[l[0]] += 1
        h[l[1]] -= 1
    end
    h = h.sort
    max = 0
    h.each_with_index do |t,i|
        next if i == 0
        h[i][1] += h[i-1][1]
        max = h[i][1] if h[i][1] > max
    end
    p max
end

Measured memory_bytes: 8968
N, M = map(int, input().split())
y_if = {1}
num = [1] * N
for i in range(M):
    x, y = map(int, input().split())
    num[x - 1] -= 1
    num[y - 1] += 1
    if x in y_if:
        if num[x - 1] == 0:
            y_if.remove(x)
        y_if.add(y)
print(len(y_if))


Measured memory_bytes: 53080
#pragma region Template
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define EPS 1e-14
#define FOR(a,b) for (int i=(a);i<(b);i++)
#define REP(n) FOR(0, n)
#define PI 2*acos(0.0)
#define ALL(a) (a).begin(),(a).end()
#define DEBUG(x) cout<<#x <<": "<< x << "\n"
#define DEBUG_ARR(a) REP(i, size(a)){ cout << #a << "[" << i << "]: " << a[i] << "\n"; }
const int VX[] = { 0, 1, 0, -1 };
const int VY[] = { 1, 0, -1, 0 };
const long MOD = 1000000007;

#pragma endregion

int main() {
	//	--- I/O 高速化 ---
	cin.tie(0);
	ios::sync_with_stdio(false);
	// --- ここまで ---

	string a, b, c;
	queue<char> A, B, C;
	cin >> a >> b >> c;
	REP(a.length()) A.push(a[i]);
	REP(b.length()) B.push(b[i]);
	REP(c.length()) C.push(c[i]);

	char turn = 'a';
	while (true) {
		switch (turn)
		{
		case 'a':
			if (A.empty()) {
				cout << "A\n";
				return 0;
			}
			turn = A.front();
			A.pop();
			break;

		case 'b':
			if (B.empty()) {
				cout << "B\n";
				return 0;
			}
			turn = B.front();
			B.pop();
			break;

		case 'c':
			if (C.empty()) {
				cout << "C\n";
				return 0;
			}
			turn = C.front();
			C.pop();
			break;

		default:
			break;
		}


	}

	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200001],ans;
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]),ans^=a[i];
	for(int i=1;i<=n;i++)
	printf("%lld ",ans^a[i]);
    return 0;
}

Measured memory_bytes: 5212
program scoring
    implicit none
    integer(8)::D,C(26),last(26,365),i,j,k,M
    integer(8),allocatable::S(:,:),T(:),V(:),Q(:,:)
    read*,D,C
    allocate(S(26,D))
    allocate(T(D))
    allocate(V(D))
    read*,S,T
    read*,M
    allocate(Q(2,M))
    read*,Q
    
    V=0!各日にちの得点
    last=0

    !初期得点の計算
    do i=1,D
        !前日分を引き継ぎ
        if(i>=2)last(:,i)=last(:,i-1)

        if(i==1)then
            V(i)=V(i)
        else
            V(i)=V(i-1)
        end if
        V(i)=V(i)+S(T(i),i)
        last(T(i),i)=i
        do j=1,26
            V(i)=V(i)-C(j)*(i-last(j,i))
        end do
    end do

    !クエリ処理
    !Q(1,i)日目に行うコンテストをQ(2,i)に変更する 
    do i=1,M
        !lastの書き換え
        if(Q(1,i)==1)then
            last(T(Q(1,i)),1)=0
            last(Q(2,i),1)=1
        else
            last(T(Q(1,i)),Q(1,i))=last(T(Q(1,i)),Q(1,i)-1)
            last(Q(2,i),Q(1,i))=Q(1,i)
        end if
        !日付に対応するコンテストタイプの書き換え
        T(Q(1,i))=Q(2,i)

        !Q(1,i)日目の得点の再計算
        if(Q(1,i)==1)then
            V(Q(1,i))=0
        else
            V(Q(1,i))=V(Q(1,i)-1)
        end if
        V(Q(1,i))=V(Q(1,i))+S(T(Q(1,i)),Q(1,i))
        do j=1,26
            V(Q(1,i))=V(Q(1,i))-C(j)*(Q(1,i)-last(j,Q(1,i)))
        end do

        !Q(1,i)日目以降の得点の再計算
        do j=Q(1,i)+1,D
            last(:,j)=last(:,j-1)
            V(j)=V(j-1)
            V(j)=V(j)+S(T(j),j)
            last(T(j),j)=j
            do k=1,26
                V(j)=V(j)-C(k)*(j-last(k,j))
            end do
        end do
        print'(i0)',V(D)
    end do
end program scoring

Measured memory_bytes: 4868
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i=s;i<e;i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(),(a).end()
typedef long long LL;

int main() {
  int d,g;
  cin>>d>>g;
  vector<int> p(d),c(d);
  REP(i,d) cin>>p[i]>>c[i];
  int ans=1e9;
  REP(i,round(pow(2,d))){
    int tmp=0, s=0, etc=-1;
    REP(j,d){
      if(i&(1<<j)){
        tmp+=p[j];
        s+=p[j]*(j+1)*100+c[j];
      }else{
        etc=j;
      }
    }
    if(s >= g){
      ans=min(ans,tmp);
    }else{
      REP(j,p[etc]){
        s+=(etc+1)*100;
        tmp++;
        if(s >= g){
          ans=min(ans,tmp);
          break;
        }
      }
    }
  }
  cout<<ans<<endl;
      
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        a: i64, b: i64, k: i64,
    }
    let mut a = a;
    let mut b = b;
    let mut k = k;
    let r = min(a, k);
    a -= r;
    k -= r;
    let r = min(b, k);
    b -= r;
    k -= r;
    puts!("{} {}\n", a, b);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
    int A,B,M;
    cin >> A >> B >> M;
    vi a(A); vi b(B); vi x(M); vi y(M); vi c(M);

    rep(i,A) cin >> a[i];
    rep(i,B) cin >> b[i];
    rep(i,M) cin >> x[i] >> y[i] >> c[i];

    vi total_discount(M);
    rep(i,M){
        total_discount[i] = a[x[i] - 1] + b[y[i] - 1] - c[i];
    }

    sort(all(a));
    sort(all(b));
    sort(all(total_discount));
    int total_normal = a[0] + b[0];

    cout << min(total_normal,total_discount[0]) << endl;
    return 0;
}

Measured memory_bytes: 2560
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
k =  int(input())
ans=0
for i in range(k):
     for j in range(k):
          for h in range(k):
               ans += gcd(gcd(i+1,j+1),h+1)
print(ans)

Measured memory_bytes: 73824
var input = '';
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  input += chunk;
});

readable.on( 'end', function() {
  var data = input.split( "\n" );
  var n = data[0];
  var tscore = 0;
  var hscore = 0;
  for( var i=1; i<data.length-1; i++ ) {
    var taha = data[i].split( ' ' );
    if( taha[0] < taha[1] ) {
      hscore += 3;
    } else if( taha[1] < taha[0] ) {
      tscore += 3;
    } else {
      hscore += 1;
      tscore += 1;
    }
  }
  console.log( tscore+' '+hscore );
});

Measured memory_bytes: 8840
def main():
  N, M = map(int, input().split())
  H_l = list(map(int, input().split()))
  best_l = [1] * N
  for i in range(M):
    x_1, y_1 = map(int, input().split())
    x = x_1 - 1
    y = y_1 - 1
    if H_l[x] > H_l[y]:
      best_l[y] = 0
    elif H_l[x] < H_l[y]:
      best_l[x] = 0
    else:
      best_l[x] = 0
      best_l[y] = 0
  print(sum(best_l))
main()

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

int main(){
    ll n; cin >> n;
    map<ll,ll> mp; rep(i,n){
        ll tmp;
        cin >> tmp;
        mp[tmp]++;
    }

    ll m1 = 0, m2 = 0;
    for(auto x:mp){
        if(x.second > 1 && (x.first > m1 || x.first > m2)){
            if(m1 < m2){
                m1 = x.first;
            }else{
                m2 = x.first;
            }
        }
        if(x.second > 3){
            if(x.first > m1){
                m1 = x.first;
            }
            if(x.first > m2){
                m2 = x.first;
            }
        }
    }
    
    put(m1 * m2);
}

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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int N, M;
  cin >> N >> M;

  if (N == M) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
  int n,i,j;
  cin>>n;
  double x[n],y[n],a[n],sum,ans;
  for (i=0;i<n;i++)cin>>x[i];
  for (i=0;i<n;i++)cin>>y[i];
  for (i=0;i<n;i++)a[i]=fabs(x[i]-y[i]);
  for (j=1;j<4;j++){
    for (i=0;i<n;i++)sum+=pow(a[i],j);
    ans=pow(sum,1.0/j);
    cout<<fixed<<ans<<endl;
    sum=0;
  }
  ans=0;
  for (i=0;i<n;i++){
    if (a[i]>ans)ans=a[i];
  }
  cout<<fixed<<ans<<endl;
}



Measured memory_bytes: 3412
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
	int n, m;
	cin >> n >> m;
	priority_queue<ll> que;
	rep(i, n) {
		ll a;
		cin >> a;
		que.push(a);
	}
	rep(i, m) {
		ll a = que.top();
		que.pop();
		a /= 2;
		que.push(a);
	}
	ll ans = 0;
	while(!que.empty()) {
		ans += que.top();
		que.pop();
	}
	cout << ans << endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;

int main() {
	int a, b, c;

	std::cin >> a >> b >> c;

	if (b / a > c) {
		std::cout << c << std::endl;
	}
	else {
		std::cout << b / a << std::endl;
	}
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

struct Edge
{
    int to;
    int col;
    int index;
};

void Main()
{
    int n;
    cin >> n;
    vector<vector<Edge>> g(n);
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].pb({b, -1, i});
        g[b].pb({a, -1, i});
    }

    vint dist(n, -1);
    dist[0] = 0;

    queue<pint> q;
    q.emplace(0, 0);

    while (!q.empty())
    {
        auto v = q.front();
        auto vi = v.first;
        auto vc = v.second;
        q.pop();

        int cnt = 0;
        for (auto &nv : g[vi])
        {
            if (dist[nv.to] != -1)
            {
                continue;
            }
            ++cnt;
            dist[nv.to] = dist[vi] + 1;
            DUMP(cnt);
            DUMP(nv.col);
            if (vc == cnt)
            {
                ++cnt;
            }
            nv.col = cnt;
            DUMP(vi);
            DUMP(vc);
            DUMP(nv.to);
            DUMP(nv.col);
            DUMP(nv.index);
            q.emplace(nv.to, nv.col);
        }
    }

    int mans = 0;
    vector<int> ans(n - 1);
    rep(i, n)
    {
        for (const auto &nv : g[i])
        {
            if (nv.to < i)
                continue;
            ans[nv.index] = (ans[nv.index], nv.col);
            mans = max(ans[nv.index], mans);
        }
    }
    cout << mans << endl;
    rep(i, n - 1)
    {
        cout << ans[i] << 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: 7936
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    string s;
    cin >> s;
    size_t N = s.size();
    string ans;
    REP(i, N)
    {
        if (s[i] == '0')
        {
            ans.push_back('0');
        }
        else if (s[i] == '1')
        {
            ans.push_back('1');
        }
        else
        {
            if (ans.empty()) continue;
            else ans.pop_back();
        }
        
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

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

ll v[55], c[55][55];
signed main(void)
{
	int n, a, b;
	cin >> n >> a >> b;
	REP(i, n) cin >> v[i];
	sort(v, v+n, greater<ll>());

	REP(i, n+1) REP(j, i+1) {
		if(j==0 || j==i) {
			c[i][j] = (ll)1;
		} else {
			c[i][j] = c[i-1][j-1] + c[i-1][j];
		}
	}

	double d = 0;
	REP(i, a) d += v[i];
	d /= a;

	int e=0, f=0;
	REP(i, n) {
		if(v[i] == v[a-1]) {
			e++;
			if(i < a) f++;
		}
	}

	ll cnt = 0;
	if(f==a) {
		FOR(i, a, b+1) cnt += c[e][i];
	} else {
		cnt += c[e][f];
	}

	cout.precision(20);
	cout << fixed << d << endl << cnt << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	ll n, p;
	cin >> n >> p;
	if( n == 1 ){
		cout << p << endl;
		return 0;
	}
	ll ans = 1;
	for( ll i = sqrt(p); i > 1; --i ){
		int cnt = 0;
		while( p % i == 0 ){
			p /= i;
			++cnt;
		}
		if( cnt >= n ){
			ans *= i;
		} else {
			for( int j = 0; j < cnt; ++j ){
				p *= i;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  ll sunuke = 0,araiguma = 0;
  ll ans = 1e20;
  /*cout << ans << endl;*/
  rep(i,n) araiguma += a.at(i);
  rep(i,n-1){
    sunuke += a.at(i);
    araiguma -= a.at(i);
    ans = min(ans,abs(sunuke-araiguma));
  }
  cout << ans << endl;
  return 0;
}





Measured memory_bytes: 1024
import bisect
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29



def main():
    K,N = isRaw()
    As = isRaw()
    ans = K-As[0]-(K-As[-1])
    for aidx in range(len(As)-1):
        ans = min(ans,K-(As[aidx+1]-As[aidx]))
    return ans

if __name__ == "__main__":
    print(main())


Measured memory_bytes: 78792
#include<stdio.h>
#define N 500000				       
void merge(int *,int ,int,int);
void mergeSort(int *,int,int);
int count=0;
int main(){
  int i,n;
  int A[N];
  scanf("%d",&n);
  for(i=0;i<n;i++)   scanf("%d",&A[i]);
 
  mergeSort(A,0,n);

  for(i=0;i<n;i++) {
    if(i>=n-1)printf("%d",A[i]);
    else printf("%d ",A[i]);
  }
  printf("\n");
  printf("%d\n",count);
  
  return 0;
}

void  merge(int *A,int left,int mid,int right){
  int n1,n2,k,i ,j ;
  int L[N],R[N];
  n1 = mid - left;
  n2 = right - mid;
  for(i = 0;i<n1;i++)
    L[i] = A[left + i];
  
  for( i =0;i<n2;i++)
    R[i] = A[mid + i];
 
  L[n1] = 1000000000;
  R[n2] = 1000000000;
  i=0;
  j=0;

  for( k = left;k<right;k++){
    if (L[i] <= R[j]){
      A[k] = L[i];
      i++;
    }
    else{ 
      A[k] = R[j];
      j++;
    }
    count++;
  }
}
void mergeSort(int *A,int left,int right){
  int mid;
  if (left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A,left, mid, right);
  }
  
}

Measured memory_bytes: 4520
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cum = [0] 
for i in range(n):
    cum.append(cum[i] + a[i])
c = Counter(cum)
ans = 0
for v in c.values():
    ans += v * (v - 1)// 2
print(ans)

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

int main(){
    set<char> s;
    rep(i, 3){
        char tmp;
        cin >> tmp;
        s.insert(tmp);
    }
    if (s.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8


def solve(*args: str) -> str:
    x = int(args[0])

    ret = 0
    p = 100
    while p < x:
        p = int(p*1.01)
        ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 9172
s=int(input())
def col(n):
    if n%2==0:
        return n//2
    else:
        return 3*n+1
a=set()
a.add(s)
b=col(s)
count=2
while not b in a:
    a.add(b)
    b=col(b)
    count+=1
print(count)

Measured memory_bytes: 9120
while (line = gets) do
  a, b, c, d, e, f = line.split().map(&:to_f)

  c /= a
  b /= a
  a /= a

  f -= (c * d)
  e -= (b * d)
  d -= (a * d)

  f /= e
  d /= e
  e /= e

  c -= (f * b)
  a -= (d * b)
  b -= (e * b)

  c = (c*(10**3)).round
  c = (c*(10**-3))
  f = (f*(10**3)).round
  f = (f*(10**-3))

  printf("%.3f %.3f\n", c + 0.0, f + 0.0)
end

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

using namespace std;

int main(){
    int n;
    cin>>n;
    string t;
    cin>>t;
    vector<int> s(t.size());
    for (int i = 0; i < t.size(); ++i) {
        s[i]=t[i]-'A';
        s[i]+=n;
        s[i]%=26;
    }
    for (int i = 0; i < t.size()-1; ++i) {
        cout<<(char)('A'+s[i]);
    }
    cout<<(char)('A'+s.back())<<endl;
    return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC085A
{
    class Program
    {
        static void Main(string[] args)
        {
            String s;
            
            s = Console.ReadLine();

            char[] cs = s.ToCharArray();

            cs[3] = '8';

            Console.WriteLine(cs);

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

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

pair<int, pair<int, int>> dp[3010][3010];
string s, t;

int main()
{
	cin >> s >> t;
	
	dp[0][0] = make_pair(0, pair<int, int>(-1, -1));

	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < t.size(); ++j) {
			if (s[i] == t[j]) {
				dp[i + 1][j + 1] = make_pair(dp[i][j].first + 1, make_pair(i, j));
			} else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}

	//cout << dp[s.size()][t.size()].first << endl;

	if (dp[s.size()][t.size()].first == 0) {
		cout << endl;
		return 0;
	}

	string ans = "";

	pair<int, int> cur = dp[s.size()][t.size()].second;

	int cnt = 0;
	do {
		if (s[cur.first] == t[cur.second]) ans += s[cur.first];
		cur = dp[cur.first][cur.second].second;
		cnt++;
		if (cur == make_pair(-1, -1) or cnt == dp[s.size()][t.size()].first) break;
	} while (1);

	reverse(begin(ans), end(ans));

	cout << ans << endl;
}


Measured memory_bytes: 106112
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
using namespace std;

int main(){

	int N,E,limit,tmp,minimum;
	scanf("%d %d",&N,&E);

	limit = pow(2,N);

	int cost[N][N];

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++)cost[i][k] = BIG_NUM;
	}

	int from,to,value;

	for(int i = 0; i < E; i++){
		scanf("%d %d %d",&from,&to,&value);
		cost[from][to] = value;
	}

	int*** dp = new int**[N+1];
	for(int i = 0; i <= N; i++){
		dp[i] = new int*[N];
		for(int k = 0; k < N; k++){
			dp[i][k] = new int[limit];
		}
	}

	minimum = BIG_NUM;
	for(int start = 0; start <= N-1; start++){

		for(int i = 0; i <= N; i++){
			for(int k = 0; k < N; k++){
				for(int p = 0; p < limit; p++)dp[i][k][p] = BIG_NUM;
			}
		}

		tmp = pow(2,start);

		dp[0][start][tmp] = 0;

		for(int i = 1; i <= N; i++){
			for(int k = 0; k < N; k++){
				for(int p = 0; p < limit; p++){
					if(dp[i-1][k][p] != BIG_NUM){
						for(int a = 0; a < N; a++){
							if(p & (1 << a)){
								if(i == N && a == start){
									if(cost[k][start] != BIG_NUM)dp[i][start][limit-1] = min(dp[i][start][limit-1],dp[i-1][k][p]+cost[k][start]);
								}
							}else{
								if(cost[k][a] != BIG_NUM){
									tmp = p + pow(2,a);
									dp[i][a][tmp] = min(dp[i][a][tmp],dp[i-1][k][p]+cost[k][a]);
								}
							}
						}
					}
				}
			}
		}

		minimum = min(minimum,dp[N][start][limit-1]);
	}

	if(minimum == BIG_NUM){
		printf("-1\n");
	}else{
		printf("%d\n",minimum);
	}

}

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

using namespace std;

class DisjointSet {
    public:
        vector<int> rank, p;

        DisjointSet() { }
        DisjointSet(int size) {
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size; i++) makeSet(i);
        }

        void makeSet(int x) {
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x, int y) {
            return findSet(x) == findSet(y);
        }

        void unite(int x, int y) {
            link(findSet(x), findSet(y));
        }

        void link(int x, int y) {
            if (rank[x] < rank[y]) {
                p[x] = p[y];
            } else {
                p[y] = p[x];
                if (rank[x] == rank[y]) {
                    rank[x]++;
                }
            }
        }

        int findSet(int x) {
            while (x != p[x]) {
                x = p[x];
            }
            return p[x];
        }
};

int main(int argc, char const *argv[])
{
    int n, a, b, q;
    int t;

    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);
    for (int i = 0; i < q; i++) {
        cin >> t >> a >> b;
        if (t == 0) ds.unite(a, b);
        else if (t == 1) {
            if (ds.same(a, b)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
using pi = pair<int,int>;

signed main(){
	int q; cin>>q;
	vector<ll> vec(100100);
	rep(i,1,100100){
		vec[i]=vec[i-1];
		if(i%2==0)continue;
		bool ok=true;
		if(i==1)ok=false;
		for(ll j=2;j*j<=i;j++){
			if(i%j==0){
				ok=false;
				break;
			}
		}
		ll k=(i+1)/2;
		if(k==1)ok=false;
		for(ll j=2;j*j<=k;++j){
			if(k%j==0){
				ok=false;
				break;
			}
		}
		if(ok)vec[i]++;
	}
	while(q--){
		ll l,r; cin>>l>>r;
		cout<<vec[r]-vec[l-1]<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 4036
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,A,B;
	int t[1001];
	int ans=0;
	scan(N);scan(A);scan(B);
	rep(i,N){
		scan(t[i]);
		if(t[i]<A||t[i]>=B) ans++;
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 256
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-27 10:46
# @url:https://atcoder.jp/contests/abc164/tasks/abc164_b
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    nums=list(map(int,input().split()))
    a,b,c,d=nums[0],nums[1],nums[2],nums[3]
    if math.ceil(a/d)>=math.ceil(c/b):
        print ("Yes")
    else:
        print ("No")
if __name__ == "__main__":
    main()

Measured memory_bytes: 68392
n,k = map(int,input().split())
h_lst = list(map(int,input().split()))

if n<=k:
    number = 0
elif 0<k<n:
    h_lst.sort()
    number = sum(h_lst)-sum(h_lst[-k:])
elif k==0:
    number = sum(h_lst)

print(number)

Measured memory_bytes: 26024
#include <iostream>

using namespace std;

int gcd(int a, int b)
{
	if (a == 0)
		return b;
	else if (b == 0)
		return a;

	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

int main()
{
	int n;
	cin >> n;
	int a[n + 1];
	a[0] = 0;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int L[n + 1], R[n + 2], m[n + 1];
	L[0] = 0;
	R[n + 1] = 0;

	for (int i = 1; i <= n; i++)
		L[i] = gcd(L[i - 1], a[i]);

	for (int i = n; i >= 1; i--)
		R[i] = gcd(a[i], R[i + 1]);

	for (int i = 1; i <= n; i++)
		m[i] = gcd(L[i - 1], R[i + 1]);

	int max = m[1];
	for (int i = 2; i <= n; i++)
		if (max < m[i])
			max = m[i];

	cout << max << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <stack>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

// range-add, range-min query

struct SegTree{
	int size;
	vector<llint> seg, delay;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
		delay.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++){
			seg[i] = -inf;
			delay[i] = 0;
		}
	}
	
	void eval(int l, int r, int k)
	{
		if(delay[k]){
			seg[k] += delay[k];
			if(l < r){
				delay[k*2] += delay[k];
				delay[k*2+1] += delay[k];
			}
			delay[k] = 0;
		}
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = max(seg[i*2], seg[i*2+1]);
		}
	}
	
	void add(int a, int b, int k, int l, int r, llint val)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return;
		if(a <= l && r <= b){
			delay[k] += val;
			eval(l, r, k);
			return;
		}
		add(a, b, k*2, l, (l+r)/2, val);
		add(a, b, k*2+1, (l+r)/2+1, r, val);
		seg[k] = max(seg[k*2], seg[k*2+1]);
	}
	void add(int a, int b, llint val){
		if(a > b) return;
		add(a, b, 1, 0, (1<<size)-1, val);
	}

	llint query(int a, int b, int k, int l, int r)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return -inf;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return max(lval, rval);
	}
	llint query(int a, int b)
	{
		if(a > b) return 0;
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

llint w, h, n;
llint x[300005], y[300005];
SegTree seg(19);

llint calc()
{
	vector<P> vec;
	for(int i = 1; i <= n; i++) vec.push_back(make_pair(x[i], y[i]));
	sort(vec.begin(), vec.end());
	if(vec.front().first > 0) vec.insert(vec.begin(), make_pair(0, h/2));
	if(vec.back().first < w) vec.push_back(make_pair(w, h/2));
	
	llint ret = 0;
	for(int i = 1; i < vec.size(); i++) ret = max(ret, vec[i].first-vec[i-1].first + h);
	seg.init();
	for(int i = 0; i < vec.size(); i++) seg.update(i, -vec[i].first);
	
	stack<P> stk[2];
	stk[0].push(make_pair(-inf, 0)), stk[1].push(make_pair(-inf, 0));
	for(llint i = 1; i < vec.size(); i++){
		for(int j = 0; j < 2; j++) seg.add(stk[j].top().second, i-1, h/2);
		ret = max(ret, seg.query(0, i-2) + vec[i].first);
		for(int j = 0; j < 2; j++) seg.add(stk[j].top().second, i-1, -h/2);
		int side;
		if(vec[i].second >= h/2) side = 0;
		else side = 1;
		llint val = abs(vec[i].second - h/2);
		while(stk[side].size() && stk[side].top().first >= val){
			llint l, r = stk[side].top().second - 1, v = stk[side].top().first;
			stk[side].pop();
			l = stk[side].top().second;
			seg.add(l, r, -v);
		}
		int l = stk[side].top().second, r = i-1;
		seg.add(l, r, val);
		stk[side].push(make_pair(val, i));
	}
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> w >> h >> n;
	w *= 2, h *= 2;
	
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i], x[i] *= 2, y[i] *= 2;
	llint ans = calc();
	
	swap(h, w);
	for(int i = 1; i <= n; i++) swap(x[i], y[i]);
	ans = max(ans, calc());
	
	cout << ans << endl;
	return 0;
}

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

int main(){
	int up, front, side, sum, n;
	string com;
	while(1){
		cin >> n;
		if( n == 0 )	break;
		up = 1;
		front = 2;
		side = 3;
		sum = 1;
		for( int i=0; i<n; i++ ){
			cin >> com;
			int nup, nfront, nside;
			if( com == "North" ){
				nup = front;
				nfront = 7 - up;
				nside = side;
			}else if( com == "East" ){
				nup = 7 - side;
				nfront = front;
				nside = up;
			}else if( com == "South" ){
				nup = 7 - front;
				nfront = up;
				nside = side;
			}else if( com == "West" ){
				nup = side;
				nfront = front;
				nside = 7 - up;
			}else if( com == "Right" ){
				nup = up;
				nfront = side;
				nside = 7 - front;
			}else if( com == "Left" ){
				nup = up;
				nfront = 7 - side;
				nside = front;
			}
			up = nup;
			front = nfront;
			side = nside;
			sum += up;
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 0
from functools import lru_cache


N = int(input())
MOD = 10**9+7


def ok(last4):
    for i in range(4):
        t = list(last4)
        if i > 0:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') > 0:
            return False
    return True


@lru_cache(maxsize=1000)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(last3 + c):
            ret += dfs(cur+1, last3[1:] + c)
            ret %= MOD
    return ret


print(dfs(0, 'TTT'))


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

int main() {
  string S;
  cin >> S;
  bool is_good = true;
  for (int i = 0; i < 3; i++) {
    if (S.at(i) == S.at(i+1)) is_good = false;
  }
  if (is_good) cout << "Good" << endl;
  else cout << "Bad" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    String ans = "second";
    for (int i = 0; i < N; i++) {
      if (a[i] % 2 == 1) {
        ans = "first";
      }
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 49996
#include<stdio.h>
#include<math.h>

int main(void){
  
  int  x,h;
  double high;

  while(1){
    scanf("%d %d",&x,&h);
    if(!x && !h)break;

    high = sqrt( x/2.0 * x/2.0 + h*h);

    printf("%lf\n",x*x + 2*high*x);
  }

  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
const int INF = 1LL<<30;

int main(){
    int n,q;
    string S;
    cin>>n>>q>>S;
    vector<int> a(n,0);
    for(int i=1;i<n;i++){
        if(S[i-1]=='A' && S[i]=='C'){
            a[i]=1;
        }
    }

    vector<int> s(n+1,0);
    rep(i,n) s[i+1]=s[i]+a[i];

    rep(i,q){
        int l,r;
        cin>>l>>r;
        l--;
        int ans=s[r]-s[l];
        if(l>=1){
            if(S[l-1]=='A' && S[l]=='C') ans--;
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 4332
#include <bits/stdc++.h>
using namespace std;
int k,w,a[20]; 

void nextLunlun(){
	if(w>1&&a[0]>a[1])swap(a[0],a[1]);
	else{
		int i=0;
		while(i<w&&a[i]==9){
			a[i]=0;
			i++;
		}
		a[i]++;
		if(i==w)w++;
		for(int j=i-1;j>=0;j--)a[j]=max(0,a[j+1]-1);
	}
	int p=w;
	for(int i=0;i<w-1;i++){
		if(a[i]-a[i+1]>1){
			a[i+1]++;
			p=i;
		}
	}
	if(p!=w){
		for(int i=p;i>=0;i--)a[i]=max(0,a[i+1]-1);
	}
}
int main(){
	cin>>k;
	a[0]=1;
	w=1;
	for(int i=1;i<k;i++){
		nextLunlun();
	}
	for(int i=w-1;i>=0;i--)cout<<a[i];
	return 0;
}


Measured memory_bytes: 256
from heapq import heappush, heappop

N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
c = list(map(int, input().split()))

INF = 10**10
G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
dp2 = dict()

for x, (_, z) in zip(
    sorted(c), sorted(zip(dp[1:], range(1, N + 1)), reverse=True)
):
    dp2[z] = x

ans = 0
for x, y in zip(a, b):
    ans += min(dp2[x], dp2[y])
print(ans)
ans2 = ' '.join(
    str(dp2[i])
    for i in range(1, N + 1)
)
print(ans2)


Measured memory_bytes: 10200
#include<stdio.h>

#define N 2000

int search(int c,int x);
int n,q;
int A[N],M[N];
int t;


int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
	}

		scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&M[i]);
	}

	for(i=0;i<q;i++){
		t=0;
		search(-1,M[i]);
		if(t==1){
			printf("yes\n");
		}
		else{
			printf("no\n");
		}
	}

	return 0;
}

int search(int c,int x){
	if (c>n)return 0;
	else if(x<0)return 0;
	else if(x==0 || x-A[c]==0){
		t=1;
		return 1;
	}
	else{
		search(c+1,x);
		search(c+1,x-A[c]);
	}

}

Measured memory_bytes: 588