akhauriyash/Code-Regression huggingface dataset:
import bisect

N = int(input())
creatures = list(map(int, input().split()))

creatures.sort()
cumsum = [0]
tmp = 0
for c in creatures:
    tmp += c
    cumsum.append(tmp)

count = 0
for i,c in enumerate(creatures):
    index_new = 0
    index_old = i 
    t = cumsum[i+1]
    #print(f'{i=}')
    #print(f'{t=}')
    while True:
        index_new = bisect.bisect_right(creatures,t*2)
        if N == index_new:
            #print(f'{i=}')
            count += 1
            break
        if index_old+1 < index_new:
            t = cumsum[index_new]
            #print(f'{i=} {t=}')
            index_old = index_new-1
        else:
            break

print(count)


Measured memory_bytes: 14608
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

int main() {
	int x;
	cin >> x;
	if (x == 0)cout << 1;
	else cout << 0;
	return 0;
}

Measured memory_bytes: 3620
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[210001],i,j,k,n,l,r,ans,m;
bool check(int x){
	int i;
	ll k=0;
	for (i=1;i<=x;i++) k+=a[i];
	for (i=x+1;i<=n;i++)
	 if (2LL*k<a[i]) return 0;else k+=a[i];
	return 1;
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (l=1,r=n;l<r-1;){
		m=(l+r)>>1;
		if (check(m)) r=m;else l=m+1;
	}
	ans=(check(l))?l:r;
	printf("%d\n",n-ans+1);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i, n) for (int i = 0; i < ((int)(n)); i++) // 0-indexed昇順

int main()
{
  int X,Y,Z;
  cin >> X >> Y >>Z;
  X -= Z;
  cout << X / (Y +Z) << endl;
}

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

//

#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define LL long long

int n;
LL a[1024*256];
LL b1[1024*256],b2[1024*256];
LL c[1024*256];

int main(){
  cin>>n;
  REP(i,1<<n){
    cin>>a[i];
    b1[i]=a[i];
    b2[i]=0;
  }
  REP(i,n){
    REP(j,1<<n){
      if((1<<i)&j){
	if(b2[j]<b1[j ^ (1<<i)]){
	  if(b1[j]<b1[j ^ (1<<i)]){
	    b2[j]=b1[j];
	    b1[j]=b1[j ^ (1<<i)];
	    if(b2[j]<b2[j ^ (1<<i)])
	      b2[j]=b2[j ^ (1<<i)];
	  }else{
	    b2[j]=b1[j ^ (1<<i)];
	  }
	}
      }
    }
  }

  c[1]=b1[1]+b2[1];
  FOR(i,2,1<<n)
    c[i]=max(c[i-1],b1[i]+b2[i]);
  FOR(i,1,1<<n)
    cout<<c[i]<<endl;
  return 0;
}


Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 2e5+7, INF = 5e18;
vector <ii> g[N];
int d[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, m;
    cin >> n >> m;

    for (int i = 1; i < n; ++i) 
        g[i+1].app(mp(i, 0));

    for (int i = 0; i < m; ++i) {
        int l, r, c;
        cin >> l >> r >> c;
        g[l].app(mp(r,c));
        g[r].app(mp(l,c));
    }   
    
    for (int i = 2; i <= n; ++i)
        d[i] = INF;

    priority_queue <ii> q;
    q.push(mp(0, 1));
    while (q.size()) {
        auto t = q.top();
        q.pop();

        int u = t.s;
        if (u == n) {
            cout << d[n] << endl;
            exit(0);
        }   

        //cout << u << ' ' << d[u] << endl;

        for (auto e : g[u]) {
            int v = e.f, c = e.s;
            if (d[u]+c < d[v]) {
                d[v] = d[u]+c;
                q.push(mp(-d[v],v));
            }   
        }   
    }   
    cout << -1 << endl;
}

Measured memory_bytes: 18464
function main()
	L=Char[]
	R=Char[]
	for c=chomp(readline())
		push!(R,c)
	end
	t=0
	readline()
	for s=readlines()
		if s[1]=='1'
			t=1-t
		else
			_,f,c=split(s)
			if(f=="1")!=(t==1)
				push!(L,c[1])
			else
				push!(R,c[1])
			end
		end
	end
	if t==1
		L,R=R,L
	end
	for c=reverse(L)
		print(c)
	end
	for c=R
		print(c)
	end
	println()
end
main()


Measured memory_bytes: 162304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<ll>>;

ll N, M;
Graph G;
ll dp[100010];

ll solve(ll v)
{
	if (dp[v] != -1) return dp[v];

	ll res{0};
	for (auto &nv : G[v])
	{
		res = max(res, solve(nv)+1);
	}
	return dp[v] = res;
}

int main(int argc, char **argv)
{
	cin >> N >> M;
	G.resize(N);

	for (ll i = 0; i < M; ++i)
	{
		ll a, b; cin >> a >> b; --a, --b;
		G[a].push_back(b);
	}

	for (ll i = 0; i <= N; ++i) dp[i] = -1;
	
	ll res{0};
	for (ll v = 0;v < N; ++v) res = max(res, solve(v));
	std::cout << res << std::endl;
}


Measured memory_bytes: 8576
// Beginner159.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <climits>
#include <vector>

using namespace  std;

bool is_strong_pa(const string& s, int from, int to)
{
	bool is_pal = true;

	for (int i = from; i <= (to-from)/2; ++i)
	{
		if (s[i] != s[to-i])
		{
			is_pal = false;
			break;
		}
	}
	
	return is_pal;
}

