akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;
using ll = int64_t;

bool ok(const vector<ll>& A, ll k, ll allowed) {
  ll cost = 0;
  for(ll i=0; i<A.size(); i++) {
    // smallest K s.t. allowed*K >= A[i]
    // cost += K-1
    // 1..allowed -> 0
    // allowed+1..2*allowed -> 1
    cost += (A[i]-1)/allowed;
  }
  return cost <= k;
}

int main() {
  ll n,k;
  cin >> n >> k;
  vector<ll> A(n, 0);
  for(ll i=0; i<n; i++) {
    cin >> A[i];
  }

  ll lo = 1;
  ll hi = 1e9;
  while(lo < hi) {
    ll mid = (lo+hi)/2;
    //cerr << " mid=" << mid << " ok=" << ok(A, k, mid) << endl;
    if(ok(A, k, mid)) {
      hi = mid;
    } else {
      lo = mid+1;
    }
  }
  cout << lo << endl;
}


Measured memory_bytes: 4720
#include <cmath>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

#define forsn(i,s,n) for (int i = (s);i < (int)(n);i++)
#define forn(i,n) forsn(i,0,n)
#define dforsn(i,s,n) for (int i = (n-1);i >= (int)(s);i--)
#define dforn(i,n) dforsn(i,0,n)
#define all(v) (v).begin(), (v).end()
#define F first
#define S second

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

	int n; cin >> n;
	string s, t; cin >> s >> t;
	
	int suffixLength = 0;
	forn(i,n + 1) {
		if (s.substr(s.size() - i, i) == t.substr(0, i)) suffixLength = i;
	}
	
	cout << 2 * n - suffixLength << endl;
}


Measured memory_bytes: 256
r,g,b,n =  map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        #print(i,j)
        #print(n-i*r-j*g)
        if int(n-(i*r)-(j*g)) % b ==0 and int(n-(i*r)-(j*g)) >=0 :
            #print("a")
            #print(i,j)
            cnt+=1
print(cnt)


Measured memory_bytes: 40684
fun main(args: Array<String>) {
    val (x, y, z) = readLine()!!.split(" ").map { it.toInt() }
    var dnl = mutableListOf<Int>()
    for (i in 1 .. 100){
        if (x % i == 0 && y % i == 0) dnl.add(i)
    }
    dnl = dnl.reversed().toMutableList()
    println(dnl[z - 1])
}

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

int ide(ul n,ll *p,ll *q) {
  for (size_t i = 0; i < n; i++)
  {
    if (p[i]!=q[i]) return 0;
  }
  return 1;
  
}

int main() {
  ul n;
  cin>>n;
  ll p[8],q[8],s[8]={1,2,3,4,5,6,7,8};

  for (size_t i = 0; i < n; i++)
  {
    cin >> p[i];
  }
  for (size_t i = 0; i < n; i++)
  {
    cin >> q[i];
  }
  ll a=-1,b=-1,ct=0;
  do {
    ct++;
    if (a < 0 && ide(n, p, s))
      a = ct;
    if (b < 0 && ide(n, q, s))
      b = ct;

  } while (next_permutation(s,s+n));
  cout<<abs(a-b)<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); ++i)

int main() {
    string s, t;
    cin >> s >> t;
    int sn = s.size();
    int tn = t.size();
    vector<vector<int>> dp(sn+1, vector<int>(tn+1));
    rep(i, sn) {
        rep(j, tn) {
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            if (s[i] == t[j]) {
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
            }
        }
    }
    string ans = "";
    while (sn > 0 && tn > 0) {
        if (dp[sn][tn] == dp[sn-1][tn]) sn--;
        else if (dp[sn][tn] == dp[sn][tn-1]) tn--;
        else {
            sn--; tn--;
            ans = s[sn] + ans;
        }
    }
    cout << ans << endl;
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main(){
  int n;
  long long a[100001];
  long long sum=0, sum2=0;
  int ptt;
  int i;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a+n, greater<int>());
  if(n==3){
    sum=a[0]+a[1]-a[2]*2;
    cout << max(a[0]*2-a[1]-a[2], a[0]+a[1]-a[2]*2) << '\n';
    return 0;
  }
  if(n==2){
    sum=a[0]-a[1];
    cout << sum << '\n';
    return 0;
  }

  if(n%2==1){
    ptt=n/2;
    for (i=0; i < ptt; i++) {
      sum+=(2*a[i]);
    }
    sum-=a[i];
    i++;
    sum-=a[i];
    i++;
    for(;i<n;i++){
      sum-=(2*a[i]);
    }
    ptt=n/2-1;
    for (i=0; i < ptt; i++) {
      sum2+=(2*a[i]);
    }
    sum2+=a[i];
    i++;
    sum2+=a[i];
    i++;
    for(;i<n;i++){
      sum2-=(2*a[i]);
    }
    if(sum<sum2){
      sum=sum2;
    }

  }else{
    ptt=n/2-1;
    for (i=0; i < ptt; i++) {
      sum+=(2*a[i]);
    }
    sum+=a[i];
    i++;
    sum-=a[i];
    i++;
    for(;i<n;i++){
      sum-=(2*a[i]);
    }
  }


  cout << sum << '\n';
  return 0;
}


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

int max(int a, int b){
	return a >= b ? a : b;
}

int min(int a, int b){
	return a <= b ? a : b;
}

