akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

def main():
    S = input()
    if S == 'SUN':
        print(7)
    elif S == 'MON':
        print(6)
    elif S == 'TUE':
        print(5)
    elif S == 'WED':
        print(4)
    elif S == 'THU':
        print(3)
    elif S == 'FRI':
        print(2)
    elif S == 'SAT':
        print(1)


if __name__ == "__main__":
    main()


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






int main(){
  


  int n;
  cin>>n;
  
  vector<vector<int>> data(3,vector<int>(n+1));
  
  for (int i=1;i<=2;i++){
    for (int j=1;j<=n;j++){
      int tmp;
      cin>>tmp;
      data.at(i).at(j)=tmp;
    }
  }
  
  
  int answer=0;
  
  for (int i=1;i<=n;i++){
    
    
    int tmp=0;
    
    
    for (int j=1;j<=i;j++){
      tmp+=data.at(1).at(j);
    }
    
    for (int j=i;j<=n;j++){
      tmp+=data.at(2).at(j);
    }
    
    answer=max(answer,tmp);
  }
  
  cout<<answer<<endl;
  
    
    
    
      
  
    

  
  
    
  
  
  
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

if 7 == a[0]:
    if 5 == a[1] and 5 == a[2]:
        print("YES", end="\n")
    else:
        print("NO", end="\n")   

elif 5 == a[0]:
    if (7 == a[1] and 5 == a[2]) or (5 == a[1] and 7 == a[2]):
        print("YES", end="\n")
    else:
        print("NO", end="\n")   
else:
    print("NO", end="\n")

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

int perm(int N, int i, int d, vector<int> types, int ans, vector<int> a) {
  if (i == d) {
    double x = 0;
    int c[7 + 1] = {0};

    bool non_zero = true;
    for (int i = 0; i < d; i++) {
      int v = a[i];
      x += v * pow(10, d - i - 1);
      if (non_zero && v != 0) non_zero = false;
      if (!non_zero) c[v]++;
    }
    /*
    // ref:
    https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3655130 for
    (int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << ", "; for (int i
    = 0; i <= 7; i++) cout << c[i] << " "; cout << ", " << x; cout << endl;
    */

    if (c[0] == 0 && c[7] >= 1 && c[5] >= 1 && c[3] >= 1 && x <= N) {
      ans++;
    }

    return ans;
  }

  for (auto t : types) {
    a[i] = t;
    ans = perm(N, i + 1, d, types, ans, a);
  }

  return ans;
}

int runPerm(int N, int d, vector<int> types) {
  auto a = vector<int>(d, 0);
  int ans = perm(N, 0, d, types, 0, a);
  return ans;
}

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

  int d = S.size();
  vector<int> types = {0, 3, 5, 7};
  int ans = runPerm(N, d, types);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
package main

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

var sc *bufio.Scanner = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}()

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = nextInt()
	}
	return ints
}

func newPlayer(num int, order []int) player {
	return player{num: num, nowIndex: 0, order: order}
}
func newPlayers(ps ...player) players {
	players := make(players, len(ps))
	for i := range ps {
		players[i+1] = &ps[i]
	}
	return players
}

type player struct {
	num      int
	nowIndex int
	order    []int
}

func (p *player) next() {
	p.nowIndex++
}
func (p *player) isFinished() bool {
	return p.nowIndex >= len(p.order)
}
func (p *player) getOppNum() int {
	return p.order[p.nowIndex]
}

func (p *player) String() string {
	return fmt.Sprintf("{%v,%v,%v}", p.num, p.nowIndex, p.order)
}

type players map[int]*player

type matchSet map[int]struct{}

func (ms *matchSet) add(i int) {
	(*ms)[i] = struct{}{}
}
func (ms *matchSet) isEmpty() bool {
	return len(*ms) == 0
}
func (ms *matchSet) contains(i int) bool {
	_, ok := (*ms)[i]
	return ok
}

func decide(n int, players players) int {
	mainQueue := make([]int, 0, n)
	for i := 0; i < n; i++ {
		mainQueue = append(mainQueue, i)
	}

	days := 0
	for len(mainQueue) > 0 {
		queue := mainQueue
		mainQueue = nil

		days++

		isMatched := false
		visited := matchSet{}

		for _, i := range queue {
			p, ok := players[i]
			if !ok {
				continue
			}
			if visited.contains(p.num) {
				continue
			}
			visited.add(i)
			popp, ok := players[p.getOppNum()]
			if !ok {
				continue
			}
			if visited.contains(popp.num) {
				continue
			}
			if p.num != popp.getOppNum() {
				continue
			}
			p.next()
			popp.next()
			// only when they are matched, opponent is visited.
			visited.add(popp.num)
			isMatched = true

			if !p.isFinished() {
				mainQueue = append(mainQueue, p.num)
			}
			if !popp.isFinished() {
				mainQueue = append(mainQueue, popp.num)
			}
		}
		if !isMatched { //空なら失敗
			return -1
		}
	}
	return days
}