int main()
{
	/*int n, m;
	cin >> n >> m;

	int sum = 0;
	sum += n * (n - 1) / 2;
	sum += m * (m - 1) / 2;
	cout << sum;*/

	/*string s;
	cin >> s;

	const int n = s.length();

	bool is_pal = is_strong_pa(s, 0, n - 1) &&
		is_strong_pa(s, 0, (n - 1) / 2 - 1) &&
		is_strong_pa(s, (n + 3) / 2 - 1, n - 1);

	cout << (is_pal ? "Yes" : "No");*/

	int l;
	cin >> l;

	double side = 1.0*l / 3;
	double res = side * side * side;

	cout.precision(10);

	cout << res;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>; // (city, city)

struct UnionFind {
    vector<int> rank;
    vector<int> parent;

    void init(int n) {
        rank = vector<int>(n);
        parent = vector<int>(n);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        return parent[x] = (x == parent[x] ? x : find(parent[x]));
    }

    void unite(int x, int y) {
        int px = find(x);
        int py = find(y);

        if(px == py)  return;
        if(rank[px] == rank[py]) {
            parent[px] = py;
            rank[py]++;
        }
        else if(rank[px] < rank[py])
            parent[px] = py;
        else
            parent[py] = px;
    }
};

int n, k, l;
UnionFind road;
UnionFind railway;

int main() {
    cin >> n >> k >> l;
    road.init(n+1);
    railway.init(n+1);

    for(int i = 1; i <= k; i++) {
        int p, q;
        cin >> p >> q;
        road.unite(p, q);
    }

    for(int i = 1; i <= l; i++) {
        int r, s;
        cin >> r >> s;
        railway.unite(r, s);
    }

    map<P, int> mp;
    for(int i = 1; i <= n; i++)
        mp[P(road.find(i), railway.find(i))]++;

    for(int i = 1; i <= n; i++) {
        cout << mp[P(road.find(i), railway.find(i))];
        cout << (i == n ? "\n" : " ");
    }
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
 
int main(){
   int N;
   cin>>N;
   vector<int>v(N);
   for(int i = 0; i<N;i++){
       cin>>v.at(i);
   }
   sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  cout<<v.at(0)-v.at(N-1)<<endl;
 
}

Measured memory_bytes: 3600
#include<stdio.h>

int main(){
 double v;

 while(scanf("%lf",&v)!=EOF){
  v=v/9.8;
  v=v*v*4.9+5.0;
  if(v!=(double)((int)v)){
   printf("%d\n",(int)(v/5+1.0));
  }else{
   printf("%d\n",(int)(v/5));
  }
 }
 return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

string str;
int ct[27];
int a;
int main()
{
	cin >> str;
	for (auto it:str)
	{
		ct[it-'A']++;
	}
	for (int i = 0; i<26; i++)
	{
		if (ct[i] == 2)
			a++;
	}
	cout << (a==2?"Yes":"No");
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999

int n, v[52];
double ans = 0;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v, v + n);
	ans = (double)v[0];
	for (int i = 1; i < n; i++) {
		ans = ((double)v[i] + ans) / 2.0;
	}
	cout << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 256
INF = 10 ** 20
n = int(input())
s = input()

w_cum = [0]
e_cum = [0]

w_acc = 0
e_acc = 0
for i in range(n):
  if s[i] == "W":
    w_acc += 1
  else:
    e_acc += 1
  w_cum.append(w_acc)
  e_cum.append(e_acc)

ans = INF
for i in range(1, n + 1):
  ans = min(ans, w_cum[i - 1] + e_cum[-1] - e_cum[i])

print(ans)

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

using namespace std;

int main()
{

  int N,i;
  cin >> N;
  vector<int> ans(N+1);

  for(i=2;i<=N;i++){
    int a;
    cin >> a;
    ans[a]++;
  }

  for(i=1;i<=N;i++)
  cout << ans[i] << endl;

  return 0;
}


Measured memory_bytes: 4048
#include<bits/stdc++.h>
using namespace std;
long long n,a,maxx,minn=10000000000;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		maxx=max(maxx,a);
		minn=min(minn,a);
	}
	cout<<maxx-minn;
	return 0;
}

Measured memory_bytes: 256
import itertools

n, m, x = map(int, input().split())

l = []
for i in range(n):
    l.append([int(x) for x in input().split()])

p = list(itertools.product([0, 1], repeat=n))

lc = []
for i in range(2 ** n):
    list_sum_k = []
    for k in range(1, m+1):
        sum_c = 0
        sum_k = 0
        for j in range(n): #上からj行目を加算の対象とする
            if p[i][j] == 1: #j行目の和をk(1-m)について出す
                sum_c += l[j][0]
                sum_k += l[j][k]
        list_sum_k.append(sum_k)
    #print(sum_c)
    #print(list_sum_k)
    if all(k >= x for k in list_sum_k):
        #print('reach')
        lc.append(sum_c)
        #print(lc)

if not lc:
    print('-1')
else:
    print(min(lc))

Measured memory_bytes: 9660
#include<stdio.h>
int main()
{
    int A,B,c,d;
    scanf("%d%d",&A,&B);
    c=B*2;
    d=(A-c);
    if(A<=c)
    {
        printf("0");

    }
    else
    {
        printf("%d",d);

    }
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
 ll n,m;
 cin>>n>>m;
  if(n==m){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}
  

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

using namespace std;


int main(){

	string s,t;
	cin>>s>>t;
	bool flag=true;
	int n = t.size();
	for(int i=0; i<n-1; i++){
		if(s[i]!=t[i]){
			cout<<"No"<<endl;
			flag=false;
			break;
		}
	}
	if(flag==true) cout<<"Yes"<<endl;
}

Measured memory_bytes: 3624
#include<stdio.h>

int main(){
int i,j=0;
char c;

//while((c=getchar())!=EOF){
//string[j]=c;
//j++;
//}

scanf("%c",&c);

//for(i=0;i<=j;i++){
if(c>='A'&&c<='Z'){
printf("A\n");
}else if(c>='a'&&c<='z'){
printf("a\n");
}
//}
}

Measured memory_bytes: 1592
import math
A,B,H,M=map(int,input().split())

degA = (30*H+0.5*M)/360*(2*math.pi)
degB = 6*M/360*(2*math.pi)
xa = A*math.cos(degA)
ya = A*math.sin(degA)
xb = B*math.cos(degB)
yb = B*math.sin(degB)
res = ((xa-xb)**2+(ya-yb)**2)**0.5
print(res)


Measured memory_bytes: 9572
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

// ModInt
// region
class ModInt(x: Long) {

    companion object {
        const val MOD = 1000000007L
        //const val MOD = 998244353L
    }

    val x = (x % MOD + MOD) % MOD

    operator fun plus(other: ModInt): ModInt {
        return ModInt(x + other.x)
    }

    operator fun minus(other: ModInt): ModInt {
        return ModInt(x - other.x)
    }

    operator fun times(other: ModInt): ModInt {
        return ModInt(x * other.x)
    }

    operator fun div(other: ModInt): ModInt {
        return this * other.inv()
    }

    fun pow(exp: Long): ModInt {
        if (exp == 0L) return ModInt(1L)
        var a = pow(exp shr 1)
        a *= a
        if (exp and 1L == 0L) return a
        return this * a
    }

    fun inv(): ModInt {
        return this.pow(MOD - 2)
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as ModInt

        if (x != other.x) return false

        return true
    }

    override fun hashCode(): Int {
        return x.hashCode()
    }

    override fun toString(): String {
        return "$x"
    }

}

val fac = mutableListOf<ModInt>()
val invfac = mutableListOf<ModInt>()

fun fact(n: Long, b: Boolean): ModInt {
    if (fac.count() == 0) {
        fac.add(ModInt(1))
        invfac.add(ModInt(1))
    }
    while (fac.count() <= n) {
        fac.add(fac.last() * ModInt(fac.count().toLong()))
        invfac.add(fac.last().inv())
    }
    return if (b) {
        fac[n.toInt()]
    } else {
        invfac[n.toInt()]
    }
}

fun comb(n: Long, k: Long): ModInt {
    return fact(n, true) * fact(k, false) * fact(n - k, false)
}

fun comb2(n: Long, k: Long): ModInt {
    var ans = ModInt(1)
    for (i in 0 until k) {
        ans = ans * ModInt(n - i) / ModInt(k - i)
    }
    return ans
}
// endregion

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val a = Array(n) { ModInt(sc.nextLong()) }
    var sum = ModInt(0)
    var sqsum = ModInt(0)
    for (i in 0 until n) {
        sum += a[i]
        sqsum += a[i] * a[i]
    }
    println((sum * sum - sqsum) / ModInt(2))
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 62856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1LL<<60;
const int INF = 1LL<<17;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ll bit[500500];
ll n;
#define N 500010

void add(ll i, ll x){
    while(i<=n){
        bit[i] += x;
        i += i&-i;
    }
}

ll sum(ll i){
    ll res=0;
    while(0<i){
        res += bit[i];
        i -= i&-i;
    }
    return res;
}
// int sum(int i){
//     int res=0;
//     for(;i>0;i-=i&-i)res+=bit[i];
//     return res;
// }
ll rsum(ll l, ll r){
    return sum(r)-sum(l-1);
}
vector<vector<ll>> qr(N), qri(N);
vector<ll> a(N), c(N), res(N);
int main(){
    ll q;   cin >> n >> q;


    rep(i, n) cin >> c[i+1];
    
    rep(i, q){
        ll a, b;    cin >> a >> b;
        qr[b].push_back(a);
        qri[b].push_back(i);
    }

    FOR(i, 1, n+1){
        if(a[c[i]]>0) add(a[c[i]], -1);
        add(i, 1);
        a[c[i]] = i;
        rep(j, qr[i].size()){
            res[qri[i][j]] = rsum(qr[i][j], i);
        }
    }
    rep(i, q) cout << res[i] << endl;
}


Measured memory_bytes: 62632
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(t) for(ll i=0;i<t;i++)
#define ll long long int
#define ld long double
#define umpl unordered_map<ll,ll> 
#define vl vector<ll>
#define vld vector<ld>
#define vvl vector<vl>
#define pb push_back
#define mod 1000000007
#define inf 1e18
#define pcout(x,p) cout<<fixed<<setprecision(p)<<x
#define all(a) a.begin(),a.end()
#define endl "\n"

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c >= mod) c -= mod; return c; }
inline ll max(ll a, ll b){return a>b?a:b;}
inline ll min(ll a, ll b){return a<b?a:b;}
inline ll ceil(ll a,ll b){if(a%b==0)return a/b;else return a/b+1;}
inline ll mo(ll a,ll b){if(b<0){b=abs(b)%mod;b=a-b;return (b<0)?b+mod:b;}else{return (a+b)%mod;}}
inline ll pow(ll a,ll b){if(b==0){return 1;}else{if(b%2==0){ll temp=pow(a,b/2);return temp*temp;}
else{return a*pow(a,b-1);}}}

