akhauriyash/Code-Regression huggingface dataset:
def main():
    N = int(input())

    def prime_factorize(n):
        res = []
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append((i, ex))
        if n != 1:
            res.append((n, 1))
        return res

    def euler_totient_function(n):
        # オイラーのφ関数
        # 1からnのうち，nと互いに素な整数の個数
        pf = prime_factorize(n)
        res = n
        for p, _ in pf:
            res *= p-1
            res //= p
        return res

    print(euler_totient_function(N))


if __name__ == '__main__':
    main()



Measured memory_bytes: 5600
program abc042_a
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: k,i,n,t
    integer(int32),allocatable:: d(:)
    logical:: hate, hnum(0:9)


    read*, n,k
    allocate(d(k))
    read*, d(:)

    hnum(:) = .false.
    do i=1,k
        hnum(d(i)) = .true.
    end do

    do
        hate = .false.
        do i=0,int(log10(dble(n)))
            t = mod(n/(10**i),10)
            if (hnum(t)) hate=.true.
        end do
        if (hate) then
            n=n+1
        else
            print'(i0)', n
            stop
        end if
    end do
end program abc042_a

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>

int mas[3][3];
int cpy[3][3];

void input() {
  int i, j;
  for(i = 0; i < 3; i++)
    for(j = 0; j < 3; j++)
      scanf("%d", &mas[i][j]);
}

void output() {
  int i, j;
  for(i = 0; i < 3; i++) {
    for(j = 0; j < 3; j++) printf("%3d", mas[i][j]);
  }
}

int calc() {
  int i, sum = 0;
  for(i = 0; i < 9; i++) {
    int v = mas[i/3][i%3];
    if(v) {
      v--;
      sum += abs(i/3-v/3)+abs(i%3-v%3);
    }
  }
  return sum;
}

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

int dfs(int x, int y, int p, int dep, const int lim) {
  int i, h = calc(),a;
  if(h == 0) return dep;
  if(dep+h > lim) return -1;

  for(i = 0; i < 4; i++) {
    int nx = x+dx[i], ny = y+dy[i], res;
    if(~p && i == (p+2)%4) continue;
    if(!(0<=nx&&nx<3&&0<=ny&&ny<3)) continue;
    a = mas[y][x];
    mas[y][x] = mas[ny][nx];
    mas[ny][nx] = a;
    res = dfs(nx, ny, i, dep+1, lim);
    if(~res) return res;
    a = mas[y][x];
    mas[y][x] = mas[ny][nx];
    mas[ny][nx] = a;
  }

  return -1;
}

void get_empty(int *x, int *y) {
  int i, j;
  for(i = 0; i < 3; i++) {
    for(j = 0; j < 3; j++) {
      if(!mas[i][j]) {
    *x = j;
    *y = i;
    return;
      }
    }
  }
}

int solve() {
  int x, y, lim, ans,i,j;
  get_empty(&x, &y);
  for(lim = 0; lim < 50; lim++) {
  	for(i = 0; i < 3; i++)
  	    for(j = 0; j < 3; j++) cpy[i][j] = mas[i][j];
    if((ans = dfs(x, y, -1, 0, lim)) != -1) return ans;
    for(i = 0; i < 3; i++)
        for(j = 0; j < 3; j++) mas[i][j] = cpy[i][j];
  }
  return -1;
}

int main() {
  input();
  printf("%d\n", solve());
  return 0;
}



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

