akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main()
{
    int n,a,b,c;
    while(cin>>n>>a>>b)
    {
        c=b-a;
        if(c<0)c=-1*c;

        if(c%2==0) cout<<"Alice"<<endl;
        else cout<<"Borys"<<endl;

    }
    return 0;
}


Measured memory_bytes: 256
func main() {
    let abck = readLine()!.split(separator: " ").map {Int($0)!}
    let (A, B, C, K) = (abck[0], abck[1], abck[2], abck[3])
    // a + b + c = k, a > b > c
    var total: Int
    total = min(K, A) * 1
    if K > A {
        total += min(K-A, B) * 0
        if K - A > B {
            total += (K - A - B) * -1
        }
    }
    print(total)
}

main()


Measured memory_bytes: 8176
#include<iostream>
using namespace std;
#define endl "\n"
int main(int argc, char const *argv[])
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a==5&&b==7&&c==5||a==5&&b==5&&c==7||a==7&&b==5&&c==5)
     cout<<"YES"<<endl;
    else
     cout<<"NO"<<endl;
	return 0;
}

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

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

    vector<int>a(n);
    rep(i,0,n){
        cin>>a[i];
    }

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

    int minimum=4000000;

    for (int i=a[0];i<=a[n-1];i++) {
        int sum=0;
        for(int j=0;j<n;j++){
            sum+=pow((a[j]-i),2);
        }
        minimum=min(minimum,sum);
    }
    cout<<minimum<<endl;
}

Measured memory_bytes: 256
while True:
    w, h = map(int, input().split())
    if not w and not h:
        break

    n = int(input())
    constructions = set(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n))

    patterns = [[0] * w for _ in range(h)]
    patterns[0][0] = 1
    for j in range(1, w):
        if (j, 0) in constructions:
            break
        patterns[0][j] = 1
    for i in range(1, h):
        if (0, i) in constructions:
            break
        patterns[i][0] = 1
    for i in range(1, h):
        for j in range(1, w):
            if (j, i) in constructions:
                continue
            patterns[i][j] = patterns[i - 1][j] + patterns[i][j - 1]
    print(patterns[-1][-1])

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


void solve(std::string X, std::string Y){
    if(X < Y) cout << "<" << endl;
    if(X == Y) cout << "=" << endl;
    if(X > Y) cout << ">" << endl;
}

int main(){
    std::string X;
    std::cin >> X;
    std::string Y;
    std::cin >> Y;
    solve(X, Y);
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< int, int > pii;

const double pi = 3.14159265358979323846;

// #define fio() cin.tie(0); ios::sync_with_stdio(false);
// template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
// template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos
// 1e18

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

  long double a, b, c;
  cin >> a >> b >> c;
  long double eps = 1e-14;

  if (sqrt(a) + sqrt(b) + eps < sqrt(c)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int a=scan.nextInt(),b=scan.nextInt(),c=scan.nextInt();
double d=0,ans1=1000;
int ans=0;
for(int i=0;i!=a;i++) {
d=scan.nextInt();
d=b-(d*0.006);
d-=c;
if(d<0) {d*=-1;}
if(d<ans1) {ans1=d;ans=i+1;}
}
System.out.println(ans);
}
}

Measured memory_bytes: 23508
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int count = stdIn.nextInt();
		List<Integer> l = new ArrayList<>();

		for(int i = 0; i < count; i++){
			int command = stdIn.nextInt();

			switch(command){
				case 0:
					l.add(stdIn.nextInt());
					break;

				case 1:
					System.out.println(l.get(stdIn.nextInt()));
					break;

				case 2:
					l.remove(l.size() - 1);
					break;
			}

		}

		stdIn.close();
	}
}


Measured memory_bytes: 140912
import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long N = scanner.nextLong(); // Items
    long M = scanner.nextLong(); // Discount tickets

    PriorityQueue<Long> queue = new PriorityQueue<>();
    while (scanner.hasNextInt()) {
      long price = scanner.nextInt();
      // Use the negative version because PriorityQueue is a min heap!
      queue.add(-price);
    }

    while (M-- > 0) {
      long negativePrice = queue.poll();
      queue.add(negativePrice / 2);
    }

    long totalPrice = 0;
    for (long negativePrice : queue) {
      long price = -negativePrice;
      totalPrice += price;
    }

    System.out.println(totalPrice);
  }
}


Measured memory_bytes: 62008
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx
# from bisect import bisect_left,bisect_right
k=n0()
s=s0()
if len(s)<=k:
    print(s)
else:
    print(f"{s[:k]}...")

Measured memory_bytes: 9204
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

//-----------------------ここから-----------