struct comp { 
    template<class T1,class T2,class T3,class T4>
    bool operator()(const pair<T1,T2> &p1,const pair<T3,T4> &p2){
        if(p1.first!=p2.first)return p1.first<p2.first;
        else return p1.second<p2.second;
    }
}; 

int main()
{
    fio;
    ll n;cin>>n;
    vl a(n);
    f(n)cin>>a[i];
    vl dp(n,inf);
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(ll i=2;i<n;i++){
        dp[i]=min(abs(a[i]-a[i-1])+dp[i-1],abs(a[i]-a[i-2])+dp[i-2]);
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 4688
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int h[10];
	for(int i=0;i<10;i++) {
		scanf("%d",&h[i]);
	}
	sort(h,h+10);
	for(int i=0;i<3;i++) {
		printf("%d\n",h[9-i]);
	}
}

Measured memory_bytes: 1044
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<fstream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	string s;
	cin>>s;
	for(int i=0;i<=a+b;i++)
	{
		if(i==a&&s[i]!='-')
		{
			cout<<"No"<<endl;
			return 0; 
		}
		if(i!=a&&(s[i]<'0'||s[i]>'9'))
		{
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl; 
	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  
  long h[N];
  long dp[N];
  for (int i = 0; i < N; i++) {
    cin >> h[i];
    dp[i]=LONG_MAX;
  }
  
  dp[0]=0L;
  for (int i = 0; i < N; i++) {
    for (int j = 1; j <= K ; j++) {
      if(i+j>=N) break;
      dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
    }
  }
  
  cout << dp[N-1] << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
    chutiyaap;
    string s,t;cin>>s>>t;
    int n=s.length();
    if(t.length()!=n+1)cout<<"No";
    else
    {
        int cnt=0;
        for(int i=0;i<n;i++)if(s[i]==t[i])cnt++;
        if(cnt==n)cout<<"Yes";
        else cout<<"No";
    }
}


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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    ll a[n];
    ll sum = 0;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++){
        sum ^= a[i];
    }
    if(sum) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
void trace(int A[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}

void insertionSort(int A[],int N){
  int i,j,v;
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j >= 0&& A[j] > v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}

int main(){
  int A[100],N,i,j;
  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  trace(A,N);
  insertionSort(A,N);
  
  return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    double A,B,H,M;
    cin >> A >> B >> H >> M;
    double ans = 0;
    ans = A*A+B*B-2*A*B*cos(2.0*asin(1.0) / 180 * abs((30*H+M/2)-6*M));
    cout << sqrt(ans)<< "\n";
}

Measured memory_bytes: 4176
import sys
from queue import deque
input = sys.stdin.readline

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = deque([0])

    while nodes:
        node = nodes.pop()
        visited[node] = True
        for _node in graph[node]:
            if visited[_node]:
                continue
            points[_node] += points[node]
            nodes.append(_node)
    
    print(*points)
    
main()

Measured memory_bytes: 65320
#include <bits/stdc++.h>
using namespace std;
 int main () {
   int N, M; //N cities, M roads.
   cin >> N >> M;
   vector<int> NumberOfRoads(N);
   
   for (int i = 0; i < 2 * M; i++) {
     int city;
     cin >> city;
     NumberOfRoads.at(city - 1)++;
   }
   
   for (int i = 0; i < N; i++) {
     cout << NumberOfRoads.at(i) << endl;
   }
   
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    bool a, b, c;
    a = b = c = false;
    for (int i = 0; i < 3; i++) {
        a |= s[i] == 'a';
        b |= s[i] == 'b';
        c |= s[i] == 'c';
    }
    cout << (a && b && c ? "Yes" : "No") << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int age_lank[7];

int main(void)
{
	int age,  i, n;
	
	while (1){
		scanf("%d", &n);
		
		if (n == 0){
			break;
		}
		for (i = 0; i < n; i++){
		
			scanf("%d", &age);
		
			if (age < 10){
				age_lank[0]++;
			}
			else if (age < 20){
				age_lank[1]++;
			}
			else if (age < 30){
				age_lank[2]++;
			}
			else if (age < 40){
				age_lank[3]++;
			}
			else if (age < 50){
				age_lank[4]++;
			}
			else if (age < 60){
				age_lank[5]++;
			}
			else{
				age_lank[6]++;
			}
		}
		
		for (i = 0; i < 7; i++){
			printf("%d\n", age_lank[i]);
		}
		for (i = 0; i < 7; i++){
			age_lank[i] = 0;
		}
	}
	return (0);
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
 
using namespace std;
int n ;
long long a[200];
int main()
{
    cin >>n;
    for(int i = 1 ; i<=n ; i++)
        cin >> a[i];
    if(n == 1) return cout<<a[1] , 0;
    long long p = 1 , last = a[1];
    for(int i = 2 ; i<=n ; i++)
    {
        long long k = __gcd(last , a[i]);
        last = last/k*a[i];
    }
    cout<<last;
    return 0;
}

Measured memory_bytes: 256
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

int main() {
  init_ios();
  int a, b;
  cin >> a >> b;
  cout<<a*b<<"\n";
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char alpha;
  cin >> alpha;
  
  if (alpha=='a' || alpha=='b' || alpha=='c' || alpha=='d' || alpha=='e') {
    cout << 'a' << endl;
  }
  
  else if (alpha=='f' || alpha=='g' || alpha=='h' || alpha=='i' || alpha=='j') {
    cout << 'a' << endl;
  }
  
  else if (alpha=='k' || alpha=='l' || alpha=='m' || alpha=='n' || alpha=='o') {
    cout << 'a' << endl;
  }
  
   else if (alpha=='p' || alpha=='q' || alpha=='r' || alpha=='s' || alpha=='t') {
    cout << 'a' << endl;
  }
  
  else if (alpha=='u' || alpha=='v' || alpha=='w' || alpha=='x' || alpha=='y') {
    cout << 'a' << endl;
  }
  
  else if (alpha=='z') {
    cout << 'a' << endl;
  }
  
  else  {
      cout << 'A' << endl;
    }
    
}


Measured memory_bytes: 3640
def main():
    K = input()
    K = int(K)
    S = input()
    Slen = len(S)
    Sstr = str(S)
    
    if Slen <= K:
        print(Sstr)
    else:
        print(str(S[0:K]) + "...")

if __name__ == "__main__":
    main()

Measured memory_bytes: 9180
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	ds := make([]int, n)
	for i := range ds {
		fmt.Scan(&ds[i])
	}

	counter := make(map[int]int)
	for _, d := range ds {
		counter[d]++
	}

	fmt.Println(len(counter))
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
   string str;
   cin>>str;
  
    int sum=0;
   if(str=="SUN")
     cout<<sum+7<<endl;
   else if(str=="MON")
     cout<<sum+6<<endl;
   else if(str=="TUE")
     cout<<sum+5<<endl;
   else if(str=="WED")
     cout<<sum+4<<endl;
   else if(str=="THU")
     cout<<sum+3<<endl;
   if(str=="FRI")
     cout<<sum+2<<endl;
   else if(str=="SAT")
     cout<<sum+1<<endl;
}

Measured memory_bytes: 256
import sys

X, Y = map(int, input().split())
mod = int(1e9) + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# 組み合わせ(1e9+7で割る場合)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if (X + Y) % 3 != 0:
    print(0)
    sys.exit()

n = (-X + 2*Y) // 3
m = (2 * X - Y) // 3
if n < 0 or m < 0:
    print(0)
    sys.exit()

print(cmb(n+m, n, mod))


Measured memory_bytes: 213160
use std::io::{stdin, Read};

macro_rules! parse {
    ($iter:ident) => {
        $iter.next().unwrap().parse().unwrap()
    };
    ($iter:ident, 2) => {
        (parse!(iter), parse!(iter))
    };
    ($iter:ident, 3) => {
        (parse!(iter), parse!(iter))
    };
    ($iter:ident, 4) => {
        (parse!(iter), parse!(iter))
    };
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut iter = s.split_whitespace();
    let n: isize = parse!(iter);
    let mut se = vec![vec![0; 10]; 10];
    for mut i in 1..(n + 1) {
        let s = i % 10;
        while i >= 10 {
            i /= 10;
        }
        se[i as usize][s as usize] += 1;
    }
    let mut res = 0u64;
    for i in 0..10 {
        for j in 0..10 {
            res += se[i][j] * se[j][i]
        }
    }
    println!("{}", res);
}


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

int main(){
	int n, m; cin >> n >> m;
	string s[n];
	for (int i = 0; i < n; i++) cin >> s[i];
	for (int i = 0; i < 2 * n; i++) {
		for (int j = 0; j < m; j++) cout << s[i / 2][j];
		cout << '\n';
	}
}


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

int main() {
  long long a, b, c; cin >> a >> b >> c;
  long long d = min(a, c);
  a -= d, c -= d;
  long long e = min(b, c);
  b -= e, c -= e;
  
  cout << a << " " << b << endl;
}

Measured memory_bytes: 256
n,m=map(int, input().split())
q=[]
for i in range(m):
    a,b=map(int, input().split())
    q.append([a,b])
    q.append([b,a])
p=[[1]]
count=0
route=set()
while len(p)!=0:
    p1=p.pop()
    for i,j in q:
        #print(i,j)
        if i == p1[-1]:
            if j not in p1:
                p.append(p1+[j])
    if len(p1)==n: count+=1
    route |= {tuple(p1)}
    #print(p,p1)
print(count)

Measured memory_bytes: 4988
#include <iostream>
#include <vector>
#include <algorithm> // sort

using namespace std;

int main(){
        long long n,elem,sum=0;
        vector<long long> numArray;
        cin >> n;
        for(int i = 0; i < n; ++i){
            cin >> elem;
            numArray.push_back(elem);
            sum += elem;
        }
        sort(numArray.begin(),numArray.end());
        cout << numArray[0]  << " " << numArray[n - 1] << " " << sum << endl;
}



Measured memory_bytes: 3288
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let ab: Vec<(usize, usize)> = (1..n)
        .map(|_| {
            let a = input();
            let b = input();
            (a, b)
        })
        .collect();

    let mut path = vec![vec![]; n + 1];
    for (a, b) in ab {
        path[a].push(b);
        path[b].push(a);
    }

    let mut d1 = vec![-1; n + 1];
    d1[1] = 0;
    let mut dn = vec![-1; n + 1];
    dn[n] = 0;
    let mut q = std::collections::VecDeque::new();

    q.push_back(1);
    while !q.is_empty() {
        let i = q.pop_front().unwrap();
        for &next in &path[i] {
            if d1[next] >= 0 {
                continue;
            }

            q.push_back(next);
            d1[next] = d1[i] + 1;
        }
    }

    q.push_back(n);
    while !q.is_empty() {
        let i = q.pop_front().unwrap();
        for &next in &path[i] {
            if dn[next] >= 0 {
                continue;
            }

            q.push_back(next);
            dn[next] = dn[i] + 1;
        }
    }

    let mut m = vec![0; n + 1];
    for i in 1..n + 1 {
        if d1[i] <= dn[i] {
            m[i] = 1;
        } else {
            m[i] = 2;
        }
    }

    let c1 = m.iter().filter(|&i| *i == 1).count();
    let c2 = n - c1;

    println!("{}", if c1 > c2 { "Fennec" } else { "Snuke" });
}


Measured memory_bytes: 12540
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        init();
        int n = nextInt();

        for (int i = 0; i <= n; i++) {
            if ((int) Math.floor(i*1.08) == n) {
                System.out.println(i);
                return;
            }
        }

        System.out.println(":(");
    }

    //Input Reader
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    private static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    private static String next() throws IOException {
        String read;
        while (!tokenizer.hasMoreTokens()) {
            read = reader.readLine();
            if (read == null || read.equals(""))
                return "-1";
            tokenizer = new StringTokenizer(read);
        }

        return tokenizer.nextToken();
    }

    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

//    private static long nextLong() throws IOException {
//        return Long.parseLong(next());
//    }
//
//    //    Get a whole line.
//    private static String line() throws IOException {
//        return reader.readLine();
//    }
//
//    private static double nextDouble() throws IOException {
//        return Double.parseDouble(next());
//    }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define hell 1000000007
#define PI 3.14159265358979323846
using namespace std;

int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    //int c=0;
    while(t--) {
      ll n,w,i,j,s=0;
      cin>>n>>w;
      ll val[n+1],we[n+1];
      for(i=0;i<n;i++)
      {
          cin>>we[i]>>val[i];
          s+=val[i];
      }
      ll dp[n+1][s+1];
      for(i=0;i<=n;i++)
        dp[i][0]=0;
        for(i=1;i<=s;i++)
            dp[0][i]=hell;
      for(i=1;i<=s;i++)
      {
          for(j=1;j<=n;j++)
          {
              dp[j][i]=hell;
          //    cout<<dp[j][i]<<" ";
              if(dp[j-1][i])
                {
                    dp[j][i]=dp[j-1][i];
                //    cout<<dp[j][i]<<" ";
                }
              if(val[j-1]<=i && dp[j-1][i-val[j-1]]!=hell)
                {
                    dp[j][i]=min(dp[j][i],dp[j-1][i-val[j-1]]+we[j-1]);
              //      cout<<dp[j][i]<<" ";
                }
               // cout<<"\n";
          }
      }
      ll ans=0;
     /* for(i=0;i<=s;i++)
        cout<<i<<" "<<dp[n][i]<<"\n";*/
      for(i=s;i>=0;i--)
        {
          //  cout<<dp[n][i]<<"\n";
            if(dp[n][i]<=w)
      {

          break;
      }
        }
      cout<<i;
    }

}