int main() {
  int n; cin >> n;
  int ans = 0;
  for (int i=1; i<=n; i++) {
    if (i < 10) ans++;
    if (100 <= i && i < 1000) ans++;
    if (10000 <= i && i < 100000) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }


int main() {
    map<string, int> mp;
    int n; scanf("%d", &n);
    string pre = "";
    rep(i, n) {
        string s; cin >> s;
        if (mp[s] || (i != 0 && pre.back() != s[0])) {
            puts("No"); return 0;
        }
        mp[s] = 1;
        pre = s;
    }
    puts("Yes");

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>

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

    std::vector<int> d(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> d[i];
    }
    
    const std::set<int> s(d.cbegin(), d.cend());
    const auto ret = s.size();

    std::cout << ret << std::endl;
}


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

bool isPrime(int n){
    for( int i = 2 ; i < int (sqrt(n)+1) ; i++)
        if( n % i == 0)
            return 0;
    return 1;
}
int main()
{
    int N,X;
    int index = 0;
    cin>> N;
    for(int i = 0; i < N ;i++){
        cin >> X ;
        if(isPrime(X))
            index++;
    }
    cout << index <<endl;
    return 0;
}



Measured memory_bytes: 3096
// AOJ 2335: 10-Year-Old Dynamic Programming
// 2017.11.27 bal4u@uu
// 2017.12.2

#include <stdio.h>

#define M 1000000007

int fact[2020001];

int egcd(int a, int b, int *x, int *y)
{
	int d;

	if (b == 0) { *x = 1; *y = 0; return a; }
	d = egcd(b, a % b, y, x);
	*y -= a / b * (*x);
	return d;
}

int inverse(int a)
{
    int x, y;
	egcd(a, M, &x, &y);
	if (x < 0) x += M;
	return x;
}

int comb(int n, int k)
{
//    if (n < 0 || k < 0 || n < k) return 0;
	if (k == 0) return 1;
    return (long long)fact[n] * inverse(((long long)fact[k]*fact[n-k]) % M) % M;
}

int main()
{
	int n, m, k, i, j, kk, ii, jj, r, c, ans;

	for (fact[0] = 1, i = 1; i < 2020001; i++) fact[i] = ((long long)fact[i-1]*i) % M;

	scanf("%d%d%d", &n, &m, &k);

    ans = 0; kk = n + m + (k << 1);
    for (j = k, i = 0; i <= k; i++, j--) {
        ii = n + (i << 1), jj = m + (j << 1);
        r = comb(ii, i) - comb(ii, i-1); if (r < 0) r += M;
        c = comb(jj, j) - comb(jj, j-1); if (c < 0) c += M;
        ans = (ans + ((long long)r*c) % M * (long long)comb(kk, ii)) % M;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 9716
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
#define init(c) memset(c,0,sizeof c)
#define S second
#define F first
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=20000005;
int n,k,x,t,a,b,m;
string s;
vi v;
 
void solve(){
	scanf("%d",&n);
	map<int,int>freq;
	for(int i =0;i<n;i++){
		scanf("%d",&x);
		v.push_back(x);
		freq[x]++;
	}
	int sq = 1e3+10;
	bool pairwise = true;
	bool vis[1000005];
	for(int i =0;i<=1e6;i++){
		vis[i]=false;
	}
	for(int i=2;i<=1e6;i++){
		int cnt=0;
		if(!vis[i]){
			for(int j=i;j<=1e6;j+=i){
				cnt+=freq[j];
				vis[j]=true;
			}

			if(cnt>1){
				pairwise=false;
				break;
			}
		}
	}
	if(!pairwise){
		int gd = v[0];
		for(int i =1;i<n;i++){
			gd = __gcd(v[i],gd);
		}
		if(gd==1){
			printf("setwise coprime");
		}else{
			printf("not coprime");
		}
	}else{
		printf("pairwise coprime");
	}
 
}
 
int main(){

	t=1;
	while(t--){
		solve();
	}
	
	return 0;
}

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

using namespace std;

int main(void) {
	long int N, r=0;
	int A[100002] = { 0 };

	cin >> N ;
	for (int i=1;i <= N;i++)
		cin >> A[i];

	for (int i=0;i <= N+1 ;i++) {
		r += abs(A[i]-A[i+1]);
	}
	for (int i = 1 ; i <= N;i++) {
		int sa = abs(A[i -1] - A[i + 1]) - abs(A[i-1] - A[i]) - abs(A[i] - A[i+1]);
		cout << r + sa<<endl;
	}
	return 0;
}

Measured memory_bytes: 1664
row=[]
r,c=gets.split.map(&:to_i)
a = r.times.map { gets.split.map(&:to_i) }
total = a.sum{|x| x.sum}
a.transpose.each { |u| row<<u.sum }
row << total
a.each { |u| u<<u.sum }

a.each { |b| puts b.join(' ') }
puts row.join(' ')



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

int n, m, x, y;
bool flag = 1;
int f[10];

int main() {
	memset(f, -1, sizeof(f));
	cin >> n >> m;
	if (n == 1 && !m) {
		puts("0");
		return 0;
	}
	while (m--) {
		cin >> x >> y;
		if ((x == 1 && !y && n > 1) || (f[x] != -1 && f[x] != y)) flag = 0;
		f[x] = y;
	}
	if (!flag) {
		puts("-1");
		return 0;
	} 
	if (n == 1 && !f[1]) {
		puts("0");
		return 0;
	} 
	if (f[1] == -1) putchar('1');
	else putchar(f[1] ^ 48);
	for (int i = 2; i <= n; i++) {
		if (f[i] == -1) putchar('0');
		else putchar(f[i] ^ 48);
	}
	putchar('\n');
	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int i, n;
	int money;
	long long int moneySum=0;
	scanf("%d", &n);
	for(i=0; i<n; i++)
	{
		scanf("%d", &money);
		moneySum += money;
	}
	printf("%lld\n", moneySum/n);
	return 0;
}

Measured memory_bytes: 592
///Bismillahir Rahmanair Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    int a,b;
    cin>>a>>b;
    if(a<=0 && b>=0)
    {
        cout<<"Zero"<<endl;
        return 0;
    }
    if(a>0 && b>0)
    {
        cout<<"Positive"<<endl;
        return 0;
    }
    if(a<0 && b<0)
    {
        int gap=abs(a)-abs(b)+1;
        if(gap%2==0)
        {
            cout<<"Positive"<<endl;
            return 0;
        }
        cout<<"Negative"<<endl;
        return 0;
    }
















    return 0;

}













Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define forn(i, a, n) for(int i = a; i < n; ++i)
#define pb push_back
#define mp make_pair
#define f first
//#define sex second

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <ostream>
#include <queue>
#include <functional>
#include <sstream>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#pragma comment(linker, "/STACK:228228000")
const ll mod = 998244353;

ll a, b, k, n;
ll res;
ll fs[2280000];

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

pll wev(ll a, ll b)
{
	if (a == 0)
		return mp(0, 1);
	pll ret;
	ret = wev(b%a, a);
	ll x = ret.second - (b / a)*ret.f;
	ll y = ret.f;
	return (mp(x, y));
}

ll fact(ll t)
{
	if (fs[t] > -1)
		return fs[t];
	ll q = t;
	while (fs[q] < 0)
	{
		q--;
	}
	forn(i, q, t)
	{
		fs[i + 1] = fs[i] * (i + 1);
		fs[i + 1] %= mod;
	}
	return fs[t];
}

ll diva(ll a, ll b)
{
	ll q = ev(b, mod);
	if (q > 1) return -1;
	b = (wev(b / q, mod / q).f + mod) % mod;
	return (a*b) % mod;
}

int main()
{
	/*
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/
	forn(i, 0, 2200000)
	{
		fs[i] = -1;
	}
	fs[0] = 1;

	cin >> n >> a >> b >> k;
	forn(i, 0, n+1)
	{
		ll kn = a*i;
		if ((k - kn) % b) continue;
		ll se = (k - kn) / b;
		if (se > n || se < 0) continue;
		ll sum = diva(fact(n), fact(n - se));
		if (sum < 0) continue;
		sum *= diva(fact(n), fact(n - i));
		if (sum < 0) continue;
		sum %= mod;
		sum = diva(sum, fact(i));
		sum = diva(sum, fact(se));
		res = (res + sum)%mod;
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 17408
uses math;
var
	ans,n,Ma,Mb,i,j,a,b,c,x,mp,mm:Longint;
	p,m:array[0..200]of Longint;
begin
	read(n,Ma,Mb);
	ans:=10000;
	for i:=1 to 200 do begin
		p[i]:=ans;
		m[i]:=ans;
	end;
	for i:=1 to n do begin
		read(a,b,c);
		x:=Ma*b-Mb*a;
		if x>0 then begin
			mp:=min(mp+x,200);
			for j:=mp-x downto 0 do p[j+x]:=min(p[j+x],p[j]+c);
		end else if x<0 then begin
			mm:=min(mm-x,200);
			for j:=mm+x downto 0 do m[j-x]:=min(m[j-x],m[j]+c);
		end else ans:=min(ans,c);
	end;
	for i:=1 to 200 do ans:=min(ans,p[i]+m[i]);
	if ans<10000 then writeln(ans)else writeln(-1);
end.

Measured memory_bytes: 128
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input!{
        s:i64
    }
    let v = 1_000_000_000;
    let x:i64 = (v-s%v)%v;
    let y:i64 = (s+x)/v;
    println!("{} {} {} {} {} {}", 0, 0,v, 1, x, y);
}

Measured memory_bytes: 4352
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second > b.second; }

signed main() {
    string s;
    bool xx,xyx;
    cin>>s;
    rep(i,s.size()-1)if(s[i]==s[i+1]){
        cout<<i+1<<" "<<i+2<<endl;
            return 0;
    }
    rep(i,s.size()-2)if(s[i]==s[i+2]){
        cout<<i+1<<" "<<i+3<<endl;
            return 0;
    }
    cout<<-1<<" "<<-1<<endl;
}


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
		String s;
		int inCnt = 0;
		while ((s = stdIn.readLine()) != null) {
			int in = Integer.valueOf(s);
			if (in == 0)
				break;
			doMain(++inCnt, in);
		}
		System.exit(0);
	}

	private static void doMain(int inCnt, int in) {
		System.out.println("Case " + inCnt + ": " + in);

	}
}

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

ll f(int index, ll sum, ll value) {

    if (index == s.size())
        return sum + value;

    return f(index+1, sum + value, s[index]-'0') + f(index+1, sum, value*10+s[index]-'0');

}

int main() {

    cin >> s;
    cout << f(1, 0, s[0]-'0');


	return 0;
}


























Measured memory_bytes: 256
class Array
	def pluse i
		newArray=[]
		self.each{|num|
			newArray<<num+i
		}
	newArray
	end

	def sum
		sum_n=0
		self.size.times do |i|
			sum_n+=self[i]
		end
	sum_n
	end
end

count=[]
array=[]
n=[]
x=[]

loop do
 	input=STDIN.gets.split(" ")
 	n<<input[0].to_i
 	x<<input[1].to_i
	if(input[0].to_i==0)&&(input[1].to_i==0)
		break
	end
end

def howManyWays(i,n,a,array)
	if i!=a.size-1
		while a[i]<=n
			start=a.slice(i+1,a.size-1)
			howManyWays(i+1,n,a,array)
			a[i]+=1
			b=start.pluse(1)
			a.slice!(i+1,a.size-1)
			a+=b
		end
	else
		while a[i]<=n
			array<<a.dup
			a[i]+=1
		end
	end
	array
end

#2.upto(n) do |i|
#	i=3
0.upto(n.size-2) do |i|
	count[i]=0
	a=(1..3).to_a
	array=howManyWays(0,n[i],a,[])
#end
	array.each do |arr|
		if arr.sum==x[i]
			count[i]+=1
		end
	end
end

count.each do |i|
	puts i
end

Measured memory_bytes: 36224
//    https://youtu.be/N3oCS85HvpY

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef long long unsigned llu;
typedef pair<long long, long long> pll;
const long long inf = 2000000000000000000LL;	// 2e18
#define pi                  acos(-1.0)
#define fast                ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define shesh               "\n"
#define ff                  first
#define ss                  second
#define pb                  push_back
#define bp                  pop_back
#define pf                  push_front
#define fp                  pop_front
#define ub                  upper_bound
#define lb                  lower_bound
#define all(x)              x.begin(), x.end()
#define debug(x)            cout<<"debug "<<x<<"\n"
#define mest(a,b)           memset(a,b,sizeof(a))

int main(){
    fast;
    ll t,n,m,i,j,k,temp,flag,ans=0;
    cin>>n;
    map<ll,ll>mp;
    while(n--){
        cin>>temp;
        mp[temp]++;
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        if(it->second%2) ans++;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 6528
a = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]

bingo = 'No'

for t in zip(*a):
    a.append(list(t))

a.append([a[i][i] for i in range(3)])
a.append([a[i][2-i]for i in range(3)])

for line in a:
    if all(item in b for item in line):
        bingo = 'Yes'

print(bingo)



Measured memory_bytes: 9072
h, w = gets.chomp.split(" ").map(&:to_i)

g = []

h.times do
  g += gets.chomp.split("")
end

cand = []
w.times do |i|
  x = h.times.map{|j| i + j * w}
  if x.map{|j| g[j]}.all?{|c| c == "."}
    cand += x
  end
end

g = (h * w).times.select{|i| !cand.include?(i)}.map{|i| g[i]}

w -= (cand.length / h)

g.each_slice(w) do |row|
  if row.all?{|c| c == "."}
    next
  else
    puts row.join("")
  end
end


Measured memory_bytes: 6780
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]
ca = Counter(A)

s = sum(A)
for b, c in bc:
  tmp = ca[b]
  s = s - tmp*b + tmp*c
  ca[c] += ca[b]
  ca[b] = 0
  print(s)

Measured memory_bytes: 103992
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ACandyDistributionAgain solver = new ACandyDistributionAgain();
        solver.solve(1, in, out);
        out.close();
    }

    static class ACandyDistributionAgain {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            long x = in.nextLong();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
            }
            Arrays.sort(a);
            for (int i = 0; i < n; i++) {
                x -= a[i];
                if (x == 0) {
                    out.println(i + 1);
                    return;
                } else if (x < 0) {
                    out.println(i);
                    return;
                }
            }
            if (x == 0) {
                out.println(n);
            } else {
                out.println(n - 1);
            }
        }

    }
}



Measured memory_bytes: 24276
from sys  import stdin,stdout
 
st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")
 
mod=1000000007
INF=float('inf')


 
 
for _ in range(1):
    n=inp()
    f=0
    ans=0
    for i in range(n):
        a,b=mp()
        if a==b:
            ans+=1
        else:
            ans=0
        if ans==3:
            f=1
            break
    if f:
        pr('Yes')
    else:
        pr('No')
            
        


Measured memory_bytes: 61832
#include<bits/stdc++.h>
using namespace std;
string S;
bool predicate0(){
  const bool result=S[0]=='A';
  S[0]='a';
  return result;
}
bool predicate1(){
  int n_C=0;
  for(int i=2;i<=S.size()-2;++i){
    if(S[i]=='C'){
      ++n_C;
      S[i]='c';
    }
  }
  return n_C==1;
}
bool predicate2(){
  for(const auto x:S)if(isupper(x))return false;
  return true;
}
main(){
  cin>>S;
  string s;
  if(predicate0()&&predicate1()&&predicate2()){
    s="AC";
  }else{
    s="WA";
  }
  cout<<s<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define INT long long
using namespace std;

int main()
{
    int n;
    double m=0;
    cin >> n;
    double a;
    string s;
    for(int i=0;i<n;i++){
        cin >> a >> s;
        if(s=="JPY") m+=a;
        else m+=a*380000.0;
    }
    cout << m << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int vis[3 * N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, K;
	cin >> n >> K;
	if(2 * K <= n + 1){
		for(int i = 2 * n; i < K + 2 * n; i++){
			cout << K + i - 2 * n << ' ' << i << ' ' << K + 2 * i - 2 * n << "\n";
			vis[i - 2 * n] = 1;
			vis[i - K] = 1;
			vis[2 * i - 2 * n] = 1;
		}
		vector<int> a, b, c;
		for(int i = 0; i < n; i++) if(!vis[i])
			a.push_back(K + i);
		for(int i = n; i < 2 * n; i++) if(!vis[i])
			b.push_back(K + i);
		for(int i = 2 * n; i < 3 * n; i++) if(!vis[i])
			c.push_back(K + i);
		for(int i = a.size() - 1; i >= 0; i--)
			cout << a[i] << ' ' << b[i] << ' ' << c[i] << "\n";
	}
	else{
		cout << "-1\n";
	}
	return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
set<int> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		S.insert(x);
	}
	
	cout<<S.size()<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N, K;
    cin >> N >> K;
    if(K > (N+1)/2){
        cout << -1 << endl;
        return 0;
    }
    int p[N];
    rep(i, N){
        p[i] = K+2*N-1-i;
    }
    if(!(N & 1)){
        cout << K+N-1 << ' ' << p[N-1] << ' ' << K+3*N-1 << endl;
    }
    int m = (N-1)/2;
    for(int i = m; i >= 0; i -= 2){
        int a = (m-i)/2;
        //小さい方
        cout << K+a << ' ' << p[a+i] <<  ' ' << K+2*(N+a) << endl;
        if(i == 0) break;
        //大きい方
        cout << K+a+i << ' ' << p[a] << ' ' << K+2*(N+a+i) << endl;
    }
    for(int i = m-1; i >= 0; i -= 2){
        int a = (m-1-i)/2;
        //小さい方
        cout << K+m+1+a << ' ' << p[m+1+a+i] << ' ' << K+1+2*(N+a) << endl;
        if(i == 0) break;
        //大きい方
        cout << K+m+1+a+i << ' ' << p[m+1+a] << ' ' << K+1+2*(N+a+i) << endl;
    }
}

Measured memory_bytes: 2688
/*
    Name: *3 or /2 
    Author: FZSZ-LinHua
    Date: 2018 06 16
    Exec time: 2ms
    Memory usage: 256KB
    Score: 300
    Algorithm: Bit operation 
*/
# include "cstdio"

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=-w;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}

inline int n_lowbit(int x){	//取出含有质因子2的个数 
	int count=0;
	while(x){
		if(x&1){
			return count; 
		}
		count++; 
		x>>=1; 
	}
	return count; 
} 

int
	ans, //记录答案 
	N; 

int main(){
	N=read();
	while(N--){
		ans+=n_lowbit(read()); //更新答案 
	}
	printf("%d",ans); 
	return 0; 
} 

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

using namespace std;

typedef long long ll;

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

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

	int n, ma, mb;
	cin >> n >> ma >> mb;

	vector<int> a(n), b(n), c(n);
	rep(i, n) cin >> a[i] >> b[i] >> c[i];

	int max_m = 404;
	int INF = 1e9;
	vector<vector<vector<int>>> dp(2, vector<vector<int>>(max_m, vector<int>(max_m, INF)));
	dp[0][0][0] = 0;

	rep(i, n){
		rep(j, max_m) rep(k, max_m) dp[(i+1)%2][j][k] = INF;

		rep(j, max_m){
			rep(k, max_m){
				chmin(dp[(i+1)%2][j][k], dp[i%2][j][k]);
				if(j + a[i] < max_m && k + b[i] < max_m){
					chmin(dp[(i+1)%2][j + a[i]][k + b[i]], dp[i%2][j][k] + c[i]);
				}
			}
		}
	}

	int ans = INF;
	for(int y = 1; max(y * ma, y * mb) < max_m; y++){
		chmin(ans, dp[n%2][y * ma][y * mb]);
	}

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


Measured memory_bytes: 5308
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define double long double
#define vi vector<int>
#define vd vector<double>
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define sortv(v) sort(all(v))
#define sortg(v) sort(all(v), greater<int>())
#define countv(v, c) count(all(v), c)
#define gcd __gcd
#define _rep(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) _rep(i, 0, n)
#define _rev(i, m, n) for(int i=(int)(m-1);i>=(int)(n);i--)
#define rev(i, n) _rev(i, n, 0)
#define each(i, n) for(auto&& i: n)
void in(){}
template<typename F, typename... R>
bool in(F& f, R&... r){
	if(cin >> f){in(r...);return true;}
	else{return false;}
}
#define inv(x) each(i, x) in(i)
#define out(x) cout << (x)
#define space() cout << " "
#define indent() cout << '\n'
void print(){}
template<typename F, typename... R>
void print(F f, R... r){out(f), indent(), print(r...);}
#define printv(x) each(i, x) out(i), space(); indent()
#define debughead(x) cerr << "Line " << __LINE__ << ": " << #x << ": "
#define debugout(x) cerr << (x) << " "
#define debugindent() cerr << '\n'
#define debug(x) debughead(x), debugout(x), debugindent()
#define debugv(x) debughead(x); each(i, x) debugout(i); debugindent()
#define YN(x) out((x) ? "YES" : "NO"), indent()
#define Yn(x) out((x) ? "Yes" : "No"), indent()
#define yn(x) out((x) ? "yes" : "no"), indent()
const int INF = 1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-15;
const double PI = acos(-1);
const int dx[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int dy[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
int lcm(int a, int b){return a / gcd(a, b) * b;}
int factorial(int a){return a < 2 ? 1 : factorial(a - 1) * a;}
int summation(int a){return a < 1 ? 0 : (a * a + a) / 2;}
int combination(int n, int r){
	int res = 1;
	_rep(i, 1, r + 1){
		res *= n--, res /= i;
	}
	return res;
}
bool isPrime(int n){
	_rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		if(!(n % i)){
			return false;
		}
	}
	return true;
}
vector<int> divisor(int n){
	vector<int> ans;
	_rep(i, 1, sqrt(n) + 1){
		if(!(n % i)){
			ans.pb(i);
			if(i * i < n){
				ans.pb(n / i);
			}
		}
	}
	return ans;
}
map<int, int> factorization(int n){
	map<int, int> ans;
	_rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		while(!(n%i)){
			ans[i]++, n /= i;
		}
	}
	if(n > 1){
		ans[n]++;
	}
	return ans;
}
signed main(){INCANT;
	/*-----------------------------------------------*/
	
	int X; cin >> X;
	_rep(i, X, X + INF){
		if (isPrime(i)) {
			print(i);
			break;
		}
	}

	/*-----------------------------------------------*/
}

Measured memory_bytes: 256
let [|S;T|] = stdin.ReadLine().Split()
let [|A;B|] =
    stdin.ReadLine().Split()
    |> Array.map int
let U = stdin.ReadLine()

match U with
| x when x = S -> printfn "%d %d" (A-1) B
| x when x = T -> printfn "%d %d" A (B-1)

Measured memory_bytes: 30044
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
ll n,pos;
ll a[200010],b[200010];
vector<pll >s;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;for(int i=0;i<n;i++)cin>>a[i]>>b[i],s.pb(m_p(b[i],a[i]));sort(s.begin(),s.end());
	vector<pll >::iterator it=s.begin();
	for(;it!=s.end();it++){
		pll p=*it;
		pos+=p.sec;
		if(pos>p.fir){
			cout<<"No";
			return 0;
		}
//		cout<<pos-p.sec<<"-->"<<pos<<"   "; 
	}
	cout<<"Yes";
	return 0;
}


Measured memory_bytes: 8432
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
int main(void){
  int n,a,b,c,d,i;
  string s;
  cin >> n >> a >> b >> c >> d;
  cin >> s;
  for (i=a-1;i<c-1||i<d-1;i++) if (s.at(i)=='#'&&s.at(i+1)=='#'){
    cout << "No" << endl;
    return 0;
  }
  if (c<d){
    cout << "Yes" << endl;
    return 0;
  }
  bool ans=false;
  for (i=b-2;i<=d-2;i++) if (s.at(i)=='.'&&s.at(i+1)=='.'&&s.at(i+2)=='.'){
    ans=true;
    break;
  }
  if (ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct S{
  int number;
  int AC[10]={},WA[10]={},time=0;
  int sumAC=0;
};
bool cmp(S a,S b){
  if(a.sumAC==b.sumAC){
      if(a.time==b.time)return a.number>b.number;
      return a.time<b.time;
  }
  return a.sumAC>b.sumAC;
 
}
signed main (){
  int M,T,P,R;
  while(cin>>M>>T>>P>>R&&M){
    vector<S> v(T);
    for(int i=0;i<T;i++)v[i].number=i+1; //まずは番号を入れる
    for(int i=0;i<R;i++){
      int m,t,p,j;
      cin>>m>>t>>p>>j;
      t--;p--; //0-indexに
      if(j==0){ //正解なら
          v[t].AC[p]++;
          v[t].time+=v[t].WA[p]*20;
          v[t].time+=m;
      }
      else v[t].WA[p]++; //誤答なら
    }
    for(int i=0;i<T;i++){
      for(int j=0;j<P;j++){
        v[i].sumAC+=v[i].AC[j]; //各チームの正解数を求める
      }
    }
    sort(v.begin(),v.end(),cmp); //上で書いた比較関数cmpを使ってソート。配列の中身が強い順になる
 
    for(int i=0;i<T;i++){
      cout<<v[i].number;
      while(i+1<T&&v[i].sumAC==v[i+1].sumAC&&v[i].time==v[i+1].time){ //順位が同じ時の処理
          i++;
          cout<<'='<<v[i].number;
      }
      if(i!=T-1)cout<<','; //最後はカンマ打ちません
    }
    cout<<endl;
  }
}


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

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

    int a_tax , b_tax;

    int base = 1;
    bool can = true;
    while(1) {
        a_tax = base * 0.08;
        b_tax = base * 0.1;
        if (a_tax == a && b_tax == b) {
            break;
        }
        base++;
        if (base > 1000) {
            can = false;
            break;
        }
    }

    if (can) cout << base << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int calc(int p, int x) {
    return p * (100 + x) / 100;
}

void solve(int X, int Y, int S) {
    int ans = 0;
    FOR(i, 1, S) {
        FOR(j, i, S ) {
            if (calc(i, X) + calc(j, X) == S) {
                ans = max(ans, calc(i, Y) + calc(j, Y));
            }
        }
    }
    cout << ans << endl;
}

signed main(void) {
    int n, m, p, a, b, c, x, y, z;
    string s;
    while (cin >> x >> y >> z) {
        if (x == 0 && y == 0 && z == 0) return 0;
        solve(x, y, z);
    }
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
		
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  vector<pair<int, int>> r, b;
  for(int i = 0; i < n; i++) {
  	int x, y;
  	cin >> x >> y;
  	r.emplace_back(x, y);
  }
  for(int i = 0; i < n; i++) {
  	int x, y;
  	cin >> x >> y;
  	b.emplace_back(x, y);
  }
  sort(r.begin(), r.end());
  sort(b.begin(), b.end());
  vector<int> a;
  int cnt = 0;
  int i = 0, j = 0;
  while(j < n) {
  		//cout << "blue" <<  b[j].first << endl;
  	while(i < n && r[i].first <= b[j].first) {
  		a.push_back(r[i].second);
  			//cout << "red" << r[i].first << endl;
  		i++;
  	}
  	sort(a.begin(), a.end());
  	auto itr = lower_bound(a.begin(), a.end(), b[j].second);
  	if(itr != a.begin()) {
  		a.erase(itr - 1);
  		cnt++;
  	}
  	j++;
  }
  cout << cnt << endl;
	return 0;
}	


Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
	char c = sc.next().charAt(0);
	char d = sc.next().charAt(1);
	char e = sc.next().charAt(2);

	System.out.println(c+""+d+""+e);
    }
}

Measured memory_bytes: 21844
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <unordered_set>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long

int n, a, b;
int main(void)
{
    cin >> n >> a >> b;
    int diff = b - a;

    if (diff % 2 == 0)
        printf("Alice");
    else
        printf("Borys");

    return 0;
}


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

const int maxn = 1e5 + 100;

int m, n, e_n, nxt[maxn << 1], head[maxn], to[maxn << 1], cyc[maxn], par[maxn], dep[maxn];
long long s, ans, val[maxn];
bool isr[maxn];

long long abs(long long x) {
	return x < 0 ? -x : x;
}

long long dfs(int u, int f, int p) {
	long long x = p ? 1 : -1;
	for (int i = head[u]; i; i = nxt[i]) {
		if(to[i] != f && !isr[to[i]]) {
			x += dfs(to[i], u, p ^ 1);
		}
	}
	if(f) {
		ans += abs(x);
	}
	return x;
}

void dfs2(int u, int f) {
	dep[u] = dep[f] + 1;
	par[u] = f;
	for (int i = head[u]; i; i = nxt[i]) {
		if(to[i] != f) {
			if(dep[to[i]]) {
				if(dep[to[i]] < dep[u]) {
					for(int v = u; v != to[i]; v = par[v]) {
						isr[cyc[m++] = v] = 1;
					}
					isr[cyc[m++] = to[i]] = 1;
				}
			}
			else {
				dfs2(to[i], u);
			}
		}
	}
	return;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int u, v, i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v);
		nxt[++e_n] = head[u];
		to[e_n] = v;
		head[u] = e_n;
		nxt[++e_n] = head[v];
		to[e_n] = u;
		head[v] = e_n;
	}
	if(m == n - 1) {
		return !printf("%lld\n", dfs(1, 0, 0) ? -1 : ans);
	}
	m = 0;
	dfs2(1, 0);
	for (int i = 0; i < m; ++i) {
		s += (val[i] = dfs(cyc[i], 0, 0));
	}
	if(s & 1) {
		return !puts("-1");
	}
	if(m & 1) {
		s /= 2;
		for (int i = 1; i < m; i += 2) {
			s -= val[i];
		}
		for (int i = 0; i < m; ++i) {
			ans += abs(s);
			s = val[i] - s;
		}
		return !printf("%lld\n", ans);
	}
	s = 0;
	for (int i = 0; i < m; ++i) {
		val[i] *= ((i & 1) ? -1 : 1);
		s += val[i];
	}
	if(s) {
		return !puts("-1");
	}
	for (int i = 1; i < m; ++i) {
		val[i] += val[i - 1];
	}
	std::sort(val, val + m);
	m >>= 1;
	for (int i = 0; i < m; ++i) {
		ans += val[i + m] - val[i];
	}
	return !printf("%lld\n", ans);
}

