akhauriyash/Code-Regression huggingface dataset:
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// ここまで

fn run() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let mut cnt = [0; 3];
    for a in a {
        cnt[a - 1] += 1;
    }
    let mut dp = vec![vec![0.0; cnt[0] + cnt[1] + cnt[2] + 1]; cnt[1] + cnt[2] + 1];
    let p = 1.0 / (n as f64);
    for i in 0..(cnt[2] + 1) {
        for j in 0..(cnt[1] + cnt[2] - i + 1) {
            for k in 0..(cnt[0] + cnt[1] + cnt[2] - i - j + 1) {
                if i == 0 && j == 0 && k == 0 {
                    continue;
                }
                let mut sum = 1.0;
                if i > 0 {
                    sum += (i as f64) * p * dp[j + 1][k];
                }
                if j > 0 {
                    sum += (j as f64) * p * dp[j - 1][k + 1];
                }
                if k > 0 {
                    sum += (k as f64) * p * dp[j][k - 1];
                }
                dp[j][k] = sum / (((i + j + k) as f64) * p);
            }
        }
    }
    let ans = dp[cnt[1]][cnt[0]];
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,a,b;
    cin>>n>>a>>b;
    string s;
    cin>>s;
    int sum=a+b;
    int foreigner=0;
    for (int i=0;i<n;i++) {
        if (s[i]=='c') {
            cout<<"No"<<endl;
        } else if (s[i]=='a') {
            if (sum>0) {
                cout<<"Yes"<<endl;
                sum--;
            } else {
                cout<<"No"<<endl;
            }
        } else if (s[i]=='b') {
            if (sum>0&&foreigner<b) {
                cout<<"Yes"<<endl;
                sum--;
                foreigner++;
            } else {
                cout<<"No"<<endl;
            }
        }
    }
}

Measured memory_bytes: 3772
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define SZ(x) ((int)(x).size())
#define MEM(x,a) memset(x,a,sizeof(x))
#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--)
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
const ll mod=1000000007,N=1e5+5,M=1e5+5,INF=0x3f3f3f3f;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//head
char s[100010];
int main(void){
    list<char>l;
    int q;
    scanf("%s%d",s,&q);
    bool flag=0;
    for(int i=0;s[i];++i)l.emplace_back(s[i]);
    while(q--){
        int x,x2;
        char s1[5];
        scanf("%d",&x);
        if(x==1){
            flag=!flag;
        }
        else{
            scanf("%d%s",&x2,s1);
            if(x2==1){
                if(!flag)l.emplace_front(s1[0]);
                else l.emplace_back(s1[0]);
            }
            else{
                if(!flag)l.emplace_back(s1[0]);
                else l.emplace_front(s1[0]);
            }
        }
    }
    if(!flag)for(auto i:l){
        printf("%c",i);
    }
    else{
        auto la=l.end();
        --la;
        while(la!=l.begin()){
            printf("%c",*la);
            --la;
        }
        printf("%c",*la);
    }
    return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

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

    ll N,K; cin >> N >> K;
    vector<i_i> a(N);
    rep(i,N) cin >> a[i].fs >> a[i].sc;
    sort(all(a));

    int trig;
    rep(i,N) {
        if(a[i].sc < K) {
            K -= a[i].sc;
        }
        else {
            trig = i;
            break;
        }
    }
    cout << a[trig].fs << endl;
    return 0;
}


Measured memory_bytes: 1024
use std::io::{BufRead, Write, stdin, stdout};

fn solve<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut s = String::new();
    input.read_line(&mut s).unwrap();
    s.clear();
    input.read_line(&mut s).unwrap();
    let answers: Vec<bool> = s.trim().chars().map(|x| x == 'o').collect();
    let mut result: Vec<bool> = Vec::with_capacity(answers.len());
    for init in &[[true, true], [true, false], [false, true], [false, false]] {
        result.extend(init);
        for i in 2..answers.len() {
            let buf = !(result[i - 2] ^ !(answers[i - 1] ^ result[i - 1]));
            result.push(buf);
        }
        if (result[answers.len() - 2] == result[0]) ==
           !(answers[answers.len() - 1] ^ result[answers.len() - 1]) &&
           (result[answers.len() - 1] == result[1]) == !(answers[0] ^ result[0]) {
            break;
        } else {
            result.clear();
        }
    }
    writeln!(output,
             "{}",
             if result.is_empty() {
                 "-1".to_owned()
             } else {
                 result.iter().map(|&x| if x { 'S' } else { 'W' }).collect::<String>()
             })
        .unwrap();
}

fn main() {
    let stdin = stdin();
    solve(stdin.lock(), stdout());
}

#[cfg(test)]
mod tests {
    fn test(input: &str, output: &str) {
        let mut v = Vec::<u8>::new();
        ::solve(input.as_bytes(), &mut v);
        assert_eq!(String::from_utf8(v).unwrap(), output);
    }
    #[test]
    fn case1() {
        test("6
ooxoox\n",
             "SSSWWS\n");
    }
    #[test]
    fn case2() {
        test("3
oox\n",
             "-1\n");
    }
    #[test]
    fn case3() {
        test("10
oxooxoxoox\n",
             "SSWWSSSWWS\n");
    }
    #[test]
    fn custom() {
        test("4
xxxx\n",
             "WWWW\n");
    }
}

Measured memory_bytes: 4352
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>