Measured memory_bytes: 82480
# Problem https://atcoder.jp/contests/abc064/tasks/abc064_a
# Python 3rd Try
yes = "YES"
no = "NO"
if __name__ == "__main__":
    r, g, b = map(int, input().split(' '))
    answer = ""
    checkNo = (g*10+b) % 4
    if checkNo == 0:
        answer = yes
    else:
        answer = no
    print(answer)
exit

Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>

using namespace std;


int main() {
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	int tgt = 1;
	for (int i = 0; i < n; i++) {
		int ai;
		cin >> ai;
		if (ai == tgt) {
			tgt++;
		}
	}
	if (tgt == 1)
		cout << "-1\n";
	else
		cout << n - (tgt - 1) << "\n";
	//system("pause");
	return 0;
}

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

using namespace std;

inline void Boost() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
typedef unsigned long long int ll;
typedef long double ld;

const int NMax = 2050;

int v[NMax];
bitset < NMax * NMax > DP;


int main() {
	Boost();

	int n;
	cin >> n;

	int sum = 0;
	DP[0] = 1;
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;

		DP |= (DP << x);

		sum += x;
	}

	int ans;
	for(ans = (sum + 1) / 2; DP[ans] == 0; ++ans);

	cout << ans;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <functional>
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin >> n;

    int m_cnt = 0;
    vector<int> a(n);

    int sum = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        if(a[i] < 0){
            m_cnt++;
            sum -= a[i];
        }
        else sum += a[i];
    }

    if(m_cnt <= 1){
        sort(a.begin(),a.end());
        if(m_cnt == 0)sum -= 2 * a[0];
        cout << sum << endl;
        int now = a[0];

        for(int i = 1;i < n;i++){
            if(i != n - 1){
                cout << now << " " << a[i] << endl;
                now -= a[i];
            }else{
                cout << a[i] << " " <<  now << endl;
            }
        }
    }
    else if(m_cnt >= n-1){
        sort(a.begin(),a.end());
        if(m_cnt == n)sum += 2 * a[n-1];
        cout << sum << endl;
        int now = a[n-1];

        for(int i = 0;i < n -1;i++){
            cout << now << " " << a[i] << endl;
            now -= a[i];
        }
    }
    else{
       sort(a.begin(),a.end());
       cout << sum << endl;

       int m = a[0];
       int p = a[n-1];

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


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

#define LL long long
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }

// 4近傍（右, 下, 左, 上）
const std::vector<int> dy = { 0, -1, 0, 1 };
const std::vector<int> dx = { 1, 0, -1, 0 };

using namespace std;


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

    while (true) {
        int n, s;
        cin >> n >> s;
        if (n == 0 and s == 0) { break; }

        // dp[i][j][k] = iまで見たときにj個を使ってkをつくる組み合わせの数
        vector<vector<vector<LL>>> dp(102, vector<vector<LL>>(n + 1, vector<LL>(s + 1, 0)));
        dp[0][0][0] = 1;


        FOR(i, 0, 101) {
            for(int j = dp[0].size() - 1; j >= 0; --j) {
                for (int k = dp[0][0].size() - 1; k >= 0; --k) {
                    if (dp[i][j][k] == 0) { continue; }

                    // not use
                    dp[i + 1][j][k] += dp[i][j][k];

                    // use
                    if (j + 1 < dp[0].size() and k + i < dp[0][0].size()) {
                        dp[i + 1][j + 1][k + i] += dp[i][j][k];
                    }
                }
            }
        }

        cout << dp[101][n][s] << endl;

    }
    return 0;
}


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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string>vst;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define all(ct) ct.begin() , ct.end()
#define endl "\n"
#define fr(i,a) for(auto i:a)
#define f(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define in(d,v) d.find(v)!=d.end()
#define mp make_pair
#define size(a) int(a.size())