int main(void){
    int N, K;
    cin >> N >> K;
    
    vector<int> balls(N);
    for(int i = 0; i < N; i++){
        cin >> balls[i];
    }
    
    int backet[200100] = {0};
    
    for(int i = 0; i < N; i++){
        backet[balls[i]]++;
    }
    
    int numOfBallType = 0;
    vector<int> numOfBallList;
    for(int i = 0; i < 200100; i++){
        if(backet[i]){
            numOfBallType++;
            numOfBallList.push_back(backet[i]);
        }
    }
    
    sort(numOfBallList.begin(), numOfBallList.end());
    
    int gap = numOfBallType - K;
    
    
    int ans = 0;
    for(int i = 0; i < gap; i++){
        ans += numOfBallList[i];
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 2936
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner inp = new Scanner(System.in);
int w = inp.nextInt();
int h = inp.nextInt();
int x = inp.nextInt();
int y = inp.nextInt();
int r = inp.nextInt();

int indikator = 0;
int xplus = x+r;
int xmin = x-r;
int yplus = y+r;
int ymin = y-r;

if ((xplus>w)||(xplus<0))
indikator = 1;
if ((xmin>w)||(xmin<0))
indikator = 1;
if ((yplus>h)||(yplus<0))
indikator = 1;
if ((ymin>h)||(ymin<0))
indikator = 1;

if (indikator == 1)
System.out.println("No");
else 
System.out.println("Yes");

}
}


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

using namespace std;

using ll = long long;
using ld = long double;
using li = __int128;
using uli = unsigned __int128;

#define fi first
#define se second

template <typename T> void s_min(T& a, T b) {
	if (a > b) a = b;
}

template <typename T> void s_max(T& a, T b) {
	if (a < b) a = b;
}

int main() {
	ios_base::sync_with_stdio(0);

	int N, W;
	cin >> N >> W;
	vector<int> w(N + 1), v(N + 1);
	for (int i = 1; i <= N; i++) cin >> w[i] >> v[i];
	vector<vector<ll>> dp(N + 1, vector<ll> (W + 1, 0));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			dp[i][j] = dp[i - 1][j];
			if (w[i] > j) continue;
			s_max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	cout << dp[N][W];

	return 0;
}

Measured memory_bytes: 83180
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;

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

    int sm = 0;
    for(int i = 0; i < M; ++i) sm += A[i];
    
    if(N >= sm) cout << N-sm << endl;
    else cout << -1 << endl;

}

Measured memory_bytes: 3632
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

long long n,a[300010]={0},mx=-100000000000,s=0;
long long p[100010]={0};//,m[300010]={0};
priority_queue<long long,vector<long long>,greater<long long>>q;
priority_queue<long long,vector<long long>> qq;

signed main(){
    cin>>n;
    for(int i=0;i<3*n;++i){
        cin>>a[i];
        if(i<n){
            q.push(a[i]);
            s+=a[i];
        }
    }
    p[0]=s;
    for(int i=n;i<2*n;++i){
        s+=a[i];
        q.push(a[i]);
        s-=q.top();
        q.pop();
        p[i+1-n]=s;
    }

    
    s=0;
    for(int i=3*n-1;i>=2*n;--i){
        s+=a[i];
        qq.push(a[i]);
    }
    mx=p[n]-s;
    for(int i=2*n-1;i>=n;--i){
        s+=a[i];
        qq.push(a[i]);
        s-=qq.top();
        qq.pop();
        mx=max(mx,p[i-n]-s);
    }
    

    cout<<mx<<endl;

    return 0;
}

Measured memory_bytes: 5748
#include <stdio.h>

#define H 500000

int left(int i) {return i*2;}
int right(int i) {return i*2 + 1;}

int n,A[H+1];

void maxHeapify(int i){
  int l,r,largest,tmp;

  l = left(i);
  r = right(i);
  if(l<=n && A[l] > A[i]) largest = l;
  else largest = i;
  if(r<=n && A[r] > A[largest]) largest = r;


  if(largest != i){
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(largest);
  }
}

int main(){

  int i,j;

  scanf("%d",&n);

  for(i=1;i<=n;i++) scanf("%d",&A[i]);

  for(j=n/2;j>=1;j--) maxHeapify(j);

  for(i=1;i<=n;i++) printf(" %d",A[i]);

  printf("\n");
  return 0;
}


Measured memory_bytes: 3652
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する