Measured memory_bytes: 8960
#include<bits/stdc++.h>
#define endl "\n"
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MAXN (int)(1e5+1)
using namespace std;
int main(){
	int mod=1e9+7;
	int n,k;cin>>n>>k;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<long long>dp(k+1,0);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		vector<long long> newdp(k+1,0);
		vector<long long> pref(k+1,0);
		for(int j=0;j<=k;j++){
			pref[j]=((j>=1?pref[j-1]:0)+dp[j])%mod;;
		}
		for(int j=0;j<=k;j++){
			int r=j,l=max(0,j-a[i]);
			if(l==0)newdp[j]=pref[r];
			else newdp[j]=(mod+(pref[r]-pref[l-1])%mod)%mod;
		}
		dp=newdp;
	}	
	cout<<dp[k]<<endl;
}


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

int main() {
  int n;
  int b, f, r, v;
  int p[4][3][10] = {0};

  cin >> n;
  rep(i,n) {
    cin >> b >> f >> r >> v;
    p[b-1][f-1][r-1] += v;
  }

  rep(i,4) {
    rep(j,3) {
      rep(k,10) {
        cout << " " << p[i][j][k];
      }
      cout << endl;
    }
    if (i == 3) break;
    cout << "####################" << endl;
  }

  return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;

int n;
pii a[500];
int par[500];
int fpr(int u){return par[u] == u ? u : par[u] = fpr(par[u]);}
int main(){
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i].fi >> a[i].se;
  for (int i = 0; i < n; i++) par[i] = i;
  map<pii, int> mp;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++){
      if (i == j) continue;
      pii x = {a[i].fi - a[j].fi, a[i].se - a[j].se};
      pii y = {a[j].fi - a[i].fi, a[j].se - a[i].se};
      if (x.fi != 0 || x.se != 0) mp[x]++;
      if (y.fi != 0 || y.se != 0) mp[y]++;
    }
  pii c = (*mp.begin()).first;
  for (auto it = mp.begin(); it != mp.end(); it++){
    if (it -> se > mp[c]) c = it->fi;
  }
 // cout << c.fi << ' ' << c.se << '\n';
  for (int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (i != j && a[i].fi - a[j].fi == c.fi
          && a[i].se - a[j].se == c.se){
//		  cout << "merge " << i << ' ' << j << '\n';
        par[fpr(j)] = fpr(i);
      }
  int cnt =0;
  for (int i = 0; i < n; i++)
    if (i == fpr(i)) cnt++;
  cout << cnt << '\n';
  return 0;
}


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

