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

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

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        if (n == 1 || n % 2 == 1) {
            System.out.println(((n / 2) + 1 >= k) ? "YES" : "NO");
        } else {
            System.out.println((n / 2 >= k) ? "YES" : "NO");
        }
    }
}


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

int main(void)
{
    int N, n;
    cin >> N;
    vector<queue<int>> stacks(N, queue<int>());
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            cin >> n;
            stacks.at(i).push(n);
        }
    }
    int count = 1;
    int pop_count = 0;
    stack<int> push_s;
    set<int> need_check;
    for(int i=0;i<N;i++){
        need_check.insert(i);
    }
    while(true){
        set<int> need_check_more;
        for(auto itr=need_check.begin();itr!=need_check.end();itr++){
            int i = *itr;
            if(stacks.at(i).size()==0){
                continue;   
            }
            n = stacks.at(i).front();
            if(stacks.at(n-1).front() == i+1){
                if(need_check_more.count(i)==0){
                    push_s.push(i);
                    need_check_more.insert(i);
                }
                if(need_check_more.count(n-1)==0){
                    push_s.push(n-1);
                    need_check_more.insert(n-1);
                }
            }
        }
        need_check = need_check_more;
        if(push_s.size() == 0){
            cout << -1;
            return 0;
        }
        while(push_s.size() > 0){
            n = push_s.top();
            push_s.pop();
            stacks.at(n).pop();
            pop_count++;
        }
        if(pop_count == N*(N-1)){
            cout << count;
            return 0;
        }
        count++;
    }

    return 0;
}

Measured memory_bytes: 4736
#include<stdio.h>
int main(void){
   int r,c;
   int i,j;
   int sheet[101][101];
   scanf("%d%d",&r,&c);
   for(i=0;i<=r;i++){
      for(j=0;j<=c;j++){
         sheet[i][j]=0;
      }
   }
   for(i=0;i<r;i++){
      for(j=0;j<c;j++){
         scanf("%d",&sheet[i][j]);
         printf("%d ",sheet[i][j]);
         sheet[i][c]+=sheet[i][j];
         sheet[r][j]+=sheet[i][j];
      }
      printf("%d\n",sheet[i][c]);
   }
   for(j=0;j<c;j++){
      printf("%d ",sheet[r][j]);
      sheet[r][c]+=sheet[r][j];
   }
   printf("%d\n",sheet[r][c]);
   return 0;
}

Measured memory_bytes: 636
#!/usr/bin/env python3

def solve(n,a):
    l = [0]*n
    for i in range(n):
        l[i] = sum(a[0][:i+1]) + sum(a[1][i:])
    return max(l)


def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(2)]
    print(solve(N,a))

if __name__ == '__main__':
    main()

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

int main()
{
  int64_t n, ans = 0, i = 357, ma = 999999999;
  string s;
  cin >> n;
  ma = min(n, ma);
  map<char, int> sft;

  while (i <= ma)
  {
    map<char, int> sft;
    s = to_string(i);

    bool flag = 1;
    int cnt = (int)s.size();

    for (char c : s)
    {
      if (c != '7' and c != '5' and c != '3')
      {
        flag = 0;
        i += (pow(10, cnt - 1));

        break;
      }
      else
      {
        ++sft[c];
      }
      --cnt;
    }
    if (flag)
    {
      if (sft.count('7') and sft.count('5') and sft.count('3'))
      {
        ++ans;
      }
      ++i;
    }
  }

  cout << ans << "\n";
}

Measured memory_bytes: 384
N,K = gets.chomp.split(" ").map(&:to_i)
a,b = N.times.map{gets.split.map(&:to_i)}.transpose
arr = Array.new(a.max+1,0)
N.times do |i|
  arr[a[i]] += b[i]
end
i = 1
sum = 0
while sum < K
  sum += arr[i]
  break if sum >= K
  i += 1
end
puts i