const int mod = 1e9 + 7;
const ll inf = ll(1e18);
const double PI = acos(-1);

ll modexp(ll x,ll n,int md){
    if(n==0)return 1;
    if(n%2==0)return modexp((x*x)%md,n/2,md);
    return (x*modexp((x*x)%md,n/2,md))%md;
}

int main(){
    fastio;
    //clock_t tm = clock();
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    ll t=(n*(n+1))/2;
    ll l=t;
    ll r=0;
    for(ll i=n+1;i>=k;--i){
        ll cr1=t-r;r+=(n+1-i);
        ll cr2=l;l-=(i-1);
        ans=(ans+(cr1-cr2+1))%mod;
    }
    cout<<ans<<endl;
    //cout<<((clock()-tm)*1.0)/CLOCKS_PER_SEC<<endl;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define ll long long
#define MAX 1000005
#define MOD (ll)(1e9+7)
#define INF INT32_MAX
#define INFL INT64_MAX
using namespace std;

void solve()	{
	int h,w;
	cin >> h >> w;
	string s[h];
	for(int i=0; i<h; i++)	cin >> s[i];
	for(int i=0; i<h; i++)	{
		bool f=1;
		for(int j=0; j<w; j++)	if(s[i][j]=='#') f=0;
		if(f)	{
			for(int j=0; j<w; j++)	s[i][j]='o';
		}
	}
	for(int i=0; i<w; i++)	{
		bool f=1;
		for(int j=0; j<h; j++)	if(s[j][i]=='#') f=0;
		if(f)	{
			for(int j=0; j<h; j++)	s[j][i]='o';
		}
	}
	for(int i=0; i<h; i++)	{
		bool f=0;
		for(int j=0; j<w; j++)	{
			if(s[i][j]!='o')	{f=1; cout << s[i][j];}
		}
		if(f) cout << endl;
	}
}

int main()	
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin >> t;
	for(int i=1; i<=t; i++)	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e6+10;
int a[maxn],b[maxn];
struct node{
	int val,loc;
}sub[maxn];
long long tre[maxn],n;
int cmp(const node &a,const node &b){
	if(a.val==b.val) return a.loc<b.loc;
	else return a.val<b.val;
}
inline int lowbit(int x){
	return x&(-x);
}
void add(int pos,int val){
	while(pos<=n){
		tre[pos]+=val;
		pos+=lowbit(pos);
	}
	return;
}
long long query(int pos){
	long long sum=0;
	while(pos>0){
		sum+=tre[pos];
		pos-=lowbit(pos);
	}
	return sum;
}
long long check(int val){
	memset(tre,0,sizeof(tre));
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]<val) sub[i].val=-1;
		else sub[i].val=1;
		sub[i].val+=sub[i-1].val;
		sub[i].loc=i;
	}
	sort(sub+1,sub+n+1,cmp);
	for(int i=1;i<=n;i++){
		add(sub[i].loc,1);
		ans+=query(sub[i].loc-1);
		if(sub[i].val>=0) ans++;
	}
	return ans;
}
int erf(int l,int r){
	int mid;
	long long _std=(n+1)*n/4+(((n+1)*n/2)&1);
	while(l<r){
		mid=(l+r+1)>>1;
		if(check(b[mid])>=_std) l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);b[i]=a[i];
	}
	
	sort(b+1,b+n+1);
	cout<<b[erf(1,n)];
	
	return 0;
}