int main(){
  int N ; cin >> N ;
  bool ans = false ;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(i*j==N) ans = true;
    }
  }
  
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}


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

using namespace std;

int main()
{
    int n;
    cin>>n;
    int temp;
    float arr[n+1];
    arr[0]=0;
    for(int i=1;i<=n;i++){
        cin>>temp;
        arr[i] = arr[i-1]+temp;
    }
    float tofind = arr[n]/2;
    int lo = 1;
    int high = n;
    int mid = (lo+high)/2;
    while(lo<high){
        mid = (lo+high)/2;
        if(arr[mid]>=tofind){
            high =mid;
        }
        else{
            lo =mid+1;
        }
    }
    int ans;
    if(lo>1){
        ans = 2*min(abs(tofind-arr[lo-1]),abs(tofind - arr[lo]));
    }
  	else{
    	ans =2*abs(tofind - arr[lo]);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace::std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/numeric/interval.hpp>
// #include <boost/numeric/interval/io.hpp>
// #include <boost/intrusive/rbtree.hpp>
// #include <boost/geometry.hpp>
// #include <boost/geometry/geometries/linestring.hpp>
// #include <boost/geometry/geometries/polygon.hpp>
// #include <boost/geometry/geometries/point_xy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
using namespace::std;
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cfloat;
// typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"");if(i>INF/2)cout<<"INF";else cout<<i;f=1;}cout<<"\n";}while(0)
#define output2(v) for(auto j:v)output(j);
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define SUM(v) accumulate(all(v),0LL)
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define LINF 9223372036854775807
#define MOD 1000000007
#define endl "\n"
template<typename T=lint>T in(){return *istream_iterator<T>(cin);}
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};

int main(){
    lint n;
    cin>>n;
    vec a(n);
    rep(i,n)cin>>a[i];
    lint cnt=0,cnt2=0;
    rep(i,n)if(a[i]%2)cnt++;
    else cnt2++;
    if(cnt==0||cnt2==0){
        cout<<0<<endl;
        return 0;
    }else{
        cout<<n-(2-cnt%2)<<endl;
    }
}


Measured memory_bytes: 4424
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <map>
#include <cassert>
#include <sstream>
#include <numeric>
#include <regex>
#include <cctype>
#include <utility>
#include <stdio.h>
#include <set>
#include <queue>
#include <deque>

typedef long long ll;

#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define MOD 1000000007
#define pb push_back
#define llnums vector<ll>
#define FOR(i,n) for(int i{0}; i < n; ++i)

using namespace std;

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  double a, b, h;
  cin >> a >> b >> h;
  cout << ( (a+b)*h)/2 << '\n'; 
  return 0;
}