int main(){
	int N, a, mina = 100000, maxa = 0, i;
	scanf("%d", &N);
	int *anum = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		anum[i] = 0;
	}
	for(i = 0; i < N; i++){
		scanf("%d", &a);
		anum[a]++;
		mina = min(mina, a);
		maxa = max(maxa, a);
	}
	if((maxa + 1) / 2 != mina){
		printf("Impossible\n");
		return 0;
	}
	if(maxa % 2 == 0){
		if(anum[mina] != 1){
			printf("Impossible\n");
			return 0;
		}
	}
	else{
		if(anum[mina] != 2){
			printf("Impossible\n");
			return 0;
		}
	}
	for(i = mina + 1; i <= maxa; i++){
		if(anum[i] < 2){
			printf("Impossible\n");
			return 0;
		}
	}
	printf("Possible\n");
	return 0;
}

Measured memory_bytes: 128
//解法AC...
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using INT=mp::cpp_int;
using namespace std;
using ll=long long;
using vec=vector<ll>;
using vect=vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
INT LCM(INT x,INT y){
  INT z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
INT modinv(INT a, INT m) {
    INT b = m, u = 1, v = 0;
    while (b) {
        INT t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main() {
  cout << fixed << setprecision(30);
  ll n,k;
  cin>>n>>k;
  vec x(n);
  loop(i,n)cin>>x[i];
  ll ans=1e18,preans1,preans2;
  loop(i,n-k+1){
    ll l=x[i],r=x[i+k-1];
    preans1=abs(l)+abs(r-l);
    preans2=abs(r)+abs(r-l);
    ans=min(ans,min(preans1,preans2));
  }
  putout(ans);
}

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

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

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

const int CASES = 3;

vector<P> prime_factorize(ll n) {
    vector<P> res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

map<ll, int> sisuu;

ll rec(map<ll, int>::iterator p, ll mul) {
    if (p == sisuu.end()) {
        if (mul == 1) return 1;
        else return 0;
    }

    ll res = 0;
    for (int i = 0; i < p->second + 1; ++i) {
        if (mul % (i+1) != 0) continue;
        res += rec(++p, mul / (i+1));
        --p;
    }
    return res;
}

void solve(){
    sisuu.clear();
    int N; cin >> N;
    for (int i = 2; i <= N; ++i) {
        auto ps = prime_factorize(i);
        for (auto it : ps){
            sisuu[it.first] += it.second;
        }
    }

    cout << rec(sisuu.begin(), 75) << endl;
    return;
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
#define MAX 1e9
struct edge { ll s, t, x; };
typedef pair<ll, ll> P;
typedef pair<ll,P> event;
#define MOD 1000000007

int main(){
  char S;
  cin>>S;
  int x=S-'0';
  if(49<=x&&x<=74){cout<<'a'<<endl;}
  else{cout<<'A'<<endl;}
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x) cout << #x << " = " << (x) << endl;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define P pair<int, int>
#define V vector<int>
#define M map<int, int>
#define S set<int>
int N;
vector<P> x;
V X[100010], Y[100010];
int dx[100010], dy[100010];
int cx[100010], cy[100010];

void s(int a, int b, int c, int n)
{
    /*
    dump(a);
    dump(b);
    dump(c);
    dump(n);
    cout << endl;
    */
    if (c) {
        for (int i = 0; i < (int)Y[b].size(); i++) {
            int m = Y[b][i];
            //dump(m);
            if (dx[m] == 0) {
                dx[m] = n;
                s(m, b, 0, n);
            }
        }
    } else {
        for (int i = 0; i < (int)X[a].size(); i++) {
            int m = X[a][i];
            //dump(m);
            if (dy[m] == 0) {
                dy[m] = n;
                s(a, m, 1, n);
            }
        }
    }
}

void solve()
{
    int ans = 0;
    int j = 1;
    for (int i = 0; i < (int)x.size(); i++) {
        if (dx[x[i].first] == 0) {
            dx[x[i].first] = j;
            dy[x[i].second] = j;
            s(x[i].first, x[i].second, 0, j);
            s(x[i].first, x[i].second, 1, j);
            j++;
        }
    }
    for (int i = 0; i < 100005; i++) {
        cx[dx[i]]++;
        cy[dy[i]]++;
    }
    for (int i = 1; i < j; i++) {
        ans += cx[i] * cy[i];
    }
    /*for (int i = 0; i < 10; i++) {
        cout << i << " " << (int)X[i].size() << " " << (int)Y[i].size() << endl;
    }*/
    for (int i = 0; i < 10; i++) {
        // cout << i << " " << dx[i] << " " << dy[i] << endl;
    }
    ans -= N;
    cout << ans << endl;
}

signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(i, 0, N)
    {
        int a, b;
        cin >> a >> b;
        x.pb(make_pair(a, b));
        X[a].pb(b);
        Y[b].pb(a);
    }
    solve();
    return 0;
}


Measured memory_bytes: 15856
n = int(input())
a = list(map(int, input().split()))
c = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if a[i] != a[j] and a[j] != a[k] and a[k] != a[i]:
                if a[i] + a[j] > a[k] and a[j] + a[k] > a[i] and a[k] + a[i] > a[j]:
                    c += 1

print(c)


Measured memory_bytes: 9200
#include "bits/stdc++.h"

typedef long long ll;

using namespace std;

int main() {
	int A,B,res;
	cin >> A >> B;
	if (A>=13) {
		cout << B << endl;
	}
	else if(A>=6){
		cout << B/2 << endl;
	}
	else {
		cout << "0" << endl;
	}
}

Measured memory_bytes: 256
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let board: Vec<_> = (0..n).map(|_| sc.chars()).collect();

    let ok = board
        .iter()
        .any(|row| row.iter().find(|&&c| c == '#').is_some());
    if !ok {
        println!("-1");
        return;
    }

    let unfilled_columns = (0..n)
        .filter(|&column| {
            let unfilled = (0..n).find(|&i| board[i][column] != '#').is_some();
            unfilled
        })
        .count();

    let ans = (0..n)
        .map(|i| {
            let filled_count = board[i].iter().filter(|&&c| c == '#').count();
            let has = board.iter().find(|row| row[i] == '#').is_some();
            let required_turns = n - filled_count + if has { 0 } else { 1 };
            required_turns + unfilled_columns
        })
        .min()
        .unwrap();
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]

    saitan_data = [[10 ** 10 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c
        saitan_data[a][b] = c
        saitan_data[b][a] = c


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                if i == j:
                    saitan_data[i][j] = 0
                    continue
                saitan_data[i][j] = min(saitan_data[i][j], saitan_data[i][k] + saitan_data[k][j])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

Measured memory_bytes: 59224
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((ll)2e5+5)
#define MOD ((ll)1e9 + 7)
#define INF ((ll)1e9 + 9)
#define prime 37
#define prime2 101
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<ll,ll>
#define mid ((l+r)/2)

string s;
ll n;
vector <ll> h;
ll p_[MAXN];
ll invp[MAXN];

vector <ll> h2;
ll p2_[MAXN];
ll invp2[MAXN];

ll C(char c)
{
	return (c - 'a');
}

ll M(ll a)
{
	return a%MOD;
}

void mul(ll& a,ll b)
{
	a *= b;
	a%=MOD;
}
ll modInverse(ll a)
{
	ll m = MOD;
	ll y = 0, x = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		ll q = a / m;
		ll t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0)
		x += MOD;
	return x;
}
void setup()
{
	h[0] = C(s[0]) % MOD;
	ll p = 1;
	p_[0] = 1;
	invp[0] = 1;
	for (ll i = 1; i < n; ++i)
	{
		h[i] = M(h[i-1] + M(p * C(s[i])));
		mul(p,prime);
		p_[i] = p;
		invp[i] = modInverse(p_[i]);
	}
}

void setup2()
{
	h2[0] = C(s[0]) % MOD;
	ll p2 = 1;
	p2_[0] = 1;
	invp2[0] = 1;
	for (ll i = 1; i < n; ++i)
	{
		h2[i] = M(h2[i-1] + M(p2 * C(s[i])));
		mul(p2,prime2);
		p2_[i] = p2;
		invp2[i] = modInverse(p2_[i]);
	}
}

ll ext(ll l, ll r)
{
	if(l)
		return M(M(h[r] - h[l-1] + MOD) * invp[l-1]);

	return M(h[r]);
}

ll ext2(ll l, ll r)
{
	if(l)
		return M(M(h2[r] - h2[l-1] + MOD) * invp2[l-1]);

	return M(h2[r]);
}


bool check(ll sz)
{
	if(sz == 0) return true;
	map <pair<ll,ll>,vector<ll>> mp;

	for (ll i = 1; i < n-sz+1; ++i)
	{// l : i  , r : i+sz-1
		mp[{ext(i,i+sz-1),ext2(i,i+sz-1)}].pb(i);
	}

	for (auto i : mp)
	{
		if(i.second.back() - i.second.front() >= sz)
			return true;
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n >> s;
	s = '#' + s;
	n = n+1;
	h.resize(n);
	h2.resize(n);
	setup();
	setup2();
	

	// TRACE(n);
	// for (ll i = 0; i < n; ++i)
	// 	TRACE2(i, h[i]);

	// return 0;
	ll l = 0;
	ll r = n/2;
	// ll resul
	TRACE(check(2));

	// return 0;
	while(l < r)
	{
		TRACE2(l,r);
		if(check(mid))
			l = mid+1;
		else
			r = mid;
	}

	if(check(l))
		cout << l << endl;
	else
		cout << l-1 << endl;

}

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

int main()
{
  long long n, m, x, i;
  priority_queue<long long> a;
  long long ans = 0;
  cin >> n >> m;
  for (i=0; i<n; i++){
    cin >> x;
    a.push(x);
  }
  
  for (i=0; i<m; i++){
    x = a.top();
    a.pop();
    a.push(x / 2);
  }
  
  for (i=0; i<n; i++){
    ans += long(a.top()) ;
    a.pop();
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>
#include <math.h>

int isPrime(int x){
  int i;
  if(x==2){
    return 1;
  }
  if(x<2 || x%2==0){
    return 0;
  }
  i=3;
  while(i<=sqrt(x)){
    if(x%i==0){
      return 0;
    }
    i+=2;
  }
  return 1;
}

int main(){
  int i,n,x,z;
  int sum=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    z=isPrime(x);
    sum+=z;
  }
  printf("%d\n",sum);
  
  return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int A,B,C;	cin>>A>>B>>C;
	if(A+B+C>=22)	cout<<"bust"<<endl;
	else cout<<"win"<<endl;


    return 0;
}



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

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

    long long res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            int k = lower_bound(L.begin(), L.end(), L[i] + L[j]) - L.begin();
            res += max(k - (j+1), 0);
        }
    }
    cout << res << endl;
}


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

using namespace std;

int imos[512][2048];

int main()
{
    int n, m;
    
    while (scanf("%d %d", &n, &m) && n){
        int r;
        scanf("%d", &r);
        
        vector<int> xs;
        pair<pair<int, int>, pair<int, int> > p[1024];
        for (int i = 0; i < r; i++){
            int t, n, m, s;
            scanf("%d %d %d %d", &t, &n, &m, &s);
            p[i] = make_pair(make_pair(n, t), make_pair(m, s));
            xs.push_back(m);
        }
        
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        sort(p, p + r);
        
        memset(imos, 0, sizeof(imos));
        
        for (int i = 0; i < r; i++){
            int s = lower_bound(xs.begin(), xs.end(), p[i].second.first) - xs.begin();
            if (p[i].second.second) imos[s][p[i].first.second]++;
            else imos[s][p[i].first.second]--;
        }
        
        for (int i = 0; i < xs.size(); i++){
            for (int j = 540; j <= 1260; j++){
                imos[i][j] += imos[i][j - 1];
            }
            for (int j = 540; j <= 1260; j++){
                imos[i][j] = !!imos[i][j];
                imos[i][j] += imos[i][j - 1];
            }
        }
        
        int q;
        scanf("%d", &q);
        for (int i = 0; i < q; i++){
            int s, e, m;
            scanf("%d %d %d", &s, &e, &m);
            if (binary_search(xs.begin(), xs.end(), m) == 0){
                printf("0\n");
            }
            else {
                m = lower_bound(xs.begin(), xs.end(), m) - xs.begin();
                printf("%d\n", imos[m][e - 1] - imos[m][s - 1]);
            }
        }
    }
    
    return (0);
}

Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<n;i++)
#define repf(i,a,n) for(long long i=a;i<n;i++)
typedef long long ll;
const ll INF=1LL << 40;

int main(){
    int n,k;string s; cin >> n >> k >> s;
    s[k-1]-='A'-'a';
    cout << s << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=0;i<n;i++){
		double xa,ya,ra,xb,yb,rb;
		scanf("%lf %lf %lf %lf %lf %lf",&xa, &ya, &ra, &xb, &yb, &rb);
		double d = sqrt(pow(xa-xb,2)+pow(ya-yb,2));
		if( rb+d < ra ) cout << "2" << endl;
		else if( ra+d < rb ) cout << "-2" << endl;
		else if( d > ra+rb) cout << "0" << endl;
		else cout << "1" << endl;
	}
	return 0;
}

Measured memory_bytes: 3200
from collections import Counter, defaultdict
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()
c = Counter(a)
ans = 0
for i, count in c.items():
    if count == i:
        continue
    elif count > i:
        ans += count - i
    else:
        ans += count
print(ans)


Measured memory_bytes: 18668
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <deque> 

using namespace std;


int n, m;
int a[30][30];
int b[30];
int c;

int main()
{
	scanf("%d%d%d", &n, &m, &c);
	for (int i = 0 ; i < m ; i++)
		scanf("%d", &(b[i]));
		
	int count = 0;
	for (int i = 0 ; i < n ; i++)
	{
		long num = c;
		for (int j = 0 ; j < m ; j++)
		{
			scanf("%d", &(a[i][j]));
			num = num + a[i][j] * b[j];
		}
		
		if (num > 0)
			count++;
	}
	
	printf("%d\n", count);
	
	
	return 0;
}



Measured memory_bytes: 128
// beetに勝つ
 
#include <bits/stdc++.h>
 
using namespace std;
 
using int64 = long long;
 
int main() {
  int N, M, P[100000], Q[100000];
  cin >> N >> M;
  map< int, vector< int > > mp;
  for(int i = 0; i < M; i++) {
    cin >> P[i] >> Q[i];
    mp[P[i]].emplace_back(Q[i]);
  }
  for(auto &p : mp) {
    sort(begin(p.second), end(p.second), [&](int a, int b) {
      return a < b;
    });
  }
  for(int i = 0; i < M; i++) {
    auto it = lower_bound(begin(mp[P[i]]), end(mp[P[i]]), Q[i]) - begin(mp[P[i]]);
    printf("%06d%06d\n", P[i], (int) (it + 1));
  }
}
 

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

#define ll long long
#define MAX 300005
#define pp pair<int,int>
#define pb push_back
#define mod 10

using namespace std;
/*
 * author: Kruti_20
 */
ll power(ll x, ll y);

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

ll cost[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int h[n];
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cost[i] = 2000000000;
    cost[0] = 0;
    for (int i = 1; i < n; i++) {
        cost[i] = min(cost[i], cost[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) cost[i] = min(cost[i], cost[i - 2] + abs(h[i] - h[i - 2]));
    }
    cout << cost[n - 1];
    return 0;
}


ll power(ll x, ll y) {
    ll res = 1;
    x = x % mod;
    while (y > 0) {
        if (y & 1) res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res;
}

Measured memory_bytes: 1408
#include<bits//stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i <n;i++)
#define ALL(a) a.begin(),a.end()
int main(){
  int n = 0;string s;
  cin >> s;
  if(s == "RSR") {
    cout << 1 << endl;
      return 0;
  }rep(i,3){
    if(s[i] == 'R')n++;
  }cout << n << endl;
}

Measured memory_bytes: 3624
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n_query = 0;

int ask(int y1, int x1, int y2, int x2)
{
	++n_query;
	printf("? %d %d %d %d\n", y1, x1, y2 - 1, x2 - 1);
	fflush(stdout);
	int a;
	scanf("%d", &a);
	return a;
}

int score(int q)
{
	if (q > 2500) return 0;
	if (q >= 930) return max((int)(1e-8 + 125 - 3.2 * sqrt(q - 920)), 40);
	if (q >= 880) return (int)(1e-8 + 288 - 22 * sqrt(q - 870));
	return min(2860 - 3 * q, 300);
}

int H, W, N, K;
int C[50][50];

void solve(int y1, int x1, int y2, int x2, int cnt)
{
	if (y2 - y1 == 1 && x2 - x1 == 1) {
		C[y1][x1] = cnt;
		return;
	}
	if (cnt == 0) return;
	if ((y2 - y1) * (x2 - x1) == cnt) {
		for (int i = y1; i < y2; ++i) {
			for (int j = x1; j < x2; ++j) {
				C[i][j] = 1;
			}
		}
		return;
	}

	if (x2 - x1 == 1) {
		int ym = (y2 + y1) / 2;
		int a = ask(y1, x1, ym, x2);
		solve(y1, x1, ym, x2, a);
		solve(ym, x1, y2, x2, cnt - a);
	} else {
		int xm = (x2 + x1) / 2;
		int a = ask(y1, x1, y2, xm);
		solve(y1, x1, y2, xm, a);
		solve(y1, xm, y2, x2, cnt - a);
	}
}

int main()
{
	scanf("%d%d%d%d", &H, &W, &N, &K);
	solve(0, 0, H, W, N);

	int ret = 0;
	int pw = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			ret += C[i][j] * pw;
			ret %= K;
			pw = pw * 2 % K;
		}
	}
	int aa = ask(0, 0, 20, 20);
	while (score(n_query) > aa) {
		ask(0, 0, 1, 1);
	}

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


Measured memory_bytes: 596
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

 
const int MAXN = 200+10;
struct Node{
	int x;
	int y;
	int col;
}nod[MAXN];

set<int,greater<int> >s1;

int cmp1(Node a,Node b){
	return a.x<b.x;
}

int main(){
	int N = 0;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d %d",&nod[i].x,&nod[i].y);
		nod[i].col = 0;
	}
	for(int i=N;i<2*N;i++){
		scanf("%d %d",&nod[i].x,&nod[i].y);
		nod[i].col = 1;
	}
	sort(nod,nod+2*N,cmp1);
	int ans = 0;
	
	for(int i=0;i<2*N;i++){
		if(nod[i].col==0)	s1.insert(nod[i].y);
		else{
			int p = nod[i].y;
			set<int,greater<int> >::iterator it = s1.begin();
			int q;
			for(it;it!=s1.end();it++){
				q = *it;
				if(q<p){
					it = s1.erase(it);
					ans++;
					break;
				}
			}
		}
	}
	printf("%d\n",ans);
	
	return 0;
}



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


//SHORTCUTS

#define ll long long
#define endl '\n'
#define i1(a) cin>>a
#define i2(a,b) cin>>a>>b
#define i3(a,b,c) cin>>a>>b>>c
#define o1(a) cout<<a<<endl
#define o2(a,b) cout<<a<<" "<<b<<endl
#define o3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define f(i,a,b) for(int i = a;i<b;i++)
#define fe(i,a,b) for(int i = a;i<=b;i++)
#define fi(i,a,b) for(i=a;i<b;i++)
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair


// DEBUG CODE & FAST OUTPUT

#define printv(a) for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
#define printvl(a) for (int i = 0; i < a.size(); i++) cout << a[i] << endl;
#define printa(a, n) for (int i = 0; i< n; i++) cout << a[i] << ' ';
#define printal(a, n) for (int i = 0; i < n; i++) cout << a[i] << endl;


//DATA STRUCTURES

#define pq priority_queue
#define ms multiset
// #define y0 _y0_
// #define y1 _y1_
// #define div divi

typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;


//IMP CONSTANT
const int mod = 1e9 + 7, inf = 1e9 + 7;
const ll infll = 1e18 + 7;
bool google_contest = false;

//MODULAR OPERATIONS
ll myadd(ll a,ll b){
    ll ans = a+b;
    ans-= ans>=mod ? mod : 0;
    return ans; 
}
ll mysub(ll a, ll b){
    return (a-b+mod)%mod;
}
ll mymul(ll a,ll b){
    return (a*b)%mod;
}
ll mypow(ll a, ll b){
    ll ans = 1;
    while(b>0)
        if(b&1) ans = mymul(ans,a),b--;
        else a = mymul(a,a),b >>= 1;
    return ans;
}
ll nCr(ll n,ll r){
    if(r==0)return 1;
    if(r==1)return n;
    if(n==0)return 0;
    return mymul(n,mymul(nCr(n-1,r-1),mypow(r,mod-2)));
}




const int dx[4] = {1, -1, 0,  0};
const int dy[4] = {0, 0,  1, -1};
//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    | 



int main(){

ios_base::sync_with_stdio(0);
cin.tie(0); 
cout.tie(0);

int t,tt;
t=1;
// i1(t);
if(google_contest)tt=1;

while(t--){
string s;
i1(s);

cout<<s[0]<<s[1]<<s[2]<<endl;


if(google_contest){
    cout<<"Case "<<tt++<<": ";
}
}

return 0;   
}


//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    |   OVER!!!!



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

int main() {
  bool ask=false;
  vector<bool>aska(1000000010);
  int N;
  cin>>N;
  rep(i,N){
    int x;
    cin>>x;
    if(aska[x]==false){
      aska[x]=true;
    }
    else if(aska[x]==true){
      ask=true;
    }
  }
  if(ask) cout<<"NO";
  else  cout<<"YES";
}


Measured memory_bytes: 122368
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; // [9,223,372,036,854,775,807 to -9.....808] 19 digits
typedef long double ld;
#define inc(i, a, b) for (long long int i = a; i <= b; i++)
#define dec(i, a, b) for (long long int i = a; i >= b; i--)
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define lv vector<ll>
#define cv vector<char>
#define dv vector<ld>
#define rall(c) (c).rbegin(), (c).rend()
#define lpr pair<ll, ll>
#define mp make_pair
#define cin(c) \
    ll c;      \
    cin >> c;
#define lmap unordered_map<ll, ll>
#define vinp(a, n) \
    inc(i, 1, n)   \
    {              \
        cin(k);    \
        a.pb(k);   \
    }
#define LIM 1000000007
#define F first
#define S second
#define fr(i, n) inc(i, 0, n - 1)
#define fri(n, a) \
    inc(i, 0, n - 1) { cin >> a[i]; }
#define end cout << "\n";
#define debug(p) cout << p;
#define umap unordered_map
#define uset unordered_set
#define fill(a, val, n) \
    inc(i, 0, n - 1) { a[i] = val; }
void i_love_Accepted()
{
    ll x;
    cin>>x;
    ll p=x;
    ll ans=0;
    while(x!=0)
    {
        ans++;
        x=(p*ans)%360;
    }
    cout<<ans;
}   
int main()
{
    fast;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        i_love_Accepted();
        end;
    } 
}