int main() {
    string s;
    string g;
    cin >> s;
    vector<int> v;
    int cnt = 0;
    REP(i, 0, s.size()) {
        if (s[i] == 'x') {
            cnt++;
        } else {
            v.push_back(cnt);
            cnt = 0;

            g += s[i];
        }
        if(i == s.size() - 1){
            v.push_back(cnt);

        }
    }

    string gr = g;
    reverse(gr.begin(), gr.end());
    if (gr != g) {
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 0; v.size() - 1 - i > i; i++) {
        ans += abs(v[v.size() - 1 - i] - v[i]);
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

const int N = 100;

int a[1 + N], b[1 + N], c[1 + N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i < n; i++)
        cin >> c[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 1 && a[i] == a[i - 1] + 1)
            ans += c[a[i - 1]];
        ans += b[a[i]];
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
h1=A[:N]
L=[0 for i in range(N+1)]
L[0]=sum(h1)
sum1=sum(h1)
import heapq
heapq.heapify(h1)
for i in range(N):
  heapq.heappush(h1,A[N+i])
  a=heapq.heappop(h1)
  sum1=sum1+A[N+i]-a
  L[i+1]=sum1
h=A[2*N:]
h2=[-i for i in h]
R=[0 for i in range(N+1)]
R[N]=-sum(h2)
sum2=-sum(h2)
heapq.heapify(h2)
for i in range(N):
  heapq.heappush(h2,-A[2*N-1-i])
  a=heapq.heappop(h2)
  sum2=sum2+A[2*N-1-i]+a
  R[N-i-1]=sum2
import math
ans=-math.inf
for i in range(N+1):
  ans=max(ans,L[i]-R[i])
print(ans)

Measured memory_bytes: 112820
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        String t = sc.next();

        for(int i = 0; i<n; i++) {
            System.out.print(s.charAt(i));
            System.out.print(t.charAt(i));
        }
        System.out.println();
            

    }
}

Measured memory_bytes: 21716
import java.util.*;

public class Main{
	final static int MOD = 1000000007;
	final static int INF = 1000000000;
	
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int ans = -2 * INF, minv = 2 * INF;
		for(int i = 0; i < n; ++i){
			int R = Integer.parseInt(sc.next());
			ans = Math.max(ans, R - minv);
			minv = Math.min(minv, R);
		}
		sc.close();
		System.out.println(ans);
	}
	
}



Measured memory_bytes: 70880
using System;
using static System.Console;
using System.Linq;

namespace AC
{
   public class shiokara
   {
      static void Main(string[] args)
      {
         int N = int.Parse(ReadLine());
         int curX = 0, curY = 0, nextX = 0, nextY = 0;
         int curT = 0, nextT = 0;
         int move = 0, time = 0;
         for(int i = 0; i < N; i++){
            int[] tmp = ReadLine().Split(' ').Select(int.Parse).ToArray();
            nextT = tmp[0]; nextX = tmp[1]; nextY = tmp[2];
            move = abs(curX, nextX) + abs(curY, nextY);
            time = abs(curT, nextT);
            if(time % move != 0 || move - time > 0){
               WriteLine("No");
               return;
            }
            curX = nextX; curY = nextY; curT = nextT;
         }
         WriteLine("Yes");
      }

      static int abs(int a, int b){
         if(a > b) return a - b;
         else return b - a;
      }
   }
}

Measured memory_bytes: 17448
import scala.collection.mutable.HashMap
import scala.collection.mutable.ArrayBuffer

object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  val d  = inputs(0).toInt // 365
  val ci = inputs(1).split(" ").map(_.toInt)
  val sdi = HashMap.empty[Long, Seq[Long]]
  // 日付ごとに、満足度の配列を持つ
  inputs.splitAt(2)._2.zipWithIndex.foreach { case (line, index) =>
    sdi.update(index, line.split(" ").map(_.toLong))
  }

  solve(d, ci, sdi)

  // 1. 単純にでかい数を持っているものを抽出
  // 2. 減少分と上昇分を考慮して最大になる物を選ぶ
  def solve(d: Int, ci: Array[Int], sdi: HashMap[Long, Seq[Long]]): Unit = {
    val last = ArrayBuffer.fill(26)(1)
    var score = 0L
    val range = Range(0, 26, 1)

    (0 until d).foreach { day =>
      val todayValues = sdi(day)
      val max = todayValues.max
      // println(s"max value = $max")
      // TODO: 同じ数値のものが複数ある可能性を考慮
      val maxIndexes = range.map { i =>
        if (max == todayValues(i)) {
          i
        } else {
          -1
        }
      }.filter(v => v != -1)

      val minCiOfTopValue = maxIndexes.map(v => ci(v)).min
      val minCiOfTopValueIndex = range.filter(i => maxIndexes.exists(_ == i) && ci(i) == minCiOfTopValue).min

      // println(s"selected: $i")
      println(minCiOfTopValueIndex + 1)

      last.update(minCiOfTopValueIndex, d)
      score = score + max - range.map(i => ci(i) * (day - last(i)) ).sum
      // println(s"score: $score")
    }

  }

}

Measured memory_bytes: 61716
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>



using namespace std;

int main() {
   

    long long n;
    cin >> n;
    long long F[50];
    F[0] = F[1] = 1;
    for (int i=2;i<=n;i++){
        F[i] = F[i-1] + F[i-2];
    }
    cout << F[n] << endl;


}


Measured memory_bytes: 3124
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	long long a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << max(a*b,c*d);
}

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

using namespace std;