Measured memory_bytes: 23240
#include<stdio.h>
int main(){
    int r,g,b,k;
    scanf("%d%d%d%d",&r,&g,&b,&k);
    int cnt=0;
    while(g<=r) g<<=1,cnt++;
    while(b<=g) b<<=1,cnt++;
    if(cnt<=k) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 1636
#include <stdio.h>

int p[10001];

int isprime(int n)
{
	int i;
	for(i = 2; i*i <= n ; i++){
		if(n%i == 0)
		return 0;
	}
	return 1;
}

int main(void)
{
  	int i, n;
	int p[10001];
	for ( i= 0; i<10001; i++){
		p[i] = isprime(i);
	}
	 
	while(1){
		scanf("%d" , &n);
		if(n == 0)
			break;
		for(i = n ; i > 1;i--){
			if(p[i]*p[i -2] ==1)
				break;
		}
			if(n >= 5)
				printf("%d %d\n",i-2,i);
	}
		return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF 1e15

#define MAX_N 1000

double width(int* X,int* Y,int n,double x){
	double lb=INF,ub=-INF;
	rep(i,n){
		double x1=X[i],y1=Y[i],x2=X[(i+1)%n],y2=Y[(i+1)%n];
		if((x1-x)*(x2-x)<=0&&x1!=x2){
			double y=y1+(y2-y1)*(x-x1)/(x2-x1);
			lb=min(lb,y);
			ub=max(ub,y);
		}
	}
	return max(0.0,ub-lb);
}

int M,N;
int X1[111],Y1[111];
int X2[111],Z2[111];

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>M>>N;
		if(M==0&&N==0)break;
		rep(i,M)cin>>X1[i]>>Y1[i];
		rep(i,N)cin>>X2[i]>>Z2[i];

		int min1=*min_element(X1,X1+M),max1=*max_element(X1,X1+M);
		int min2=*min_element(X2,X2+N),max2=*max_element(X2,X2+N);
		vector<int> xs;
		rep(i,M)xs.pb(X1[i]);
		rep(i,N)xs.pb(X2[i]);
		sort(all(xs));

		double res=0;
		rep(i,xs.size()-1){
			double a=xs[i],b=xs[i+1],c=(a+b)/2;
			if(min1<=c&&c<=max1&&min2<=c&&c<=max2){
				double fa=width(X1,Y1,M,a)*width(X2,Z2,N,a);
				double fb=width(X1,Y1,M,b)*width(X2,Z2,N,b);
				double fc=width(X1,Y1,M,c)*width(X2,Z2,N,c);
				res+=(b-a)/6*(fa+4*fc+fb);
			}
		}
		printf("%.10f\n", res);
	}
	return 0;
}

Measured memory_bytes: 1272
#include <stdio.h>

int main()
{
  long long int k;
  scanf("%lld", &k);
  
  if (k % 2 == 0 || k % 5 == 0)
  {
    printf("-1");
    return 0;
  }
  
  long long int n = 7;
  for (long long int i = 1; i < 2e32; i++)
  {
    if (n % k == 0)
    {
      printf("%lld", i);
      return 0;
    }
    n *= 10;
    n += 7;
    n %= k;
  }
  
  printf("-1");
  return 0;
}
   

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  string s;
  cin>>n>>s;
  int count=0;
  for(int i=0; i<n-2; i++){
    if(s.at(i)=='A'&&s.at(i+1)=='B'&&s.at(i+2)=='C'){
      count++;
    }
  }
  cout<<count<<endl;
}

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

int main() {
    int n; cin >> n;
    set<string> st;

    rep(i, n) {
        string s;
        cin >> s;
        st.insert(s);
    }
    
    cout << st.size() << endl;
}

Measured memory_bytes: 19220
use strict;
use warnings;

my $n;
my $a;
my $b;
my $c;
my $d;
my $s;
($n, $a, $b, $c, $d) = split /\s/, <>;
chomp($s = <>);
my $s1 = $s;

my $ans = "Yes";
$s1 = substr($s, $a - 1, $c - $a + 1);

if ($c < $d) {
	my $cpath = substr($s, $a - 1, $c - $a + 1);
	my $dpath = substr($s, $b - 1, $d - $b + 1);
	if ($cpath =~ m/##/ or $dpath =~ m/##/) {
		$ans = "No";
	}
} elsif ($s1 =~ m/##/) {
	$ans = "No";
} else {
	# $c > $d
	my $t = substr($s, $b -2, $d - $b + 3);
	if ($t !~ m/\.{3}/) {
		$ans = 'No';
	}
}

print $ans, "\n";


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

int main() {
  //input
  int64_t N, A, B;
  cin >> N >> A >> B;
  //calc
  int64_t diff = B - A;
  int64_t answer = -1;
  if ( diff % 2 == 0 ) {
    answer = diff / 2;
  }
  else {
    answer = min(A-1, N-B) + (diff+1)/2;
  }
  //output
  cout << answer << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        int H = Integer.parseInt(scanner.next());
        int W = Integer.parseInt(scanner.next());
        int h = Integer.parseInt(scanner.next());
        int w = Integer.parseInt(scanner.next());

        final int result = H * W - (h * W) - (w * (H - h));
        System.out.println(result);
    }
}


Measured memory_bytes: 23636
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;
int main()
{
	double R,G;
	cin >> R >> G;
	cout << 2*G - R << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c,d,n,ans=0;
  while(scanf("%d",&n)!=EOF){
    for(a=0;a<=9;a++){
      for(b=0;b<=9;b++){
	for(c=0;c<=9;c++){
	  for(d=0;d<=9;d++){
	    if(a+b+c+d==n){
	      ans++;
	    }
	  }
	}
      }
    }
    printf("%d\n",ans);
    ans=0;
  }
  return(0);
}

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

typedef long long int64;
int n, k, a[1005];
vector <int64> cur;