Measured memory_bytes: 3648
#include<iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  int M;
  int ans=0;
  for(int i=0;i<N;i++){
    int P;
    cin>>P;
    if(i==0)M=P,ans++;
    else{
      M=min(M,P);
      if(M==P)ans++;
    }
  }
  cout<<ans<<endl;
}


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

int main() {
	string	s;
	while (cin >> s, s != "-")
	{
		int	na;
		cin >> na;
		rep(i, na)
		{
			int nb;
			cin >> nb;
			s = s.substr(nb) + s.substr(0, nb);
		}
		cout << s << endl;
	}
}



Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,i,j;
	cin>>n>>k;
	int cost[n];
	int h[n];
	cost[0]=0;
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	cost[1]=abs(h[1]-h[0]);
	for(i=2;i<n;i++)
	{
		int x=INT_MAX;
		j=1;
		//cout<<"i="<<i<<endl;
		if(k<=i)
		{
			//cout<<"if================="<<endl;
		
			while(j<=k)
			{
				x=min((cost[i-j]+abs(h[i]-h[i-j])),x);
				//cout<<"j="<<j<<endl;
				//cout<<"x="<<x<<endl;
				j++;	
			}
	
		cost[i]=x;
		}
		else
		{
			//cout<<"else================"<<endl;
			j=i-1;
			while(j>=0)
			{
			x=min((cost[j]+abs(h[i]-h[j])),x);
			//cout<<"j="<<j<<endl;
			//cout<<"x="<<x<<endl;
			j--;	
			}
	
			cost[i]=x;
		}
	}
	cout<<cost[n-1]<<endl;
}