int main(){

  int N, T, A, answer=0;
  int H[1001];
  double diff_target = 200.0, diff[1001];

  cin >> N >> T >> A;

for (int i = 0; i < N; i++) {
  cin >> H[i];
}

for(int i = 0; i < N; i++){
  diff[i] = abs(T - H[i]*0.006 - A);
  diff_target = diff[answer];
    if(diff[i] < diff_target)
      answer = i;
}
  cout << answer+1 << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
	char a, b;
	scanf("%c %c", &a, &b);
	if(a < b){
		printf("<");
		}
		if(a > b){
			printf(">");
			}
			if(a == b){
				printf("=");
				}
	}

Measured memory_bytes: 128
def is_kaibun(string):
    for i in range(int(len(string)/2)):
        if string[i] != string[-i-1]:
            return False
    return True

s = input()
n = int(len(s)/2)

s1 = s[:n]
s2 = s[n+1:]
s2 = s2[::-1]

if is_kaibun(s) == True:
  if is_kaibun(s1) == True:
    if is_kaibun(s2) == True:
      print('Yes')
    else:
      print('No')
  else:
    print('No')
else:
  print('No')

Measured memory_bytes: 3064
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include <ctime>
#include<list>
#include <numeric>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include <array>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(int i = 0; i < n; i++)
#define FORAB(i, a, b) for(int i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))
#define AIN(A, B, C) assert(IN(A, B, C))

typedef long long int LL;
//typedef __int128 LLL;
typedef long long LLL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VP;
typedef vector<double> VD;
typedef vector<vector<int>> VVI;
typedef vector<string> VS;
typedef long double ld;

#define MAXN 1000006
//#define MAXN 1006

const LL MOD = 1000000007;
//const LL MOD = 998244353;
const LL INF = 2000000000000000001LL; //2e18 + 1

LL Calc(VI& A) {
	int n = SZ(A);
	VL max_node(n + 1, 0);
	LL cur = 1;
	max_node[0] = 1;
	for (int i = 0; i < n; i++) {
		cur -= A[i];
		if (cur < 0) return -1;
		cur = max_node[i + 1] = MIN(2 * cur, 200000000000000LL);
	}

	cur = 0;
	LL ret = 0;
	for (int i = n - 1; i >= 0; i--) {
		cur += A[i];
		cur = max_node[i] = MIN(cur, max_node[i]);
		ret += max_node[i];
	}
	return ret;
}

void solve(int ks) {
	int n;
	scanf("%d", &n);
	VI A(n + 1, 0);
	for (int i = 0; i <= n; i++) scanf("%d", &A[i]);
	LL ans = Calc(A);
	printf("%lld\n", ans);
}

void gen() {
}

int main()
{
	double start_time = clock();
#ifdef LOCAL
	freopen("C:\\Home\\ContestCodes\\sample.in", "r", stdin);
	// freopen("C:\\Home\\ContestCodes\\sample.in", "r", stdin);
	//	freopen("out.out", "w", stdout);
#endif

	gen();

	if (0) {
		int T;
		scanf("%d", &T);
		//AIN(T, 1, 5000);
		for (int ks = 1; ks <= T; ks++) {
			solve(ks);
			if (ks % 1 == 0) fprintf(stderr, "%d done\n", ks);
		}
	}
	else {
		solve(0);
	}

	double end_time = clock();
	fprintf(stderr, "Time = %lf\n", (end_time - start_time) / CLOCKS_PER_SEC);

	return 0;
}


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

int main(){
    int n,m;
    cin >>n>>m;
    
    vector<vector<int>> connect(n);
    int a,b;
    
    rep(i,m){
        cin >> a >> b;
        connect[a-1].push_back(b-1);
        connect[b-1].push_back(a-1);
    }
    
    vector<int> reach(n,-1);
    reach[0]=0;
    
    queue<int> q;
    q.push(0);
    
    while(!q.empty()){
        for(int i : connect[q.front()]){
            if(reach[i]==-1){
                reach[i] = q.front();
                q.push(i);
            }
        }
        q.pop();
    }
    
    cout << "Yes" << endl;
    for(int i=1; i<n; i++){
        cout << reach[i]+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 10192
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 1; i < n; i++){
    cin >> a[i];
  }
  vector<int> b(n);
  for(int i = 1; i < n; i++){
    b[a[i]]+=1;
  }
  for(int i = 1; i < n; i++){
    cout << b[i] << endl;
  }
  cout << "0" << endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<long> line(n);
  
  for (int i = 0; i < n; i++) {
    if (((i + 1) % 15) == 0) {
      line.at(i) = 0;
    } else if (((i + 1) % 3) == 0) {
      line.at(i) = 0;
    } else if (((i + 1) % 5) == 0) {
      line.at(i) = 0;
    } else {
      line.at(i) = i + 1;
    };
  };
  long sum = 0;
  for (int i = 0; i < n; i++) {
    sum = sum + line.at(i);
  }
  cout << sum;
}


Measured memory_bytes: 11016
#include <iostream>

using namespace std;

int main() {
    int temp;
    int sum[2];
    for(int i = 0; i<2; i++) {
        sum[i] = 0;
        for(int j=0; j<4; j++) {
            cin >> temp;
            sum[i] += temp;
        }
    }

    if( sum[0] > sum[1] ) cout << sum[0] << endl;
    else cout << sum[1] << endl;

    return 0;
}