int main() {
	scanf("%d%d", &n, &k);

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

		int64 s = 0;
		for(int j = i; j > 0; j--) {
			s += a[j];
			cur.push_back(s);
		}
	}

	int64 ans = 0;
	for(int i = 50; i >= 0; i--) {
		vector <int64> tmp;

		int cnt = 0;
		for(int64 o : cur) {
			if(o & 1LL << i) {
				cnt++;
				tmp.push_back(o);
			}
		}

		if(cnt >= k) {
			ans += 1LL << i;
			cur = tmp;
		}
	}

	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6512
n = int(input())
b = list(map(int, input().split()))
a = [i for i in [0]*n]
a[0] = b[0]
for i in range(n-1):
    a[i+1] = b[i]
    if b[i] < a[i] and i != 0:
        a[i] = b[i]
print(sum(a))


Measured memory_bytes: 3060
a,b=map(int,input().split())
List = list(map(int, input().split()))
wa = 0
List.sort(reverse = True)
for i in range(a):
  wa += List[i]
thresi = wa / (4 * b)
flag = False
for i in range(b):
  if List[i] >= thresi:
    flag = True
  else:
    flag = False
if flag:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9088
#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 gcd(int a, int b){
   if (a%b == 0){
       return(b);
   }
   else{
       return(gcd(b, a%b));
   }
}

int lcm(int a, int b){
   return a * b / gcd(a, b);
}

