akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main(){
	int x,y;
	cin >> x >> y;
	if(x==1||x==3||x==5||x==7||x==8||x==10||x==12){
		if(y==1||y==3||y==5||y==7||y==8||y==10||y==12){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}else if(x==4||x==6||x==9||x==11){
		if(y==4||y==6||y==9||y==11){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}else{
		cout << "No" << endl;
	}
	return 0;
}

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

using namespace std;

int main(){
    string S,T,S_dash,tmp;
    int pos,len_sd,len_t;
    bool flag;

    cin >> S_dash >> T;

    S = "";
    pos = 0;
    len_sd = S_dash.length();
    len_t = T.length();
    while(pos <= len_sd - len_t){
        flag = true;
        for(int i = 0;i < len_t;i++){
            if(S_dash[pos+i] == '?') continue;
            if(S_dash[pos+i] != T[i]){
                flag = false;
                break;
            }
        }
        if(flag){
            tmp = S_dash;
            for(int i = 0;i < len_sd;i++){
                if(tmp[i] == '?') tmp[i] = 'a';
            }
            for(int i = 0;i < len_t;i++) tmp[pos + i] = T[i];

            if(S == ""){
                S = tmp;
            }else{
                if(strcmp(S.c_str(),tmp.c_str()) > 0){
                    S = tmp;
                }
            }
        }
        pos++;
    }
    
    if(S == ""){
        cout << "UNRESTORABLE" << endl;
    }else{
        cout << S << endl;
    }
}

Measured memory_bytes: 256
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll int h,w;
		cin>>h>>w;
		char arr[h+1][w+1];
		ll int dp[h+1][w+1];
		memset(dp,0,sizeof(dp));
		dp[1][1]=1;
		for(ll int i=1;i<=h;i++)
		{
			for(ll int j=1;j<=w;j++)
			{
				cin>>arr[i][j];
			}
		}
		for(ll int i=1;i<=h;i++)
		{
			for(ll int j=1;j<=w;j++)
			{
				if(dp[i][j]!=0) continue;
				if(arr[i][j]=='#') continue;
				dp[i][j]=((arr[i][j-1]=='.')*dp[i][j-1]+(arr[i-1][j]=='.')*dp[i-1][j])%hell;
			}
		}
		cout<<dp[h][w];
	}
	return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
int main(){

  char x;
  char y=10;
  for(int i=0; i<4; i++){
	cin >> x;
	if(x==y){
	  cout << "Bad" << endl;
	  break;
	}
	if(i == 3)cout << "Good" << endl;
	y = x;
  }
  

  return 0;
}



Measured memory_bytes: 256
s = input()

if 1 <= int(s[:2]) <= 12 and 1<= int(s[2:]) <= 12:
    print("AMBIGUOUS")
elif 1 <= int(s[:2]) <= 12:
    print("MMYY")
elif 1 <= int(s[2:]) <= 12:
    print("YYMM")
else:
    print("NA")



Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include<list>
#include<algorithm>
#define ll long long int
#define ld long double
#define pb push_back
#define FF first
#define SS second
#define rep(a,b,c) for(a=b;a<c;a++)
#define repr for(i=n-1;i>=0;i--)
#define PLL pair<ll, ll>
#define inf 100000001
#define mod 1000000007
#define LP lower_bound
#define UP upper_bound
#define MP make_pair
#define rep1 for(i=1;i<=n;i++)
#define VLL vector<ll>
#define ef else if
#define all(x) (x).begin(), (x).end()
#define SORT(A) sort(A.begin(), A.end());
#define REVERSE(A) reverse(A.begin(), A.end());
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define UMP unordered_map
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll myXOR(unsigned long long int x, unsigned long long int y)
{
    return (x|y)&(~x|~y);
}
ll powerLL(ll x, ll n) 
{ 
    ll result = 1; 
    while (n) { 
        if (n & 1) 
            result = result * x % mod; 
        n = n / 2; 
        x = x * x % mod; 
    }
    return result; 
}
int main()
{
    fastio
    ll a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r, t,u,w,x,y,z;
    string str, ss, str1;
    /*
    **  author : mahiman12
    **  created : 2020-05-03 17:35 
    */
    cin>>n>>k;
    map<ll,ll>mp;
    rep(i,0,k)
    {
        cin>>d;
        rep(j,0,d)
        {
            cin>>a;
            mp[a]++;
        }
    }
    ll res=0;
    rep(i,1,n+1)
    {
        if(mp[i]==0)
            res++;
    }
    cout<<res;
}

Measured memory_bytes: 3668
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    vvl dp(n+10, vl(3));  // dp[i][j] : i文字目までで最後の分割の文字数がjのときの分割個数の最大値
    dp[1][1] = 1;
    exrep(i, 1, n) {  // i文字目まで分割したとする
        exrep(j, 1, 2) {  // 最後の分割はj文字とする
            exrep(k, 1, 2) {  // 次の分割はk文字にする
                bool ok = true;  // 次の分割が可能ならtrue
                if(j == k) {
                    if(j == 1) {
                        if(s[i-1] == s[i]) {
                            ok = false;
                        }
                    }
                    else if(j == 2) {
                        if(2 <= i && i < n-1 && s[i-2] == s[i] && s[i-1] == s[i+1]) {
                            ok = false;
                        }
                    }
                }
                if(ok) {
                    chmax(dp[i+k][k], dp[i][j] + 1);        
                }
            }
        }
    }

    out(max(dp[n][1], dp[n][2]));
    re0;
}

Measured memory_bytes: 14404
#include <iostream>
#include <string>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  string t;
  for (char c : s) {
    t += 'A' + (c - 'A' + n) % 26;
  }
  cout << t << endl;

  return 0;
}


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