Measured memory_bytes: 3076
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int n,a[100001],dp[100001];

int main()
{Tie
	cin>>n;
	a[0]=-1000000000;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int j=2;j<=n;j++)
		dp[j]=min(dp[j-1]+abs(a[j-1]-a[j]),dp[j-2]+abs(a[j-2]-a[j]));
	cout << dp[n]<<'\n';
}

Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N = INT()
	total = N
	cnt = 0
	for i in range(1, N+1):
		if i%2: cnt += 1
	
	print(cnt/total)

if __name__ == '__main__':
	main()

Measured memory_bytes: 3064
fn main() {
    let v = read_vec::<u64>();
    let h = v[0];
    let w = v[1];
    if h != 1 && w != 1 {
        println!("{}", (h * w + 1) / 2);
    } else {
        println!("1");
    }
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<class U, class V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}

int main() {
	int a; cin >> a;
	string s; cin >> s;
	if(a >= 3200) cout << s << "\n";
	else cout << "red\n";
}

Measured memory_bytes: 256
n = int(input())
ans = [0] * n
for i in range(1,n+1):
    j = i-1
    while j < n:
        ans[j] += 1
        j += i
k = 0
for i in range(0,n,2):
    if ans[i] == 8:
        k += 1
print(str(k))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int mxn=2e5+1;
ll fac[mxn],inv[mxn];
ll p(ll a,ll n)
{
  ll ans=1;
  while(n)
  {
    if(n&1)
      ans=(ans*a)%mod;
    a=(a*a)%mod;
    n=n>>1;
  }
  return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

  int t=1;
//  cin>>t;
  int tt=1;
  while(t--){
    ll n,k,i;
    cin>>n>>k;
    fac[0]=1;
    fr(i,1,mxn)
    fac[i]=(fac[i-1]*i)%mod;
    fr(i,0,mxn)
    inv[i]=p(fac[i],mod-2);
    fr(i,1,k+1)
    {
      ll blue;
      blue=(fac[k-1]*inv[i-1])%mod;
      blue*=inv[k-i];
      blue%=mod;
      if(i-1>n-k)
      {
        cout<<0<<"\n";
        continue;
      }
      ll red=(fac[n-k+1]*inv[i])%mod;
      red*=inv[n-k-i+1];
      red%=mod;
      ll temp=(blue*red)%mod;
     // cout<<blue<<" "<<red<<" "; 
      cout<<temp<<"\n";
   // cout<<"Case #"<<tt<<": ";
   // tt++;
    }
    }
  return 0;
}



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

string op;

bool check(int lef,int rig)
{
  if(lef == -1 || rig == -1)
    return true;

  lef %= 3,rig %= 3;
  if(lef == 0 && (rig == 1 || rig == 2))
    return false;
  else if(lef == 2 && rig == 1)
    return false;
 
  return true;
}

int Do(bool step)
{
  if(op.size() <= 1)
    return 0;

  int res = 0;
  int l,r,pl,pr;
  l = r = pl = pr = -1;
  for(int i=0;i<op.size();i++)
    {
      if(!step)
	l = op[i]-'0',step = !step;
      else 
	r = op[i]-'0',step = !step;

      if(!check(l,r))
	{
	  if(step)
	    r = l,l = pl;
	  else
	    l = r,r = pr;
	  step = !step;
	  res++;
	}
      pr = r, pl = l;
    }
  return res;
}

int main()
{
 
  while(cin >> op, op != "#")
    cout << min(Do(1),Do(0)) << endl;
    
  return 0;
}

Measured memory_bytes: 1316
import java.util.Scanner;

public class Main {
    public static void main(String... args) {
        // 入力
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();

        int div = 0;
        if (a > b) div = b;
        else div = a;

        for (int i = div; i > 0; i--) {
            if (a % i == 0 && b % i == 0) {
                k--;
                if (k == 0) System.out.println(i);
            }
        }
    }
}

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

#define pi acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define sf scanf
#define pf printf
#define nl printf("\n")
#define ps(s) printf("%s",s.c_str())
#define	inf (ll)1e15
#define mod 1000000007
#define mem(x,val) memset(x,val,sizeof x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend() 
#define sz(x) (int)(x).size()
#define test_case int ___t;scanf("%d", &___t);for(int cs=1;cs<=___t;cs++)

using namespace __gnu_pbds;
using namespace std;

inline string str_inp(int n){char ch[n+5];sf(" %s",ch);return string(ch);}
inline string line_inp(int n)
{char ch[n+5];fgets(ch,n+5,stdin);string s=string(ch);s.pop_back();return s;}

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;