Measured memory_bytes: 3768
#!/usr/bin/ruby
Z=10**9+7
def d(x,y) x.zip(y).reduce(0){|s,(a,b)|s+a*b} end
def mul(x,y)
	y=y.transpose
	[[d(x[0],y[0])%Z,d(x[0],y[1])%Z],[d(x[1],y[0])%Z,d(x[1],y[1])%Z]]
end
def pow(x,y)
	z=1
	while y>0
		z=z*x%Z if y%2>0
		x=x*x%Z
		y/=2
	end
	z
end
H,W,K=gets.split.map(&:to_i)
if K==0
	p 1
	exit
end
K-=1
M=$<.map{|e|e.chomp.chars}
c=M.count{|s|s[0]=='#'&&s[-1]=='#'}
d=M.transpose.count{|s|s[0]=='#'&&s[-1]=='#'}
if c>0&&d>0
	p 1
	exit
end
if d>0
	c,d=d,c
	M=M.transpose
H,W=W,H
end
a=b=0
M.each{|s|W.times{|i|
	a+=1 if s[i]=='#'
	b+=1 if i<W-1&&s[i]=='#'&&s[i+1]=='#'
}}
if c==0&&d==0
	p pow(a,K)
	exit
end

e=[[1,0],[0,1]]
m=[[a,-b],[0,c]]
k=K
while k>0
	e=mul(e,m) if k%2>0
	m=mul(m,m)
	k/=2