int main() {
    int n, k;
    cin >> n >> k;
    
    long a = 1;
    while (a < k && n > 0) {
        a *= 2;
        n -= 1;
    }
    for (int i = 0; i < n; i++) {
        a += k;
    }
    cout << a << endl;
}


Measured memory_bytes: 256
s = [int(input()) for i in range(5)]
c =10
n = 0
for i in range(5):
    t =s[i] % 10
    if t != 0 and c > t:
        c = t
    
    if t == 0:
        n += s[i]
    else:
        n += 10 *((s[i]//10)+1)

print(n - (10 - c))

Measured memory_bytes: 3060
from collections import Counter
from itertools import combinations as comb

N = int(input())
d = Counter()
for _ in range(N):
    s = input()
    d[s[0]] += 1

ans = 0
for i, j, k in comb(["M","A","R","C","H"], 3):
    ans += d[i]*d[j]*d[k]
print(ans)


Measured memory_bytes: 9404
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int n,m;
int rx,ry;
int px,py;
int pic[101][101];
int pic2[101][101];
int p[101][101];

bool check(int x,int y){
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(p[j][i]!=-1 && p[j][i]!=pic[x+j][y+i])return false;
		}
	}
	return true;
}

void pc(){
	for(int j=0;j<m;j++){
		if(p[j][0]!=-1){
			px=j;
			return;
		}
	}
}

void dfs(){
	for(int i=0;i<=n-m;i++){
		for(int j=0;j<=n-m;j++){
			if(check(j,i) && (i<ry || i==ry && j+px<rx)){
				rx=j+px;
				ry=i;
				break;
			}
		}
	}
}

void turn(){
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++)pic2[m-1-i][j]=p[j][i];
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			p[j][i]=pic2[j][i];
			//printf("%d ",pic[j][i]);
		}
		//printf("\n");
	}
}

int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		memset(pic,0,sizeof(pic));
		memset(pic2,0,sizeof(pic2));
		memset(p,0,sizeof(p));
		if(n==0 && m==0)break;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)scanf("%d",&pic[j][i]);
		}
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++)scanf("%d",&p[j][i]);
		}
		rx=n,ry=n;
		for(int i=0;i<=4;i++){
			pc();
			dfs();
			turn();
		}
		if(rx==n && ry==n)printf("NA\n");
		else printf("%d %d\n",rx+1,ry+1);
	}
    return 0;
}

Measured memory_bytes: 1324
import java.util.Scanner;

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

    int n = sc.nextInt();
    int k = sc.nextInt();

    int result = 0;
    for (int i = 0; i < n; i++) {
      int h = sc.nextInt();
      if (h >= k) {
        result++;
      }
    }
    System.out.println(result);
  }
}


Measured memory_bytes: 47712
#include <iostream>
#include <cstdio>
#include <cstdlib>


int main(void) {
  int N;
  // w : left
  // e : right
  std::string s;
  int *cnt;
  int lw=0, re;
  int w=0, e=0;
  int res;
  std::cin >> N;
  std::cin >> s;

  for(int i=0;i < N;i++) {
    if (s[i] == 'E') e++;
  }
  re = e;
  res = re;
  cnt = (int *) calloc(N, sizeof(int));
  for (int i=0;i < N;i++) {
    if (s[i] == 'E') {
      // res = (re+lw > res) ? res : re+lw;
      if (re > 0) re--;
    } else {
      // res = (re+lw > res) ? res : re+lw;
      lw++;
    }
    res = (re+lw > res) ? res : re+lw;
  }
  std::cout << res << std::endl;
  return 0;
}


Measured memory_bytes: 900
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	ll H, W, ans = mod, S;
	ll s1, s2, s3, row;
	cin >> H >> W;
	if (H % 3 == 0 || W % 3 == 0) {
		cout << 0 << endl;
	}
	else {
		//縦に割る
		row = (H + 1) / 3;
		s1 = row * W;
		s2 = (H - row) * (W / 2);
		s3 = (H - row) * (W - W / 2);
		S = max({ s1,s2,s3 }) - min({ s1,s2,s3 });
		ans = min(ans, S);
		//cout << s1 << " " << s2 << " " << s3 << " " << S << endl;

		//横に割る
		row = (W + 1) / 3;
		s1 = row * H;
		s2 = (W - row) * (H / 2);
		s3 = (W - row) * (H - H / 2);
		S = max({ s1,s2,s3 }) - min({ s1,s2,s3 });
		ans = min(ans, S);
		//cout << s1 << " " << s2 << " " << s3 << " " << S << endl;

		//縦に3つに割る
		row = (H + 1) / 3;
		s1 = row * W;
		s2 = ((H - row)/2) * W;
		s3 = ((H - row) - ((H - row) / 2)) * W;
		S = max({ s1,s2,s3 }) - min({ s1,s2,s3 });
		ans = min(S, ans);

		//横に3つに割る
		row = (W + 1) / 3;
		s1 = row * H;
		s2 = ((W - row) / 2) * H;
		s3 = ((W - row) - ((W - row) / 2)) * H;
		S = max({ s1,s2,s3 }) - min({ s1,s2,s3 });
		ans = min(S, ans);

		cout << ans << endl;
	}
}



