akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, S: str):
    rep_ss = []
    check_c = S[0]
    cnt = 0
    for char in S:
        if check_c == char:
            cnt += 1
        else:
            rep_ss.append(cnt)
            cnt = 1
            check_c = char
    rep_ss.append(cnt)
    adj = 0
    if K >= len(rep_ss)//2:
        K = len(rep_ss) // 2
        if len(rep_ss) % 2 == 0:
            K -= 1
            adj = 1
    ans = N - len(rep_ss) + 2 * K + adj
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4212
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
using llong = long long;
using ullong = unsigned long long;

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

  int num=0;
  char c = 'A';
  for(int i=0;i<N;++i){
    if(c!=S[i]){
      num++;
      c = S[i];
    }
  }
  cout << num << endl;
}


Measured memory_bytes: 512
s = "100 10 25"
list = list(map(int, input().split()))
#list = list(map(int, s.split()))

a = abs(list[1]-list[0])
b = abs(list[1]-list[2])
c = abs(list[2]-list[0])
if (a < b):
	print(b if b>c else c)
else :
	print(a if c<a else c)


Measured memory_bytes: 3060
#include <cstdlib>
#include <iostream>


int main(void) {
    std::string s;
    std::cin >> s;

    bool tappable = true;
    for (auto itr = s.begin(); itr != s.end(); ++itr) {
        /*
         * ODD
         */
        if (std::distance(s.begin(), itr) % 2 == 0) {
            if (*itr == 'L') {
                tappable = false;
            }
        }
        /*
         * EVEN
         */
        else {
            if (*itr == 'R') {
                tappable = false;
            }
        }

    }
    if (tappable) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.nextLine();
    int[] al = new int[26];
    for(int i = 0; i < S.length(); i++){
      al[(int)S.charAt(i) - 97]++;
    }
    
    for(int i = 0; i < 26; i++){
      if(al[i] % 2 != 0){
        System.out.println("No");
        return;
      }
    }
    
    System.out.println("Yes");
  }
}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e3 + 13;
int n, x, ans = 1e18;
int kek[N][N];
signed main()
{
#ifdef home
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin >> n >> x;
    vector<int> in(n), mda;
    for (int i = 0; i < n; i++)
        cin >> in[i];
    mda = in;
    for (int i = 0; i < n; i++)
        mda.push_back(in[i]);
    for (int i = 0; i < n + n; i++)
    {
        kek[i][i] = mda[i];
        for (int j = i + 1; j < n + n; j++)
        {
            kek[i][j] = min(kek[i][j - 1], mda[j]);
        }
    }
    for (int mx = 0; mx < n; mx++)
    {
        int lans = 0;
        for (int i = n; i < n + n; i++)
        {
            lans += kek[i - mx][i];
        }
        ans = min(ans, lans + mx * x);
    }
    cout << ans;
}