Measured memory_bytes: 14592
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x) cout<<#x<<" = "<<(x)<<endl;
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  string s; cin >> s;
  REP(i,3) {
    if (s[i] == '1') cout << 9;
    else if (s[i] == '9') cout << 1;
    else cout << s[i] - '0';
  }
  cout << endl;
  return 0;
}

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

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

        int n;
        n = in.nextInt();

        long [][]arr = new long[n][3];
        for (int i = 0; i < n; i ++){
            arr[i][0] = in.nextLong();
            arr[i][1] = in.nextLong();
            arr[i][2] = in.nextLong();
        }

        long MAX = -1;
        for (int i = 1; i < n; i ++){
            arr[i][0] = Math.max(arr[i-1][1]+arr[i][0], arr[i-1][2]+arr[i][0]);
            arr[i][1] = Math.max(arr[i-1][0]+arr[i][1], arr[i-1][2]+arr[i][1]);
            arr[i][2] = Math.max(arr[i-1][0]+arr[i][2], arr[i-1][1]+arr[i][2]);
        }

        for (int i = 0; i < 3; i ++)
            MAX = Math.max(arr[n-1][i], MAX);

        System.out.println(MAX);
    }
}

Measured memory_bytes: 100968
N, M = map(int,input().split())
maze = [input() for _ in range(N)]
dp = [[0]*M for _ in range(N)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(M):
        if maze[i][j] != "#":
            if i-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j-1 >= 0:
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod

print(dp[N-1][M-1])

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

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int h, w, m;
    cin >> h >> w >> m;
    map<int,int> r,c;
    map<pair<int,int>,int> ma;
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        ma[{x,y}]++;
        r[x]++;
        c[y]++;
    }

    int maxRow = 0;
    for(auto t: r){
        maxRow = max(t.second,maxRow);
    }
    int maxCol = 0;
    for(auto t: c){
        maxCol = max(t.second,maxCol);
    }

    vector<int> row, col;
    for(auto t: r){
        if(t.second==maxRow) row.emplace_back(t.first);
    } 
    for(auto t: c){
        if(t.second==maxCol) col.emplace_back(t.first);
    }

    bool f = false;
    for(int i=0; i<row.size(); i++){
        // cout<<row[i]<<' ';
        for(int j=0; j<col.size(); j++){
            // cout<<col[j]<<' ';
            if(ma.find({row[i],col[j]})==ma.end()){
                f=true;
                break;
            }        
        }
        // cout<<'\n';
    }

    f?cout<<maxCol+maxRow:cout<<maxCol+maxRow-1;
    cout<<'\n';

    return 0;
}


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