Measured memory_bytes: 256
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long int
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
const int inf = 0x3f3f3f3f;
char s[5];
int main()
{
	while (cin >> s)
	{
		int res = 0;
		for (int i = 0; i < 4; i++)
		{
			if (s[i] == '+') res++;
			else res--;
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#define ll long long

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

ll gcd(ll a, ll b){
	ll r, temp;

	if(b>a){
		temp = a;
		a = b;
		b = temp;
	}

	r = a % b;

	if(r==0)return b;

	return gcd(b, r);
}

int main(void){
	ll n, *a;
	ll i, j, k, ans, replay=0;

	scanf("%lld", &n);

	a = (ll *)malloc(n*sizeof(ll));

	for(i=0; i<n; i++){
		scanf("%lld", &a[i]);
	}

	ans = gcd(a[0], a[1]);
	
	for(j=2; j<n; j++){
		ans = gcd(ans, a[j]);
	}

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

Measured memory_bytes: 896
/*
      author : Nishikawa
      created: 06.08.2020 15:54:35
*/

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


int main(){
    int N;
    cin >> N;
    vector<int> a(N+1);
    vector<int> vec(100001,0);
    for(int i=1; i<=N; i++) cin >> a[i];
    for(int i=1; i<=N; i++){
        vec[a[i]]++;
    }
    int Q; 
    cin >> Q;
    vector<int> b(Q+1),c(Q+1);
    for(int i=1; i<=Q; i++) cin >> b[i] >> c[i];

    //for(int i=1; i<=Q; i++) cout << b[i] << " and " << c[i] << endl;
    //vector<ll> s(Q+1,0),t(Q+1,0);
    ll s=0;
    for(int i=1; i<=N; i++){
        s+=a[i];
    }

    for(int i=1; i<=Q; i++){
        if(vec[b[i]]!=0){
            s=s+(c[i]-b[i])*vec[b[i]];
            vec[c[i]]+=vec[b[i]];
            vec[b[i]]=0;
        }
        cout << s << endl;
    }

    return 0;
}

Measured memory_bytes: 4776
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
//typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);
void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


struct Node
{
	int key;
	Node *next, *prev;
};

Node *nil;

Node* listSearch(int key)
{
	Node *cur = nil->next;
	while (cur != nil && cur->key != key)
	{
		cur = cur->next;
	}
	return cur;
}

void init()
{
	nil = (Node *)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}

void printList()
{
	Node *cur = nil->next;
	int isf = 0;
	while (1)
	{
		if (cur == nil) break;
		if (isf++ > 0) printf(" ");
		printf("%d", cur->key);
		cur = cur->next;
	}
	printf("\n");
}

void deleteNode(Node *t)
{
	if (t == nil) return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}

void deleteFirst()
{
	deleteNode(nil->next);
}

void deleteLast()
{
	deleteNode(nil->prev);
}

void deleteKey(int key)
{
	deleteNode(listSearch(key));
}

void insert(int key)
{
	Node *x = (Node *)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}


int main()
{
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0;
	int nd = 0;
	scanf("%d", &n);
	init();
	for (i=0; i<n; i++)
	{
		scanf("%s%d", com, &key);
		if (com[0] == 'i')
		{
			insert(key);
			np++;
			size++;
		} else if (com[0] == 'd') {
			if (strlen(com) > 6)
			{
				if (com[6] == 'F') deleteFirst();
				else if (com[6] == 'L') deleteLast();
			} else {
				deleteKey(key);
				nd++;
			}
			size--;
		}
	}
	
	printList();
	
	return 0;
}


void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}


double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

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

int main(){
    int N;
    cin >> N;
    // even
    if (N % 2 == 0) {
        cout << N*(N/2-1) << endl;
        for(int i = 1; i < N; i++)
        {
            for(int j = i + 1; j < N + 1; j++)
            {
                if (i != N + 1 - j) {
                    cout << i << " " << j << endl;
                }
            }
        }
    }
    // odd
    else {
        cout << N-1+2*(N-1-N/2)*(N/2-1) << endl;
        for(int i = 1; i < N; i++)
        {
            for(int j = i + 1; j < N + 1; j++)
            {
                if (i != N - j) {
                    cout << i << " " << j << endl;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
fn qb() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let nt : Vec<&str> = input.split_whitespace().collect();
    let n : i32 = nt[0].parse().unwrap();
    let t : i32 = nt[1].parse().unwrap();

    let mut ans : i32 = 1001;

    for i in 0..n {
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let nt : Vec<&str> = input.split_whitespace().collect();
        let ni : i32 = nt[0].parse().unwrap();
        let ti : i32 = nt[1].parse().unwrap();
        if ti <= t && ni < ans {
            ans = ni;
        }
    }

    if ans == 1001 {
        println!("{}", "TLE");
    }
    else {
        println!("{}", ans);
    }
}

fn main() {
    qb();
}


Measured memory_bytes: 4352
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if (n == 0) {
			System.out.println(0);
			return;
		}
		
		StringBuilder sb = new StringBuilder();
		boolean isPlus = true;
		while (n != 0) {
			if (n % 2 != 0) {
				if (isPlus) {
					n -= 1;
				} else {
					n += 1;
				}
				sb.append(1);
			} else {
				sb.append(0);
			}
			n /= 2;
			isPlus = !isPlus;
		}
		System.out.println(sb.reverse());
	}
}


Measured memory_bytes: 23636
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 1000000007
using namespace std;
int fpow(int a,int b)
{
	int ans=1,t=a;
	while(b)
	{
		if(b&1)ans=(long long)ans*t%Mod;
		t=(long long)t*t%Mod;
		b>>=1;
	}
	return ans;
}
int lst[410];
int a[25010];
int f[25010][410],g[25010][410];
int F[25010],G[25010];
int main()
{
	int n,k,m;
	scanf("%d %d %d",&n,&k,&m);
	int all=(n-m+1);
	for(int i=1;i<=n-m;i++)
		all=(long long)all*k%Mod;
	//check a
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	for(int i=1;i<=k;i++)lst[i]=0;
	int l=0,r=m+1;
	for(int i=1;i<=m;i++)
	{
		l=max(l,lst[a[i]]+1);
		lst[a[i]]=i;
		if(i-l+1>=k){
			printf("%d\n",all);
			return 0;
		}
	}
	for(int i=1;i<=k;i++)lst[i]=m+1;
	for(int i=m;i>=1;i--)
	{
		r=min(r,lst[a[i]]-1);
		lst[a[i]]=i;
	}
	if(l==1){
		int val=1;
		for(int i=1;i<=m;i++)
			val=(long long)val*(k-i+1)%Mod;
		val=fpow(val,Mod-2);
		f[1][1]=k;
		if(m==1)g[1][1]=1;
		for(int i=2;i<=n;i++)
		{
			int sumf=0,sumg=0;
			//calc f&g
			for(int j=k-1;j>=1;j--)
			{
				sumf=(sumf+f[i-1][j])%Mod;
				sumg=(sumg+g[i-1][j])%Mod;
				f[i][j]=(sumf+(long long)f[i-1][j-1]*(k-j+1))%Mod;
				g[i][j]=(sumg+(long long)g[i-1][j-1]*(k-j+1))%Mod;
			}
			//f->g
			for(int j=m;j<k;j++)
				g[i][j]=(g[i][j]+(long long)f[i][j]*val)%Mod;
		}
		for(int i=1;i<k;i++)
			all=(all-g[n][i]+Mod)%Mod;
		printf("%d\n",all);
	}
	else{
		f[0][m-l+1]=F[0]=1;
		g[0][r]=G[0]=1;
		for(int i=1;i<=n-m;i++)
		{
			int sumf=0,sumg=0;
			//calc f&g
			for(int j=k-1;j>=1;j--)
			{
				sumf=(sumf+f[i-1][j])%Mod;
				sumg=(sumg+g[i-1][j])%Mod;
				f[i][j]=(sumf+(long long)f[i-1][j-1]*(k-j+1))%Mod;
				g[i][j]=(sumg+(long long)g[i-1][j-1]*(k-j+1))%Mod;
				F[i]=(F[i]+f[i][j])%Mod;
				G[i]=(G[i]+g[i][j])%Mod;
			}
		}
		for(int i=0;i<=n-m;i++)
			all=(all-(long long)F[i]*G[n-m-i]%Mod+Mod)%Mod;
		printf("%d\n",all);
	}
	return 0;
}

Measured memory_bytes: 80512
#include <stdio.h>
using namespace std;

int main() {
    int n, cnt1 = 0, cnt2 = 0, cnt3 = 0;
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        int x; scanf("%d", &x);
        if (x%4==0) ++cnt1;
        else if (x%2==0) ++cnt3;
        else ++cnt2;
    }
    printf("%s", cnt1>=cnt2 || (cnt1==cnt2-1 && cnt3==0) ? "Yes" : "No");
}


Measured memory_bytes: 128
from collections import deque

n = int(input())
a = [list(map(lambda x:int(x)-1,input().split())) + [-1] for _ in range(n)]

l,day = [0]*n,[0]*n

que = deque([i for i in range(n)])

while que:
    u = que.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = max(day[u],day[v]) + 1
        day[v] = day[u]
        l[u] += 1
        l[v] += 1
        que.append(u)
        que.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))

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

using namespace std;

const int max_n = 1e5 + 5;

int sumy[max_n], tab[max_n], n, drzewo[6 * max_n], rozmiar;

void aktualizuj(int x){
    drzewo[x]++;
    if (x > 1)
        aktualizuj(x / 2);
}

int znajdz(int a, int b, int p, int k, int x){
    if (p > b || k < a)
        return 0;
    if (a <= p && b >= k)
        return drzewo[x];
    int lewa = znajdz(a, b, p, (p + k) / 2, x * 2);
    int prawa = znajdz(a, b, (p + k) / 2 + 1, k, x * 2 + 1);
    return lewa + prawa;
}

bool sprawdz(int x){
    for (int i = 1; i < rozmiar * 2; i++)
        drzewo[i] = 0;
    long long wynik = 0;
    aktualizuj(rozmiar + n + 0);
    for (int i = 1; i <= n; i++){
        if (tab[i] >= x)
            sumy[i] = sumy[i - 1] + 1;
        else
            sumy[i] = sumy[i - 1] - 1;
        wynik += (long long)znajdz(0, n +  sumy[i], 0, rozmiar - 1, 1);
        aktualizuj(rozmiar + n + sumy[i]);
        //if (x == 1e9 / 2)
        //    cout << sumy[i] << "\n";
    }
    long long xd = (long long)n * (long long)(n - 1)/ 2 + (long long)n;
    //i//f (x == 1e9 / 2)
    //    cout << wynik << " " << xd << "\n";
    if (wynik >= (long long)xd / 2 + (long long)xd % 2)
        return true;
    return false;
}

int bin_search(){
    int poczatek = 0, srodek, koniec = 1e9, wynik = tab[0];
    while (poczatek <= koniec){
        srodek = (poczatek + koniec) / 2;
        if (sprawdz(srodek)){
            poczatek = srodek + 1;
            wynik = srodek;
        }
        else
            koniec = srodek - 1;
    }
    return wynik;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> tab[i];
    rozmiar = 1 << (__lg(2 * n) + 1);
    cout << bin_search() << "\n";
    return 0;
}

Measured memory_bytes: 6472
import java.util.*;

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

        String C1 = sc.next();
        String C2 = sc.next();

        if(C1.charAt(0)==C2.charAt(2) && C1.charAt(1)==C2.charAt(1) && C1.charAt(2)==C2.charAt(0)){
            System.out.println("YES");
        }
        else{
            System.out.println("NO");
        }
    }
}

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