int main(){
	int a,b,k;
	cin >> a >> b >> k;
	int cnt = 0;
	int ans = 1;
	for(int i = lcm(a,b);i >= 1;i--){
		if(a%i == 0 && b%i == 0){
			cnt++;
		}
		if(cnt == k){
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    int n;
    cin >> n;
    map<string, int> mp;
    mp["AC"] = 0;
    mp["WA"] = 0;
    mp["TLE"] = 0;
    mp["RE"] = 0;
    rep(i, n) {
        string s;
        cin >> s;
        mp[s]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
    return 0;
}

Measured memory_bytes: 3632
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


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

using namespace std;

typedef long long ll;

struct Node {
    int key;
    Node *p, *l, *r;
};

Node *root, *NIL;

Node* find(Node* u, int k) {
    while (u != NIL && k != u->key) {
        if (k < u->key)
            u = u->l;
        else
            u = u->r;
    }
    return u;
}

void insert(int k) {
    Node *y = NIL, *x = root, *z;
    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->l = NIL;
    z->r = NIL;

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

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

void inorder(Node* u) {
    if (u == NIL) return;
    inorder(u->l);
    cout << " " << u->key;
    inorder(u->r);
}

void preorder(Node* u) {
    if (u == NIL) return;
    cout << " " << u->key;
    preorder(u->l);
    preorder(u->r);
}

int main() {
    int n; cin >> n;
    
    for (int i = 0; i < n; i++) {
        string com; cin >> com;

        if (com[0] == 'f') {
            int x; cin >> x;
            Node* t = find(root, x);
            if (t != NIL) cout << "yes" << endl;
            else cout << "no" << endl;
        } else if (com == "insert") {
            int x; cin >> x;
            insert(x);
        } else if (com == "print") {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }
}



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

#define ll long long

int main()
{
  char s[7];
  cin >> s;
  if (s[2] == s[3] && s[4] == s[5])
    cout << "Yes\n";
  else
    cout << "No\n";

  return 0;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
s=[list(map(int,input().split())) for i in range(M)]
p=list(map(int,input().split()))
ans=0
for i in range(2**N):
  ptn=bin(i)[2:].rjust(N,'0')
  light=True
  for j in range(M):
    tmp=0
    for n in range(1,s[j][0]+1):
      if ptn[s[j][n]-1]=='1':
        tmp+=1
    if tmp%2!=p[j]:
      light=False
  if light:
    ans+=1
print(ans)

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

int main(void)
{
    string S;
    cin >> S;

    string T;
    cin >> T;

    int numS = S.size();
    int numT = T.size();

    int flag =1;
    int i;

    for(i=0;i<numS;i++){
        if(S[i]!=T[i]){
            flag=0;
            break;
        }
    }

    if((numS+1==numT) && flag ==1){ 
        char Tend = char(T[numS]);
        if(Tend >= 'a' && Tend<='z'){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    else{
        cout << "No" << endl;
    }
   
    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
int main() {
int A,B,C,x;
scanf("%d%d%d%d",&A,&B,&C,&x);
int cnt=0;
int a,b,c;
  for(a=0;a<=A;a++){
    for(b=0;b<=B;b++){
      for(c=0;c<=C;c++){
        int goukei=500*a+100*b+50*c;
        if(goukei==x){
          cnt++;
        }
      }
    }
  }
  printf("%d",cnt);
  return 0;
}


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

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int K,X;
	cin>>K>>X;
	
	int min=X-K+1;
	int max=X+K-1;
	
	for(int i=min;i<=max;i++){
		cout<<i<<" ";
	}
	
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

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

    int syou = n / 1000;
    int amari = n % 1000;
    if(amari==0){
        cout << 0 << endl;
    } else {
        cout << 1000-amari << endl;
    }
}

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

const int maxn = 100;
int a[maxn], b[maxn];

int main() {
    int n, m, c;
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    int sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        sum = 0;
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[j]);
            sum += a[j] * b[j];
        }
        sum += c;
        if (sum > 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <regex>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
//const int INF = 100100100;
const int INF = (1LL << 32);
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;

static const int MAX = 10000;
static const int INFTY = 1 << 29;

class Disjoint {
public:
	Disjoint() {}
	Disjoint(int size) {
		p.resize(size, 0);
		rank.resize(size, 0);
		int i;
		rep(i, size) makeSet(i);
	}

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

	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}
	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = p[x];
		}
		else {
			p[x] = p[y];
			if (rank[x] == rank[y])
				rank[y]++;
		}
	}
	int findSet(int x) {
		if (p[x] != x) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
private:
	vector<int> p, rank;
};

class Edge {
public:
	int source, target, cost;
	Edge(int source = 0, int target = 0, int cost = 0) 
		: source(source),target(target),cost(cost){}
	bool operator<(const Edge& e)const { return cost < e.cost; }
};

int kruskal(int N, vector<Edge> edges) {
	int totalCost = 0;
	sort(ALL(edges));
	Disjoint dset = Disjoint(N + 1);
	rep(i, N) dset.makeSet(i);
	int source, target;
	rep(i, edges.size()) {
		Edge e = edges[i];
		if (!dset.same(e.source, e.target)) {
			totalCost += e.cost;
			dset.unite(e.source, e.target);
		}
	}
	return totalCost;
}

signed main() {
	ios::sync_with_stdio(false);
	int N, M, cost;
	cin >> N >> M;
	int source, target;
	vector<Edge> edges;
	rep(i, M) {
		cin >> source >> target >> cost;
		edges.pb(Edge(source, target, cost));
	}
	cout << kruskal(N, edges) << endl;
 	return 0;
}




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

int main(){
    int a,a1,a2,a3;
    cin >> a1 >> a2 >> a3;
    a = a1 +a2 + a3;
    if( a > 21) cout << "bust" << endl;
    else    cout << "win" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

using ll = long long;

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

const int MOD = (int) 1e9 + 7;

int n;
bool memo[2][100001];

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	
	cin >> n;
	
	
	int cnt = 1;
	memo[0][1] = true;
	for (int i = 6; i < n + 1; i *= 6) {
		memo[0][i] = true;
	}
	for (int i = 9; i < n + 1; i *= 9) {
		memo[0][i] = true;
	}
	
	
	while (memo[0][n] == false) {
		FOR(i, 1, n + 1) {
			if (memo[0][i]) {
				memo[1][i + 1] = true;
				for (int j = 6; j < 100000 - i; j *= 6) {
					memo[1][i + j] = true;
				}
				for (int j = 9; j < 100000 - i; j *= 9) {
					memo[1][i + j] = true;
				}
			}
		}
		FOR(i, 1, n + 1) {
			memo[0][i] = memo[1][i];
			memo[1][i] = false;
		}
		cnt++;
	}
	
	
	cout << cnt << endl;
	
	return 0;
}


Measured memory_bytes: 512
use std::io::stdin;

fn main() {
    let result:Vec<i32> = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692].to_vec();
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let k = st.trim().parse::<usize>().unwrap();
    println!("{:?}",result[k-1]);
}

Measured memory_bytes: 2080
#include<bits/stdc++.h>
using namespace std;
int main (){
    int N,D;
    cin>>N>>D;
    vector<vector<int> >a(N,vector<int>(D));
    int count=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<D;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            double sum=0;
            for(int k=0;k<D;k++){
                sum+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
            }
            for(int n=1;n<150;n++){
                if(sqrt(sum)==n){
                    count++;
                }
            }
            }

        }
        cout<<count<<endl;
    }

Measured memory_bytes: 256
use proconio::{input, fastout};
use std::cmp::min;

macro_rules! echo {
  ($val:expr) => {
    println!("{}", $val);
  }
}

#[fastout]
fn main() {
  input!{
    n: usize,
    k: usize,
    mut xa: [i32; n]
  };
  let ans = match xa.iter().position(|&x| x > 0) {
    None => {
      xa[n-k] * -1
    },
    Some(mid) => {
      let mut ans = std::i32::MAX;
      xa.insert(mid, 0);
      for i in 0..=k {
        if mid >= k-i && mid+i <= n {
          let cost = min(xa[mid + i] * 2 + xa[mid-(k-i)]*-1, xa[mid+i] + xa[mid-(k-i)] * -2);
          // dbg!(i, cost);
          ans = min(ans, cost);
        }
      }
      ans
    }
  };
  echo!(ans);
}


Measured memory_bytes: 3452
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

#define int long long

signed main(){
	int a, b, c;
	cin >> a >> b >> c;
	if(a + b + c >= 22)cout << "bust" << endl;
	else cout << "win" << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <limits>
#include <numeric>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

#define INFint (1<<30)
#define BOUND 27182818284
#define MAT 2

typedef long long ll;
typedef long long int lli;
typedef pair<ll, ll> P;

ll MOD = 1000000007;
const ll INF = (1ll<<60);
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i=int(a);i<int(b);++i)

template<class T>
bool umax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool umin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// gcd
template<typename T>
T gcd(T a, T b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int findGCD(vector<int> arr) {
    int result = arr[0];
    for (auto a: arr) {
        result = gcd(a, result);
    }
    return result;
}

template<typename T>
T lcm(T m, T n) {
    // 引数に0がある場合は0を返す
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *) array, (T *) (array + N), val);
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};

int main() {
    int M1, M2, D1, D2; cin >> M1 >> D1 >> M2 >> D2;

    if(M1+1==M2){
        cout << 1 << endl;
    }else{
        cout << 0 <<endl;
    }
    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<string.h>
#include<bitset>
#include<set>
using namespace std;

struct S {
	int cost, x, y, o, xh;
	S(int c, int in_x, int in_y, int in_o, int in_xh) : cost(c), x(in_x), y(in_y), o(in_o), xh(in_xh) {}
	bool operator<(const S &s) const {
		if (cost != s.cost)
			return cost < s.cost;
		else
			return o < s.o;
	}
};

const int INF = -1000000000, INF2 = 10000000;
int w, h, f, m, o, ans;
int stratum[110][110];
int c[11][11][51];
priority_queue<S> pq;

void dijkstra() {
	int move[3] = { 1, -1, 1 };//??´y,??´x,??´x
	while (!pq.empty()) {
		S a = pq.top();
		pq.pop();
		if (a.o == 0) continue;
		if (a.y == h) {
			if (-a.cost <= f)
				ans = -a.cost;
			break;
		}
		if (a.o == 1) continue;
		for (int i = 0; i < 3; i++) {
			int x = a.x;
			int y = a.y;
			if (i)
				x += move[i];
			else
				y += move[i];
			int xx = 1 << (w - x);
			xx = xx&a.xh;
			if (!xx || !i) {
				if (x <= w && 0 < x&&y <= h) {
					if (stratum[y][x] < 0) {
						if (a.cost + stratum[y][x] >= -f&&a.cost + stratum[y][x] > c[y][x][a.o - 1]) {
							c[y][x][a.o - 1] = a.cost + stratum[y][x];
							if (i)
								pq.push(S(c[y][x][a.o - 1], x, y, a.o - 1, a.xh | 1 << (w - x)));
							else
								pq.push(S(c[y][x][a.o - 1], x, y, a.o - 1, 1 << (w - x)));
						}
					}
					else if (stratum[y][x] >0) {
						int hokyuuu;
						hokyuuu = stratum[y][x] + a.o - 1;
						if (hokyuuu + a.o - 1 >= m)
							hokyuuu = m;
						c[y][x][hokyuuu] = a.cost;
						if (i)
							pq.push(S(c[y][x][hokyuuu], x, y, hokyuuu, a.xh | 1 << (w - x)));
						else
							pq.push(S(c[y][x][hokyuuu], x, y, hokyuuu, 1 << (w - x)));
					}
					else {
						pq.push(S(0, x, y, o, a.xh | 1 << (w - x)));
					}
				}
			}
			else {
				if (a.cost > c[y][x][a.o - 1] && a.o - 1) {
					c[y][x][a.o - 1] = a.cost;
					pq.push(S(c[y][x][a.o - 1], x, y, a.o - 1, a.xh));
				}
			}
		}
	}
}


int main() {
	while (cin >> w >> h&&w&&h) {
		cin >> f >> m >> o;
		memset(stratum, sizeof(stratum), 0);
		ans = INF2;
		for (int i = 1; i <= 10; i++)
			for (int j = 1; j <= 10; j++)
				fill(c[i][j], c[i][j] + 51, INF);
		while (!pq.empty())
			pq.pop();
		for (int i = 1; i <= h; i++)
			for (int j = 1; j <= w; j++)
				cin >> stratum[i][j];
		pq.push(S(0, 1, 0, o, 1 << (w - 1)));
		dijkstra();
		if (ans != INF2)
			cout << ans << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

Measured memory_bytes: 1272
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author teiwa
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // input data
            int[] input = new int[5];
            for (int i = 0; i < 5; i++) {
                input[i] = in.nextInt();
            }
            // extract the number that first place is the least
            int firstPlaceMin = 9;
            int target = input[0];
            for (int i = 0; i < 5; i++) {
                int firstPlace = input[i] % 10;
                if (firstPlace != 0 && firstPlace < firstPlaceMin) {
                    firstPlaceMin = firstPlace;
                    target = input[i];
                }
            }

            // calculate the summation of round up number except the target
            int sum = 0;
            for (int i = 0; i < 5; i++) {
                sum += ((input[i] - 1) / 10) * 10 + 10;
            }
            sum = sum - (((target - 1) / 10) * 10 + 10) + target;

            out.println(sum);
        }

    }
}



Measured memory_bytes: 23380
N=int(input())
A=list(map(int, input().split())) #ダムの水
#山ダム山ダム山ダム。。。。。
B=[0]*N
A1=0
for i in range(N):
    if i%2==0:
        A1+=A[i]
    else:
        A1-=A[i]
B[0]=A1
for i in range(1,N):
    B[i]=2*A[i-1]-B[i-1]
print(*B)

Measured memory_bytes: 14028
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;

struct segtree{
	int size;
	vector<ll> dat,lazy;
	segtree(int n){
		size = 1;
		while(size<n) size *= 2;
		dat.assign(2*size-1,0);
		lazy.assign(2*size-1,0);
	}
	void lazy_evaluate(int k,int l,int r){
		dat[k] += lazy[k] * (r - l);
		if(k<size-1){
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void update(int a,int b,ll x,int k,int l,int r){
		lazy_evaluate(k,l,r);
		if(b<=l||r<=a) return;
		else if(a<=l&&r<=b){
			lazy[k] += x;
			lazy_evaluate(k,l,r);
		}
		else{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k] = dat[2*k+1] + dat[2*k+2];
		}
	}
	void update(int a,int b,ll x){
		update(a-1,b,x,0,0,size);
	}
	ll sum(int a,int b,int k,int l,int r){
		lazy_evaluate(k,l,r);
		if(b<=l||r<=a) return 0;
		else if(a<=l&&r<=b) return dat[k];
		else{
			ll vl = sum(a,b,2*k+1,l,(l+r)/2);
			ll vr = sum(a,b,2*k+2,(l+r)/2,r);
			return vl + vr;
		}
	}
	ll sum(int a,int b){
		return sum(a-1,b,0,0,size);
	}
};

int main(){
	int n,q;
	scanf("%d %d",&n,&q);
	segtree st(n);
	for(int i=0;i<q;i++){
		int cmd;
		scanf("%d",&cmd);
		if(cmd==0){
			int s,t,x;
			scanf("%d %d %d",&s,&t,&x);
			st.update(s,t,x);
		}else{
			int s,t;
			scanf("%d %d",&s,&t);
			printf("%lld\n",st.sum(s,t));
		}
	}
	return 0;
}

Measured memory_bytes: 6348
/***************************************** 
****       Solution by SlavicG        ****
*****************************************/
 
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm> 
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;++i)
#define MX 10000000001
#define pow2(a) ((a)*(a))
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define endl "\n"
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 int longestIncreasingSubsequenceLenghtDP(int a[],int n){
    int dp[n],ans=0;
    for(int k = 0;k<n;k++){
        dp[k] = 1;
        for(int i = 0;i<k;i++){
            if(a[i] <= a[k]){
                dp[k] = max(dp[k],dp[i] + 1);
                ans = max(dp[k],ans);
            }
        }
    }
    return ans;
 }
int result[1000] = {0};
int factDP(int n) 
{
   if (n >= 0) {
      result[0] = 1;
      for (int i = 1; i <= n; ++i) {
         result[i] = i * result[i - 1];
      }
      return result[n];
   }
}
bool checkPrime(int n)
{
    if(n<2) return false;
    for(int x = 2;x*x <=n;x++)
    {
        if(n%x == 0)return false;
    }
    return true;
}
vector<int> primeFactors(int n){
    vector<int> f;
    for(int x = 2;x*x<=n;x++){
        while(n%x==0){
            f.push_back(x);
            n/=x;
        }
    }
    if(n>1)f.push_back(n);
    return f;
}
int binary_Search_Classic(int n, int arr[],int target){
	int l,r,mid;
	l=0;
	r=n-1;
	while(l<=r){
		mid= l+(r-l)/2;
		if(arr[mid] == target){
			return mid;
		}
		if(arr[mid] < target){
			l=mid+1;
		}else
		{
			r=mid-1;
		}
	}
	return -1;
}
int binary_Search_First_Greater(int n, int arr[],int target){
	int l,r,ans,mid;
	l = 0;
	r = n-1;
	ans=-1;
	while(l<=r){
		mid = l + (r-l)/2;
		if(arr[mid] > target){
			ans=mid;
			r=mid-1;
		}else{
			l = mid+1;
		}
	}
	return ans;
}
int countDistinctCharsString(string s) {
    unordered_map<char, int> m; 
    for (int i = 0; i < s.length(); i++) { 
        m[s[i]]++; 
    }
    return m.size(); 
} 
int main()
{
	int n,a;
	cin >> n >> a;
	if(n*2<= a && n*4>=a && a%2 ==0)
	{
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i, n) for (int i = 0; i < ((int)(n)); i++) // 0-indexed昇順

int main()
{
    int N;
    cin >> N;
    cout << (N * (N + 1) / 2) << endl;
}

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

int main(){
  int W,H,N; cin>>W>>H>>N;
  int o=0,d=W,t=0,f=H;
  int x,y,a;
  for(int i=0;i<N;i++){
    cin>>x>>y>>a;
    if(a==1)
      o=max(o,x);
    if(a==2)
      d=min(d,x);
    if(a==3)
      t=max(t,y);
    if(a==4)
      f=min(f,y);
  }
  int ax=d-o; if(ax<0) ax=0;
  int ay=f-t; if(ay<0) ay=0;
  cout<<ax*ay<<endl;
}

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

int main(){
  int N; cin >> N;
  vector<char> A(2*N);
  for(int i=0;i<2*N;i++){
    cin >> A[i];
  }
  if(A[0]=='W' || A[2*N-1]=='W'){
    cout << 0 << endl;
    return 0;
  }
  vector<int> B(2*N);
  B[0]=1;
  for(int i=1;i<2*N;i++){
    if(A[i-1]==A[i]){
      B[i]=B[i-1]*(-1);
    }
    else B[i]=B[i-1];
  }
  long long count=1;
  long long ans=1;
  for(int i=1;i<2*N;i++){
    if(B[i]==1){
      count++;
    }
    else {
      ans=(ans*count)%1000000007;
      count--;
    }
  }
  if(count!=0){
    cout << 0 << endl;
    return 0;
  }
  for(int i=1;i<=N;i++){
    ans=(ans*i)%1000000007;
  }
  cout << ans << endl;
}
      
  

Measured memory_bytes: 1280
import statistics
n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

median_min=statistics.median(A)
median_max=statistics.median(B)

if n%2!=0:
    ans=int(median_max-median_min+1)
else:
    ans=int(2*median_max-2*median_min+1)

print(ans)

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

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))
#define INF (1<<28)
#define pb push_back
#define fs first
#define sc second

const char dx[]={0,1,0,-1},dy[]={1,0,-1,0};
template<class T>
ostream &operator<<(ostream &out, const vector<T> &v){
	out << "{";
	rep(i,v.size()) out << v[i] << ", " ;
	return out << "}" << endl;
}
template<class S,class T>
ostream &operator<<(ostream &out, const pair<S,T> p){
	return out << "(" << p.fs << ", " << p.sc << ")";
}
int main(){
	int n;
	string s;
	cin >> s;
	string ans = "";
	rep(i,s.length() - 8){
		ans += s[i];
	}
	cout << ans<< endl;
	return 0;
}


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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  int n;
  cin >> n;
  vl a(n);
  string s;
  cin >> a[0];
  rep1 (i, n - 1) {
    char c;
    cin >> c;
    s.push_back(c);
    cin >> a[i];
  }
  int m = 3;
  vll dp(n, vl(m, -INF));
  dp[0][0] = a[0];
  rep1 (i, n - 1) {
    char op = s[i - 1];
    rep (j, m) {
      ll bai;
      if (j % 2 == 0) {
        bai = 1;
      }
      else {
        bai = -1;
      }
      if (op == '+') {
        dp[i][j] = max(dp[i][j], dp[i - 1][j] + bai*a[i]);
        if (j != 0) {
          dp[i][j - 1] = max(dp[i][j - 1], dp[i - 1][j] - bai*a[i]);
        }
      }
      else {
        dp[i][j] = max(dp[i][j], dp[i - 1][j] - bai*a[i]);
        if (j != 0) {
          dp[i][j] = max(dp[i][j], dp[i - 1][j] + bai*a[i]);
        }
        if (j != m - 1) {
          dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j] - bai*a[i]);
        }
      }
    }
  }
  ll ans = -INF;
  rep (j, m) {
    chmax(ans, dp[n - 1][j]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 6656
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
vector<vector<pii> >G(100010);
ll d[100010];
void dfs(int i,int p,int w){
    d[i]=d[p]+w;
    for(auto e:G[i]){
        int ni=e.first;
        int c=e.second;
        if(ni==p)continue;
        dfs(ni,i,c);
    }
}
int main(){
    int n;cin>>n;
    rep(i,n-1){
        int a,b,c;cin>>a>>b>>c;
        G[a].pb(make_pair(b,c));
        G[b].pb(make_pair(a,c));
    }
    int q,k;cin>>q>>k;
    dfs(k,0,0);
    rep(i,q){
        int x,y;cin>>x>>y;
        cout<<d[x]+d[y]<<endl;
    }
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
#define MAX_V 1000
struct edge{int to,cap,rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(int i=0;i<G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
	level[e.to]=level[v]+1;
	que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  for(int &i=iter[v];i<G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  for(;;){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0)flow+=f;
  }
}

int main(){
  int V,E;
  cin>>V>>E;
  for(int i=0;i<E;i++){
    int u,v,c;
    cin>>u>>v>>c;
    add_edge(u,v,c);
  }
  cout<<max_flow(0,V-1)<<endl;
  return 0;
}



Measured memory_bytes: 3244
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		int max = a > b ? a : b;
		max = max > c ? max : c;
		cout << ((max*max == a * a + b * b + c * c - max * max) ? "YES" : "NO") << endl;
	}
}


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

int main() {
    int n;
    cin >> n;
    vector<float> v(n);
    rep(i, n) cin >> v[i];

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    while (v.size() > 1) {
        float f1 = v.back();
        v.pop_back();
        float f2 = v.back();
        v.pop_back();
        v.push_back((f1 + f2) / 2.0);
    }

    cout << v[0] << endl;
    return 0;
}


Measured memory_bytes: 256
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


n = int(input())
a = list(map(int, input().split()))
ans = 0
ansans = 0
for i in range(n):
    for j in range(n):
        ans = abs(a[i]-a[j])
        ansans = max(ansans, ans)
print(ansans)


Measured memory_bytes: 3832
use proconio::fastout;
use proconio::input;

#[fastout]
fn main() {
    input! { n: u64 }
    let mut now = n;
    let mut ans = 0;
    for i in 2.. {
        if n < i * i {
            if n != 1 {
                ans += 1;
            }
            break;
        }
        if now < i {
            break;
        }
        let mut cnt = 0;
        while now % i == 0 {
            now /= i;
            cnt += 1;
        }
        for j in 1.. {
            if cnt >= j {
                ans += 1;
                cnt -= j;
            } else {
                break;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2168
N, K = map(int, input().split())
x = list(map(int,input().split()))

ans = 100000000000
#最初と最後だけ調べればOK
for i in range(N - K + 1):
    tmp_min = x[i]
    tmp_max = x[i + K - 1]
    ans = min(ans, min(abs(tmp_min), abs(tmp_max)) + abs(tmp_min - tmp_max))
print(ans)





Measured memory_bytes: 14384
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream cin("in.txt");
#endif
  int N, Q;
  while (cin >> N >> Q) {
    string S;
    cin >> S;
    vector<char> T(Q), D(Q);
    for (int q = 0; q < Q; q++) cin >> T[q] >> D[q];
    auto simulate = [&](int i, int edge) {
      for (int q = 0; q < Q; q++) {
        if (S[i] == T[q]) {
          i += D[q] == 'L' ? -1 : +1;
        }
        if (i < 0 || i >= N) return i == edge;
      }
      return false;
    };
    auto bsearch = [&](int edge, int pass, int fail) {
      while (abs(pass - fail) > 1) {
        int i = (pass + fail) / 2;
        if (simulate(i, edge)) {
          pass = i;
        } else {
          fail = i;
        }
      }
      return pass;
    };
    int res = N;
    res -= bsearch(-1, -1, N) + 1;
    res -= N - bsearch(N, N, -1);
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 900
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

struct RollingHash {
	static const int base1 = 1007, base2 = 2009;
	static const int mod1 = 1e9+7, mod2 = 1e9+9;
	vector<long long> hash1, hash2, power1, power2;

	// RollingHashの構築
	RollingHash(const string &S) {
		int n = (int)S.size();
		hash1.assign(n+1, 0);
		hash2.assign(n+1, 0);
		power1.assign(n+1, 1);
		power2.assign(n+1, 1);
		for (int i = 0; i < n; i++) {
			hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
			hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
			power1[i+1] = (power1[i] * base1) % mod1;
			power2[i+1] = (power2[i] * base2) % mod2;
		}
	}

	// get hash of S[left:right]
	inline pair<long long, long long> get(int l, int r) const {
		long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
		if (res1 < 0) res1 += mod1;
		long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
		if (res2 < 0) res2 += mod2;
		return {res1, res2};
    }
};

int main() {
	int N;
	string S;
	cin >> N >> S;

	// ローリングハッシュ
	RollingHash rh(S);

	// S.substr(i, m) == S.substr(j, m) となるような (i, j) が存在するかどうかを判定,substrは部分文字列を見る(ラムダ式)
	auto check = [&](int d) -> bool {
		map<pair<long long, long long>, int> ma;
		for (int i = 0; i + d <= N; i++) {
			auto p = rh.get(i, i + d);
			if (ma.count(p)) { // maにpが存在するなら真
				if (i - ma[p] >= d) return true;
			}
			else ma[p] = i;
		}
		return false;
	};

	// 二分探索
	int left = 0, right = N/2 + 1;
	while (right - left > 1) {
		int mid = (left + right) / 2; // 中点
		if (check(mid)) left = mid; // 上記のcheckにかけて長さmidの部分文字列が存在するか
		else right = mid;
	}

	cout << left << endl;
}

Measured memory_bytes: 768