#define LL long long int
#define pb push_back
#define mp make_pair
#define MAX 100005
#define MOD 1000000007

using namespace std;

LL sum(LL num) {
	if(num < 0) return 0;
	return (num * (num + 1)) / 2; 
}

int main() {
	LL n, k;
	cin>>n>>k;
	
	LL possible = 0;
	for(LL i=k;i<=n+1;i++) {
		LL mini = sum(i-1);
		LL maxi = sum(n) - sum(n-i);
		
		possible = ((maxi - mini + 1) + possible) % MOD;
		//cout<<possible<<endl;
	}
	
	cout<<possible<<endl;
    return 0;
}



Measured memory_bytes: 3632
S = input()
y,m,d = S.split("/")
y,m,d = int(y),int(m),int(d)

if y == 2019:
  if m <= 4:
    if d <= 30:
      ans = "Heisei"
    else:
      ans = "TBD"
  else:
    ans = "TBD"
elif y < 2019:
  ans = "Heisei"
else:
  ans = "TBD"
  
print(ans)

Measured memory_bytes: 9124
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

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

  vector<ll> sum(n + 2, 0);
  for (int i = n; i >= 0; i--){
    sum[i] = sum[i + 1] + a[i];
  }


  ll ans = 0, can_use = 1, ok = 1;
  if (n == 0){
    if (a[0] == 1)
      ans = 1;
    else
      ok = 0;
  }
  else if (n == 1){
    if (a[0] == 0 && a[1] == 1){
      ans = 2;
    }
    else if (a[0] == 0 && a[1] == 2){
      ans = 3;
    }
    else 
      ok = 0;
  }
  else {
    for (int i = 0; i < n + 1; i++){
      // n = 0, n = 1はコーナーケース
      if (i == 0){
        if (a[i] == 0){
          can_use = 1;
          ans++;
        }
        else {
          ok = 0;
          break;
        }
      }
      else if (i == n){
        if (a[i] <= 2*can_use)
          ans += a[i];
        else 
          ok = 0;
      }
      else {
        if (can_use <= 1e15){
          can_use = 2*can_use - a[i];
          ans += a[i] + min(can_use, sum[i + 1]);// 使う分;
        }
        else {
          ans += a[i] + sum[i + 1];
        }
      }


      if (can_use <= 0){
        ok = 0;
        break;
      }
    }
  }

  if (ok){
    cout << ans << endl;
  }
  else 
    cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 4788
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int,int> mii;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = b-1; i >= a; i--)
#define F0Rd(i,a) for (int i = a-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
const int MOD = 1000000007;
double PI = 4*atan(1);

ll sub[5001][51];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int N,A; cin >> N >> A;
	vi X(N);
	F0R(i,N) {
		cin >> X[i];
		X[i] -= A;
	}
	sub[2500][0] = 1;
	F0R(j,N) F0R(i,5001) {
		sub[i][j+1] = sub[i][j];
		if ((i-X[j])>= 0 && (i-X[j]) <= 5000) sub[i][j+1] += sub[i-X[j]][j];
		// if (sub[i][j+1]) cout << i << " " << (j+1) << " " << sub[i][j+1] << "\n";
	}
	cout << (sub[2500][N]-1);
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    deque<ll> deq;
    int reverse = 0;

    rep(i,n) {
        ll a;
        cin >> a;
        if(reverse) deq.push_front(a);
        else deq.push_back(a);

        reverse ^= 1;
    }

     reverse = n % 2;

    if(reverse){
        rep(i,n) {
            cout << deq.back() << " ";
            deq.pop_back();
        }
    }else{
        rep(i,n) {
            cout << deq.front() << " ";
            deq.pop_front();
        }
    }


    return 0;
}

Measured memory_bytes: 5200
macro_rules! input {
    ($ttype:ty) => {
        {
            let mut input = String::new();
            let _= std::io::stdin().read_line(&mut input);
            input.trim().parse::<$ttype>().unwrap()
        }
    };

    ($($ttype:ty),*) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let mut iter = input.trim().split_whitespace();
            (
                $(iter.next().unwrap().parse::<$ttype>().unwrap(),)*
            )
        }
    };

    ($ttype:ty; $x:expr) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let v: Vec<$ttype> = input
                .trim()
                .split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect();
            v
        }
    };

    ($ttype:ty; $x:expr; $y:expr) => {
        {
            use std::io::BufRead;
            let mut matrix = Vec::with_capacity($y);
            for _ in 0..$y {
                let mut input = String::new();
                let stdin = std::io::stdin();
                let _ = stdin.lock().read_line(&mut input);
                let v: Vec<$ttype> = input
                    .trim()
                    .split_whitespace()
                    .map(|x| x.parse().unwrap())
                    .collect();
                matrix.push(v);
            }
            matrix
        }
    };
}

fn main() {
    const N: usize = 3;
    let mut c: Vec<Vec<i32>> = Vec::with_capacity(N);
    for _ in 0..N {
        c.push(input!(i32; N));
    }

    'outer: for a1 in 0..c[0][0]+1 {
        let mut a: Vec<i32> = Vec::with_capacity(N);
        let mut b: Vec<i32> = Vec::with_capacity(N);
        for i in 0..N {
            b.push(c[0][i] - a1);
            a.push(c[i][0] - b[0]);
        }
        for i in 1..N {
            for j in 1..N {
                if c[i][j] != a[i] + b[j] {
                    continue 'outer;
                }
            }
        }
        println!("Yes");
        return;
    }
    println!("No");
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#define MAXN 20000