const int S=200100;
int main()
{
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //#endif
	int n,m;
	while(~sf("%d %d",&n,&m))
	{
		int a[m+5],b[m+5],c[m+5],dis[n+5][n+5];


		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i==j)dis[i][j]=0;
				else dis[i][j]=100000000;
			}
		}

		for(int i=1;i<=m;i++)
		{
			sf("%d %d %d",&a[i],&b[i],&c[i]);
		}

		for(int i=1;i<=m;i++)
		{
			dis[a[i]][b[i]]=min(dis[a[i]][b[i]],c[i]);
			dis[b[i]][a[i]]=min(dis[b[i]][a[i]],c[i]);
		}

		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
				{
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				}
			}
		}

		int ans=m;
		for(int i=1;i<=m;i++)
		{
			bool has=false;
			for(int j=1;j<=n;j++)
			{
				if(dis[j][a[i]]+c[i]==dis[j][b[i]])has=true;
			}
			if(has)ans--;
		}
		pf("%d\n",ans);
	}
    return 0;
}
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    long long int a;
    cin>>n;
    int K=0,G=0;
    for (int i=0;i<n;i++) {
        cin>>a;
        if (a%2==0) {
            G++;
        } else {
            K++;
        }
    }
    if (K%2==1) {
        cout<<"NO"<<endl;
    } else {
        cout<<"YES"<<endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
using namespace std;

string s;
int n;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
   cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
 cin>>s;
 n=stoi(s);
 int m=s.size();
 int sum=0;
 for(int i=0;i<m;i++){
  sum+=s[i]-'0';
 }
 if(n%sum==0){
  cout<<"Yes"<<"\n";
 }else cout<<"No"<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

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

using namespace std;

void trace(int a[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( i > 0 ) printf(" ");
    printf("%d", a[i]);
  }
  printf("\n");
}

int main(void){

  int n;
  int a[1001];
  cin >> n;
    for( int i = 0 ; i < n ; i++ ) // read
      cin >> a[i];
  
  for( int i = 1 ; i < n ; i++ ){
    int temp = a[i];
    trace(a , n);
    if( a[i - 1] > temp ){ // ?????????????????則??????
      int j = i;
      do{
	a[j] = a[j - 1];
	j--;
      } while( j > 0 && a[j - 1] > temp );
      a[j] = temp;
    }
  }
  for( int i = 0 ; i < n ; i++ ){
    if( i > 0 ) cout << " "; 
    cout << a[i];
  }
  cout << endl; 
  return 0;
}

Measured memory_bytes: 1200
import math

def solve(x):
    init_money = 100

    i = 0
    while True:
        i += 1
        init_money = math.floor(init_money * 1.01)
        if init_money >= x:
            break
    return i
if __name__ == "__main__":
    x = int(input())
    print(solve(x))

Measured memory_bytes: 9176
#include <iostream>
using namespace std;
int main(void){
    int n;
    int A[100+1];
    int B[100];
    int mini, ans, a, i;
    
    a = 1000000; 
    
    cin >> n;
    
     for(i=0; i < n; ++i){
        A[i] = -1;
    }
    
    for(i=0; i < n-1; ++i){
        cin >> B[i];
    }
    
    for(i=0; i < n-1; ++i){
        int minc = a;
        for(int j = 0; j < n-1; ++j){
            if(B[j] < minc){
                minc = B[j];
                mini = j;
            }
        }
        if(A[mini] == -1){
            A[mini] = B[mini];
        }
        if(A[mini+1] == -1){
            A[mini+1] = B[mini];
        }
        B[mini] = a;
    }
    
    ans = 0;
    
    for(int i = 0; i < n; ++i){
        ans += A[i];
    }
    
    cout << ans;
    
    return 0;
    
}

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

void solve(int n, int m, int k) {
    vector<vector<double> > dp(n + 1, vector<double>(n * m + 1, 0.0));
    dp[0][0] = 1.0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n * m; j++) {
            for (int k = 1; k <= m; k++) {
                if (j - k < 0) continue;
                dp[i][j] += dp[i - 1][j - k] / m;
            }
        }
    }
    vector<double> ans(n * m - k + 1, 0.0);
    for (int i = 1; i <= n * m; i++) {
        ans[max(1, i - k)] += dp[n][i];
    }
    double res = 0.0;
    for (int i = 1; i <= n * m - k; i++) {
        res += i * ans[i];
    }
    cout << fixed << setprecision(8);
    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, K;
    while (true) {
        cin >> N >> M >> K;
        if (N == 0 && M == 0 && K == 0) break;
        solve(N, M, K);
    }
    return 0;
}


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


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


Measured memory_bytes: 256
#include<stdio.h>

//昇順にソート
void insertionSort(int a[],int n){
    int i,j,v;
    for(i=1;i<n;i++){
        v=a[i];          //v:未ソート部分の先頭
        j=i-1;
        while(j>=0&&a[j]>v){
            a[j+1]=a[j];    //vより大きい要素を後方へ移動
            j--;
        }
        a[j+1]=v;
    }
}