end
p mul(e,[[1,0],[1,0]])[0][0]%Z
#p (e[0][0]+e[0][1])%Z

Measured memory_bytes: 97148
from itertools import accumulate


N, K = map(int, input().split())
A = list(map(int, input().split()))


expected = [(a+1)/2 for a in A]
accum_expected = list(accumulate(expected))
accum_expected.insert(0, 0)

ans = 0
for i in range(K, N+1):
    ans = max(ans, accum_expected[i]-accum_expected[i-K])
print(ans)

Measured memory_bytes: 25152
#include <iostream>
//#include <cmath>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;


int32_t main()
{
    
    IOS;
    //fill(isprime, true);
    //pre();
    
    int t;
    cin>>t;
    t=!t;
    cout<<t;
    
}





Measured memory_bytes: 3660
from collections import defaultdict
import heapq

while True:
    N, M, L = map(int, input().split())
    if N==M==L==0:
        break
    E = defaultdict(lambda: defaultdict(lambda: float("inf")))
    for _ in range(M):
        A, B, D, E_ = map(int, input().split())
        E[A][B] = (D, E_)  # 金、コスト
        E[B][A] = (D, E_)  # 金、コスト

    start = (1, 0)

    dist = defaultdict(lambda: float("inf"))  # 始点から各頂点までの(仮の)最短距離を格納する
    dist[start] = 0
    q = []  # 各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    heapq.heappush(q, (0, start))  # 始点をpush
    while len(q) != 0:
        prov_cost, v_m = heapq.heappop(q)  # pop  # 一度取り出された時点でコストは確定
        v, m_v = v_m

        # プライオリティキューに格納されている最短距離が
        # 現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[v] < prov_cost:
            continue

        if v==N:
            print(prov_cost)
            break

        # 辺を探索
        Us = {}
        for u, (m, c) in E[v].items():
            Us[(u, m_v)] = c
            if m_v+m <= L:
                Us[(u, m_v+m)] = 0

        for u_m, c in Us.items():
            if dist[u_m] > dist[v_m] + c:
                dist[u_m] = dist[v_m] + c  # distの更新
                heapq.heappush(q, (dist[u_m], u_m))  # キューに新たな仮の距離の情報をpush



Measured memory_bytes: 8376