// ノードを表す構造体
struct Node {
  int data ;
  int hight;
  struct Node * next ;
} ;

typedef struct Node Node ;

// 新しいノードのメモリを確保する
Node *create_node(int new_data, int new_hight) {
  Node *new_node = (Node *) malloc(sizeof(Node));
  if (!new_node) {
    fprintf(stderr, "could not allocate a node.\n");
    exit(1);
  }
  new_node->data = new_data;
  new_node->hight = new_hight;
  new_node->next = NULL;
  return new_node;
}

// リストのメモリを解放する
void clear_list(Node * head) {
  while (head) {
    Node * target = head ;
    head = head->next ;
    free(target) ;
  }
}

//リストが空か否か判定する
int is_empty(Node *head){
  if(head == NULL){
    return 1;
  }
  return 0;
}


// リストの先頭へ新しいノードを追加する
// リストの先頭のポインタを差し替えるため、リストの先頭へのポインタへのポインタを渡す
void push_front(Node **head, int new_data, int new_hight) {
  Node *new_node = create_node(new_data, new_hight) ;
  new_node->next = *head;
  *head = new_node;
}

//リストの先頭からノードを削除する
int pop_front(Node **head){
  Node *tmp = *head;
  int c = (*head)->data;
  *head = (*head)->next;
  free(tmp);
  return c;
}

// リストの要素を先頭から順に出力する
void print_list(const Node * head) {
  while(head) {
    printf("| %d |-> ", head->data);
    head = head->next;
  }
  printf("NULL\n");
}

int main(void) {

  Node * top = NULL ;
  Node *sq = NULL;
  int data ;

  char s[MAXN];
  fgets(s, MAXN, stdin);
  //printf("%s\n", s);

  int i = 0, res = 0, h = 0,  c;

  while((c = s[i++]) != '\n' && c != '\0'){
    switch(c){
    case '\\':
      push_front(&top, i, 0);
      push_front(&sq, 0, h);
      h--;
      break;
    case '_':
      break;
    case '/':
      h++;
      if(!is_empty(top)){
        int tmp = pop_front(&top);
        res += i - tmp;
        int h2;
        tmp = i - tmp;
        while(!is_empty(sq) && (h2 = sq->hight) < h){
          tmp += pop_front(&sq);
          if(h2 == h){
            break;
          }
        }
        push_front(&sq, tmp, h);
      }
      break;
    default:
      break;
    }
  }

  printf("%d\n", res);
  //print_list(sq);
  int ans[MAXN] = {0}, j = 0;
  while(!is_empty(sq)){
    if(sq->data != 0){
      ans[j++] = sq->data;
    }
     pop_front(&sq);
  }
  printf("%d", j);
  for(i = j-1; i >= 0; --i){
    printf(" %d", ans[i]);
  }
  
  printf("\n");
    
  clear_list(top) ;

  return 0 ;
}



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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string bans(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int n,m;cin>>n>>m;
  int wa=0;
  int ac=0;
  map<int,int> wac;
  map<int,bool> res;
  REP(i,m){
    int p;cin>>p;
    string r;cin>>r;
    if(res.find(p)==res.end()){
      res[p]=false;
      wac[p]=0;
    }
    if(!res[p]){
      if(r=="WA"){
        wac[p]++;
      }else if(r=="AC"){
        ac++;
        res[p]=true;
      }
    }
  }
  for(auto i=res.begin();i!=res.end();++i){
    if(i->second){
      wa+=wac[i->first];
    }
  }
  cout << ac << " "<< wa << endl;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
typedef long long lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()

using namespace std;

void execute()
{
	int N;
	cin >> N;
	cout << N * N << endl;
	return;
}

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

	int stop;
	cin >> stop;

	return 0;
}

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

int nxt[200022][26],dp[200022],last[26];
char s[200022];

int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    for(int i = 1;i <= n;++i){
        for(int j = last[s[i]-'a'] + 1;j <= i;++j)
            nxt[j][s[i]-'a'] = i;
        last[s[i]-'a'] = i;
    }
    for(int i = 0;i < 26;++i)
        for(int j = last[i] + 1;j <= n;++j)
            nxt[j][i] = n + 1;
    dp[n+1] = 1;
    for(int i = n;i >= 1;i--){
        int mn = 1e9;
        for(int j = 0;j < 26;++j)
            mn = min(mn,dp[nxt[i][j]+1]);
        dp[i] = mn + 1;
    }
    for(int i = 1;i <= n;){
        for(int j = 0;j < 26;++j) if(dp[i] == dp[nxt[i][j]+1] + 1){
            putchar(j + 'a');
            i = nxt[i][j] + 1;
            break;
        }
    }
    putchar('\n');

    return 0;
}


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

int main(int argc, char const *argv[])
{
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++)
    cin >> a[i];

  int min = a[0], max = a[0];
  long long sum = 0;

  for(int i = 0; i < n; i++)
  {
    sum += a[i];
    if(a[i] > max)
      max = a[i];
    if(a[i] < min)
      min = a[i];
  }
  cout << min << " " << max << " " << sum << endl;
  return 0;
}

Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    string s1;
    string s2;
    getline(cin,s1);
    //cin.ignore();
    getline(cin,s2);
    int c=0;
    //cout<<s1<<" "<<s2<<endl;
    for(int i=0;i<s1.size();i++)
    {
        if(s1[i]==s2[i])
        {
            continue;
        }
        else
        {
            c++;
        }
    }
    cout<<c<<endl;
    return 0;
}


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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