Measured memory_bytes: 1024
import math
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // math.gcd(ans, a[i])

tmp = ans - 1
mod = 0
f = 0
for i in range(N):
    mod = tmp % a[i]
    f += mod
print(f)

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

int main()
{
    char ch[2][3];
    int i,j;
    for(i = 0 ; i < 2; i++)
    {
        for(j = 0; j < 3; j++)
        {
            scanf("%c",&ch[i][j]);
        }
        getchar();
    }
    for(i = 0 ; i < 2; i++)
    {
        for(j = 0; j < 3; j++)
        {
            if(ch[1-i][2-j]!=ch[i][j])
            {
                printf("NO");
                return 0;
            }
        }
    }
    printf("YES");
    return 0;


}


Measured memory_bytes: 128
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    res = 0
    r = 1000000007
    for k in range(K, N+2):
        # print(N-k+2, N+1, 1, k)
        res += (sigma(N-k+2, N+1) - sigma(1, k) + 1)
        res %= r

    print(res)


def sigma(left, right):
    return (right - left + 1) * (left + right) // 2


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


if __name__ == '__main__':
    main()


Measured memory_bytes: 64704
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  int s,u,d;
  string ans;
  cin >> s;

  u= s/100;
  d= s%100;

  if(1 <= d && d <= 12 && 1 <= u && u <= 12 )
    ans= "AMBIGUOUS";
  else if(1 <= d && d <= 12 )
    ans= "YYMM";
  else if(1 <= u && u <= 12 )
    ans= "MMYY";
  else
    ans= "NA";

  cout << ans << endl;
}


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

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

    string ans = "";
    if (a == b) {
        for (int i = 0; i < a; ++i) {
            ans += to_string(a);
        }
    }

    if (a > b) {
        for (int i = 0; i < a; ++i) {
            ans += to_string(b);
        }
    } else if (a < b) {
        for (int i = 0; i < b; ++i) {
            ans += to_string(a);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
# https://atcoder.jp/contests/abc133/tasks/abc133_d

n = gets.to_i
nums = gets.split.map(&:to_i)

sum = nums[0] * 2
res = Array.new(n - 1)

sign = -1
1.upto(n - 1) do |i|
  num = nums[i]
  sum += 2 * num * sign
  sign *= -1
end

res[0] = sum / 2

(n - 1).downto(1) do |i|
  next_i = i == n - 1 ? 0 : i + 1
  res[i] = 2 * nums[i] - res[next_i]
end

puts res.join(' ')

Measured memory_bytes: 14084
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define vel vector<int>
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
	int ans = 0;
	int n; cin >> n;
	int cab = 0, ca = 0, cb = 0;
	rep(i, n) {
		string s; cin >> s;
		int sz = s.length();
		rep(i, sz - 1) {
			if (s[i] == 'A' and s[i + 1] == 'B') { ans++; }
		}
		if (s[0] == 'B' and s[sz-1] == 'A') { cab++; }
		else if (s[0] == 'B') { cb++; }
		else if (s[sz - 1] == 'A') { ca++; }
	}
	ans += cab;
	ans += min(ca, cb);
	if (ca==0 and cb == 0 and cab != 0) { ans--; }
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int x,a,b,z,y;
    cin>>x>>a>>b;
    z=(x-a);
    y=(x-b);
    if(z<0)
     z*=-1;
    if(y<0)
     y*=-1;
    if(z>y)
    cout<<"B"<<endl;
    else
    cout<<"A"<<endl;
    return 0;

}

Measured memory_bytes: 256
N,K =map(int,input().split())
a = list(map(int,input().split()))
# print(a*K)
count = 0
dis = 0
mod = (10**9+7)
for i in a:
    for k in a:
        if k < i:
            count +=1
        count %= mod
for i in range(N):
    for k in a[i:]:
        if k<a[i]:
            dis += 1
        dis %= mod
print(int((K * dis + K * (K - 1) * count // 2) % mod))

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
using namespace std;

int  main()
{
  ios::sync_with_stdio(false);

  long long N,K;
  cin>>N>>K;
  vector<vector<long long>>dp(N+1,vector<long long >(K+1,-1));
  vector<long long  >a(N+1);
  for(long long i=0;i<N;i++)
  {
    cin>>a[i+1];
  }
  for(long long i=0;i<K+1;i++)
  {
    if(a[1]>=i)dp[1][i]=i+1;
    else  dp[1][i]=a[1]+1;
  }
  for(long long i=2;i<N+1;i++)
  {
    dp[i][0]=1;
    for(long long j=1;j<K+1;j++)
    {
      if(j>a[i])dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-a[i]-1];
      else dp[i][j]=dp[i][j-1]+dp[i-1][j];
      dp[i][j]%=1000000007;
    }
  }
  if(dp[N][K]<0){dp[N][K]+=(long long)10*1000000007;}
  dp[N][K]%=1000000007;
  long long res=dp[N][K]-dp[N][K-1];
  if(res<0){res+=(long long)10*1000000007;}
  res%=1000000007;
  if(K>0){cout<<res;return 0;}
  cout<<dp[N][K];
  cout<<endl;

}


Measured memory_bytes: 80256
int main()
{
  int t[4][3][10]={0};
  int b,f,r,v,i,j,k,n;
  scanf("%d",&n);
  for(i=0;i<n;i++){
  scanf("%d%d%d%d",&b,&f,&r,&v);
t[b-1][f-1][r-1]=t[b-1][f-1][r-1]+v;
 
       
     
  }
  for(i=0;i<4;i++){
    for(j=0;j<3;j++){
      for(k=0;k<10;k++){
    printf(" %d",t[i][j][k]);
      }
      printf("\n");
    }
    if(i!=3)printf("####################\n");
  }
  return 0;
}


Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
int main() {
  int a,b,h,m;
  double c,d,t,x;
  cin>>a>>b>>h>>m;
  c=30.0*(h+m/60.0);
  d=6.0*m;
  t=max(d-c,c-d);
  if(t>180.0) t=360.0-t;
  t*=M_PI/180.0;
  x=pow(-2.0*a*b*cos(t)+a*a+b*b,0.5);
  cout<<fixed<<setprecision(20)<<x<<endl;
}

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

int main(){
    unsigned long N, M;
    cin >> N >> M;
    class union_find{
        vector<long> parent, tree_size;
    public:
        union_find(unsigned long _n) : parent(_n), tree_size(_n, 1){
            for(unsigned long i = 0; i < _n; ++i)parent[i] = i;
        }
        long find(long x){
            while(parent[x] != x)x = parent[x] = parent[parent[x]];
            return x;
        }
        bool marge(long a, long b){
            a = find(a);
            b = find(b);
            if(a == b)return false;
            if(tree_size[a] < tree_size[b])swap(a, b);
            tree_size[a] += tree_size[b];
            parent[b] = a;
            return true;
        }
    } uf{N};
    unsigned long ans{N};
    for(unsigned long i = 0, a, b, c; i < M; ++i){
        cin >> a >> b >> c;
        ans -= uf.marge(a - 1, b - 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import itertools
import bisect

def read():
    N = int(input().strip())
    L = list(map(int, input().strip().split()))
    return N, L

def solve(N, L):
    L.sort()
    x = 0
    t = [0 for _ in range(N+1)]
    for i in range(N):
        for j in range(i+1, N):
            k = bisect.bisect_left(L, L[i] + L[j])
            if j < k:
                x += (k - j - 1)
    return x

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


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

int N;
int A[210];        

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i];

    int res = 0;

    
    while (true) {
        bool exist_odd = false;  
        for (int i = 0; i < N; ++i) {
            if (A[i] % 2 != 0) exist_odd = true;  
        }

        if (exist_odd) break;  
       
        for (int i = 0; i < N; ++i) {
            A[i] /= 2;
        }
        ++res;  
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n ;
    map < string , int > m;
    m.clear();
    while(n--) {
        string s;
        cin >> s;
        m[s]++;
    }
    cout << m.size() <<endl;
}


Measured memory_bytes: 19220
S = input()
pre, lat = int(S[0:2]), int(S[2:4])
pre_M = 1 <= pre <= 12
lat_M = 1 <= lat <= 12
if pre_M and lat_M:
  print("AMBIGUOUS")
elif pre_M:
  print("MMYY")
elif lat_M:
  print("YYMM")
else:
  print("NA")

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            String str = sc.next();
            if(str.equals("-")){
                break;
            }
            int n = sc.nextInt();
            for(int i=0;i<n;i++){
                int r = sc.nextInt();
                String x = str.substring(0,r);
                String y = str.substring(r);
                str = y+x;
            }
            System.out.println(str);
            }
        sc.close();
        }    
    }

     


Measured memory_bytes: 26472
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(const T a, const T b){return a>=0 ? a/b : (a+1)/b-1;}
template<class T> T div_ceil(const T a, const T b){return a>=0 ? (a-1)/b+1 : a/b;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

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

int main(){
    int t, n;
    while(scanf("%d%d", &t, &n) && t){
        set<pii> S, used;
        rep(i, n){
            int x, y;
            scanf("%d%d", &x, &y);
            S.emplace(x, y);
        }
        int sx, sy;
        scanf("%d%d", &sx, &sy);
        queue<pair<pii, int>> que;
        que.push({{sx, sy}, 0});
        used.emplace(sx, sy);
        while(!que.empty()){
            int x, y, td;
            tie(x, y) = que.front().fi;
            td = que.front().se;
            que.pop();
            if(td == t) continue;
            rep(i, 6){
                int nx = x+dx[i], ny = y+dy[i];
                if(S.find({nx, ny}) == S.end() && used.find({nx, ny}) == used.end()){
                    used.emplace(nx, ny);
                    que.push({{nx, ny}, td+1});
                }
            }
        }
        printf("%d\n", used.size());
    }
}


Measured memory_bytes: 3420
#include <stdio.h>

int main(void)
{
    int num_int;
    scanf("%d", &num_int);

    if (num_int == 0) {
        printf("undefined\n");
    } else {
        int in_int_1;
        scanf("%d", &in_int_1);
        int min, max;
        long sum;
        min = max = sum = in_int_1;

        int i;
        for (i = 2; i <= num_int; i++) {
            int in_int_i;
            scanf("%d", &in_int_i);

            if (min > in_int_i) {
                min = in_int_i;
            }

            if (max < in_int_i) {
                max = in_int_i;
            }

            sum += in_int_i;
        }

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

Measured memory_bytes: 600
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

#define rep(i, n) for(long int i = 0; i < n; i++)
#define P pair<int, int>
#define ll long long
typedef vector<int> vec;
typedef vector<vec> mat;

int main(){
    ll n;
    cin >> n;
    ll a[n];
    bool flag = false;
    rep(i, n) {
        cin >> a[i];
        if(a[i] == 0) flag = true;
    }
    if(flag){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1;
    rep(i, n){
        ll ans_n = ans * a[i];

        if(ans_n < ans){
            cout << -1 << endl;
            return 0;
        }
        ans = ans_n;
    }
    if(ans <= 1000000000000000000){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    
}


Measured memory_bytes: 4412
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    in_arr(int, a, n);
    
    ll ans = LLONG_MAX;
    rep(i, n - k + 1){
        ll min_ = a[i], max_ = a[i + k - 1];
        if(max_ >= 0){
            ans = min(ans, max_ + 2 * abs(min((ll)0, min_)));
        }
        if(min_ <= 0){
            ans = min(ans, abs(min_) + 2 * max((ll)0, max_));
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> island;
    rep(i, M){
        int a, b;
        cin >> a >> b;
        if(a == 1) island.push_back(b);
        if(b == N) island.push_back(a);
    }

    sort(island.begin(), island.end());
    int tmp = island[0];
    FOR(i, 1, island.size()){
        if(tmp == island[i]){
            cout << "POSSIBLE" << endl;
            return 0;
        }else{
            tmp = island[i];
        }
    }
    
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

Measured memory_bytes: 1400