typedef long long ll;
#define pa pair<int, int> 
#define pal pair<long long, long long>
#define pad pair<double, double>
#define pb push_back
#define mp make_pair
#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}

typedef vector<bool> bvec;
typedef vector<int> ivec;
typedef vector<long long> lvec;
typedef vector<double> dvec;
typedef vector<pa> pvec;

typedef vector< vector<bool> > bmat;
typedef vector< vector<int> > imat;
typedef vector<string> svec;
typedef vector< vector<string> > smat;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n ;
    ivec d(n);
    for (int i=0; i<n; i++) cin >> d[i];
    sort(d.begin(), d.end());
    int k;
    if(n % 2 != 0) k=0;    
    else{
        int s = n/2;
        int f = d[n/2], b = d[n/2-1];
        if (f==b) k=0;
        else k=f-b;
    }
    cout << k << endl;




        
}

Measured memory_bytes: 640
#include <cstring>
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
int main(){
long long N;
cin>>N;
int i=0;
while(i*(i-1)<=2*N){
if(2*N!=i*(i-1)){
i++;}
else{
cout<<"Yes"<<endl;
cout<<i<<endl;
int counter=0;
int coua=1;
int coub=0;
int couc=i;
int coud=1;
int coue=0;
for(int j=1; j<i+1;j++){
cout<<i-1<<" ";
coud=j-1;
for(int k=0; k<couc-1;k++){
cout<<coua<<" ";
coua++;}
for(int r=0; r<coub;r++){
cout<<coud<<" ";
coud=coud+i-2-r;}
couc--;
coub++;
cout<<endl;}
goto as;
}}

cout<<"No"<<endl;
as:
cout<<endl;}


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


int main(){
  int N;
  string str = "A";
  int cnt = 0;

  cin >> N;
  vector<string> S(N);
  for(int i=0;i<N;++i){
    cin >> S.at(i);
  }
  sort(S.begin(),S.end());
  for(int i=0;i<N;++i){
    if(str != S.at(i)){
      cnt += 1;
    }
    str = S.at(i);
  }
  cout << cnt << endl;

}


Measured memory_bytes: 9512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

int N,M;
vector<ll> A;
vector<ll> B,C;

int main(){
  cin>>N>>M;
  A.resize(N);
  B.resize(M);
  C.resize(M);
  for(int i=0;i<N;i++) cin>>A[i];
  for(int i=0;i<M;i++) cin>>B[i]>>C[i];

  sort(A.begin(),A.end());
  vector<pair<ll,int>> v;
  for(int i=0;i<M;i++) v.push_back(mkp(C[i],i));
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());

  int it=0;
  for(int i=0;i<M;i++){
    if(A[it]<v[i].first){
      int tmp=B[v[i].second];
      while(tmp>0&&it<N&&A[it]<v[i].first){
        A[it]=v[i].first;
        it++;
        tmp--;
      }
    }
  }

  ll ans=0;
  for(int i=0;i<N;i++) ans+=A[i];
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 4724
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    if(a-b < c) cout << c-(a-b) << endl;
    else{
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256