Measured memory_bytes: 125312
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    ans = 0
    for i, a in enumerate(A):
        if ((i + 1) % 2 == 1) and (a % 2 == 1):
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9176
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    ll a,b;
    cin >> a >> b;
    if((a<0 &&  b>0) || (a>0 && b<0)){
        cout << "Zero" << endl;
    }else if(a>0 && b>0){
        cout << "Positive" << endl;
    }else{
        if((abs(a)-abs(b))%2==0){
            cout << "Negative" << endl;
        }else{
            cout << "Positive" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
ans = 0
wnasi = []
for i in range(1, int(pow(N - 1, 0.5)) + 1):
    if (N - 1) % i == 0:
        wnasi.append(i)
        if i != (N - 1) // i:
            wnasi.append((N - 1) // i)
ans += len(wnasi) - 1
wari = []
for i in range(2, int(pow(N, 0.5)) + 1):
    if N % i == 0:
        wari.append(i)
        if i != N // i:
            wari.append(N // i)

for i in wari:
    if i == 1:
        continue
    tmpN = N
    while True:
        if tmpN % i == 0:
            tmpN //= i
        else:
            if tmpN % i == 1:
                ans += 1
            break

print(ans + 1)

Measured memory_bytes: 9420
// ALDS1_6_C: Quick Sort

fn scan<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

fn scan_cards(n: usize) -> Vec<Card> {
    let mut vec: Vec<Card> = Vec::new();
    for _ in 0..n {
        let s: String = scan();
        let mut it = s.split_whitespace();
        let a: char = it.next().unwrap().to_string().chars().collect::<Vec<char>>()[0];
        let b: i64 = it.next().unwrap().parse().ok().unwrap();
        let c = Card{ suit: a, value: b };
        vec.push(c);
    }
    vec
}

#[derive(Clone, Copy)]
struct Card {
    suit: char,
    value: i64,
}

fn merge(a: &mut Vec<Card>, left: usize, mid: usize, right: usize) {
    let mut l: Vec<Card> = Vec::new();
    let mut r: Vec<Card> = Vec::new();
    for i in left..mid {
        l.push(a[i]);
    }
    for i in mid..right {
        r.push(a[i]);
    }
    let c = Card{ suit: 'z', value: std::i64::MAX };
    l.push(c);
    r.push(c);
    let mut i: usize = 0;
    let mut j: usize = 0;
    for k in left..right {
        if l[i].value <= r[j].value {
            a[k] = l[i];
            i += 1;
        } else {
            a[k] = r[j];
            j += 1;
        }
    }
}

fn merge_sort(a: &mut Vec<Card>, left: usize, right: usize) {
    if left + 1 < right {
        let mid = (left + right) / 2;
        merge_sort(a, left, mid);
        merge_sort(a, mid, right);
        merge(a, left, mid, right);
    }
}

fn partition(a: &mut Vec<Card>, p: usize, r: usize) -> usize {
    let x = a[r];
    let mut i = p;
    for j in p..r {
        if a[j].value <= x.value {
            a.swap(i, j);
            i += 1;
        }
    }
    a.swap(i, r);
    i
}

fn quick_sort(a: &mut Vec<Card>, p:usize, r: usize) {
    if p < r {
        let q = partition(a, p, r);
        quick_sort(a, p, q - 1);
        quick_sort(a, q + 1, r);
    }
}

fn main() {
    let n: usize = scan();
    let mut a: Vec<Card> = scan_cards(n);
    let mut b = a.clone();
    merge_sort(&mut a, 0, n);
    quick_sort(&mut b, 0, n - 1);

    let mut stable = true;
    for i in 0..n {
        if a[i].suit != b[i].suit {
            stable = false;
            break;
        }
    }

    if stable {
        println!("Stable");
    } else {
        println!("Not stable");
    }

    for i in 0..n {
        println!("{} {}", b[i].suit, b[i].value);
    }
}


Measured memory_bytes: 11100
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr ll mod = 1e9+7;
int main() {
  int n;
  cin >> n;
  ll res = 1;
  for (int i = 1; i <= n; i++) (res *= i) %= mod;
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 256
//Radhe Radhe
#include<bits/stdc++.h>//157B
#define ll long long
#define fixed cout.setf(ios::fixed);
#define rep1    for( i=0; i<n; i++)
#define Precise cout.precision(7);
using namespace std;

int main()
{
    ll i,j,a,b,n,x,y,z;
    cin>>a>>b>>n;
    x=min(b-1,n);
    y=(a*x)/b;
    z=a*(x/b);
    cout<<y-z<<endl;
    return 0;
}





Measured memory_bytes: 3644
#include <bits/stdc++.h>
        
using namespace std;
        
typedef long long ll;
#define mp make_pair
#define pub push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define db double

int n, m, k;
  
int main(){ 
    srand('D' + 'E' + 'N' + 'I' + 'S' + 'S' + 'O' + 'N' + time(NULL));
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("spoiler.in", "r", stdin);
    //freopen("spoiler.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i <= n; i++){
    	for (int j = 0; j <= m; j++){
    		ll ans = i * m;
    		ll bal = n - i;
    		bal -= i;
    		ans += bal * j;

    		if (ans == k) cout << "Yes", exit(0);
    	}
    }
    cout << "No";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main(){
    int N,K,i,ans=0;
    cin >> N >> K;
    vector<int> l(N);
    for(i=0;i<N;i++) cin >> l.at(i);
    sort(l.begin(),l.end());
    for(i=0;i<K;i++) ans += l.at(N-1-i);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

fn main() {
    input! {
        N: usize,
        A: usize,
        B: usize,
    }

    let mut ans = 0;
    for i in 1..(N+1) {
        let mut tmp = 0;
        let mut n = i;
        while n > 0 {
            tmp += n % 10;
            n /= 10;
        }
        if A <= tmp && tmp <= B {
            ans += i;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
module Main where

import Control.Applicative
import Text.Printf
import Numeric

main :: IO ()
main = loop

loop :: IO ()
loop = do
  { [as, os, bs] <- getStrings
  ; case os of
      "?" -> return ()
      "+" -> print (readInt' as + readInt' bs) >> loop
      "-" -> print (readInt' as - readInt' bs) >> loop
      "*" -> print (readInt' as * readInt' bs) >> loop
      "/" -> print (readInt' as `div` readInt' bs) >> loop
  }
--

getInts :: IO[Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble x = showFFloat Nothing x ""

getStrings :: IO [String]
getStrings = words <$> getLine

readInt' :: String -> Int
readInt' = read 



Measured memory_bytes: 4188
t[9999];n,p,a;main(x){for(;scanf("%d%d",&n,t)*n;printf("%d\n",a)){for(p=n;a=p;)scanf("%d",t+p--);for(;p++<*t;n>1?n-=x+t[n-x]:0,a=a|n>1?a:p)scanf("%d",&x);}}

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n;
	cin>>n;
	ll a[n];
	priority_queue<long double,vector<long double>,greater<long double> > q;
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];
		q.push(a[i]);
	}
	long double ans = 0;
	while(q.size()!=1)
	{
		long double Ans = q.top();
		q.pop();
		long double Ans1 = q.top();
		q.pop();
		q.push((Ans+Ans1*1.0)/2);
 	}
 	cout<<fixed<<setprecision(13)<<q.top();

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N;
  cin>>N;
  vector<int>p(N);
  for(int i=0;i<N;i++) cin>>p[i];
  vector<int>P(N);
  for(int i=0;i<N;i++) P[i]=i+1;
  int s=0;
  for(int i=0;i<N;i++){
	if(p[i]!=P[i]) s++;
  }
  if(s==0||s==2) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
  

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	
	int k,x,n; 
	
	scanf("%d",&x);
	
	n=1;
	
	for(k=1;k<=3;k++){
		n=n*x;
	}
	
	printf("%d\n",n);
	
	return 0;
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=200005;
int n,a[max_n];
int s[max_n];
int ans[max_n];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    s[n+1]=n+1;
    for(int i=n;i>=1;i--){
        if((n-i)%2==0)s[i]=s[i+1]-i;
        else s[i]=s[i+1]+i;
    }
    for(int i=1;i<=n;i++)ans[s[i]]=a[i];
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,w;
    cin>>h>>w;
    char v[h][w];
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
            cin>>v[i][j];
    }
    long long dp[h][w]={0};
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
    {
       dp[i][j]=0;
    }
    }
    for(int i=0;i<h;i++)
    {
        if(v[i][0]=='#')
            break;
            dp[i][0]=1;
    }
    for(int i=0;i<w;i++)
    {
        if(v[0][i]=='#')
            break;
            dp[0][i]=1;
    }
    for(int i=1;i<h;i++)
        for(int j=1;j<w;j++)
    {
        if(v[i][j]=='#')
            dp[i][j]=0;
        else{
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
        }
    }
    cout<<dp[h-1][w-1]%1000000007<<endl;
    return 0;
}


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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> s(H);
  for (int i = 0; i < H; i++) {
    cin >> s[i];
  }
  const int dx[] = {0, 0, -1, 1};
  const int dy[] = {-1, 1, 0, 0};
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (s[i][j] == '#') {
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
          int y = i + dy[k];
          int x = j + dx[k];
          if (0 <= y && y < H && 0 <= x && x < W) {
            if (s[y][x] == '#') {
              cnt++;
            }
          }
        }
        if (cnt == 0) {
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int cnt;
int t;
int field[121][121];

void dfs(int x,int y,int turn){
  int dx[6] = {0, 1, 1, 0, -1, -1};
  int dy[6] = {1, 1, 0, -1, -1, 0};

  if(x<0 || x>120 || y<0 || y>120) return;

  if(turn>t) return;

  /*if(field[x][y]==0){
    field[x][y] = turn;
    if(turn==0) field[x][y]=100;
    //cnt++;
  }
  else return;
  */

  if(field[x][y] <= turn && field[x][y] > 0) return;
  if(field[x][y] == -1) return;

  field[x][y] = turn;

  for(int i=0;i<6;++i){
    dfs(x+dx[i],y+dy[i],turn+1);
  }
  //cout << turn << " " << x-30 << " " << y-30 << endl;
  return;
}

int main(){

  for(int n;cin>>t>>n,t;){
    cnt = 0;

    // initialize
    for(int i=0;i<121;++i){
      for(int j=0;j<121;++j){
        field[i][j] = 0;
      }
    }

    // syougaibutsu
    for(int i=0;i<n;++i){
      int x,y;
      cin>>x>>y;
      field[x+60][y+60] = -1;
    }

 /*   for(int i=0;i<61;++i){
      for(int j=0;j<61;++j){
       cout << field[i][j] << " ";
      }
      cout << endl;
    }
*/
    int sx,sy;
    cin>>sx>>sy;

    dfs(sx+60,sy+60,0);
    field[sx+60][sy+60]=1;

    for(int i=0;i<121;++i){
      for(int j=0;j<121;++j){
        if(field[i][j]>0) cnt++;
     }
    }

    cout << cnt << endl;

  }

  return 0;
}

Measured memory_bytes: 1216
n,m = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|a| -a}
arr = [a_arr]

while m >= 1 do
  m -= 1
  a = a_arr.shift
  a /= 2
  index = a_arr.bsearch_index{|x| a >= x}
  if index.nil? then
    a_arr << a
  elsif m >= index
    a_arr.insert(index, a)
    (0..(index-1)).each do |i|
      a_arr[i] /= 2
    end
    a_arr = a_arr.sort_by{|a| -a}
    m -= index
  else
    a_arr.insert(index, a)
    (0..(m-1)).each do |i|
      a_arr[i] /= 2
    end
    m = 0
  end
end

puts a_arr.inject(&:+)




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

int main(){
  int a,b;
  cin >> a >> b;
  if(a==1&&b==2 || a==2&&b==1){
    cout << 3 << endl;
  }else if(a==1&&b==3 || a==3&&b==1){
    cout << 2 << endl;
  }else{
    cout << 1 << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define pb push_back
#define vec vector<int>
#define fo(i, n) for (int i = 0; i < n; i++)
#define foo(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define deb(x) cout << #x << " --> " << x << endl;
#define deb1a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
        cout << it << " ";        \
    cout << endl;
#define deb2a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
    {                             \
        for (auto it1 : it)       \
        {                         \
            cout << it1 << " ";   \
        }                         \
        cout << endl;             \
    }
#define deb3a(v)                               \
    cout << #v << "-->" << endl;               \
    for (auto it : v)                          \
    {                                          \
        cout << it.fi << " " << it.se << endl; \
    }
#define mod 1000000007
#define so(v) sort(v.begin(), v.end())
#define fi first
#define se second
#define db1(x) cout << #x << "=" << x << endl
#define db2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
int mI(int a, int m)
{
    return power(a, m - 2, m);
}
vector<vector<int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

#define MAXN 10000001
#define double long double



void solve()
{
    int n;
    cin >> n;
    int ans = power(10, n, mod);
    int ans1 = 2*power(9, n, mod) - power(8, n, mod) ;
    ans1 %= mod;
    if(ans1<0){
        ans1 += mod;
    }
    ans -= ans1;
    if(ans<0){
        ans += mod;
    }
    cout << ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(0));

    // FILE *fin = freopen("ip.txt","r",stdin);
    // FILE *fout = freopen("op.txt","w",stdout);
    int t = 1, nn = 1;
    //cin >> t;
    while (t--)
    {
        // cout << "Case #" << nn << ":"
        //      << " ";
        // nn++;
        
        solve();
    }
}

Measured memory_bytes: 3656
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int c,y,t;
    c=a*b;
    y=a-b;
    t=a+b;
    if(c>=t&&c>=y)
    {
        cout<<c;
    }
    else if(y>=c&&y>=t)
    {
        cout<<y;
    }
    else if(t>=c&&t>=y)
    {
        cout<<t;
    }



    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int a,b,c,x,m,n,i,j,num=0,f1;
  scanf("%d%d%d%d",&a,&b,&c,&x);
  f1=x/500;
  if(f1<a)
    a=f1;
   for(i=0;i<=a;i++)
   {
      m=x-i*500;
      for(j=0;j<=b;j++)
      {
        n=m-100*j;
        if(n>=0&&n%50==0&&n/50<=c)
            num++;
      }

   }
   printf("%d\n",num);
   return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N, x;
    cin >> N >> x;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (x >= a[i]) {
            ans++;
            x -= a[i];
        }
        else {
            x = 0;
        }
    }
    if (x) ans--;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a;
	double n;
	cin>>a;
	
		for(int i=a;i>=0;i--){
			n=sqrt(i);
			if(int(sqrt(i))==n){
				printf("%d\n",i);
				return 0;
			}
		}
	
	
	
	return 0;
} 

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

using namespace std;

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

    if(a*b % 2 == 0)
    {
        cout << "Even" << endl;
    }
    else
    {
        cout << "Odd" << endl;
    }
    

    return 0;
}

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

int main() {
    int n, m, ret = 0;
    std::cin >> n >> m;
    std::vector<std::deque<int>> g(n);
    std::deque<std::pair<int, int>> e;
    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
        e.emplace_back(a, b);
    }

    for (int i = 0; i < m; i++) {
        auto& edge = e[i];
        std::deque<int> q;
        std::vector<bool> done(n, false);
        q.push_back(0);
        while (!q.empty()) {
            auto curr = q.front();
            done[curr] = true;
            for (auto to : g[curr]) if (!done[to] && (edge.first != std::min(curr, to) || edge.second != std::max(curr, to))) q.push_back(to);
            q.pop_front();
        }
        if (!std::all_of(done.begin(), done.end(), [](auto b) { return b; })) ret++;
    }
    
    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int comp(const void* a, const void* b) {
  return *(int*)b - *(int*)a;
}

#define BUF_SIZE 200
int main(void) {
  FILE *fp = stdin;
  char line[BUF_SIZE];

  if(!fgets(line, BUF_SIZE, fp)) return 0;
  int num, k;
  sscanf(line, "%d %d", &num, &k);
  int *arr = malloc(sizeof(int)*num);
  // line 2
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  int i;
  char* tmpbuf = line;
  for(i = 0; i < num; i++) {
    char *buf = strtok(tmpbuf, " ");
    arr[i] = strtol(buf, NULL, 10);
    tmpbuf = NULL;
  }
  qsort(arr, num, sizeof(int), comp); // descending

  int sum = 0;
  for(i = 0; i < k; i++) {
    sum += arr[i];
  }

  printf("%d\n", sum);
  return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 998244353;

const int MAXN = 2e3 + 5;

ll dp[MAXN][MAXN][2];

ll c[2 * MAXN][2 * MAXN];

ll ans[2 * MAXN];

ll get_ans(int n, int k, int lim) {
	/*if (k == 1) {
		printf("%d %d %d %lld\n", n, k, lim, c[n + lim - k - 1][lim - k - 1]);
		return c[n + lim - 2][lim - 2];
	}*/
	ll ans = 0ll;
	REPN(i, 0, n) {
		ll mul = 0ll;
		if (k <= lim) {
			mul = c[n - i + lim - k][lim - k];
		} else {
			if (i == n) {
				mul = 1;
			} else {
				mul = 0;
			}
		}
		ll mul2 = (dp[i][k / 2][0] + dp[i][k / 2][1]) % MOD;
		ans = (ans + mul * mul2) % MOD;
		
		/*if (k == 5) {
			printf("n = %d, k = %d, lim = %d, i = %d: %lld %lld %lld\n", n, k, lim,i,  mul, mul2, ans);
		}*/
	}
	return ans;
}

void solve(){
	int lim = 2001;
	REPN(i, 0, lim) {
		dp[0][i][0] = 1;
	}
	dp[0][1][0] = 1;
	REPN(i, 0, lim) {
		REPN(j, 1, lim) {
			dp[i + 1][j][1] = (dp[i + 1][j][1] + 2 * dp[i][j][0] + dp[i][j][1]) % MOD;
			if (i) {
				dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][0] + dp[i][j][1]) % MOD;
			}
		}
	}
	
	/*REPN(i, 1, lim) {
		REPN(j, 1, lim) {
			printf("%d %d %lld %lld\n", i, j, dp[i][j][0], dp[i][j][1]);
		}
	}*/
	
	REPN(i, 0, 2 * lim) {
		c[i][0] = c[i][i] = 1;
		REP(j, 1, i) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		}
		
		/*REPN(j, 0, i) {
			printf("%ld ", c[i][j]);
		}
		putchar('\n');*/
	}
	
	int n, k;
	cin >> k >> n;
	REPN(i, 2, 2 * k) {
		if (i <= k + 1) {
			if (i % 2 == 1) {
				//ans[i] = get_ans(n, i, k);
				//ans[i - 1] = ans[i];
			} else {
				ans[i] = (get_ans(n, i - 1, k - 1) + get_ans(n - 1, i - 1, k - 1)) % MOD;
				ans[i + 1] = ans[i];
			}
		} else {
			ans[i] = ans[2 * k + 2 - i];
		}
		cout << ans[i] << endl;
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 187008
#include "bits/stdc++.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = 1e9;
const LL LLINF = 1e18;
#define pow10(n) int(1e##n + n)

void solve()
{
    string S, T;
    cin >> S >> T;
    int A;
    cin >> A;
    int B;
    cin >> B;
    string U;
    cin >> U;

    if (U == S)
        A--;
    else
        B--;

    cout << A << " " << B << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,sse4.2")

const int MOD = 998244353;

int calc(int k) {
    if (k == 0) {
        return 1;
    } else if (k == 1) {
        return 2;
    } else if (k % 2 == 0) {
        int sq = calc(k / 2);
        return (sq * sq) % MOD;
    } else {
        return (2 * calc(k - 1)) % MOD;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, s;
    cin >> n >> s;
    vector<int> kek(n);
    for (int i = 0; i < n; i++) {
        cin >> kek[i];
    }
    int dp[n][s + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s; j++) {
            if (j == 0) {
                dp[i][j] = calc(i + 1);
            } else if (i == 0) {
                if (kek[i] == j) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            } else {
                dp[i][j] += dp[i - 1][j] * 2;
                if (j >= kek[i]) dp[i][j] += dp[i - 1][j - kek[i]];
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[n - 1][s] << '\n';

    fflush(stdout);
    return 0;
}


Measured memory_bytes: 73988
using System;
using System.Collections.Generic;
using System.Linq;
using static Scanner;

class Program
{
    static void Main() => new Program().Solve();

    public void Solve()
    {
        int n = ReadInt();
        var s = Read(n).ToArray();
        Console.WriteLine($@"AC x {s.Count(x => x == "AC")}
WA x {s.Count(x => x == "WA")}
TLE x {s.Count(x => x == "TLE")}
RE x {s.Count(x => x == "RE")}");
    }
}

static class Scanner
{
    static Queue<string> que = new Queue<string>();
    public static string Read() { if (!que.Any()) foreach (var s in Console.ReadLine().Split()) que.Enqueue(s); return que.Dequeue(); }
    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());
    public static decimal ReadDecimal() => decimal.Parse(Read());
    public static IEnumerable<string> Read(long n) { for (long i = 0; i < n; i++) yield return Read(); }
    public static IEnumerable<int> ReadInt(long n) => Read(n).Select(int.Parse);
    public static IEnumerable<long> ReadLong(long n) => Read(n).Select(long.Parse);
    public static IEnumerable<double> ReadDouble(long n) => Read(n).Select(double.Parse);
    public static IEnumerable<decimal> ReadDecimal(long n) => Read(n).Select(decimal.Parse);
}


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

template<int MOD> struct Fp {
long long val;
constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
if (val < 0) val += MOD;
}
constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
return os << x.val;
}
friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
if (n == 0) return 1;
auto t = modpow(a, n / 2);
t = t * t;
if (n & 1) t = t * a;
return t;
}
};

const int MOD = 1000000007;
using mint = Fp<MOD>;


int main() 
{
    int n,m;
    cin >> n >> m;
    vector<int> x(n),y(m);
    rep(i,n) cin >> x[i];
    rep(i,m) cin >> y[i];

    vector<mint> X(n-1),Y(m-1);
    rep(i,n-1) X[i] = x[i+1] - x[i];
    rep(i,m-1) Y[i] = y[i+1] - y[i];

    mint L = 0, R = 0;
    rep(i,n-1) L += X[i] * (i+1) * (n-i-1);
    rep(i,m-1) R += Y[i] * (i+1) * (m-i-1); 

    cout << L * R << endl;
    return 0;
}

Measured memory_bytes: 5612
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

output: in_order + pre_order
1 12 17 20 25 30 88
30 12 1 20 17 25 88

"""

import sys


class Node(object):
    def __init__(self, data):
        self.data = data
        self.left, self.right = None, None

    def insert(self, data):
        """
        insert data according to BST rules
        """
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)

        return None


def pre_order(node):
    if node is not None:
        print('', node.data, end='')
        pre_order(node.left)
        pre_order(node.right)
    return None


def in_order(node):
    if node is not None:
        in_order(node.left)
        print('', node.data, end='')
        in_order(node.right)
    return None


def action(command, content):
    if command[0] == 'i':
        tree_root.insert(data=int(content))

    elif command[0] == 'p':
        in_order(tree_root)
        print('')
        pre_order(tree_root)
        print('')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    # assert len(command_list) == array_length
    # print(array_length, *command_list)

    flag, tree_root = False, None
    for each in command_list:
        command, content = each[0], each[-1]
        if (not flag) and command.startswith('in'):
            tree_root = Node(data=int(content))
            flag = True
            continue
        action(command=command, content=content)

Measured memory_bytes: 288692
#include<bits/stdc++.h>
using namespace std;
 
int main() {
 int n, c(0);
 cin >> n;
 vector<int> f(101);
 for(int i(0);i<n;i++){
   int d;
   cin >> d;
   f.at(d)=1;
 }
  for(int i(0);i<101;i++)
    c += f.at(i);
 cout << c;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dpp[6000],dpc[6000];
const int mod = 1e9+7;
int32_t main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    string s;
    cin>>n>>s;
    dpc[1] = 1;
    for(int i=0;i<n-1;i++)
    {
        swap(dpp,dpc);
        if(s[i]=='<')
        {
            dpc[1] = 0;
            for(int j=2;j<=i+2;j++)
            {
                dpc[j] = (dpc[j-1]+dpp[j-1])%mod;
            }
        }
        else
        {
            dpc[i+2] = 0;
            for(int j=i+1;j>=1;j--)
            {
                dpc[j] = (dpc[j+1]+dpp[j])%mod;
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans += dpc[i];
    }
    ans%=mod;
    cout<<ans;
    return 0;
}

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

using namespace std;
using ll = long long;

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

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(int, N);
    CINS(string, s, N);

    int countAB = 0;
    int countAandB = 0;
    int countAonly = 0;
    int countBonly = 0;

    for (int i = 0; i < N; i++) {
        string si = s[i];

        if (si[0] == 'B' && si[si.size()-1] == 'A') {
            countAandB++;
        } else if (si[si.size()-1] == 'A') {
            countAonly++;
        } else if (si[0] == 'B') {
            countBonly++;
        }

        for (int j = 0; j < s[i].size()-1; j++) {
            if ( s[i][j] == 'A' && s[i][j+1] == 'B' ) {
                countAB++;
            }
        }
    }

    int ans = countAB;

    ans += min(countAonly + countAandB, countBonly + countAandB);
    if ( countAonly == 0 && countBonly == 0 && countAandB > 0 ) {
        ans--;
    }

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

Measured memory_bytes: 768
/*
ID: wangjun30
LANG: C++11
TASK:
*/
#include<iostream>
#include<algorithm>
#include<array>
#include<unordered_map>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<unordered_set>
#include<vector>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
//#include<fstream>
#define int long long
using namespace std;
//ifstream cin(".in");
//ofstream cout(".out");
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if((a+d-1)/d>=(c+b-1)/b)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 3600
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define int long long
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)

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

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){rep(i,vec.size())is>>vec[i];return is;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int imos[100005];

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

    imos[0] = 1;

    rep(i, N) {
        int a, b; cin >> a >> b;

        imos[a]++, imos[b + 1]--;
    }

    rep(i, 100005) if (i) imos[i] += imos[i - 1];

    int ma = 0;

    rep(i, 100005) {
        if (imos[i] >= i) ma = i;
    }

    cout << ma - 1 << endl;
}

Measured memory_bytes: 1940
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;
#define MOD 1000000007
//#define MOD 998244353
#define N 100010
#define INF 1e18
#include <ctime>
#define rep(i, x, n) for (ll i = x; i < n; i++)
#define rev(i, n, x) for (ll i = n; i > x; i--)
#define all(c) (c).begin(), (c).end()
#define int long long int
#define endl "\n"
#ifdef mishra
#define debug(x) cout << " >> " << #x << ": " << x;
#define debugend() cout << endl;
#define print_time() cout << setprecision(6) << "time: " << (clock() - start) / (double)CLOCKS_PER_SEC << '\n';
#else
#define debug(x) ;
#define debugend() ;
#define print_time() ;
#endif

clock_t start;
void FAST(ll argc)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    start = clock();
    if (argc == 2)
        freopen("std.in", "r", stdin);
}

/*vector<ll> v;
void seive()
{
    v.pb(2);
    for (int i = 3; i < 100000; i += 2)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (i % v[j] == 0)
                break;
            if (v[j] * v[j] > i)
            {
                v.pb(i);
                break;
            }
        }
    }
}
/*
void prime_factor(ll x, vector<ll> &r)
{
    ll sqrt_x = sqrt(x);

    for (ll i : v)
    {
        if (i > sqrt_x)
            break;

        if (x % i == 0)
            r.pb(i);

        while (x % i == 0)
        {
            x /= i;
        }
    }

    if (x >= 2)
        r.pb(x);
}
*/
/*
ll power(ll x, ll y)
{
    ll res = 1;
    x = x % MOD;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % MOD;
        y = y >> 1;
        x = (x * x) % MOD;
    }
    return res;
}
*/
/*
inline void dfs(ll curr, ll prev)
{

    for (ll i : a[curr])
        if (i != prev)
            dfs(i, curr);
}
*/
/*
ll multi(ll a, ll b)
{
    return ((a * b) % MOD);
}
*/
//---------------------CODE STARTS HERE---------------------

signed main(char argc, char *argv[])
{
    FAST(argc);

    ll testcase = 1;
    //cin >> testcase;

    while (testcase--)
    {
        int n, k;
        cin >> n >> k;
        int a[n];
        rep(i, 0, n)
                cin >>
            a[i];
        int dp[N] = {0};
        // map<int, int> m;
        // stack<pair<int, int>> st;
        rep(i, 0, N)
        {
            rep(j, 0, n)
            {
                if (i + a[j] >= N)
                    break;
                dp[i + a[j]] = max((1 - dp[i]), dp[i + a[j]]);
            }
        }
        if (dp[k])
            cout << "First" << endl;
        else
            cout << "Second" << endl;

        //--------??--------CLEAR VECTORS--------??--------
    }

    //v.clear();
    print_time();
    return 0;
}

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

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

const double INF=1e9;

int main(){
  int n;
  cin>>n;
  vector<int>t(n),v(n);
  int T=0;
  rep(i,n){
    cin>>t[i];
    T+=t[i];
  }
  rep(i,n)cin>>v[i];

  //初期化
  vector<double>maxV(2*T+1,INF);
  int now=0;
  rep(i,n){
    rep(j,2*t[i]){
      chmin(maxV[now],(double)v[i]);
      chmin(maxV[now+1],(double)v[i]);
      now++;
    }
  }

  //各点の位置を決める
  maxV[0]=maxV[2*T]=0;

  rep(i,2*T){
    chmin(maxV[i+1],maxV[i]+0.5);
  }

  for(int i=2*T; i>0; --i){
    chmin(maxV[i-1],maxV[i]+0.5);
  }

  //台形の面積を計算
  double ans=0;
  rep(i,2*T){
    ans+=(maxV[i]+maxV[i+1])*0.5/2;
  }
  printf("%.6f\n",ans);
}


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

int main(void){
    string s;
    cin >> s;
    
    int a[15];
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '1') a[i] = 1;
        if (s[i] == '2') a[i] = 2;
        if (s[i] == '3') a[i] = 3;
        if (s[i] == '4') a[i] = 4;
        if (s[i] == '5') a[i] = 5;
        if (s[i] == '6') a[i] = 6;
        if (s[i] == '7') a[i] = 7;
        if (s[i] == '8') a[i] = 8;
        if (s[i] == '9') a[i] = 9;
        if (s[i] == '0') a[i] = 0;
    }
    
    int min = 10000;
    for (int i = 0; i < s.size() - 2; i++) {
        if (min > abs(753 - (100 * a[i] + 10 * a[i + 1] + a[i + 2]))) {
            min = abs(753 - (100 * a[i] + 10 * a[i + 1] + a[i + 2]));
        }
    }
    
    cout << min << endl;
}


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

#define ll long long
#define ld long double
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"=================================="<<endl;
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second
 
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"
 
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e12;
#define PI 3.14159265
 
const ll N = 200005;

ll C[N];
V adj[N];
ll block[N], sub[N];
ll ans[N];

void dfs(ll n,ll p){
    ll a=0;
    sub[n]=1;
    ll b=block[C[n]];
    for(auto i:adj[n]){
        if(i==p)    continue;
        block[C[n]]=b;
        dfs(i,n);
        sub[n]+=sub[i];
        if(block[C[n]]!=b){
            ll c = block[C[n]] - b;
            c = sub[i] - c;
            // err1(c);
            ans[C[n]] += c*(c+1)/2;
        }
        else{
            ans[C[n]] += sub[i]*(sub[i]+1)/2;
        }
    }
    block[C[n]] = b + sub[n];
}

void solve(){
    ll n;
    cin>>n;
    rep(i,1,n+1)    cin>>C[i];
    rep(i,0,n-1){
        ll u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,0);
    // rep(i,1,n+1)    cout<<block[i]<<" ";cout<<endl;
    rep(i,1,n+1){
        ll c = n - block[i];
        ans[i] += c*(c+1)/2;
        ans[i] = n*(n+1)/2 - ans[i];
        cout<<ans[i]<<endl;
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll no;
    // cin>>no;
    no = 1;
    while(no--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 36352
#include<stdio.h>


void qsort(int a[],int left,int right);
int partition(int a[],int left,int right);
void exchange(int *num1,int *num2);


int main(){
    int i;
   int size=10;
   int heigh[size];
   
   for(i=0;i<size;i++){
                       scanf("%d",&heigh[i]);
   }
   qsort(heigh,0,size-1);
   
   for(i=0;i<3;i++){
                       printf("%d\n",heigh[i]);
   }         getchar();getchar();
   
   return 0;
} 

void qsort(int a[],int left,int right){
     if(left<right){
                    int q;
                    q=partition(a,left,right);
                    qsort(a,left,q-1);
                    qsort(a,q+1,right);
     }
}

int partition(int a[],int left,int right){
    int x=a[right];
    int index=left-1;
    int i;
    
    for(i=left;i<right;i++){
                           if(a[i]>x)exchange(&a[++index],&a[i]);
    }
    
    exchange(&a[++index],&a[right]);
    
    return index;
}

void exchange(int *num1,int *num2){
     int t;
     t=*num1;
     *num1=*num2;
     *num2=t;
}

Measured memory_bytes: 604