akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

int main() {
    ll n;
    while(cin >> n, n) {
        vector<ll> dp(n+1, 0);
        dp[0] = 1;
        for(int i=0; i<n; ++i) {
            dp[i+1] += dp[i];
            if(i+2 < n+1) {
                dp[i+2] += dp[i];
            }
            if(i+3 < n+1) {
                dp[i+3] += dp[i];
            }
        }
        ll day = (dp[n] + 9) / 10;
        ll year = (day + 364) / 365;
        cout << year << endl;
    }
}


Measured memory_bytes: 3056
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun May 31 21:08:18 JST 2020
 **/

signed main() {
    Int a;
    std::string s;
    std::cin >> a >> s;
    s.erase(1, 1);
    Int b = stoll(s);
    std::cout << a * b / 100 << std::endl;
}


Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <stdio.h>

using namespace std;

int main()
{
    int a,b,c,x,count;
    count=0;
    cin >>a ;
    cin >>b;
    cin>>c;
    cin>>x;
    for(int i=0;i<=a;i++){
        
        for(int j=0;j<=b;j++){
            
            for(int k=0;k<=c;k++){
                if(x==((i*500)+(j*100)+(k*50)))count++;
                
            }
        }
    }
    cout<<endl<<count;
}






Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int a,b,n,x,y,i,j,dp[101][101];
	while(1){
		scanf("%d%d",&a,&b);
		if(a==0&&b==0) break;
		scanf("%d",&n);
		for(i=1;i<=a;i++){
			for(j=1;j<=b;j++){
				dp[i][j]=0;
			}
		}
		for(i=1;i<=n;i++){
			scanf("%d%d",&x,&y);
			dp[x][y]=-1;
		}
		dp[1][1]=1;
		for(i=1;i<=a;i++){
			for(j=1;j<=b;j++){
				if(dp[i][j]!=-1){
					if(dp[i+1][j]==0&&i<=a){
						dp[i+1][j]=dp[i][j];
					}
					if(dp[i][j+1]!=-1&&j<=b){
						dp[i][j+1]=dp[i][j]+dp[i][j+1];
					}
				}
			}
		}
		printf("%d\n",dp[a][b]);
	}
    return 0;
}

Measured memory_bytes: 2580
// AOJ 1085: Spellcasters
// 2017.8.19 bal4u@uu
// 2017.11.11 

#include <stdio.h>
#include <string.h>

int c[105];

char buf[20], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int n, S;
	int i, j, ans;

	while (fgets(p=buf, 20, stdin) && *p != '0') {
		n = getint(), p++, S = getint();
		memset(c, 0, sizeof(c));
		for (i = 0; i < n; i++) {
			fgets(p=buf, 10, stdin);
			c[getint()]++;
		}
		for (ans = i = 0; i < S; i++) {
			if (!c[i]) continue;
			if (i + i <= S) ans += (c[i] * (c[i]-1)) >> 1;
			for (j = i + 1; j < S; j++)
				if (c[j] && i + j <= S) ans += c[i] * c[j];
		}
		printf("%d\n", n*(n-1) / 2 - ans);
	}
	return 0;
}

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

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

//#define int long long
//signed main(){
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int n=s.size();
    int r=0;
    for(int i = 0; i < n-2; i++) {
        if(s[i]==s[i+1] || s[i+1]==s[i+2] || s[i+2]==s[i]){
            cout << i+1 << " " << i+3 << "\n";
            return 0;
        }
    }
    if(n==2 && s[0]==s[1]) cout << "1 2" << "\n";
    else cout << "-1 -1" << "\n";
    return 0;
}

Measured memory_bytes: 3748
using System;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split();
            double T, X;
            T = double.Parse(s[0]);
            X = double.Parse(s[1]);
            double res = T / X;
            Console.WriteLine("{0:f4}", res);
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n - h + 1) * (n - w + 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <list>
#include <string>
#include <memory.h>
#include <bitset>
#include <stack>
#include <assert.h>
#include <ctime>
#include <unordered_set>
using namespace std;
#define ll long long
#define ppi pair<int, int>
#define mp make_pair
const int N = 2e5 + 11, K = 20;
const int mod = 1e9 + 7;
int main()
{
#ifndef ONLINE_JUDGE
	//freopen("inp.txt", "r", stdin);
#endif
	int a, b, c;
	cin >> a >> b >> c;
	swap(a, b);
	swap(a, c);
	cout << a << " " << b << " " << c;
}


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

constexpr auto INF = INT_MAX/2;
constexpr auto MOD = 1000000007;

int main() {
	int n, m;
	cin >> n >> m;
	vi a(n);
	int sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}

	sort(all(a),greater<int>());
	bool can = true;
	if (a[m - 1] * 4 * m < sum)can = false;

	cout << (can ? "Yes" : "No") << endl;

}

Measured memory_bytes: 256
import bisect

n = (int)(input())
a = sorted(list(map(int, input().split(" "))))
b = list(map(int, input().split(" ")))
c = sorted(list(map(int, input().split(" "))))

count = 0
for i in b:
  #print((a[:bisect.bisect_right(a, i - 1)]), i, c[bisect.bisect_left(c, i + 1):]) 
  #print(bisect.bisect_right(a, i - 1), i, (n - bisect.bisect_left(c, i + 1)) ) 
  count += bisect.bisect_right(a, i - 1) * (n - bisect.bisect_left(c, i + 1)) 