typedef long long LL;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    int x,y;
    cin>>n;
    int maxx=0;
    int maxy=0;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if(x>maxx) maxx=x,maxy=y;
    }
    cout<<maxx+maxy<<endl;
}


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

int main(){
    string s;
    int n;
    cin >>s>>n;
    for(int i=0;i<n;i++){
      string S;
      cin >> S;
        if(S=="print"){
            int a,b;
            cin >>a>>b;
            cout<<s.substr(a,b-a+1)<<endl;
        }else if(S=="replace"){
            int a,b;
            string r;
            cin >>a>>b>>r;
            /*s.replace(a, b-a+1, r)*/
          	for(int i=a;i<=b;i++){
                s[i] = r[i-a];
            }
        }else{
            int a,b;
            cin >>a>>b;
            /*reverse( str.begin() + a, str.begin() + b + 1);*/
          	string t = s;
            for(int i=a;i<=b;i++){
                s[i] = t[a+b-i];
                s[a+b-i] = t[i];
            }
        }
    }
}




Measured memory_bytes: 3172
import numpy as np
import math
x = int(input())
ys = []
i = 1
while i**2 < x:
    if x%i == 0:
        ys.append(i)
        ys.append(x//i)
    i += 1
if i**2 == x:
    ys.append(i)

f = False

for j in ys:
    for i in range(10**3):
        if i**5-(i-j)**5 == x:
            print(i,i-j)
            break
        elif i**5-(i-j)**5 > x and i-j > 0:
            break
    if f:
        break

Measured memory_bytes: 27120
import java.util.Scanner;

/**
 * お遊び
 *
 * @author s-sugimoto
 */
public class Main {

	/**
	 * 隠蔽
	 */
	private Main() {
	}

	/**
	 * main
	 *
	 * @param args 起動引数
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Integer num1 = scanner.nextInt();

		if (num1.toString().contains("9")) {
			System.out.println("Yes");

		} else {
			System.out.println("No");
		}
	}
}

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

#define pb push_back
#define fi first
#define se second
#define ll long long
#define pq priority_queue
#define mp make_pair
#define pii pair<int,int>
#define mod 998244353

const int N=1e5+11;

int lowbit(int x) {return x&(-x);}

int n,K;
int h[N],f[N];

int main(){
	scanf("%d%d",&n,&K);
	for (int i=0;i<n;i++) scanf("%d",&h[i]),f[i]=2e9;
	f[0]=0;
	for (int i=1;i<n;i++) 
		for (int j=1;j<=K&&i-j>=0;j++) 
			f[i]=min(f[i],f[i-j]+abs(h[i]-h[i-j]));
	printf("%d\n",f[n-1]);
	return 0;
}


Measured memory_bytes: 1024
package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

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

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)

var T string

func main() {
	sc.Split(bufio.ScanWords)
	fmt.Scanf("%s", &T)
	ans := strings.Replace(T, "?", "D", -1)
	fmt.Println(ans)
}


Measured memory_bytes: 3892
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []


    while True:
        h,w,c = LI()
        if h == 0:
            break
        a = [LI() for _ in range(h)]
        mc = max(map(max,a))
        d = collections.defaultdict(int)
        for i in range(h):
            for j in range(w):
                d[(i,j)] = a[i][j]

        def f(c,s):
            ff = True
            ts = s
            while ff:
                r = set()
                ff = False
                for i,j in ts:
                    for di,dj in dd:
                        ni = i + di
                        nj = j + dj
                        if d[(ni,nj)] == c and not (ni,nj) in ts:
                            ff = True
                            r.add((ni,nj))
                ts = ts | r
            return ts

        r = 0
        s = f(a[0][0], set([(0,0)]))
        for ca in itertools.product(range(1,mc+1), repeat=4):
            ts = s
            for nc in ca:
                ts = f(nc, ts)
            ts = f(c, ts)
            if r < len(ts):
                r = len(ts)
        rr.append(r)

    return '\n'.join(map(str, rr))



print(main())



Measured memory_bytes: 9112
import java.io.*;
import java.lang.*;
import java.util.*;

class Main
{
	public static void main(String args[])throws IOException
	{
		FastReader scn = new FastReader();
		long N = scn.nextLong();
		long M = 1000000007L;

		long a = getPowerModulo(10, N, M);
		long b = getPowerModulo(8, N, M);
		long c = getPowerModulo(9, N, M);

		long ans = (a + b - 2*c)%M;
		if(ans < 0)
			ans = ans + M;

		System.out.println(ans);
	}

	public static long getPowerModulo(long a, long p, long m)
    {   
        if(p==0)
            return 1;
 
        long temp = getPowerModulo(a, p/2, m);
        temp = (temp * temp)%m;
        if(p%2 == 0)
            return temp;
        else
            return (a * temp)%m;
 
    }
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                {
                    st = new StringTokenizer(br.readLine()); 
                }
                catch (IOException  e) 
                {
                    e.printStackTrace(); 
                }
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            {
                str = br.readLine(); 
            }
            catch (IOException e) 
            {
                e.printStackTrace(); 
            }
            return str; 
        } 
    }
}

Measured memory_bytes: 25392
package main

import "fmt"

func main() {
	var A, B int
	fmt.Scan(&A, &B)
	fmt.Println(lcm(A, B))
}
func lcm(a, b int) int {
	return a * b / gcd(a, b)
	// return a / gcd(a, b) * b   桁あふれ対策
}
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}


Measured memory_bytes: 512
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <iomanip>

using namespace std;

uint64_t N, A, B;
map<uint64_t, uint64_t> Vs;

double average() {

  uint64_t s = 0;
  uint64_t count = 0;

  for (auto it = Vs.crbegin(); count < A; ++it) {
    if (count + it->second < A) {
      s += it->first * it->second;
      count += it->second;
    } else {
      s += it->first * (A - count);
      count = A;
    }
  }

  return static_cast<double>(s) / A;
}

uint64_t gcd(uint64_t a, uint64_t b) {
  if (a == 0)
    return b;

  return gcd(b % a, a);
}

uint64_t combination(uint64_t a, uint64_t b) {

  uint64_t n = 1;
  uint64_t d = 1;

  for (uint64_t i = 1; i <= b; ++i) {
    uint64_t n_ = a - b + i;
    uint64_t d_ = i;

    auto g0 = gcd(n_, d_);
    n_ /= g0;
    d_ /= g0;

    auto g1 = gcd(n, d_);
    auto g2 = gcd(d, n_);

    n = (n / g1) * (n_ / g2);
    d = (d / g2) * (d_ / g1);
  }

  assert(d == 1);

  return n;
}

uint64_t count() {

  const auto& back = *Vs.crbegin();
  if (A <= back.second) {
    uint64_t ret = 0;

    for (uint64_t k = A; k <= min(back.second, B); ++k)
      ret += combination(back.second, k);

    return ret;
  }

  uint64_t counted = 0;
  for (auto it = Vs.crbegin(); it != Vs.crend(); ++it) {
    if (counted + it->second < A) {
      counted += it->second;
    } else {
      return combination(it->second, A - counted);
    }
  }
}

int main() {

  cin >> N >> A >> B;

  for (uint64_t i = 0; i < N; ++i) {
    uint64_t n;
    cin >> n;
    Vs[n] += 1;
  }

  cout << fixed << setprecision(7) << average() << endl;
  cout << count() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1000000000;

int n, m;
char chairs[100];
int dist[100];
int p;

bool notA(int i){
   if(i == n-1){
      return chairs[i-1] != 'A';
   }else if(i == 0){
      return chairs[i+1] != 'A';
   }else{
      return chairs[i-1] != 'A' && chairs[i+1] != 'A';
   }
}

int checkC(int idx){
   if(idx == n-1){
      if(chairs[idx-1] == '#') return -1;
      return 0;
   }else if(idx == 0){
      if(chairs[idx+1] == '#') return 1;
      return 0;
   }else{
      if(chairs[idx+1] == '#') return 1;
      if(chairs[idx-1] == '#') return -1;
      return 0;
   }
}

void setD(int idx){
   for(int i=0;idx-i>=0;i++){
      dist[idx-i] = min(dist[idx-i], i);
   }
   for(int i=0;idx+i<n;i++){
      dist[idx+i] = min(dist[idx+i], i);
   }
}

void setChar(char c){
   if(n == 1){
      chairs[0] = c;
      return;
   }
   switch(c){
      case 'A':
         for(int i=0;i<n;i++){
            if(chairs[i] != '#') continue;
            chairs[i] = 'A';
            setD(i);
            return;
         }
         break;
      case 'B':
         for(int i=n-1;i>=0;i--){
            if(chairs[i] != '#') continue;
            if(notA(i)){
               chairs[i] = 'B';
               setD(i);
               return;
            }
         }
         for(int i=0;i<n;i++){
            if(chairs[i] == '#') chairs[i] = 'B';
            setD(i);
            return;
         }
         break;
      case 'C':
         if(p == 0){
            if(n&1){
               chairs[(n+1)/2-1] = 'C';
               setD((n+1)/2-1);
            }else{
               chairs[n/2] = 'C';
               setD(n/2);
            }
            return;
         }
         for(int i=0;i<n;i++){
            if(chairs[i] == '#') continue;
            int tmp = checkC(i);
            if(tmp == 1){
               chairs[i+1] = 'C';
               setD(i+1);
               return;
            }else if(tmp == -1){
               chairs[i-1] = 'C';
               setD(i-1);
               return;
            }
         }
         break;
      case 'D':
         int idx = 0;
         int valm = -1;
         for(int i=0;i<n;i++){
            if(chairs[i] != '#') continue;
            if(dist[i] > valm){
               valm = dist[i];
               idx = i;
            }
         }
         chairs[idx] = 'D';
         setD(idx);
         break;
   }
}

main(){
   while(cin >> n >> m && (n || m)){
      fill(dist, dist+n, INF);
      fill(chairs, chairs+n, '#');
      char c;
      for(p=0;p<m;p++){
         cin >> c;
         setChar(c);
      }
      for(int i=0;i<n;i++){
         cout << chairs[i];
      }
      cout << endl;
   }
   return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm> // sort
using namespace std;

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

    sort(d.begin(), d.end());

    if(d[n/2]==d[(n/2)-1]) cout << 0;
    else cout << d[n/2]-d[(n/2)-1];
    return 0;
}

Measured memory_bytes: 768
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int  m = sc.nextInt();
        int a = (int) Math.pow(2, m);
        int b = 1900 * m * a;
        int c = (n - m) * a * 100;
        System.out.println(b + c);
    }
}


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


using namespace std;

string s;
int q, type , f, ord(1);
string ch;
string bg , ed;
void reverse(){
	ord *= -1;
}
void addbegin(){
	if(ord == 1){
		bg.append(ch);
	}else{
		ed.append(ch);
	}
}
void addend(){
	if(ord == 1){
		ed.append(ch);
	}else{
		bg.append(ch);
	}
}


int main(){
	cin >> s;
	cin >> q;
	for(int i = 1; i <= q ; i++){
		cin >> type;
		if(type == 1){
			reverse();
		}
		else{
			cin >> f;
			cin >> ch;
			if(f == 1){
				addbegin();
			}else{
				addend();
			}
		}
	}
	if(ord == 1){
		reverse(bg.begin(),bg.end());	
		cout << bg << s << ed << '\n';
	}else{
		reverse(s.begin(),s.end());
		reverse(ed.begin(),ed.end());
		cout << ed << s << bg << '\n';
	}
}


Measured memory_bytes: 1088
#include<cstdio>
#include<algorithm>

using namespace std;

bool cmp(int a, int b){
  return a>b;
}

int n,m,a[25],mem[25][50005];

int solve(int i,int v){
  if(v==0)
    return 0;
  if(a[i]==2 || a[i]==1 || i==m-2)
    return v/a[i]+v%a[i];
  if(v%a[i]==0)
    return v/a[i];
  if(mem[i][v]!=0)
    return mem[i][v];
  int mn = solve(i+1,v);
  int vv = v,c=0;
  while(vv>=a[i]){
    vv-=a[i];
    c++;
    mn = min(mn,c+solve(i+1,vv));
  }
    
  return mem[i][v]=mn;
  
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i = 0; i< m; i++){
    scanf("%d",&a[i]);
  }
  sort(a,a+m,cmp);
  printf("%d\n",solve(0,n));
}



Measured memory_bytes: 5640
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>


typedef long long ll;
typedef long double ld;

using namespace std;
const ll MOD = 1e9 + 7;
const ll MAXQ = 5000000;
ll dp[2100][2100];

int n, k;

ll fc[MAXQ];
ll bfc[MAXQ];

ll pw(ll a, ll b) {
	ll ans = 1;
	while (b) {
		while (!(b & 1))
			b>>= 1, a = (a *a) %MOD;
		--b;
		ans = (ans * a) % MOD;
	}
	return ans;
}

void init() {
	fc[0] = 1;
	for (int i = 1; i < MAXQ; ++i)
		fc[i] = (fc[i - 1] * i) % MOD;
	for (int i = 0; i < MAXQ; ++i)
		bfc[i] = pw(fc[i], MOD - 2);
}

ll cnk(ll n, ll k) {
	if (k > n)
		return 0;
	ll ans = fc[n] * bfc[k];
	ans %= MOD;
	return (ans * bfc[n - k]) % MOD;
}

int main() {
	cin >> n >> k;
	if (k == 1) {
		cout << 1 << "\n";
		return 0;
	}
	--k;
	init();
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j)
			dp[i][j] = (dp[i - 1][j] * cnk(i * k - 1 + j, k - 1)) % MOD;
		for (int j = 1; j <= i; ++j)
			dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
	}
	ll ans = dp[n][n] * fc[n];
	ans %= MOD;
	cout << ans << "\n";
	return 0;
}




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

using namespace std;

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

      
    

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] s = sc.nextLine().split(" ");
    int N = Integer.parseInt(s[0]);
    int K = Integer.parseInt(s[1]);
    String[] str = sc.nextLine().split(" ");
    int[] ans = new int[N];
    ans[0] = 0;
    for (int i = 1; i < N; i++) {
      ans[i] = Integer.MAX_VALUE;
    }

    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j <= i + K && j < N; j++) {
        ans[j] =
            Math.min(
                ans[j], Math.abs(Integer.parseInt(str[j]) - Integer.parseInt(str[i])) + ans[i]);
      }
    }
    System.out.println(ans[N - 1]);
  }
}


Measured memory_bytes: 48844
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    t = [int(i) for i in ipt().split()]
    v = [int(i) for i in ipt().split()]
    tsm = sum(t)
    st = [0]
    for i in t:
        st.append(st[-1]+i)
    sp = [min(i/2,tsm-i/2) for i in range(tsm*2+1)]

    for i,ti in enumerate(t):
        vi = v[i]
        t0 = st[i]*2
        sf = False
        ff = False
        if sp[t0] > vi:
            sf = True
        if sp[t0+ti*2] > vi:
            ff = True
        for j in range(ti*2+1):
            if sp[t0+j] > vi:
                sp[t0+j] = vi
        if sf:
            for j in range(1,1000000):
                if sp[t0-j] > vi+j/2:
                    sp[t0-j] = vi+j/2
                else:
                    break
        t0 += ti*2
        if ff:
            for j in range(1,1000000):
                if sp[t0+j] > vi+j/2:
                    sp[t0+j] = vi+j/2
                else:
                    break
#        print(sp)

    print(sum(sp)/2)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 77220
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<cmath>
#define ll long long
#define MOD 1000000007
using namespace std;
inline ll read(){
	ll re=0,flag=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re*flag;
}
ll dp[2010][2010],p[2010],sum[2010][2010];
int main(){
	ll n=read(),k=read();ll i,j;
	p[0]=1;
	for(i=1;i<=n;i++) p[i]=p[i-1]*2%MOD;
	for(i=2;i<=n;i++) dp[1][i]=1,sum[1][i]=n-i+1; 
	for(i=2;i<k;i++){
		for(j=n-i+1;j>=2;j--){
			dp[i][j]=(dp[i-1][j]+sum[i-1][j+1])%MOD;
		}
		for(j=n-i+1;j>=2;j--) sum[i][j]=(sum[i][j+1]+dp[i][j])%MOD;
	}
	ll ans=0;
	for(i=2;i<=n-k+2;i++) ans+=dp[k-1][i],ans%=MOD;
	if(k==1) ans=1;
	if(k==n) printf("%lld\n",ans);
	else printf("%lld\n",ans*p[n-k-1]%MOD);
//	cout<<n<<' '<<k<<' '<<ans<<' '<<n-k-1<<' '<<p[n-k-1]<<'\n';
}


Measured memory_bytes: 62080
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define numrep(i,p,n) for(int i=p;i<=n;i++)
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)
#define ll int64_t
#define all(v) v.begin(), v.end()

const int MOD = 1000000007;

bool isprime(int x){
  if(x<2) return false;
  for(int i=2;i*i<=x;i++){
    if(x%i==0) return false;
  }
  return true;
}


int main() {

int N; cin >> N ;

int ans;

numrep(i,N,10000000){
  if(isprime(i)){
    ans=i; break;
  }
}

cout << ans << endl;

return 0;
}

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

int main(){
  int n,m;
  double a[500];
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>a[i],a[i]+=(i?a[i-1]:0);
  double dp[501][501];
  for(int i=0;i<501;i++)for(int j=0;j<500;j++)dp[i][j]=-1e15;
  dp[0][0]=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      for(int k=0;k<=i;k++){
	dp[j+1][i+1]=max(dp[j+1][i+1],dp[j][k]+(a[i]-(k?a[k-1]:0))/(i-k+1));
      }
  printf("%.8f\n",dp[m][n]);
  return 0;
}


Measured memory_bytes: 5252
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

ll gcd(ll a,ll b){
  if(b==0)return a;
  else return gcd(b,a%b);
}

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

ll div(ll x){
  ll cnt = 0;
  while(x%2==0){
    x/=2;
    cnt++;
  }

  return cnt;
}

int main(void){
  int i;
  ll n, m, cnt;
  ll min;
  vector<ll> a;

  cin >> n >> m;
  a.resize(n);

  for(i=0;i<n;i++){
    cin >> a[i];
  }

  min = a[0] / 2;
  cnt = div(a[0]);
  for(i=1;i<n;i++){
    if(cnt!=div(a[i])){
      cout << 0 << endl;
      return 0;
    }
    min = lcm(min,a[i]/2);
  }

  cout << (m/min+1)/2 << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

typedef long long ll;
ll n, m, ans, a ,s;
map<ll, ll> d;
int main()
{
	ll i;
	cin >> n >> m;
	d[0]++;
	for (i = 0; i <n; i++) {
		scanf ("%lld", &a);
		s += a;
		s %= m;
		ans += d[s];
		d[s]++;
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define mod 1000000007
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f(i,n) for(ll i=0;i<n;i++)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ms(v,n) memset((v),n,sizeof(v));
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define sll set<ll>
#define vll vector<ll>
#define vpll vector<pll>
#define maxi(a,b,c) max(a,max(b,c))
#define maxii(a,b,c,d) max(max(a,b),max(c,d))
#define mini(a,b,c) min(a,min(b,c))
#define md(a,b)  ((a%mod)*(b%mod)+mod)%mod 
#define ad(a,b)  (a%mod+b%mod+mod)%mod
#define nl endl
#define inf 1e9
#define cases ll t;cin>>t;while(t--)
#define BLOCK 500
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
 
using namespace std;



int32_t main()
{
    fast
    ll n;
    cin>>n;
    ll h[n];
    f(i,n)
    {
        cin>>h[i];
    }

    ll dp[n];
    f(i,n)
    {
        dp[i]=inf;
    }
    dp[0]=0;

    for(ll i=1;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),(i!=1?dp[i-2]+abs(h[i]-h[i-2]):INT_MAX));
    }

    cout<<dp[n-1];



       
    return 0;
    
}


Measured memory_bytes: 1792
l=[int(x) for x in list(input())]
if l[0]+l[1]+l[2]+l[3]==7: print('{}+{}+{}+{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]+l[1]+l[2]-l[3]==7: print('{}+{}+{}-{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]+l[1]-l[2]+l[3]==7: print('{}+{}-{}+{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]+l[1]-l[2]-l[3]==7: print('{}+{}-{}-{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]-l[1]+l[2]+l[3]==7: print('{}-{}+{}+{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]-l[1]+l[2]-l[3]==7: print('{}-{}+{}-{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]-l[1]-l[2]+l[3]==7: print('{}-{}-{}+{}=7'.format(l[0],l[1],l[2],l[3]))
elif l[0]-l[1]-l[2]-l[3]==7: print('{}-{}-{}-{}=7'.format(l[0],l[1],l[2],l[3]))


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main()
{
  while (true) {
  int x, y, s;
  cin >> x >> y >> s;

  if (x == 0 && y == 0) break;
  
  //double t = x * 0.01;
  //double t2 = y * 0.01;
  int max = 0;
 
  for (int i = 1; i < s; i++) {
    for (int j = 1; j < s; j++) {
      int a = i*(x*0.01);
      int b = j*(x*0.01);
      //if (a == 13 && b == 88)
      //cout << "a::" << a << endl << "b::" << b << endl;
      int temp = a + i + b + j; 
      if (temp == s) {
	//cout << i << " " << j << endl;
	int c = (i*(y*0.01));
	int d = (j*(y*0.01));
	int tmp = c+i+d+j;
	if (tmp > max)
	  max = tmp;
      }
    }
  }

  cout << max << endl;
  }
  return 0;
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 10;
const double INF = 1e18;
using namespace std;

int n, m, T, kase = 1;
ll k, p, x;
int a[30];

int main() {
    while(cin >> a[0] >> a[1] >> a[2]) {
        int cnt = 0;
        while(1) {
            sort(a, a + 3);
            if(a[2] - a[1] >= 2) { a[1] += 2; }
            else if(a[1] - a[0] >= 2) { a[0] += 2; }
            else if(a[2] - a[1] >= 1) { a[2] -= 1; }
            else if(a[1] - a[0] >= 1) { a[1] -= 1; }
            else break;
            cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

void solve(){
    int n,k;
    cin>>n>>k;
    set<char>s;
    char c;
    rep(i,k){
        cin>>c;
        s.emplace(c);
    }
    for(int i=n;;++i){
        bool flag=0;
        string t=to_string(i);
        rep(j,t.size()){
            if(s.count(t[j])){
                flag=1;
                break;
            }
        }
        if(!flag){
            cout<<t<<"\n";
            return;
        }
    }
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 256