int main(void){
    int n,i,sum=0,cnt=0;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    insertionSort(a,n);
    for(i=n-1;i>=0;i--){
        if(cnt%2==0){
            sum+=a[i];
        }else{
            sum-=a[i];
        }
        cnt++;
    }
    printf("%d\n",sum);
    return 0;
}


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

int main() {
	int x;
	cin >> x;
	vector<bool> dp(x + 1);
	dp[0] = true;
	dp[100] = true;
	dp[101] = true;
	dp[102] = true;
	dp[103] = true;
	dp[104] = true;
	dp[105] = true;
	for(int i = 105; i <= x; i++){
		dp[i] = dp[i - 100] | dp[i - 101] | dp[i - 102] | dp[i - 103] | dp[i - 104] | dp[i - 105];
	}
	cout << dp[x] << endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int a, b, req = 0;
    cin >> a >> b;
    req = (a-1) * (b-1);
    cout << req << endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rint register int
#define LL long long
#define maxn 2007
#define inf 1000000000
#define mod 100000007
#define	QAQ freopen ("cantor.in", "r", stdin); freopen ("cantor.out", "w", stdout);
using namespace std;
inline int rf(){int r,s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;%>
int main()
{
	//QAQ 
	int n=rf(),ans=0,a[maxn];
	
	for(int i=1;i<=n;i++)
	a[i]=rf();
	
	sort(a+1,a+1+n);
	
	int la=inf;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		int qw=a[i]+a[j];
		for(int k=j+1;k<=n;k++)
		{
		if(qw>a[k]) ans++;
		else break;
		
		}
	}
	
	
	printf("%d",ans);
	
    return 0;
}
/*
We Secure. We Contain. We Protect
We programme. We submit. We accepted


JXU4RDc3JXU3ODAxJXVGRjBDJXU2NzAwJXU4RDc3JXU3ODAxJXVGRjBDJXU1MjFEJXU4RDVCJXU5MDFBJXU4RkM3JXVGRjAx
10
1 2 3 1 2  3 4 6 2 3

*/

Measured memory_bytes: 256
using System;

namespace ITP1_9_B
{
    class Program
    {
        static void Main(string[] args)
        {
            int data = 0;
            string[] result = new string[10];

            while (true)
            {
                string word = Console.ReadLine();
                if (word == "-")
                    break;
                string M = Console.ReadLine();
                int m = int.Parse(M);
                string[] shuffle = new string[m];

                for (int i = 0; i < m; i++)
                {
                    shuffle[i] = Console.ReadLine();
                    int roll = int.Parse(shuffle[i]); 
                    string substring1 = word.Substring(0, roll);
                    string substring2 = word.Substring(roll);
                    word = substring2 + substring1;
                    if (i == m - 1)
                        result[data] = word;
                }
                data++;
            }
            for(int i=0;i<10;i++)
            {
                if (result[i] != null)
                    Console.WriteLine(result[i]);
            }
        }
    }
}


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

vector<ll> get_divisors(ll num)
{
    deque<ll> divisors;
    for (ll i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            divisors.push_front(i);
            if (i * i < num) {
                divisors.push_back(num / i);
            }
        }
    }
    return vector<ll>(begin(divisors), end(divisors));
}