int main()
{
  ll n, c=0, p;
  bool last = false;
  cin >> n;
  forll(i, 0, n){
	cin >> p;
	if (p == (i + 1) && last == false){
	  c++;
	  last = true;
	}else{
	  last = false;
	}
  }
  cout << c << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   int n, k;
   cin >> n >> k;
   int i = 0;
   while(1) {
       if(n<pow(k, i)) {
           cout << i << endl;
           return 0;
       }
       i++;
   }
}

Measured memory_bytes: 256
n=int(input())
graph=[[0]*n for i in range(n)]


#graph[i][j]は、頂点iから頂点jへの枝の重みを表す(0は枝なし)
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(1,tmp_ope[1]+1):
        graph[tmp_ope[0]][tmp_ope[2*j]]=tmp_ope[2*j+1]

#S[i]＝１の時、頂点iは走査済み
S=[0]*n
#d[i]はSに含まれる点のみを使って、頂点iにたどり着くときの最短パス
d=[999999]*n
d[0]=0

for loop in range(n):
    tmp_vertex=-1

    #tmp_vertexは走査済みでない点の中で、d[i]が最小となるインデックス
    for j in range(n):
        if(S[j]==0):
            if(tmp_vertex!=-1):
                if(d[j] < d[tmp_vertex]):
                    tmp_vertex=j
            else:
                tmp_vertex=j
    
    
    S[tmp_vertex]=1

    #dを更新
    for j in range(n):
        if(graph[tmp_vertex][j]!=0 and S[j]==0):
            d[j]=min([ d[j], d[tmp_vertex] + graph[tmp_vertex][j] ])

for i in range(n):
    print(f"{i} {d[i]}")


Measured memory_bytes: 5820
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();
		System.out.println(gcd(a));
	}

	public static final int gcd(int a, int b) {
		// a > b にする（swap）
		if (a < b) {
			a = a ^ b;
			b = a ^ b;
			a = a ^ b;
		}

		// ユークリッドの互除法
		int r = -1;
		while (r != 0) {
			r = a % b;
			a = b;
			b = r;
		}

		return a; // b には r=0 の値が入るため、a を返す
	}

	/**
	 * <h1>３つ以上の最大公約数を求める[gcd(a, b, c,...)]</h1>
	 * <p>
	 * ユークリッドの互除法の繰り返しで求める。
	 * </p>
	 * 
	 * @param param ： 数値1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]
	 * @return<b>int</b> ： 最大公約数(なし=1[互いに素])
	 */
	public static final int gcd(final int[] param) {
		final int len = param.length;
		int g = gcd(param[0], param[1]); // gcd(a, b) は以前作ったもの
		for (int i = 1; i < len - 1; i++) {
			g = gcd(g, param[i + 1]); // gcd(a, b) は以前作ったもの
		}
		return g;
	}
}

Measured memory_bytes: 50624
from collections import deque
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def g(n, k, h):
    g = abs(h[1] - h[0])
    gk = deque([0, g], k)
    for i in range(2, n):
        h_i = h[i]
        j = max(i - k, 0)
        g = min(abs(h_i - h_j) + h_k for h_j, h_k in zip(h[j:i], gk))
        if i >= k:
            gk.popleft()
        gk.append(g)
    return g

print(g(N, K, h))


Measured memory_bytes: 14600
n,t = map(int,input().split())
ans = -1
for i in range(n):
    c,ti = map(int,input().split())
    if ti<=t:
        if ans==-1:
            ans = c
        else:
            ans = min(ans,c)
if ans==-1:
    print("TLE")
else:
    print(ans)

Measured memory_bytes: 62468
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
// #define DEBUG 10

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7, maxn = 500050;
const double PI = acos(-1);
vector<int> ans(30, 0);
vector<vector<int>> seg(4*maxn, vector<int> (30, 0));

void update(int i, int l, int r, int pos, int cara, int apaga){
    if (apaga != -1) seg[i][apaga]--;
    if (l == r){
        seg[i][cara]++;
        return;
    }
    
    int mid = (l+r)/2;
    
    if (pos <= mid){
        update(2*i, l, mid, pos, cara, apaga);
    }
    else {
        update(2*i+1, mid+1, r, pos, cara, apaga);
    }
    #ifdef DEBU
        cout << l << " " << r << endl;
    #endif
    for (int j=0; j<26; j++){
        seg[i][j] = seg[2*i][j] + seg[2*i+1][j];
        #ifdef DEBU
            cout << seg[i][j] << " ";
        #endif
    }
    #ifdef DEBU
        cout << endl;
    #endif
}

void query(int i, int l, int r, int ql, int qr){
    if (r < ql || l > qr) return;
    if (ql <= l and r <= qr){
        for (int j=0; j<26; j++){
            ans[j] += seg[i][j];
        }
        #ifdef DEBUG
        cout << l << " " << r << endl;
            for (int j=0; j<26; j++){
                cout << ans[j] << " ";
            }
            cout << endl;
        #endif
        return;
    }
    int mid = (l+r)/2;

    query(2*i, l, mid, ql, qr);
    query(2*i+1, mid+1, r, ql, qr);
}