func main() {
	n := nextInt()
	mp := make(players, n)
	for i := 1; i < n+1; i++ {
		p := newPlayer(i, nextInts(n-1))
		mp[i] = &p
	}
	// fmt.Println(mp)
	r := decide(n, mp)
	fmt.Println(r)
}


Measured memory_bytes: 18432
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, m;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			break;
		}
		vector<int> a(n);
		vector<int> b(m);
		int sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			sum += a[i];
		}
		for (int i = 0; i < m; i++) {
			cin >> b[i];
			sum -= b[i];
		}
		int aa, bb;
		aa = bb = 1000;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if ((a[i] - b[j]) * 2 == sum && a[i]+b[j] < aa+bb) {
					aa = a[i];
					bb = b[j];
				}
			}
		}
		if (aa == 1000) {
			cout << -1 << endl;
		}
		else {
			cout << aa << ' ' << bb << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2996
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>	
#include <cmath>
#include <string>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define Cout(s) cout<<s<<endl
using namespace std;
typedef long long ll;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================
int ketawa(int a) {
	if (a < 10)return a;
	else return a % 10 + ketawa(a / 10);
}

int a = 1, b = 0, c, d, n, k = 0, ans = 0;
string s, t;

int main()
{
	int n; cin >> n;
	vector<int> a(n); rep(i, n-1) { cin >> b; a[b-1]++; }
	rep(i, n) {
		cout << a[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 4052
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2],R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i = 0; i < n1; i++)L[i] = A[left + i];
  for(int i = 0; i < n2; i++)R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i =0, j = 0;
  for(int k = left; k < right; k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right){
  if(left+1 < right){
    int mid = (left + right) / 2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt = 0;

  cin >> n;
  for(i = 0; i < n; i++)cin >> A[i];

  mergeSort(A, n, 0, n);

  for(i = 0; i < n; i++){
    if(i)cout << " ";
    cout << A[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}

      



Measured memory_bytes: 6972
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <cstring>
#include <iomanip>
#include<queue>

using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1000000000
typedef long long  ll;

#define MOD 1000000007


struct data {
  long long a;
};
const long long minint = 0;
data resetdata = {minint};
struct RMQ {
  // except bottom size
  int sizen;
  vector<data> dat;
  RMQ(int newn = 1, data resets = resetdata) {
    reset(newn, resets);
  }
  void reset(int newn = 1, data resets = resetdata) {
    sizen = 1;
    while(sizen < newn) sizen *= 2;
    dat.resize(2 * sizen - 1);
    for(int i = 0; i < dat.size(); ++i) dat[i] = resets;
  }
  // "go up" process
  // data[k].a = newnum
  bool update(int k, long long newnum) {
    k += sizen - 1;
    dat[k].a = newnum;
    while(k > 0) {
      k = (k - 1) / 2;
      dat[k].a = max(dat[k * 2 + 1].a, dat[k * 2 + 2].a);
    }
    return 1;
  }
  // "go down" process
  // return min number in [a,b)
  // pick(a,b,0,0,sizen)
  long long pick(int a, int b, int k = 0, int l = 0,
                 int r = -1) {
    if(r == -1) r = sizen;
    // [l,r)[a,b) or [a,b)[l,r)
    if(r <= a || b <= l) return minint;
    // [a,[l,r),b)
    if(a <= l && r <= b) return dat[k].a;
    // else
    long long nowl, nowr, nextlr = k * 2 + 1,
                          med = (l + r) / 2;
    nowl = pick(a, b, nextlr, l, med);
    nowr = pick(a, b, nextlr + 1, med, r);
    return max(nowl, nowr);
  }
};

int main()
{
    int n;
    cin >> n;
    int h[n];
    ll a[n];
    REP(i, 0, n)
    {
        cin >> h[i];
    }
    REP(i, 0, n)
    {
        cin >> a[i];
    }
    ll ans = 0;

    RMQ rmq = RMQ(n + 1);
    REP(i,0,n){
        ll now = a[i];
        now += rmq.pick(0, h[i]);
        rmq.update(h[i], now);
        ans = max(ans, now);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6656
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll arr[100001];
vector<ll> cache(100001,-1);
ll n,k;

int main()
{
	string s,t;
	cin>>s>>t;
	int m = s.length();
	int n = t.length();
	int arr[m+1][n+1];
	for(int i=0;i<m+1;i++)
	{
		for(int j=0;j<n+1;j++)
		{
				arr[i][j]=0;
		}
	}
	for(int i=1;i<m+1;i++)
	{
		for(int j=1;j<n+1;j++)
		{
			if(s[i-1]==t[j-1])
			{
				arr[i][j] = arr[i-1][j-1] + 1;
			}
			else
				arr[i][j] = max(arr[i-1][j], arr[i][j-1]);
		}
	}
	int g = arr[m][n];
	char ans[g+1];
	ans[g] = '\0';
	int i=m,j=n;
	while(i>0 && j>0)
	{
		if(s[i-1]==t[j-1])
		{
			ans[g-1] =  s[i-1];
			i--;j--;g--;
		}
		else if(arr[i-1][j]>arr[i][j-1])
				i--;
			else
				j--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 36224
#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 sum = 1110;

int main() {
    int n;
    cin >> n;
    int ans;
    ans = sum-n;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define PI 3.14159265358979323846264338327950288
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

int main(void) {

	int X, A; cin >> X >> A;
	cout << (X < A ? 0 : 10) << endl;

	return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

int f_dir[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}}; //↑→↓←
int e_dir[2][8] = {{-1, -1, -1, 0, 0, 1, 1, 1}, {-1, 0, 1, -1, 1, -1, 0, 1}};
bool is_in_field(int y, int x, int h, int w){
  return (y >= 0 && y < h && x >= 0 && x < w);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  string s; cin >> s;
  int a = 0;
  for(int i = 0; i < s.length(); i++){
    a += s[i] - '0';
    a %= 9;
  }
  if(a == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    string s; cin>>s;
    bool ok = false;
    rep(i,s.length()) {
        if (s[i]=='7') ok = true;
    }
    if (ok) cout << "Yes" << '\n';
    else cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>

using namespace std;


int main(){
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;

  for(int i=0;i<abs(x1-x2);i++){
    cout<<"R";
  }

  for(int i=0;i<abs(y1-y2);i++){
    cout<<"U";
  }

  for(int i=0;i<abs(x1-x2);i++){
    cout<<"L";
  }

  for(int i=0;i<abs(y1-y2);i++){
    cout<<"D";
  }

  cout<<"D";

  for(int i=0;i<abs(x1-x2)+1;i++){
    cout<<"R";
  }

  for(int i=0;i<abs(y1-y2)+1;i++){
    cout<<"U";
  }

  cout<<"L";

  cout<<"U";

  for(int i=0;i<abs(x1-x2)+1;i++){
    cout<<"L";
  }


  for(int i=0;i<abs(y1-y2)+1;i++){
    cout<<"D";
  }

  cout<<"R"<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1000000007;

void solve() {
  int n;
  cin >> n;
  map<ll,ll> mp;

  ll res = 0;

  rep(i,n) {
    ll a;
    cin >> a;
    mp[a]++;
    res += a;
  }
  int q;
  cin >> q;
  vector<ll> b(q);
  vector<ll> c(q);
  rep(i,q) cin >> b[i] >> c[i];
  rep(i,q) {
    if (mp[b[i]]) {
      res -= b[i] * mp[b[i]];
      res += c[i] * mp[b[i]];
      mp[c[i]] += mp[b[i]];
      mp[b[i]] = 0;
    }
    cout << res << endl;
  }

}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 10468
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    if(n % 10 == 3) {
        cout << "bon" << endl;
    } else if(n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }

    return 0;
}


Measured memory_bytes: 3640
using System;

class Atcoder69
{
    public static void Main()
    {
        string grid = Console.ReadLine();
        char left = grid[0];
        char mid = grid[1];
        char right = grid[2];

        string strleft = left.ToString();
        string strmid = mid.ToString();
        string strright = right.ToString();

        int intleft = int.Parse(strleft);
        int intmid = int.Parse(strmid);
        int intright = int.Parse(strright);

        Console.WriteLine(intleft + intmid + intright);
    }
}

Measured memory_bytes: 13140
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N =  int(sys.stdin.readline())
list_H =  list(map(int, sys.stdin.readline().split()))

cnt_max = 0
cnt_max_tmp = 0

# #マスを左からチェックする
# for i in range(N):
#     #何回右へ移動できるかチェックする
#     for i in range(N):
#         if(i < N - 1):
#             if(list_H[i] >= list_H[i+1]):
#                 cnt_max_tmp += 1
#             else:
#                 break
#         else:
#             break
#     if(cnt_max_tmp > cnt_max):
#         cnt_max = cnt_max_tmp
#         cnt_max_tmp = 0

#マスを左からチェックする
for i in range(N):
    if(i == N-1):
        if(cnt_max_tmp > cnt_max):
            cnt_max = cnt_max_tmp
        cnt_max_tmp = 0
        break

    if(list_H[i] >= list_H[i+1]):
        cnt_max_tmp += 1
    else:
        if(cnt_max_tmp > cnt_max):
            cnt_max = cnt_max_tmp

        cnt_max_tmp = 0


print(cnt_max)



Measured memory_bytes: 16268
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)(v).size()
#define vi vector<int>

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;
template<typename T>
struct Edge {
    int u, v;
    T cost;
    Edge(int u, int v, T c) : u(u), v(v), cost(c) {}
    bool operator< (const Edge &e) const {return cost < e.cost;}
};

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

ll ans;
ll dp[1000005][2];

int main(void) {
  //解説あり
    string x, N = "x";
    cin >> x;
    N += x;
    dp[0][1] = 1;
    rep(i, 1, sz(N)){
      ll d = (ll)(N[i] - '0');
      dp[i][0] = min(dp[i-1][0]+d, dp[i-1][1]+10-d);
      dp[i][1] = min(dp[i-1][0]+d+1, dp[i-1][1]+10-d-1);
      //printf("%lld %lld\n", dp[i][0], dp[i][1]);
    }
    
    ans = dp[sz(N)-1][0];
    cout << ans << endl;
    
    return 0;
}





Measured memory_bytes: 20872
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int a, b, c;
    int k;
    cin >> a >> b >> c >> k;

    int cnt = 0;

    while (true)
    {
        if (a < b)
        {
            break;
        }
        b <<= 1;
        cnt++;
    }

    while (true)
    {

        if (b < c)
        {
            break;
        }
        c <<= 1;
        cnt++;
    }

    if (k < cnt)
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    double R;
    cin >> R;
    cout << fixed << setprecision(15) << 2 * M_PI * R << endl;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

 
void solve()
{
    int n;cin>>n;
    int h[n];REP(i,n)cin>>h[i];
    vector<ll>dp(n,1e9);dp[0]=0;
    REP(i,n)
    {
        if(i+1<n)dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
        if(i+2<n)dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
    }
    cout<<dp[n-1]<<endl;
}

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


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

int N,M;
bool visited[8];
vector<int> G[8];

int dfs(int s){
  bool all = true;
  for(int i=0;i<N;i++)
    if(!visited[i]) all = false;
  if(all) return 1;
  int ret = 0;
  for(int i=0;i<G[s].size();i++){
    int nx = G[s][i];
    if(visited[nx]) continue;
    visited[nx] = true;
    ret += dfs(nx);
    visited[nx] = false;
  }
  return ret;
}

int main(){
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  visited[0] = true;
  cout<<dfs(0)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main( void )
{
	while ( !cin.eof() )
	{
		long long a, b;
		cin >> a >> b;
		if ( cin.eof() )
			break;

		long long x = max(a,b);
		long long y = min(a,b);

		while ( y > 0 )
		{
			x -= y;
			if ( x < y )
				swap( x, y );
		}

		long long gcd = x;
		long long lcm = a*b / gcd;

		cout << gcd << " " << lcm << endl;

	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n,v[N];
long long c,cs[N],x[N],cs1[N];
int main() {
	//freopen("input.txt","r",stdin);
	scanf("%d%lld",&n,&c);
	for(int i = 0;i < n;i++)scanf("%lld%d",x + i,v + i);
	long long last = 0,bad = 0,ans = 0,sum = 0;
	for(int i = 0;i < n;i++){
		bad = x[i];
		last = x[i];
		sum+=v[i];
		ans = max(ans,sum - bad);
		cs[i] = sum - bad - bad;
		cs1[i] = sum - bad;
 	}
 	for(int i = 1;i < n;i++){
 		cs[i] = max(cs[i],cs[i - 1]);
 		cs1[i] = max(cs1[i],cs1[i - 1]); 
 	}
 	last = c;bad = 0;sum = 0;
 	for(int i = n - 1;i + 1;i--){
 		bad = last - x[i];
 		sum+=v[i];
		ans = max(ans,sum - bad);
 		ans = max(ans,sum - bad + (i ? cs[i - 1] : 0));	
 		ans = max(ans,sum - bad - bad + (i ? cs1[i - 1] : 0));
 	}
 	cout << ans << endl;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
int a[110];
bool fl=1;
int main()
{
	cin >>n;
	for (int i=0;i<n;i++)
	{
		cin >>a[i];
		if (a[i]%2==0) fl&=((a[i]%3==0)|(a[i]%5==0));
	}
	cout <<(fl ? "APPROVED" : "DENIED");
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
//const ll mod = 1000000007;
ll N, M;
vector<ll> paths[105000];
ll dist[105000];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        paths[a].push_back(b);
        paths[b].push_back(a);
    }
    for(int i = 0; i < N; i++) dist[i] = 1e9;
    dist[0] = 0;
    queue<int> que;
    que.push(0);
    while(!que.empty()) {
        ll now = que.front();
        que.pop();
        for(auto to : paths[now]) {
            if(chmin(dist[to], dist[now] + 1)) {
                que.push(to);
            }
        }
    }
    cout << "Yes" << endl;
    for(int i = 1; i < N; i++) {
        for(auto to : paths[i]) {
            if(dist[to] == dist[i] - 1) {
                cout << to + 1 << endl;
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 13004
#region Using directives
using System;
using static System.Console;
using static System.Convert;
using System.Collections.Generic;
using System.Linq;
#endregion

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = (ReadLine()).Split();
            long N = ToInt64(s[0]);
            long M = ToInt64(s[1]);
            long K = ToInt64(s[2]);
            for (long i = 0; i <= N; i++)
            {
                long answ = 0;
                for(long j = 0; j <= M; j++)
                {
                    answ = i*j + (N-i)*(M-j);
                    if (answ == K)
                    {
                        WriteLine("Yes");
                        ReadKey();
                        return;
                    }
                }
            }
            WriteLine("No");
            ReadKey();
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
struct node{
	int a,b;
	int tot;
};
node peo[500005];
int cmp(node x, node y){
	if (x.tot>y.tot)
		return true;
	return false;
}
int main()
{
	int n;
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> peo[i].a >> peo[i].b;
		peo[i].tot=peo[i].a+peo[i].b;
	}	
	sort(peo+1,peo+n+1,cmp);
	long long ans=0;
	for (int i=1;i<=n;i++){
		if (i%2==1) ans+=peo[i].a;
		else ans-=peo[i].b;
	}
	cout << ans;
	return 0;
}

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

#define MAX_N 100

// int M1 = 11;
// int D1 = 16;
// int M2 = 11;
// int D2 = 17;

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

    if (M1 != M2) {
        printf("%d\n", 1);
    } else {
        printf("%d\n", 0);
    }
}

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

int main() {
	string s;
	cin >> s;
	int length = 0;
	for (int i = 0, size = s.length();i < size;i ++) {
		if (s[i] == 'B') length --; // 1文字戻る
		else {
			s[length] = s[i]; // Bでないならその数字を保存
			length ++; // で、1文字長さが増える
		}
		if (length < 0) length = 0; // 空ならこれ以上減らないので
	}
	cout << s.substr(0, length);
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、Bが入力されない限り与えられたsと同じ文字が出力される
次に、Bが入力されると、1個入力されるたびに出力文字数は2文字減るし、Bの手前を上書きする
これは、上のコードのように書くと簡潔に実装できるね
*/

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int main()
{
	int n;
	int i,s=1;
	scanf("%d",&n);
	for(i=1;i<7;i++)
	{
		s*=2;
		if(n==1){
		s=1;break;}
		if(n>s&&n<s*2)break;
		if(n==s*2){
		s=s*2;break;}
		if(n==s)break;
	}
	printf("%d",s);
	return 0;
}

Measured memory_bytes: 128
from sys import stdin
import sys

A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if K <= A:
    print(K)
    sys.exit()
elif K <= A+B:
    print(A)
    sys.exit()
else:
    print(A-(K-A-B))
    sys.exit()


Measured memory_bytes: 9108
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(num,init,name) vector<int> name((num),(init));

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>> s(h+1,vector<char>(w+1,'1'));
    repf(i,1,h+1){
        repf(j,1,w+1){
            cin>>s[i][j];
        }
    }
    repf(i,1,h){
        repf(j,1,w){
            if(s[i][j]=='#'){
                if(s[i-1][j]!='#'&&s[i][j-1]!='#'&&s[i+1][j]!='#'&&s[i][j+1]!='#'){
                    cout<<"No"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;

}



Measured memory_bytes: 256
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]

yoko = [1 for i in range(h)]
tate = [1 for i in range(w)]

for i in range(h):
    if a[i].count(".") == w:
        yoko[i] = 0

a_t = [list(x) for x in zip(*a)]

for i in range(w):
    if a_t[i].count(".") == h:
        tate[i] = 0

for i in range(h):
    s = ""
    for j in range(w):
        if yoko[i] and tate[j]:
            s += a[i][j]
    if s:
        print(s)

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

bool gteq(vector<int> vec1,vector<int> vec2){
    for(int i=0;i!=vec1.size()-1;i++){
        if(vec1[i] > vec2[i]) return true;
        else if(vec1[i] < vec2[i]) return false;
    }
    return true;
}

int main(){
    string a(100,'0');
    
    cin >> a;
    int y=stoi(a.substr(0,4));
    int m=stoi(a.substr(5,2));
    int d=stoi(a.substr(8,2));
    vector<int> in(3);
    in[0]=y;in[1]=m;in[2]=d;
    vector<int> x(3);
    x[0]=2019;x[1]=4;x[2]=30;
    bool heisei = gteq(x,in);



    cout << (heisei ? "Heisei":"TBD") << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1LL<<50
#define fst first
#define sec second
#define pb push_back
#define int long long
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(int itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(int itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define debug(x)  cout << #x << " = " << (x) << endl;
typedef long long ll;
typedef pair<ll,ll> P;

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

  int n;
  cin >> n;
  
  int a[n];
  REP(i,n) cin >> a[i];
  
  sort(a,a+n);
  
  int s[n] = {};
  REP(i,n) s[i] = s[i-1==-1?0:i-1]+a[i];
  
  int ans = 0;
  REP(i,n-1){
    if(a[i+1]<=s[i]*2) ans++;
    else               ans = 0;
  }
  
  cout << ans + 1 << endl;

  return 0;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-

import sys
import re
from collections import deque, Counter, defaultdict
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, product, combinations, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
aN = LIST()

mx = -INF
l, r = 0, 1
cnt = 0
# 外ループで左を動かす
while l < N:
    # 内ループは条件を満たす限り右を動かす
    while r < N and aN[l] < aN[r]:
        # 最高値更新ならその場所が操作対象になる
        if aN[r] - aN[l] > mx:
            mx = aN[r] - aN[l]
            cnt = 1
        # 同率最高値なら操作対象が1つ増える
        elif aN[r] - aN[l] == mx:
            cnt += 1
        mx = max(aN[r] - aN[l], mx)
        r += 1
    # 左端を右端に追いつかせる
    l = r
    r += 1
print(cnt)


Measured memory_bytes: 15164
#include <iostream>

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);//高速化、endlは使わない

  int A, B, C, D;

  cin >> A >> B >> C >> D;

  int Sec[101];
  for(int i = 0; i < 101; i++){
    Sec[i] = 0;
  }

  for(int i = A; i < B; i++){
    Sec[i] += 1;
  }

  for(int i = C; i < D; i++){
    Sec[i] += 1;
  }

  int ans = 0;

  for(int i = 0; i < 101; i++){
    if(Sec[i] == 2) ans+=1;
  }

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


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

int main() {
	string s,t;
	int count=0;
	cin >> s >> t;
	if(s[0]==t[0]) count ++;
	if(s[1]==t[1]) count ++; 
	if(s[2]==t[2]) count ++;
	cout << count <<endl;
	return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<cassert>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

template<int m>
class Prime{
  std::vector<bool> p;
  std::vector<int> ps;
public:
  Prime(){
    p = std::vector<bool>(m,true);
    assert(m>1);
    p[0]=p[1]=false;
    for(int i=4;i<m;i+=2)
      p[i]=false;
    ps.push_back(2);
    for(int i=3;i<m;i+=2){
      if(p[i]){
        ps.push_back(i);
        for(int j=i+i;j<m;j+=i)
          p[j]=false;
      }
    }
  }

  bool isPrime(int n){
    assert(m>n);
    return p[n];
  }

  int operator [] (int n){
    if(n<ps.size()) return ps[n];
    else return 0;
  }

  int size(){
    return ps.size();
  }
};

int memo[1121][15][200];
Prime<1200> p;

int dp(int n, int k, int i){
  if(k == 0 && n == 0) return 1;
  if(k == 0) return 0;
  if(n < 0) return 0;
  if(i == p.size()) return 0;
  if(memo[n][k][i] != -1) return memo[n][k][i];
  return memo[n][k][i] = dp(n,k,i+1) + dp(n-p[i],k-1,i+1);
}

int main(){
  int n,k;
  memset(memo, -1, sizeof(memo));
  while(scanf("%d%d",&n,&k),n+k)
    printf("%d\n",dp(n,k,0));
  return 0;
}

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

#define reps(i,j,k) for(int i=(j);i<(k);i++)
#define rep(i,k) reps(i,0,j)
#define sc second
#define fs first
#define pb push_back
using namespace std;

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


int main(){
	int r0, w0, c, r;

	while(cin >> r0 >> w0 >> c >> r, !(r0 == 0 && w0 == 0 && c == 0 && r == 0)) {
		int cnt = 0;

		while((r0 + cnt * r) < c * w0) {
			cnt++;
		}

		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> w(n);
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i];
        sum = sum + w[i];
    }
    int result = sum;
    int b = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i];
        b = b + w[i];
        result = min(result, abs(b - (sum - b)));
    } 
    cout << result << endl;
    return 0;
}

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

int a[16][16], INF = 1e17;
vector<int> cost((1 << 16));

int calc(int x) {
    int cost = 0;
    for(int i = 0; i <= 15; i++) {
        for(int j = i+1; j <= 15; j++) {
            if((x & (1 << i)) && (x & (1 << j))) {
                cost += a[i][j];
            }
        }
    }
    return cost;
}

vector<int> dp((1 << 16) , -INF);
int solve(int mask) {
    if(mask == 0) return 0;
    else if(dp[mask] != -INF) return dp[mask];
    for(int sub = mask; sub > 0; sub = (sub-1)&mask) {
        dp[mask] = max(dp[mask] , cost[sub] + solve((mask^sub)));
    }
    return dp[mask];
}

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

    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) cin >> a[i][j];
    }
    for(int i = 0; i < (1 << n); i++) cost[i] = calc(i);
    cout << solve((1 << n)-1) << "\n";

    return 0;
}



Measured memory_bytes: 4212
#include <stdio.h>

const long long mod = 1000000007;
long long inv[200200],fact[200200],ifact[200200];

long long comb(int n, int k)
{
	return fact[n] * ifact[k] % mod * ifact[n-k] % mod;
}

int main()
{
	inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
	for (int i=2;i<200200;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	int h,w,a,b; scanf ("%d %d %d %d",&h,&w,&a,&b);

	long long ans = comb(h+w-2,h-1);

	for (int i=0;i<b;i++){
		long long u = comb(h-a-1+i,i);
		long long v = comb(a-1+w-1-i,a-1);
		ans = (ans - u * v % mod + mod) % mod;
	}
	printf ("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 4864
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
 int a , b;
 cin >> a >> b;
 cout << max({a + b , a - b , a * b}) << endl;
}

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

int main() {
  int N , K;
  cin >> N >> K;
  int l = 0;
  int x;
  for (int i = 0; i < N; i++){
    cin >> x;
    if (x * 2 < (K - x) * 2){
      l += x * 2;
    }else{
      l += (K - x) * 2;
    }
  }
  cout << l << endl;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "3 4", "2 2 4" ].parse.expand.solve == 5 );
	assert( [ "5 8", "9 9 9 9 9" ].parse.expand.solve == 0 );
	assert( [ "10 10", "3 1 4 1 5 9 2 6 5 3" ].parse.expand.solve == 152 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ns = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( ns[ 1 ], as );
}

auto solve( long s, long[] as )
{
	const M = 998244353L;
	
	// dp[ i番目 ][ i番目までで選んだ整数の合計 ] = 通り数
	auto dp = new long[][]( 1 + as.length, 1 + s );
	
	// 選ぶ整数のうち一番左をi番目にした場合、Lは0～iのi+1通りになる
	foreach( i, ref dpp; dp )
	{
		dpp[ 0 ] = 1;
	}
	
	foreach( i, a; as )
	{
		foreach( j; 0L .. dp[ i ].length.signed - 1 )
		{
			// i番目の整数を選ばないとき
			dp[ i + 1 ][ j ] = ( dp[ i + 1 ][ j ] + dp[ i ][ j ] ) % M;
			
			// i番目の整数を選ぶとき
			auto ss = j + a;
			if( ss < dp[ i + 1 ].length ) dp[ i + 1 ][ ss ] = ( dp[ i + 1 ][ ss ] + dp[ i ][ j ] ) % M;
		}
	}
	
	// 選ぶ整数のうち一番右をi番目にした場合、Rはi～nのn-i通りになる
	auto ans = 0L;
	foreach( i, ref dpp; dp )
	{
		ans = ( ans + dpp[ $ - 1 ] * ( dp.length.signed - i ) ) % M;
	}
	return ans;
}


Measured memory_bytes: 74364
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define MOD 998244353
using namespace __gnu_pbds;
using namespace std;

int n,st[200010][21],pos[200010][21],dp[200010],r[200010];
pair<int,int> a[200010];
vector<int> v[200010];
bool vis[200010];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=MOD) x-=MOD;
}

inline int query(int l,int r)
{
	int len=r-l+1,p=1,cnt=0;
	while(p<=len){p*=2;cnt++;}
	cnt--;
	if(st[l][cnt]>st[r-(1<<cnt)+1][cnt]) return pos[l][cnt];
	else return pos[r-(1<<cnt)+1][cnt];
}

inline void dfs(int x)
{
	vis[x]=1;
	for(int i=0;i<v[x].size();i++){
		r[v[x][i]]=r[x];
		dfs(v[x][i]);
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		st[i][0]=a[i].first+a[i].second;
		pos[i][0]=i;
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n;j++){
        	if(j+(1<<(i-1))>n) break;
        	if(st[j][i-1]>st[j+(1<<(i-1))][i-1]) pos[j][i]=pos[j][i-1];
        	else pos[j][i]=pos[j+(1<<(i-1))][i-1];
        	st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int loc=upper_bound(a+1,a+n+1,make_pair(a[i].first+a[i].second,0))-a-1;
		int res=query(i,loc);
		if(res==i) r[i]=loc;
		else v[res].push_back(i);
	}
	for(int i=n;i>=1;i--) if(r[i]>0&&!vis[i]) dfs(i);
	dp[n+1]=1;
	for(int i=n;i>=1;i--){
		add(dp[i],dp[i+1]);
		add(dp[i],dp[r[i]+1]);
	}
	cout<<dp[1]<<endl;
	return 0;
}

Measured memory_bytes: 43904
import math
n,m=map(int,input().split())
if abs(n-m)>1:
  print(0)
  exit()
p=10**9+7
if n==m:
  print((2*((math.factorial(m))%p)*((math.factorial(n))%p))%p)
else:
  print((((math.factorial(m))%p)*((math.factorial(n))%p))%p)

Measured memory_bytes: 4084
#include <iostream>
#include <string.h>

using namespace std;

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	char str[n];
	scanf(" %s", str);
	str[k - 1] = tolower(str[k - 1]);
	printf("%s\n", str);
	return 0;
}

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

#define ll long long
#define ar array

const int mxN=200000;
int n;
int a[mxN], b[mxN];

void read(int i) {
	string s; cin >> s;
	long long cur=0;
	bool seen=0;
	for (char c: s) {
		if (c=='.') {
			seen=1;
			continue;
		}
		if (seen) --a[i], --b[i];
		cur=10*cur+(c-'0');
	}
	while(cur%2==0) {
		cur/=2;
		++a[i];
	}
	while(cur%5==0) {
		cur/=5;
		++b[i];
	}
	a[i]=min(a[i], 15);
	b[i]=min(b[i], 15);
}

int ps[30][30];

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

	cin >> n;
	for (int i=0; i<n; ++i) {
		read(i);
		//cout << a[i] << ' ' << b[i] << '\n';
		assert(a[i]>=-9&&b[i]>=-9);
		++ps[a[i]+10][b[i]+10];
	}
	for (int i=1; i<30; ++i) for (int j=1; j<30; ++j) {
		ps[i][j]+=ps[i-1][j];
		ps[i][j]+=ps[i][j-1];
		ps[i][j]-=ps[i-1][j-1];
	}
	/*for (int i=1; i<=20; ++i) {
		for (int j=1; j<=20; ++j)
			cout << ps[i][j] << ' ';
		cout << '\n';
	}*/
	ll ans=0;
	for (int i=0; i<n; ++i) {
		int x=max(1, -a[i]+10), y=max(1, -b[i]+10);
		int add=ps[29][29]-ps[x-1][29]-ps[29][y-1]+ps[x-1][y-1];
		/*if (i==3) {
			cout << ps[x-1][29] << ' ' << ps[29][y-1] << ' ' << ps[x-1][y-1] << '\n';
		}*/
		ans+=add;
		if (a[i]>=0&&b[i]>=0) --ans;
		//cout << add << '\n';
	}
	cout << ans/2;
	return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/


Measured memory_bytes: 5160
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, a, b) for(int i=(a); i<(int)(b); i++)

typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int to, cost; };
struct Node { int from, to, cost; };

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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}

int main(void){
	string str; cin >> str;
	int ans = 0;
	rep2(i, 1, str.size()){
		if(i <= 0) i=1;
		if(str[i-1] != str[i]){
			ans += 2;
			str.erase(str.begin()+i);
			str.erase(str.begin()+i-1);
			i -= 3;
		}
		if(str.size() <= 1) break;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
x = int(input())
a = 0
b = 0
comp = 0
while comp == 0 :
    aa = a**5
    tmp = aa - x
    if tmp < 0:
        b = -(pow(-tmp,1/5))
    elif tmp == 0:
        b = 0
    else:
        b = pow(tmp,1/5)
    b = Decimal(str(b)).quantize(Decimal('0.00000001'), rounding=ROUND_HALF_UP)
    b = float(b)
    if b.is_integer():
        b = int(b)
        comp = 1
    elif a <= 0:
        a = abs(a)+1
    else:
        a = -a
print(a,b)

Measured memory_bytes: 10260
# from math import gcd
from fractions import gcd
from functools import reduce

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

def main():
    n = int(input())
    # a = [int(x) for x in input().split()]
    a = tuple(map(int, input().split()))
    lcm = lcm_list(a)
    aa = []
    for i in range(len(a)):
        aa.append(lcm // a[i])
    ans = sum(aa) % 1000000007
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 264660
#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;
int main(void){
    int n;
    bool flg = false;
    cin >> n;
    vector<string> w(n);
    set<string> s;
    for(int i = 0;i < n;i++){
        cin >> w.at(i);
        if(s.count(w.at(i))) flg = true;
        s.insert(w.at(i));
    }
    for(int i = 0;i < n-1;i++){
        if(w[i][w[i].size()-1] != w[i+1][0]) flg = true;
    }
    cout << (flg ?"No":"Yes") << endl;
    return 0;
}


Measured memory_bytes: 256
import itertools
N = int(input())
S = [input()[0] for _ in range(N)]
S = [v for v in S if v in 'MARCH']
s = list(set(S))
c = 0
for v in itertools.combinations(s, 3):
  c += S.count(v[0]) * S.count(v[1]) * S.count(v[2])
print(c)


Measured memory_bytes: 4652
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define Max 1000004
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
    fast;
    ll n;
    cin>>n;
    ll a[n+2];
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        a[x]=i;
    }
    for(ll i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
}

Measured memory_bytes: 1664
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 11:44:37 2018
ALDS1-12-A
@author: maezawa
"""
import heapq

n = int(input())
amat = [[] for _ in range(n)]
for i in range(n):
    amat[i] = list(map(int, input().split()))

adj = [[] for _ in range(n+1)]
for i in range(n):
    for j in range(i, n):
        if amat[i][j] == -1:
            continue
        adj[i+1].append([amat[i][j], j+1])
        adj[j+1].append([amat[j][i], i+1])

#print(adj)
d = [10**10]*(n+1)
h = []
heapq.heappush(h, [0, 1]) # [cost, node]
visited = [False]*(n+1)
while h:
    cost, node = heapq.heappop(h)
    if visited[node] == False and cost < d[node]:
        d[node] = cost
        visited[node] = True
        for nextnode in adj[node]:
            if visited[nextnode[1]]:
                continue
            heapq.heappush(h,nextnode)

d.pop(0)
print(sum(d))
            


Measured memory_bytes: 6628
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> left_west(300000,0),right_east(300000,0);
  for(int i=1;i<n;++i){
    if(s[i-1]=='W'){
      left_west[i] = left_west[i-1]+1;
    }else{
      left_west[i] = left_west[i-1];
    }
    // cout << left_west[i] << " ";
  }

  // cout << endl;
  for(int i=n-2;i>=0;--i){
    if(s[i+1]=='E'){
      right_east[i] = right_east[i+1]+1;
    }else{
      right_east[i] = right_east[i+1];
    }
    // cout << right_east[i] << " ";
  }
  // cout << endl;
  int min_num = 300000;
  for(int i=0;i<n;++i){
    if(min_num > left_west[i] + right_east[i]){
      min_num = left_west[i] + right_east[i];
    }
  }
  cout << min_num << endl;
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>v(1000000);
int main()
{
    ll n,p,q,t,a,i,b,ans = 0;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>a;
        ans+=a;
        v[a]+=1;
    }
    cin>>t;
    while(t--)
    {
        cin>>p>>q;
        if(v[p] != 0)
        {
            v[q]+=v[p];
            ans-=(p*v[p]);
            ans+=(q*v[p]);
            v[p] = 0;
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 10988