void solve(long long N)
{
    ll ans = 0;

    // K^m = N (m=1,2,3…)となるKの数
    auto divisors = get_divisors(N);
    for (auto d : divisors) {
        if (d > 1) {
            auto n = N;
            while (n % d == 0) {
                n /= d;
            }
            if (n % d == 1) {
                ans++;
            }
        }
    }

    // mK+1 = N (m=1,2,3…)となるKの数
    // K=(N-1)/mなので、N-1の約数の数-1だけ存在(-1するのはm=N-1の時はK=1となり、不適であるため)
    ans += get_divisors(N - 1).size() - 1;

    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
#pragma GCC diagnostic ignored "-Wunused-result"
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

char ch[1000];
int n;

int main(){
	cin >> n;
	cin >> ch;
	int maxn = 0;
	int x = 0;
	for (int i = 0; i < n; ++i)
	{
		if (ch[i] == 'I')x++;
		else x--;
		maxn = maxn>x ? maxn : x;
	}
	cout << maxn << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll i = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll i = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll i = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

int main(void){
	ll a, v, b, w, t;
	cin >> a >> v >> b >> w >> t;

	if (abs(a - b) <= (v - w) * t) puts("YES");
	else
		puts("NO");

	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define ALLA(a) a,a+a.size();
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;


int lcs(string X,string Y){
  int m = X.length();
  int n = Y.length();
  int c[m+1][n+1];
  int maxl = 0;
  //0文字目を追加1-indexed
  X = ' ' + X;
  Y = ' ' + Y;
  //0文字目と一致するはずがないので0を入れる
  REP(i,m + 1){
    c[i][0] = 0;
  }
  REP(j,n + 1){
    c[0][j] = 0;
  }

  //Xの1文字ずつループ
  FOR(i,1,m+1){
    //Yの1文字ずつループ
    FOR(j,1,n+1){
      if(X[i] == Y[j]){
	/*XとYで一致する文字を見つけた
	  ⇛ その文字が出るまでのLCSに1を足す(新たな文字)*/
	c[i][j] = c[i-1][j-1] + 1;
      }else{
	c[i][j] = max(c[i-1][j],c[i][j-1]);
      }
      
      maxl = max(maxl, c[i][j]);
    }

  }
  return maxl;
}

int main (){
  int n;
  string x,y;
  while (cin >> n){
    REP(i,n){
      cin >> x >> y;
      cout << lcs(x,y) << endl;
    }
    
  }
  return 0;
}



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

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

  sort(a.begin(), a.end(), greater<int>());

  int ans1 = a[0], ans2 = 0, d = 1000000001;
  for (int i = 1; i < n; ++i) {
    if (min(abs(a[i] - a[0] / 2), abs(a[i] - (a[0] + 1) / 2)) < d) {
      d = min(abs(a[i] - a[0] / 2), abs(a[i] - (a[0] + 1) / 2)), ans2 = a[i];
    }
  }

  cout << ans1 << ' ' << ans2 << endl;
}


Measured memory_bytes: 640
N,K=map(int, input().split())
a = list(map(int, input().split()))
dp = [0]+[float("inf")]*N
for i,h1 in enumerate(a):
    for j in range(i+1,min(i+K+1,N)):
        dp[j] = min(dp[j],dp[i]+abs(h1-a[j]))
print(dp[N-1])

Measured memory_bytes: 55136
import java.util.Scanner;
class Main
{
public static void main(String args[])
{
Scanner scan=new Scanner(System.in);
int s[]=new int[4];
for(int i=0;i<4;i++)
{
int t=scan.nextInt();
int n=scan.nextInt();
if(t==1)s[i]+=6000*n;
if(t==2)s[i]+=4000*n;
if(t==3)s[i]+=3000*n;
if(t==4)s[i]+=2000*n;
}
for(int i=0;i<4;i++)
{
System.out.println(s[i]);
}
}
}

Measured memory_bytes: 17168
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

string x;

int solve() {
    int l = x.size();
    int s = 0, res = 0;
    for (int i = 0; i < l; i++) {
        if (x[i] == 'T') {
            if (s == 0) res++;
            else s--;
        } else {
            s++;
        }
    }
    res += s;
    return res;
}

void input() {
    cin >> x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 848
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
int N,M,A,B,C,T;
V mul(const V &a, const V &b){
	V c(N*N);
	int i=0,j;
	for(;i<N;i++)for(j=0;j<N;j++)c[i*N+j]=(a[slice(i*N,N,1)]*b[slice(j,N,N)]).sum()%M;
	return c;
}
V exp(const V &a, const int n){
	if(n==1)return a;
	if(n&1)return mul(exp(a,n-1),a);
	V b=exp(a,n>>1);
	return mul(b,b);
}
V z(){
	V x(N*N);
	int i;
	if(T){
		x[0]=B;
		x[1]=C;
		for(i=1;i<N-1;i++){
			x[i*N+i-1]=A;
			x[i*N+i]=B;
			x[i*N+i+1]=C;
		}
		x[i*N+i-1]=A;
		x[i*N+i]=B;
		return exp(x,T);
	}else{
		for(i=0;i<N;i++)x[i*N+i]=1;
		return x;
	}
}
main(){
	int i;
	V s;
	for(;scanf("%d%d%d%d%d%d",&N,&M,&A,&B,&C,&T),N;){
		s.resize(N);
		for(i=0;i<N;i++)scanf("%d",&s[i]);
		const V r=z();
		for(i=0;i<N-1;i++)printf("%d ",(r[slice(i*N,N,1)]*s).sum()%M);
		printf("%d\n",(r[slice(i*N,N,1)]*s).sum()%M);
	}
}

Measured memory_bytes: 1080
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    auto S = sread();
    S.map!"a=='-'?-1:1".sum().writeln();
}


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

template<typename T>
void Warshall_Floyd(vector<vector<T>> &d,T id){
    for (int k=0;k<d.size();++k){
        for (int i=0;i<d.size();++i){
            for (int j=0;j<d.size();++j){
                if (d[i][k]==id||d[k][j]==id) continue;
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

const ll IINF=1e18;

int main(){
    int V,E; cin >> V >> E;
    vector<vector<ll>> g(V,vector<ll>(V,IINF));
    rep(i,V) g[i][i]=0;
    rep(i,E){
        int s,t; ll d; cin >> s >> t >> d;
        g[s][t]=d;
    }
    Warshall_Floyd(g,IINF);
    rep(i,V) if (g[i][i]<0){
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    rep(i,V) rep(j,V){
        if (g[i][j]==IINF) cout << "INF";
        else cout << g[i][j];
        if (j!=V-1) cout << ' ';
        else cout << endl;
    }
}


Measured memory_bytes: 3252