int main (){
    ios_base::sync_with_stdio(false);
    int n, q;
    string s;
    cin >> n >> s >> q;
    for (int i=0; i<n; i++){
        update(1, 1, n, i+1, s[i] - 'a', -1);
    }

    for (int i=0; i<q; i++){
        int tq;
        cin >> tq;
        if (tq == 1){
            int pos;
            char c;
            cin >> pos >> c;
            update(1, 1, n, pos, c - 'a', s[pos-1] - 'a');
            s[pos-1] = c;
        }
        else {
            int l, r, cnt = 0;
            cin >> l >> r;
            for (int j=0; j<26; j++) ans[j] = 0;
            query(1, 1, n, l, r);
            for (int j=0; j<26; j++){
                if (ans[j] != 0) cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 298004
function readInt(str){
    return parseInt(str, 10);
}
function range(begin, end){
    if(begin > end) return range(end, begin).reverse();
    const ans=[];
    for(let i=begin; i<=end; i++){
        ans.push(i);
    }
    return ans;
}
function solve(N,x,u){
    let sum=0;
    for(const i of range(1,N)){
        if(u[i]=='BTC'){
            sum+=x[i]*380000.0;
        }
        else{
            sum+=x[i];
        }
    }
    return sum;
}
function Main(raw) {
    const input = raw.split("\n");
    const N = parseInt(input[0],10);
    const x=[];
    const u=[];
    for(const i of range(1, N)){
        const [xraw,uraw]=input[i].split(" ");
        x[i]=parseFloat(xraw);
        u[i]=uraw;
    }
    
    //出力
    console.log("%s", solve(N,x,u).toFixed(10));
}

//DO NOT EDIT
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

// dir := true x以下, xより大きい 
//        false xより大きい, x以下
ll count(vector<ll> &A, ll x, int i, int s, int t, bool dir) {
    if (t <= s) return 0;
    if (dir) {
        if (A[i] * A[s] > x) return 0;
        if (A[i] * A[t-1] <= x) return t-s;
        int l = s; // x以下
        int r = t-1; // xより大きい
        while (r-l > 1) {
            int mid = (l+r) / 2;
            if (A[i] * A[mid] <= x) l = mid;
            else r = mid;
        }
        return l+1-s;
    } else {
        if (A[i] * A[t-1] > x) return 0;
        if (A[i] * A[s] <= x) return t-s;
        int l = s; // xより大きい
        int r = t-1; // x以下
        while (r-l > 1) {
            int mid = (l+r) / 2;
            if (A[i] * A[mid] <= x) r = mid;
            else l = mid;
        }
        return t-r;
    }
}

// 積がx以下のペアがいくつあるか
ll count(vector<ll> A, ll x) {
    ll res = 0;
    for (int i=0; i<(int)A.size()-1; ++i) {
        res += count(A, x, i, i+1, (int)A.size(), A[i] >= 0);
    }
    return res;
}

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    for (int i=0; i<N; ++i) cin >> A[i];
    sort(A.begin(), A.end());

    ll l, r;
    l = -1e18-1; // K未満
    r = 1e18+1; // K以上
    while (r-l > 1) {
        ll mid = (l+r)/2;
        if (K <= count(A, mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;

    return 0;
}

Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    int n,k;cin>>n>>k;
    ll a;
    vector<pair<ll,int>> b(n);
    rep(i,n){
        cin>>a;
        if(a>0)b[i]=mp(a,1);
        else if(a==0)b[i]=mp(a,0);
        else b[i]=mp(-a,-1);
    }
    sort(all(b));reverse(all(b));
    int mnum=0;int pnum=0;
    ll lm=(ll)1;ll lp=(ll)1;
    ll ans=(ll)1;
    rep(i,k){
        if(b[i].second==0){
            ans=0;
            break;
        }
        if(b[i].second==-1){
            mnum++;
            ans*=lm;ans%=inf;
            lm=b[i].first;
        }
        else if(b[i].second==1){
            pnum++;
            ans*=lp;ans%=inf;
            lp=b[i].first;
        }
    }
    if(mnum%2==0){
        ans*=lm;ans%=inf;
        ans*=lp;ans%=inf;
        cout<<ans<<endl;
        return 0;
    }
    if(k==n){
        ans*=lm;ans%=inf;
        ans*=lp;ans%=inf;
        cout<<inf-ans<<endl;
        return 0;
    }
    if(mnum%2){
        ll x=-2*inf;ll y=-2*inf;
        rep2(i,k,n){
            if(b[i].second==0){
                x=0;
                break;
            }
            if(b[i].second==1){
                x=b[i].first;
                break;
            }
        }
        rep2(i,k,n){
            if(b[i].second==0){
                y=0;
                break;
            }
            if(b[i].second==-1){
                y=b[i].first;
                break;
            }
        }
        if(pnum==0&&x==-2*inf){
            ans=(ll)1;
            reverse(all(b));
            rep(i,k){
                ans*=b[i].first;
                ans%=inf;
            }
            cout<<inf-ans<<endl;
            return 0;
        }
        if(pnum&&x*lp<y*lm){
            ans*=y;ans%=inf;
            ans*=lm;ans%=inf;
        }
        else{
            ans*=x;ans%=inf;
            ans*=lp;ans%=inf;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6372
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]

def f(num, x, y, z):
    if num == n:
        if min(x, y, z) > 0:
            return abs(a - x) + abs(b - y) + abs(c - z) - 30
        else:
            return 1000 * 10
    mp_0 = f(num + 1, x, y, z)
    mp_a = f(num + 1, x + l[num], y, z) + 10
    mp_b = f(num + 1, x, y + l[num], z) + 10
    mp_c = f(num + 1, x, y, z + l[num]) + 10
    return min(mp_0, mp_a, mp_b, mp_c)
print(f(0, 0, 0, 0))

Measured memory_bytes: 44136
#include<iostream>
 
using namespace std;
 
int main()
{
   int n;
   
   cin >> n;
   
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin >> a[i];
   }

   for(int i=1;i<n+1;i++)
   {
       if(i>1) {cout << " ";
           
       }
       cout << a[n-i];
   }
   
   cout << endl;

   
    return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans=LINF,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
void dfs(int j,int dat[],int now){
    if(j>8)return;
    //rep(zz,30)cout<<dat[zz]<<" ";
    //cout<<"\n";
    //そろってるかいる
    int ok=1;
    rep(zz,9){
        if(dat[0]!=dat[zz])ok=0;
    }
    rrep(zz,15,18){
        if(dat[15]!=dat[zz])ok=0;
    }
    rrep(zz,18,21){
        if(dat[18]!=dat[zz])ok=0;
    }
    rrep(zz,9,12){
        if(dat[9]!=dat[zz])ok=0;
    }
    rrep(zz,12,15){
        if(dat[12]!=dat[zz])ok=0;
    }
    rrep(zz,21,30){
        if(dat[21]!=dat[zz])ok=0;
    }
    if(ok)ans=min(ans,(ll)j);

    if(now==-1){
        dfs(j,dat,0);
        dfs(j,dat,1);
        dfs(j,dat,2);
        dfs(j,dat,3);
    }
    else{
        int newdat[40]={};
        rep(zz,30)newdat[zz]=dat[zz];
        if(now==0){
            swap(newdat[6],newdat[21]);
            swap(newdat[7],newdat[22]);
            swap(newdat[8],newdat[23]);
            swap(newdat[17],newdat[12]);
            swap(newdat[9],newdat[11]);
        }
        else if(now==1){
            swap(newdat[0],newdat[27]);
            swap(newdat[1],newdat[28]);
            swap(newdat[2],newdat[29]);
            swap(newdat[15],newdat[14]);
            swap(newdat[18],newdat[20]);
        }
        else if(now==2){
            swap(newdat[0],newdat[23]);
            swap(newdat[3],newdat[26]);
            swap(newdat[6],newdat[29]);
            swap(newdat[9],newdat[20]);
            swap(newdat[15],newdat[17]);
        }
        else{
            swap(newdat[2],newdat[21]);
            swap(newdat[5],newdat[24]);
            swap(newdat[8],newdat[27]);
            swap(newdat[11],newdat[18]);
            swap(newdat[12],newdat[14]);
        }
        dfs(j+1,newdat,0);
        dfs(j+1,newdat,1);
        dfs(j+1,newdat,2);
        dfs(j+1,newdat,3);
    }
}

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n;
    while(1){
        int a[40]={};
        rep(i,30)cin>>a[i];
        dfs(0,a,-1);
        Cout(ans);
        ans=LINF;
        n--;
        if(n==0)break;
    }
    return 0;
}


Measured memory_bytes: 3220
#include<stdio.h>

char CompareCharacter(char* a_acS);

int main(void) {
	static char s_acS[100001];

	//文字列Sに入るアルファベットを入力
	scanf("%s", s_acS);
	//Sに現れない最も早いアルファベットを調べ、出力
	if (CompareCharacter(s_acS) != 0x30) {
		printf("%c\n", CompareCharacter(s_acS));
	}
	else {
		printf("None\n");
	}
	return 0;
}

char CompareCharacter(char* a_acS) {
	int i,j;
	char acChar[27];
	char cAlp = 0x30;

	for (i = 0;i < 27;i++) {
		acChar[i] = 0x61 +(char)(0x01*i);
	}

	for (i = 0;a_acS[i] != 0x00;i++) {
		for (j = 0;j < 26;j++) {
			if (a_acS[i] == acChar[j]) {
				acChar[j] = 0x30;
			}
			else {}
		}
	}

	for (i = 0;(cAlp == 0x30 )&& i < 26;i++) {
		cAlp = acChar[i];
	}

	return(cAlp);
}

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

using namespace std;

pair<int,int> slove(string& str){
	int len=str.length();
	for(int i=0;i<len-2;i++){
		if(str[i+1]==str[i]){
			return make_pair(i+1,i+2);
		}else if(str[i+2]==str[i]){
			return make_pair(i+1,i+3);
		}
	}
	if(str[len-2]==str[len-1])
		return make_pair(len-1,len);
	return make_pair(-1,-1);
}

int main(){
	string str;
	cin>>str;
	auto ans=slove(str);
	cout<<ans.first<<' '<<ans.second<<endl;
	return 0; 
}

Measured memory_bytes: 512
"""ABC079D Wall 別解
ワーシャルフロイドでやった場合
"""

H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]

counter = {i: 0 for i in range(-1, 10)}
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        counter[tmp[j]] += 1

dp = c.copy()
for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j] = min(
                dp[i][j],
                dp[i][k] + dp[k][j]
            )

ans = sum([counter[i]*dp[i][1] for i in range(10)])
print(ans)

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

int main() {

	int N, a, min = 0, max = 0;
	int color[10];

	for (int i = 0; i <= 8; i++)color[i] = 0;

	cin >> N;

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

		cin >> a;

		if (a < 400)color[0]++;
		else if (a < 800)color[1]++;
		else if (a < 1200)color[2]++;
		else if (a < 1600)color[3]++;
		else if (a < 2000)color[4]++;
		else if (a < 2400)color[5]++;
		else if (a < 2800)color[6]++;
		else if (a < 3200)color[7]++;
		else color[8]++;

	}

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

		if (color[i] > 0)min++;

	}
	max = min + color[8];
	if (min == 0)min = 1;

	cout << min << " " << max << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t,u;
    int a,b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s.compare(u)==0){
        cout << a-1 << " " << b << endl;
    }else{
        cout << a << " " << b-1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/**
 *   @FileName	b.cpp
 *   @Author	kanpurin
 *   @Created	2020.05.16 18:39:27
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int main() {
    int a,b,c,k;cin >> a >> b >> c >> k;
    if (a >= k) {
        cout << k << endl;
    }
    else if (a + b >= k) {
        cout << a << endl;
    }
    else {
        cout << a - (k - a - b) << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
# include <bits/stdc++.h>
# define rr register
const int N=4010,INF=0x3f3f3f3f;
int sum[N][3];
int n;
char s[N];
std::map <char,int> ts;
long long ans;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	n=read();
	scanf("%s",s+1);
	ts['R']=0,ts['G']=1,ts['B']=2;
	for(rr int i=1;i<=n;++i){
		for(rr int j=0;j<=2;++j){
			sum[i][j]=sum[i-1][j];
		}
		++sum[i][ts[s[i]]];
	}
	for(rr int i=1;i<=n;++i){
		for(rr int j=1;j<i;++j){
			if(s[i]==s[j]){
				continue;
			}
			for(rr int k=0;k<=2;++k){
				if(k==ts[s[i]]||k==ts[s[j]]){
					continue;
				}
				ans+=(sum[n][k]-sum[i][k]);
				if(ts[s[i+(i-j)]]==k&&(i+(i-j))<=n){
					--ans;
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}


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

using namespace std;
using ll = long long;

int f(int x, int y, int z){
	return x*x+y*y+z*z+x*y+y*z+z*x;
}

int count(int n){
  int res=0;
	for(int x=1; x<=100; x++){
    	for(int y=x; y<=100; y++){
        	for(int z=y; z<=100; z++){
            	if(f(x,y,z)==n){
                	if(x==y && y==z)res++;
                  	if(x!=y && y!=z && z!=x)res+=6;
                  	if(x==y && y!=z) res+=3;
                  	if(y==z && x!=z) res+=3;
                  	if(x==z && x!=y) res+=3;
                }
            }
        }
    }
	return res;
}

int main()
{
  int N;
	cin >>N;
  for(int i=1; i<=N; i++)
  cout << count(i) << endl;
  return 0;
}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

int main() {
    int N, K; cin >> N >> K;
    const lli MOD = 1000000007;
    vector<lli> cum(N+1, 0);
    for (int i=1; i<=N; i++) {
        cum[i] = cum[i-1] + i;
        cum[i] %= MOD;
    }
    lli ans = 0;
    for (int i=K; i<=N; i++) {
        long v = cum[N] - cum[N-i] - cum[i-1] + 1;
        while (v < 0) v += MOD;
        v %= MOD;
        ans += v;
        ans %= MOD;
    }
    cout << (ans + 1) % MOD << endl;
}

Measured memory_bytes: 4836
#include<bits/stdc++.h>
using namespace std;
int countDivisor(int N){
  int ans=0;
  for(int i=1;i<=N;i++){
    if(N%i==0){
      ans++;
    }
  }
    return ans;
}
int main(){
  int N;
  cin>>N;
  int ans=0;
  for(int i=1;i<=N;i+=2){
    if(countDivisor(i)==8){
      ans++;
    }
  }
  cout<<ans<<endl;
}


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

#define ll long long
#define P pair<int, int>
#define F first
#define S second

const ll mod = 1000000007LL;

ll n, k, h[100005], dp[100005];
void solve() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> h[i];

  dp[0] = 0;
  for (int i = 1; i < n; i++) {
    dp[i] = INT_MAX;
    for (int j = 1; j <= k; j++) {
      if (i >= j) dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
    }
  }
  cout << dp[n - 1];
}

int main(int argc, char const *argv[]) {
/*
#ifndef ONLINE_JUDGE
  freopen("practice/input.txt", "r", stdin);
  freopen("practice/output.txt", "w", stdout);
#endif
*/
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int T = 1;
  while (T--) {
    solve();
  }

  return 0;
}

Measured memory_bytes: 1792
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

MOD = 1000000007
n, k = map(int, input().split())
r = n-k

kk = []
rr = []
for i in range(k):
	kk.append(cmb(k-1,i)%MOD)

for i in range(r):
	rr.append(cmb(r-1,i)%MOD)
rr.append(0);rr.append(0);rr.append(0)

if r == 0:
	print(1)
	for i in range(k-1):
		print(0)
else:
	for i in range(k):
		if i <= r + 1:
			print((kk[i] * (rr[i-1] + rr[i]*2 + rr[i+1]))%MOD)
		else:
			print(0)


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n - 1);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  rep(i, n - 1) cin >> c[i];
  int ans = 0;
  rep(i, n) {
    ans += b[a[i] - 1];
    if (i > 0 && a[i - 1] + 1 == a[i]) ans += c[a[i - 1] - 1];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <regex>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

signed main(){
    string s;
    cin >> s;

    regex re("A?KIHA?BA?RA?");
    if(regex_match(s, re)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}


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

using namespace std;

struct edge{
  int to, tim;
  edge(){}
  edge(int to, int tim):to(to), tim(tim){}
  bool operator < (const edge& e) const {
    return tim != e.tim ? tim < e.tim : to < e.to;
  }
};

vector< vector<edge> > graph(32768);
bool visited[32768];

typedef pair<int, int> P;

int bfs(int v, int t)
{
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(t, v));
  int ret = 0;
  while(!que.empty()){
    int now = que.top().second, tim = que.top().first; que.pop();
    if(visited[now]) continue;
    visited[now] = true;
    ret++;
    for(int i = 0; i < graph[now].size(); i++){
      if(tim < graph[now][i].tim){
	que.push(P(graph[now][i].tim, graph[now][i].to));
      }
    }
  }
  return ret;
}

int main()
{
  int N, M;
  while(cin >> N >> M, N || M){
    graph.resize(N + 1);
    while(M--){
      int t, s, d;
      cin >> t >> s >> d;
      s--, d--;
      graph[s].push_back(edge(d, t));
    }
    for(int i = 0; i < N; i++) sort(graph[i].begin(), graph[i].end());
    memset(visited, false, sizeof(visited));
    cout << bfs(0, 0) << endl;
    for(int i = 0; i < N; i++) graph[i].clear();
  }
  return 0;
}

Measured memory_bytes: 2588
#include <iostream>


int main() {
	int A, B, C, K;

	std::cin >> A >> B >> C >> K;

	if (K < A) {
		std::cout << K << std::endl;
		return 0;
	} else {
		if (A + B > K) {
			std::cout << A << std::endl;
			return 0;
		} else {
			std::cout << A - (K - A - B) << std::endl;
			return 0;
		}
	}

}


Measured memory_bytes: 3632
//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
#include <bits/stdc++.h>
#define YES "Alice"
#define NO "Borys"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a,T b){a=max(a,b);}
template<typename T> inline void minimize(T &a,T b){a=min(a,b);}
template<typename T> inline bool middle(T a,T b,T c){return b<=a && a<=c;}
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
inline void outputVI(VI x){REP(i,SI(x)){cout << three(i," ","") << x[i];}OUT("");}
const int SIZE1=1e6+1000;
const int SIZE2=5010;
const int SIZE3=400;
const int SIZE=SIZE1;
const LL p=7+1e9;
const LL INF=1LL<<60;
const long double EPS=1e-7;
string s;
ut N,M,K,X,L,Y;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE],nums[SIZE],maps[SIZE2][SIZE2],answer=zero;
 
////////////////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////////////////
void init(){
 
}
LL solve(){
	LL A,B;
	cin >> N >> A >> B;
	return ((B-A)%2)==0;
}
signed main(){
	YESNO;
	return 0;
}

Measured memory_bytes: 24448
pre_N_list=input()
N_list=pre_N_list.split(' ')
N=int(N_list[0])
K=int(N_list[1])
p=input()
p_list=p.split(' ')
exp=[]
com=[]
com_sum=[]
t=0
for i in range(N):
  p_list[i]=int(p_list[i])
for i in range(1000):
  exp.append((1+i+1)*(i+1)/(2*(i+1)))
#これでexp[i]にはその最大面の値がi+1のサイコロ期待値が格納される。#
for i in range(N):
  com.append(exp[p_list[i]-1])
#print('期待値：',com)#
#com[]はpが[p1 p2 p3 p4・・・]のときcom=[exp[p1] exp[p2] exp[p3] exp[p4]・・・]である。#
for i in range(N):
  t+=com[i]
  com_sum.append(t)
#print('期待値の和', com_sum)#
#com_sum=[com[0] com[0]+com[1] com[0]+com[1]+com[2] ・・・]#
com_dif=[]
com_dif.append(com_sum[K-1])
for i in range(N-K):
  com_dif.append(com_sum[i+K]-com_sum[i])
#print('期待値の差', com_dif)#
print(max(com_dif))

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

int main(){
    float a,b,c;
    int k;
    cin>>a>>b>>c>>k;
    int k1=0,k2=0;
    if(b<=a){
        k1 = floor(log2(a/b)) + 1;
        b = b*pow(2,k1);
    }
    if(c<=b){
        k2 = floor(log2(b/c)) + 1;
    }
    if(k>=k1+k2) cout<<"Yes\n";
    else cout<<"No\n";
}

Measured memory_bytes: 4004
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b,c;
	cin >> a >> b >> c;
	cout << min(a*b,c) << endl;
}

Measured memory_bytes: 256
N = int(raw_input())

array = []

for i in range(N):
    num = int(raw_input())
    array.append(num)

array.sort()

d = 1
pre_r = array.pop(0)

while len(array) > 0:
    tmp_r = array.pop(0)
    if pre_r < tmp_r:
        d = d +1
        pre_r = tmp_r

print d


Measured memory_bytes: 2568
import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.lang.Integer;
import java.lang.StringBuilder;
import java.lang.Math;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String c = in.next();

    switch (c) {
      case "a":
      case "i":
      case "e":
      case "o":
      case "u":
          System.out.println("vowel");
          break;
      default:
          System.out.println("consonant");
    }   
  }
}

Measured memory_bytes: 10068