print(count)

Measured memory_bytes: 23744
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<tuple>
#include<vector>
#include<map>
#include<numeric>
#include<limits>
#include<type_traits>
using namespace std;


int main(void){
  //入力
  long long int N;
  vector<long long int> D;
  cin >> N;
  long long int list[N];
  for(int i = 0; i < N; i++){
    long long int temp;
    cin >> temp;
    D.push_back(temp);
    //list[N]の初期化
    list[i] = 0;
  }
  if(D[0] != 0){
    cout << 0 << endl;
  }
  else{
    long long int ans = 1;
    bool unable_flag = false;

    //(N-1)**Nを2以上について掛け合わせる
    for(int i = 0; i < N; i++){
      list[D[i]]++;
    } 
    if(list[0] > 1){
      ans = 0;
    }
    for(int i = 1; i < N - 1; i++){
      //0が登場したらunable_flagを立てて，それ以降で0でない数が出現したらans = 0;
      if(list[i] == 0){
        unable_flag = true;
      }
      if(unable_flag && (list[i] != 0) ){
        ans = 0;
      }
      if(list[i] != 0){
        for(int j = 0; j < list[i + 1]; j++){
         ans *= list[i];
         ans %= 998244353; 
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1912
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head
 
void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    int m1 = max(max(a,b), c);
    int m2 = min(min(b,c), a);
    int m3 = a+b+c - m1 - m2;
    cout << m1*10 + m3 + m2 << '\n';
}

int main(void){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //int t; cin >> t; while (t--)
        solve();
}

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

using namespace std;

#define ll long long
#define pii pair<int, int>
#define MAX 200005

int h[MAX], dp[MAX];


int main() {

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];

    dp[n - 1] = abs(h[n] - h[n - 1]);
    for(int i = n - 2; i > 0; i--) dp[i] = min(dp [i + 1] + abs(h[i] - h[i + 1]), dp[i + 2] + abs(h[i] - h[i + 2]));
    cout << dp[1] << '\n';

    return 0;
}


Measured memory_bytes: 1024
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "cmath"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	cin >> N >> M >> K;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		int box = i;
		int bag = 0;
		while (box) {
			bag += box % 10;
			box /= 10;
		}
		if (bag <= K&&M <= bag) {
			ans += i;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
S = input()
n = 0
w = 0
s = 0
e = 0
x = len(S)
for i in range(x):
    if S[i] == 'N':
        n += 1
    elif S[i] == 'W':
        w += 1
    elif S[i] == 'S':
        s += 1
    elif S[i] == 'E':
        e += 1

if n == 0 and s == 0:
    if e * w != 0:
        print('Yes')
    else:
        print('No')

elif n != 0 and s != 0:
    if e * w != 0:
        print('Yes')
    elif e == 0 and w == 0:
        print('Yes')
    else:
        print('No')

else:
    print('No')

Measured memory_bytes: 9076
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

a_cnt = Counter(a)

x = 0
for i in a_cnt.values():
    x += i * (i - 1) // 2
    
for i in a:
    ans = x - (a_cnt[i] * (a_cnt[i] - 1) // 2)
    ans += (a_cnt[i]-1) * (a_cnt[i]-2) // 2
    print(ans)

Measured memory_bytes: 26780
n,m,*a = map(int,open(0).read().split())
mod = 10**9+7
s = [i-j-2 for i,j in zip(a+[n+1],[-1]+a)]
if -1 in s:
  print(0)
  exit()
f = [1,1]
for i in range(2,max(s)+1):
  f.append(f[i-1]+f[i-2])
ans = 1
for i in s:
  ans = ans*f[i]%mod
print(ans)

Measured memory_bytes: 460020
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef unsigned long long ll;

ll N, n, M, K;

int main(){
    cin >> N >>K;
    if (N < K) cout <<0;
    else cout << 10;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main() {
    /*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
    #endif*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    int g=n/2;
    if(n%2!=0) g++;
    if(g >= k) cout<<"YES";
    else cout<<"NO";
}

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


int main(){
  int N;
  string S;

  cin >> N;
  cin >> S;

  int x = 0;
  int X[N];

  for(int i=0; i<N; i++){
    if(S[i] == 'I'){
      x += 1;
    }
    else if(S[i] == 'D'){
      x -= 1;
    }

    X[i] = x;
  }

  int max_x = 0;
  for(int i=0; i<N; i++){
    if(max_x < X[i]){
      max_x = X[i];
    }
  }

  cout << max_x << endl;



}


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


int main()
{
    char s[10];
    scanf("%s",s);
    int a=0,b=0;
   // printf("%d",s[0]);
    a=10*(s[0]-'0')+s[1]-'0';
    b=10*(s[2]-'0')+s[3]-'0';
    if(a==b&&a==0)
        printf("NA\n");
    else if(b<=12&&b>0)
    {
        if(a<=12&&a>0)
            printf("AMBIGUOUS\n");
        else
            printf("YYMM\n");
    }
    else
    {
        if(a>=12)
        printf("NA\n");
        else
            printf("MMYY\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int LinearSearch(int );
int S[1000000],n;
int main(){

  int j,i,q,T[1000000],count=0,flag;
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
    }
  scanf("%d",&q);
   for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  
    for(j=0;j<q;j++){
      flag=LinearSearch(T[j]);
      if(flag==1) count++;
    }
 
  printf("%d\n",count);
  return 0;


}

int LinearSearch(int key){
  int i=0;
  S[n]=key;

  while(S[i]!=key){
    i++;
    if(i==n)return 0;
  }
  return 1;
}

Measured memory_bytes: 640
import java.util.*;
import java.math.*;
     
class Main{
    public static void main(String[] args) {
        
        try(Scanner sc = new Scanner(System.in)){
 
            int a = Integer.parseInt(sc.next());
            int b = Integer.parseInt(sc.next());
            int h = Integer.parseInt(sc.next());

            System.out.println((a + b)*h/2);
 
        }catch(Exception e){
            e.printStackTrace();
        }        
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <bitset>
#define ll long long int
using namespace std;


int main(){
 long long int A,B,Q;
 scanf("%lld",&A);
 scanf("%lld",&B);
 scanf("%lld",&Q);

 vector <ll> s(0);
 vector <ll> t(0);

 s.push_back(-29999999990);
 t.push_back(-29999999900);

 for(int i=0;i<A;i++){
   ll ss;
   scanf("%lld",&ss);
   s.push_back(ss);
 }

 for(int i=0;i<B;i++){
   ll tt;
   scanf("%lld",&tt);
   t.push_back(tt);
 }

 s.push_back(29999999990);
 t.push_back(29999999900);


 for(int i=0;i<Q;i++){

   ll x;
   scanf("%lld",&x);
   ll result = 39999999900;
   auto ls = lower_bound(s.begin(),s.end(),x);
   auto lt = lower_bound(t.begin(),t.end(),x);
   auto fs = ls-1;
   auto ft = lt-1;
   
   ll c1 = max(x-*ft,x-*fs);
   ll c2 = max(*ls-x,*lt-x);

   ll c3 = min( 2*(*lt-x) + (x-*fs) , 2*(x-*fs) + (*lt-x));
   ll c4 = min( 2*(*ls-x) + (x-*ft) , 2*(x-*ft) + (*ls-x)  );

   c1 = min(c1,c2);
   c3 = min(c3,c4);

   result = min(c1,c3);
//cout<<1<<endl;
   printf("%lld\n",result);
   //cout<<endl;
 }


  return 0;
}
  

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

using namespace std;

int main () {
    vector<int> num(3);
    cin >> num.at(0) >> num.at(1) >> num.at(2);

    sort(num.begin(), num.end());
    cout << num.at(2)*10 + num.at(1) + num.at(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <climits>

using namespace std;

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

  int a[1000];
  int a_idx = 0;

  int i, j;
  i = 0; j = 0;
  const int d1 = 4;
  const int d2 = 7;
  const int nmax = 100;
  j = d1;
  while (i <= nmax) {
    while (j <= nmax) {
      a[a_idx++] = j;
      j += d1;
    }
    i += d2;
    j = i;
  }

  for (i = 0; i < a_idx; i++) {
    if (N == a[i]) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

  return 0;
}


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        List<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i < q; i++){
            int op = sc.nextInt();

            if(op == 0){
                int or = sc.nextInt();
                list.add(or);
            }else if(op == 1){
                int or = sc.nextInt();
                System.out.println(list.get(or));
            }else{
                list.remove(list.size() - 1);
            }
        }
    }
}



Measured memory_bytes: 139988
n = int(input())
for i in range(n):
    Bt = [0]
    Ct = [0]
    Alis = list(map(int,input().split()))
    Bt.append(Alis[0])
    for i in range(1,len(Alis)):
        if Bt[len(Bt) - 1] < Alis[i] and Ct[len(Ct) - 1] > Alis[i]:
            Bt.append(Alis[i])
        elif Bt[len(Bt) - 1] > Alis[i] and Ct[len(Ct) - 1] < Alis[i]:
            Ct.append(Alis[i])
        elif Bt[len(Bt) - 1] > Alis[i] and Ct[len(Ct) - 1] > Alis[i]:
            print("NO")
            break
        else:
            if Alis[i] - max(Bt) > Alis[i] - max(Ct):
                Ct.append(Alis[i])
            elif Alis[i] - max(Ct) > Alis[i] - max(Bt):
                Bt.append(Alis[i])
        if i == len(Alis) - 1:
            print("YES")

Measured memory_bytes: 7496
#include <bits//stdc++.h>
using namespace std;
#define rep(i,n,k) for(int i=n;i<k;i++)
#define int unsigned long long
#define F first 
#define S second
#define P make_pair 


signed main(void){
 
    
    int n,m,q,p,r,ans,t;
    string s;
    ans=0;
    cin>>n>>m>>p>>q>>r;
    vector<int> red;
    vector<int> green;
    vector<int> white;
    vector<int> plain;
    rep(i,0,p){
        cin>>t;
        red.push_back(t);
    }
    rep(i,0,q){
        cin>>t;
        green.push_back(t);
    }
    rep(i,0,r){
        cin>>t;
        white.push_back(t);
    }
    sort(red.begin(),red.end(),greater<int>());
    sort(green.begin(),green.end(),greater<int>());
    sort(white.begin(),white.end(),greater<int>());
    rep(i,0,n)
    plain.push_back(red[i]);
    rep(i,0,m)
    plain.push_back(green[i]);
    sort(plain.begin(),plain.end(),greater<int>());
    
    
    int c=0;
    rep(i,0,m+n){
        if(plain[i]<=white[c]){
            c++;
        }
        if(c==r){
            break;
        }
        if(i==m+n-1){
            if(white[c]<plain[i]&&c>0)
                c--;
        }
    }
    
    
    rep(i,0,c)
    plain.push_back(white[i]);
    sort(plain.begin(),plain.end(),greater<int>());
    rep(i,0,n+m)
    ans+=plain[i];
    cout<<ans<<endl;
}


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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    int num = 0;
    rep(i, n - 1)
    {
        num = max(num, a[i + 1]- a[i]);
    }
    num = max(num, abs(k+a[0] - a[n - 1]));
    cout << k - num << endl;
    return 0;
}


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

const int maxn = 50;
char board[maxn][maxn];
int dir[3] = {-1, 0, 1};
int row, col;

bool check(int bufferRow, int bufferCol, int row, int col){
	if(bufferRow < 0 || bufferRow >= row || bufferCol < 0 || bufferCol >= col){
		return false;
	}
	return true;
}

int countBomb(int currentRow, int currentCol, int row, int col, char board[maxn][maxn]){
	int ans = 0;
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			if(check(currentRow+dir[i], currentCol+dir[j], row, col) && board[currentRow+dir[i]][currentCol+dir[j]] == '#'){
				ans++;
			}
		}
	}
	return ans;
}

int main() {
	cin >> row >> col;

	for(int i=0; i<row; i++){
		for(int j=0; j<col; j++){
			cin >> board[i][j];
		}
	}

	for(int i=0; i<row; i++){
		for(int j=0; j<col; j++){
			if(board[i][j] == '.'){
				cout << countBomb(i, j, row, col, board);
			}
			else{
				cout << '#';
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
package main

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

func main() {
	nextReader = newScanner()
	X := nextInt64()
	T := []int64{0}
	for i := int64(1); i < int64(4000000); i++ {
		i5 := i * i * i * i * i
		for j, t := range T {
			// fmt.Printf("X=%d i5=%d t=%d\n", X, i5, t)
			if i5-t == X {
				fmt.Printf("%d %d", i, j)
				return
			} else if i5+t == X {
				fmt.Printf("%d %d", i, j*-1)
				return
			}
		}
		T = append(T, i5)
	}
}

var nextReader func() string

func newScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	// r.Split(bufio.ScanLines)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func nextStrings() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextInt64s(n int) []int64 {
	r := make([]int64, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt64()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}


Measured memory_bytes: 1768
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
ll N,M;
struct edge
{
    ll from; ll to; ll cost;
};
vector<edge> edges;
vector<ll> to[1010], ot[1010];
bool ok[1010], ko[1010];
bool dok[1010];
ll d[1010];

void debug(){
    rep(i,N){
        cerr << d[i] <<" ";
    }
    cerr << endl;
}
void dfs(ll v, ll p){
    if(ok[v])return;
    ok[v] = true;
    for(auto nv: to[v]){
        if(nv == p)continue;
        dfs(nv, v);
    }
}
void rdfs(ll v, ll p){
    if(ko[v])return;
    ko[v] = true;
    for(auto nv: ot[v]){
        if(nv == p)continue;
        rdfs(nv, v);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> N >> M;
    rep(i,M){
        ll a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        edges.push_back({a,b,-c});
        to[a].push_back(b);
        ot[b].push_back(a);
    }
    dfs(0,-1);
    rdfs(N-1, -1);
    rep(i,N)dok[i] = ok[i] & ko[i];
    rep(i,N)d[i] = INFLL;
    d[0] = 0;
    //bellman ford
    ll step = 0;
    while(1){
        //debug();
        bool upd = false;
        rep(i,M){
            edge e = edges[i];
            if(!dok[e.from])continue;
            if(!dok[e.to])continue;
            if(chmin(d[e.to], d[e.from] + e.cost)){
                upd = true;
            }
        }

        step++;
        if(!upd)break;
        if(step > N){
            cout << "inf" << endl;
            return 0;
        }
    }
    ll ans = -d[N-1];
    cout << ans << endl;
}

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

int N, K;

int main() {
	cin >> N >> K;
	long long ans = 0;
	for (int b = 1; b <= N; b++) {
		int p = N / b, r = N%b;
		ans += p*max(0, b - K) + max(0, r - K + 1);
	}

	if (K == 0) {
		ans -= N;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

#include <bits/stdc++.h>


using namespace std;

#define INPUT_INT(valName) int valName; cin >> valName
#define INPUT_LLINT(valName) long long int valName; cin >> valName;
#define INPUT_STR(valName) string valName; cin >> valName;
#define INPUT_LINE(valName) string valName; getline(cin,s);
#define INPUT_VECTOR_INT(valName, N) vector<int> valName(N); for(int i=0; i < N; ++i) { cin >> valName[i]; }
#define INPUT_VECTOR_DOUBLE(valName, N) vector<double> valName(N); for(int i=0; i < N; ++i) { cin >> valName[i]; }

#define OUTPUT(A) cout << (A) << endl;
#define OUTPUT2(A, B) cout << (A) << " " << (B) << endl;
#define OUTPUT3(A, B, C) cout << (A) << " " << (B) << " " << (C) << endl;

#define REP(valName, N) for(int valName = 0; valName < N; ++valName)

vector<string> split(const string& str, char delimiter) {
	vector<string> ret;
	string tmp = "";
	for (auto c : str) {
		if (c != delimiter) {
			tmp.push_back(c);
		} else {
			ret.push_back(tmp);
			tmp = "";
		}
	}
	ret.push_back(tmp);
	return ret;
}

template <typename T> void sortAsc(vector<T>& v) { sort(v.begin(), v.end(), less<T>()); }
template <typename T> void sortDesc(vector<T>& v) { sort(v.begin(), v.end(), greater<T>()); }

template <typename T> void insert(vector<T>& dest, const vector<T>& src) { copy(src.begin(), src.end(), back_inserter(dest)); }

template <long long int MOD> long long int mod_inv(long long int a) {
	long long b = MOD, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= MOD;
	if (u < 0) u += MOD;
	return u;
}

template <long long int MOD> long long int mod_add(long long int a, long long int b) {
	return (a + b) % MOD;
}

template <long long int MOD> long long int mod_sum(long long int a, long long int b) {
	return (a - b) % MOD;
}

template <long long int MOD> long long int mod_mul(long long int a, long long int b) {
	return (a % MOD) * (b % MOD) % MOD;
}

template <long long int MOD> long long int mod_mul(long long int a, long long int b, long long int c) {
	return mod_mul<MOD>(a, mod_mul<MOD>(b, c));
}

template <long long int MOD> long long int mod_div(long long int a, long long int b) {
	return (a % MOD) * mod_inv<MOD>(b) % MOD;
}


//------------------------------------------------------------------------------------------------------------------------------


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

	INPUT_INT(N);

	INPUT_VECTOR_INT(B, N-1);

	int n = 0;

	vector<int> A(N);
	A[N - 1] = B[N-2];

	for (int i = N - 2; i > 0; --i) {
		A[i] = min(B[i],B[i-1]);
	}
	A[0] = B[0];

	REP(i,N) {
		n += A[i];
	}


	OUTPUT(n);

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    string s; cin>>s;
    
    for(auto &c : s) cout << "x";
    cout << ln;
    
    return 0;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
struct dt
{
	LL v, ev;
	dt(LL v = 0, LL ev = 0) : v(v % MOD), ev(ev % MOD) {}
	dt followed(const dt &o) const
	{
		dt ret;
		ret.v = (v * o.ev % MOD + o.v) % MOD;
		ret.ev = ev * o.ev % MOD;
		return ret;
	}
};
LL modExp(LL x, LL y)
{
	if (y == 0) return 1;
	if (y == 1) return x % MOD;
	LL ret = modExp(x, y / 2);
	ret = ret * ret % MOD;
	if (y & 1) ret = ret * x % MOD;
	return ret;
}
dt connect(dt x, LL y)
{
	if (y == 0) return dt(0, 1);
	if (y == 1) return dt(x.v % MOD, x.ev % MOD);
	dt ret = connect(x, y / 2);
	ret = ret.followed(ret);
	if (y % 2) ret = ret.followed(x);
	return ret;
}
typedef vector<dt> EXP;
LL calc(const EXP &e)
{
	EXP o;
	for (int i = 0; i < e.size(); ++i) {
		if (e[i].v == -3) {
			dt t = dt(o.back().v * e[i + 1].v % MOD);
			o.pop_back();
			o.push_back(t);
			++i;
		}
		else o.push_back(e[i]);
	}
	LL ret = o[0].v;
	for (int i = 1; i < o.size(); i += 2) {
		if (o[i].v == -1) ret = (ret + o[i + 1].v) % MOD;
		else ret = (ret + MOD - o[i + 1].v) % MOD;
	}
	return ret;
}
EXP compress(char *s, int r)
{
	EXP se;
	LL v = -4, len;
	for (int i = 0; s[i]; ++i) {
		if (isdigit(s[i])) {
			if (v == -4) v = 0, len = 1;
			v *= 10, v += s[i] - '0';
			len *= 10;
			v %= MOD, len %= MOD;
		}
		else {
			if (v != -4) se.push_back(dt(v, len));
			v = -4;
			if (s[i] == '+') se.push_back(dt(-1));
			else if (s[i] == '-') se.push_back(dt(-2));
			else se.push_back(dt(-3));
		}
	}
	if (v != -4) se.push_back(dt(v, len));
	if (r == 1) return se;
	int p = -1;
	for (int i = 0; i < se.size(); ++i) {
		if (se[i].v >= 0) continue;
		if (p == -1) p = i;
		else if (se[p].v < se[i].v) p = i;
	}
	EXP ret;
	if (p == -1) {
		ret.push_back(connect(se[0], r));
		return ret;
	}
	EXP re;
	for (int i = p + 1; i < se.size() + p; ++i) {
		if (!re.empty()) {
			if (re.back().v >= 0 && se[i % se.size()].v >= 0) {
				dt t = re.back().followed(se[i % se.size()]);
				re.pop_back();
				re.push_back(t);
				continue;
			}
		}
		re.push_back(se[i % se.size()]);
	}
	if (se[p].v == -2) {
		for (int i = 0; i < re.size(); ++i) {
			if (re[i].v == -1) re[i].v = -2;
			else if (re[i].v == -2) re[i].v = -1;
		}
	}
	LL val = calc(re);
	if (se[p].v == -3) val = modExp(val, r - 1);
	else val = val * (r - 1) % MOD;
	for (int i = 0; i <= p; ++i) ret.push_back(se[i]);
	ret.push_back(dt(val));
	for (int i = p; i < se.size(); ++i) ret.push_back(se[i]);
	return ret;
}
int main()
{
	int n; EXP e;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int r;
		char s[200];
		scanf("%d%s", &r, s);
		EXP se = compress(s, r);
		for (int i = 0; i < se.size(); ++i) {
			if (!e.empty()) {
				if (e.back().v >= 0 && se[i].v >= 0) {
					dt t = e.back().followed(se[i]);
					e.pop_back();
					e.push_back(t);
					continue;
				}
			}
			e.push_back(se[i]);
		}
	}
	printf("%lld\n", calc(e));
	return 0;
}


Measured memory_bytes: 5920
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>

using namespace std;
typedef long long ll;

ll flg[1145141];
vector<ll > G[1145141];
vector<ll > ans;
//flg = 1 すでに到達済み 0＝まだ到達していない
void dfs(ll idx, ll from = -1){
    /*
    ll f = 1;
    if(flg[idx] == 1){
        return 0;
    }
    */

    //参照したので到達済みフラグを１にする
    //flg[idx] = 1;

    for(ll i = 0; i < G[idx].size(); i++){
        //次の行き先は？
        ll to = G[idx][i];
        //同じだったらもう処理しない
        //頂点に戻ってきたら
        //cout << "a" << endl;
        if(to == from){
            continue;
        }

        ans[to] += ans[idx];
        dfs(to, idx);
        //閉路は無い想定なので不要！
        //from = idx > toへ
        //もしすでに到達済みの場所を参照したら、木ではなく閉路のある無向グラフ
        /*
        if(dfs(to, idx) == 1){
            //閉路ですよ
            f = 0;
        }
        */
    }
    //1が帰ったら木ですよ
    /* 
    return f;
    */

}

int main(){

    ll N, Q;
    cin >> N >> Q;
    ans.resize(N);
    //グラフを貼ります(今回は木)
    vector<ll > u(N-1);
    vector<ll > v(N-1);
    for(ll i = 0; i < N-1; i++){
        cin >> u[i];
        cin >> v[i];
        u[i]--;
        v[i]--;
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
    }
    //あるノードからそれ以下のノードに流し込むコストをどんどん加算していく
    for(ll i = 0; i < Q; i++){
        ll p, x;
        cin >> p >> x;
        ans[p-1] += x;
    }
    //伝搬実行
    dfs(0);
    for(ll i = 0; i < N - 1; i++){
        cout << ans[i] << " ";
    }
    
    cout << ans[N - 1] << endl;


}

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

using namespace std;

#define FOR(i,n) for(int i=0; i<n; ++i)
#define FORR(i,a,n) for(int i=a; i<n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
//int in() { int x; scanf("%d", &x); return x; }
//ll lin() { ll x; scanf("%lld", &x); return x; }
void printfv(VI a){ int n = a.size(); FOR(i, n) cout << a[i] << " "; }

int main(void){

	string s;
	cin >> s;

	if(((s[0] == s[1] && s[2] == s[3]) || (s[0] == s[2] && s[1] == s[3]) || (s[2] == s[1] && s[0] == s[3])) 
		&& !(s[0] == s[1] && s[0] == s[2] && s[0] == s[3])){
		cout <<  "Yes";
	} else {
		cout << "No";
	}

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N;
  cin >> N;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  double ret = 0;
  rep(i,N){
    ret += 1.0 / v[i];
  }

  printf("%.14lf\n", 1.0 / ret);
  
  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(intl i=0;i<(intl)(n);i++)
#define Rep1(i,n) for(intl i=1;i<(intl)(n)+1;i++)
#define vec vector
#define fi first
#define se second
#define pushb push_back
#define popb pop_back
#define SortA(v) sort(v.begin(), v.end())
#define SortD(v) sort(v.rbegin(), v.rend())
using intl = int64_t;
using vi = vec<intl>;
using vvi = vec<vi>;
vec<intl> dx = {0, 1, 0, -1, 1, 1, -1, -1};
vec<intl> dy = {1, 0, -1, 0, 1, -1, 1, -1};

int main(){
  double a,b,h,m,angle,c;
  cin >>a>>b>>h>>m;
  angle =( (h+m/60)/12 - m/60) *2*M_PI;
  if (angle > M_PI) { angle = 2 * M_PI -angle;} 
  c=pow( a*a + b*b - 2*a*b* cos(angle) ,0.5);
  cout << std::fixed << std::setprecision(15) << c <<endl;
}

Measured memory_bytes: 4328
#include <stdio.h>
#include <math.h>
 #define PI 3.14159265358979323846264338327950L
 int main(void)
 {
      int a, b, h, m;
      scanf("%d%d%d%d", &a, &b, &h, &m);
      long double rad = PI * 2 * ((long double)h / 12.0 + ((long double)m / 60.0) / 12.0 - (long double)m / 60.0);
      long double rsq = (long double)(a * a + b * b) - (long double)(2 * a * b) * cos(rad);
      printf("%20.20Lf\n", sqrt(rsq));
      return 0;
  }


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

int main() {
	int N;
	long long K;
	cin >> N >> K;
	int A[N + 1];
	int V[N + 1];
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		V[i] = -1;
	}
	int i = 1, rep;
	V[i] = 0;
	while (true) {
		if (V[A[i]] != -1) {
			rep = V[i] - V[A[i]] + 1;
			break;
		}
		V[A[i]] = V[i] + 1;
		i = A[i];
		K--;
		if (K == 0) {
			cout << i << endl;
			return 0;
		}
	}
	K %= rep;
	for (int j = 0; j < K; j++) {
		i = A[i];
	}
	cout << i << endl;
	return 0;
}


Measured memory_bytes: 5204
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(a<=c && c<=b){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 21844
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = 0
d2sqr = 0
d3cube = 0
d_inf = 0

for i in range(n):
    d1 += abs(a[i] - b[i])
    d2sqr += (a[i] - b[i]) ** 2
    d3cube += abs(a[i] - b[i]) ** 3
    d_inf = max(d_inf, abs(a[i] - b[i]))

d2 = d2sqr ** (1/2)
d3 = d3cube ** (1/3)

print(d1)
print(d2)
print(d3)
print(d_inf)



Measured memory_bytes: 5640
#include<stdio.h>
int main()
{
	char s[150];
	int i;
	gets(s);
	for(i = 0;s[i] != '\0';i++)
	{
		if(i == 0)
			printf("%c",s[i]);
		else
		{
			if(s[i] >= 'A' && s[i] <= 'Z')
			{
		     	if(s[i - 1] < 'A' || (s[i - 1] > 'Z' && s[i - 1] < 'a') || s[i - 1] > 'z')
			    	printf("%c",s[i]);
			}
		}
	}
	printf("\n");
	return 0;
}



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

/*
template<size_t max_N>
struct Prime{
    bool is_prime[max_N];
    constexpr Prime() : is_prime() {
        for(int i = 0; i < max_N; i++) is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;
        for (int i = 0; i < max_N; i++)
        {
            if(!is_prime[i]) continue;
            for (int j = i*i; j < max_N; j+=i) is_prime[j] = false;
        }
        
    }
};
*/

template<size_t max_N, size_t prime_size>
struct Prime{
    bool sieve[max_N];
    int_fast64_t prime[prime_size];
    size_t counter = 0;
    constexpr Prime() : sieve(), prime() {
        for(int_fast64_t i = 0; i < max_N; ++i)
            sieve[i] = true;
        sieve[0] = sieve[1] = false;
        for(int_fast64_t i = 2; i < max_N; ++i){
            if(sieve[i]){
                prime[counter] = i;
                ++counter;
                if(counter > prime_size)break;
            }
            for(int_fast64_t j = i * i; j < max_N; j += i)
                sieve[j] = false;
        }
    }
};
int main(){
    using namespace std;
    const int PRIME_MAX = 1e5+100;
    int Q; cin >> Q;
    vector<int> l(Q), r(Q);
    vector<int> n_like(PRIME_MAX, 0);
    for (int i = 0; i < Q; i++) cin >> l[i] >> r[i];
    constexpr auto p = Prime<PRIME_MAX, 10000>();
    for (int i = 1; i < PRIME_MAX; i++)
    {
        if(i%2==1 && p.sieve[i] && p.sieve[(i+1)/2]) n_like[i] = n_like[i-1] + 1;
        else n_like[i] = n_like[i-1];
    }
    
    for (int i = 0; i < Q; i++)
    {
        cout << n_like[r[i]] - n_like[l[i]-1] << endl;
    }
}


Measured memory_bytes: 2048
#include<iostream>
#include<string.h>
using namespace std;
int dp[1005][9];
int check(char a){
    switch(a){
        case 'J':
            return 1;
        case 'O':
            return 2;
        case 'I':
            return 4;
        default:
            return 0;
    }
}
int main(){
    int n,ans;
    string s;
    cin>>n>>s;
    memset(dp,0,sizeof(dp));
    dp[0][1]=1;
    char pre='J';
    for(int i=1;i<=s.length();i++){
        char now=s[i-1];
        int p=check(pre);
        int n=check(now);
        for(int k=0;k<8;k++){
            for(int j=0;j<8;j++){
                if(((k&p)&&(j&n)&&(j&k))!=0){
                    dp[i][j]+=dp[i-1][k];
                    dp[i][j]%=10007;
                }
            }
        }
        pre=now;
    }
    for(int i=0;i<8;i++)
        ans+=dp[s.length()][i];
    ans=ans%10007;
    cout<<ans<<endl;
}

Measured memory_bytes: 1248
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int maxn=200111;
const int mod=1e9+7;

int n,m,dp[maxn],pre[maxn];
char s[maxn];

int main()
{
	get2(n,m);
	scanf("%s",s+1);
	
	while(m>1&&s[m]==s[m-1])m--;
	if(m==1)
	{
		dp[0]=2;dp[1]=1;
		for(int i=2;i<=n;i++)
		{
			dp[i]=dp[i-1]+dp[i-2];
			if(dp[i]>=mod)dp[i]-=mod;
		}
		printf("%d\n",dp[n]);
		return 0;
	}
	
	if(n%2==1)
	{
		puts("0");
		return 0;
	}
	
	if(s[m]==s[1])m--;
	int bound=inf;
	for(int i=1;i<=m;i++)if(s[i]==s[1]&&s[i]!=s[i-1])
	{
		int len=0;
		while(s[i+len]==s[i])len++;
		if(len%2==1)bound=min(bound,len);
		else if(i==1)bound=min(bound,len+1);
	}
	bound=min(bound,n-1);
	
	n/=2;bound=(bound+1)/2;
	dp[0]=1;pre[0]=1;
	int sum=0;
	for(int i=0;i<=n;i++)
	{
		if(i)
		{
			if(i<=bound)dp[i]=pre[i-1];
			else dp[i]=(pre[i-1]-pre[i-bound-1]+mod)%mod;
			pre[i]=(pre[i-1]+dp[i])%mod;
		}
		if(i>=n-bound)
		{
			int coef=((n-i)*2-1);
			if(i==n)coef=1;
			sum=(sum+(LL)dp[i]*coef)%mod;
		}
	}
	printendl(sum);
	
	return 0;
}

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

int main(){
  int N,K;
  cin>>N>>K;
  int h[N];
  for (int i=0;i<N;i++){
    cin>>h[i];
  }
  sort(h,h+N);
  int maxhdif=INT_MAX;
  for (int i=0;i<N-K+1;i++){
    if(h[i+K-1]-h[i]<maxhdif){
      maxhdif=h[i+K-1]-h[i];
    }
  }
  cout<<maxhdif<<endl;

  return 0;
  
}

  
  
    

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <list>
#include <cmath>
#include <map>
#include <utility>

#define _USE_MATH_DEFINES
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define INF 999999999
#define atcoder 1000000007
#define MAX_N 100

using namespace std;

int main() {

	string s;
	cin >> s;
	if (s[0] == s[2])
		cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main(){
    string str;
    cin >> str;
    str = str.substr(5,2);
    
    if(str == "04" || str == "03" || str =="02" || str == "01"){
        cout << "Heisei" << endl;
    }else{
        cout << "TBD" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < (n); i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  long foo = 0;
  rep (i, N) {
    long a;
    cin >> a;
    if (a % 2) foo++;
  }
  if (foo % 2) cout << "NO" << endl;
  else cout << "YES" << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
n, m = list(map(int, input().split()))
matrix_a = [list(map(int, input().split())) for i in range(n)]
matrix_b = [int(input()) for i in range(m)]
for i in range(n):
    print(sum([x*y for (x,y) in zip(matrix_b,matrix_a[i])]))

Measured memory_bytes: 8112
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>



#define rep(i,p,q) for(int i = p;i < q;i++)
#define ll long long

ll CONS = 1e9 + 7;

using namespace std;

//ABC 100
int main(void) {
	ll n, m;
	cin >> n >> m;
	vector<ll> x = vector<ll>(n);
	vector<ll> y = vector<ll>(n);
	vector<ll> z = vector<ll>(n);
	rep(i, 0, n) cin >> x[i] >> y[i] >> z[i];
	
	ll ans = 0;
	rep(i, 0, 8) {
		vector<ll> values = vector<ll>(n);
		ll xKei, yKei, zKei;
		if (i & 1) xKei = 1;
		else xKei = -1;
		if (i & 1 << 1)yKei = 1;
		else yKei = -1;
		if (i & 1 << 2) zKei = 1;
		else zKei = -1;
		rep(j, 0, n) {
			values[j] = x[j] * xKei + y[j] * yKei + z[j] * zKei;
		}
		sort(values.begin(), values.end(), greater<>());
		ll newAns = 0;
		rep(j, 0, m)newAns += values[j];
		ans = max(ans, newAns);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define pi acos(-1)
#define line cout<<"----------------------------"<<endl
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
const ll  mx=3000009;
ll iv[mx];
ll facto[mx],facto1[mx];
void pre()
{
    facto[0]=1,facto1[0]=1;
    iv[1]=1;
    for(int i=2;i<mx;i++) iv[i]=mod-(mod/i)*iv[mod%i]%mod;;
    for(ll  i=1;i<mx;i++)
    {
        facto[i]=(facto[i-1]*i)%mod;
        facto1[i]=(facto1[i-1]*iv[i])%mod;
 
    }
}
int  main()
{
    pre();
    ll  r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    ll  ans=0;
    for(ll  i=c1;i<=c2;i++)
    {
        ans+=(facto[r2+i+1]*facto1[i+1])%mod*facto1[r2]%mod;
        ans-=(facto[r1+i]*facto1[i+1])%mod*facto1[r1-1]%mod;
        ans=(ans+mod)%mod;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 70528
use std::io::*;
use std::str::FromStr;
use std::cmp::min;

fn main() {
    let x: usize = read();
    let y: usize = read();
    let z: usize = read();
    let k: usize = read();
    let a: Vec<usize> = (0..x).map(|_| read()).collect();
    let b: Vec<usize> = (0..y).map(|_| read()).collect();
    let mut c: Vec<usize> = (0..z).map(|_| read()).collect();
    c.sort();

    let mut ab: Vec<usize> = Vec::new();
    for i in 0..x {
        for j in 0..y {
            ab.push(a[i] + b[j]);
        }
    }
    ab.sort();
    
    let mut sum: Vec<usize> = Vec::new();
    for i in 0..min(x*y, k) {
        for j in 0..min(z, k) {
            sum.push(ab[x * y - 1 - i] + c[z - 1 - j]);
        }
    }
    sum.sort();

    for i in 0..k {
        println!("{}", sum[sum.len() - 1 - i]);
    }
}

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


Measured memory_bytes: 44276
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define BR cout<<endl;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}

double expect(int x){
    double kitai,tem=0;
    for(int i=1;i<=x;i++){
        tem += i;
    }
    kitai = tem/x;
    cout << kitai << endl;
    return kitai;
    
}

int main(){
    int H,W,h,w;
    cin >> H >> W >> h >> w;

    cout << H * W  + h * w - h * W - w * H << endl; 
    return 0;
}



Measured memory_bytes: 3620