akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007LL;

int n;
ll k;
vector<vector<ll>> a;

vector<vector<ll>> mulMatrix(const vector<vector<ll>>& a, const vector<vector<ll>>& b)
{
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int x = 0; x < n; x++)
				res[i][j] = (res[i][j] + a[i][x] * b[x][j]) % MOD;
	return res;
}

vector<vector<ll>> binPow(const vector<vector<ll>>& a, ll x)
{
	if (x == 0)
	{
		vector<vector<ll>> res(n, vector<ll>(n));
		for (int i = 0; i < n; i++)
			res[i][i] = 1;
		return res;
	}
	if (x % 2 != 0)
		return mulMatrix(a, binPow(a, x - 1));

	vector<vector<ll>> halfPow = binPow(a, x / 2);
	return mulMatrix(halfPow, halfPow);
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	a.resize(n, vector<ll>(n));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];

	vector<vector<ll>> res = binPow(a, k);
	ll result = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			result += res[i][j];
	cout << (result % MOD) << endl;
}

Measured memory_bytes: 384
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int gcd(int x, int y)
{
     if(y == 0) return x;
     if(x < y)      return gcd(y,x);
     else        return gcd(y, x%y);
}

int n,k,tmp;
int num[100005];

int main()
{
   cin>>n>>k;
   for(int i=0;i<n;i++)cin>>num[i];
   tmp=num[0];
   for(int i=1;i<n;i++) tmp=gcd(tmp,num[i]);
   for(int i=0;i<n;i++)
   {
       if(k<=num[i]&&(num[i]-k)%tmp==0)
       {
           printf("POSSIBLE");
           return 0;
       }
   }
   printf("IMPOSSIBLE");
   return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.14159265
#define M 998244353 
#define inf 5e6
 
 int powerm(int x, unsigned int y, int p)  
{  
    int res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
 
int power(int x, unsigned int y) 
{ 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
} 
 
 
 int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
} 
 
 int gcdExtended(int a, int b, int *x, int *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    int x1, y1; // To store results of recursive call 
    int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
} 
 
int modInverse(int a, int m) 
{ 
    int x, y; 
    int g = gcdExtended(a, m, &x, &y); 
    if (g != 1) 
        cout << "Inverse doesn't exist"; 
    else
    { 
        // m is added to handle negative x 
        int res = (x%m + m) % m; 
        
        return res;
        //cout << "Modular multiplicative inverse is " << res; 
    } 
}

int vis[200001];

int  dps[200001];
int  dpt[200001];

int par[200001];
int tin[200001];
int tout[200001];
int t=0;
//int a[200001];

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



struct setcmp {
bool operator() (int x, int  y) 
{
       
         
   return x<y;
         
 

}
};


const int maxn=10000001;

int isPrime[maxn];

int nd[maxn];

void solve()
{

 int n,m,k;
 cin>>n;
 
 for(int i=1; i<=n; i++)
 {
         for(int j=i; j<=n; j+=i)
         nd[j]++;
         
 }
 
 int s=0;
 
 for(int i=1; i<=n; i++)
 s+=i*nd[i];
 
 cout<<s;
 
 
}







int32_t  main()
{
       // ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int qq=1;
       // cin>>qq;

 
	while(qq--)
	{
	        
       
       solve();
     
       cout<<"\n";
       
   
    
	}

   
      
  
}
     



 

Measured memory_bytes: 81728
n=input()
z=[0]*(n+1)
z[0]=1
for i in xrange(1,n+1):
  s=0
  if i-3>=0:
    s=z[i-3]
  z[i]=(z[i-1]+s)%(pow(10,9)+7)
print (z[-1]-z[-2])%(pow(10,9)+7)

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

int main()
{
    long k;
    long n;
    cin >> k >> n ;
    long a[n];
    long d[n];
    long i;
    for(i=0;i<n;i++)
        cin >> a[i];
    sort(a,a+n);

    for(i=1;i<n;i++){
        d[i-1]=a[i]-a[i-1];
    }
    d[n-1]=(k-a[n-1])+a[0];
    long max=0;
    for(i=0;i<n;i++){
        if(max<d[i]){
            max=d[i];
        }
    }
    cout << k-max << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll modpow(ll x,ll y){
  ll ans = 1;
  while(y){
    if(y&1) ans = ans*x%mod;
    x = x*x%mod;
    y >>= 1;
  }
  return ans;
}
ll modinv(ll a){
  ll b = mod,u = 1,v = 0,t;
  while(b){
    t = a/b;
    a -= t*b;swap(a,b);
    u -= t*v;swap(u,v);
  }
  u %= mod;
  if(u < 0) u += mod;
  return u;
}
ll P(ll n){
  ll ans = 1;
  while(n){
    ans = ans*n%mod;n--;
  }
  return ans;
}
ll nCr(ll n,ll r){
  ll ans = 1;
  for(ll i=n;i>n-r;i--) ans = ans*i%mod;
  ans = ans*modinv(P(r))%mod;
  return ans;
}
int main(){
  ll n,a,b;scanf("%lld%lld%lld",&n,&a,&b);
  ll ans = modpow(2,n)-1-nCr(n,a)-nCr(n,b);
  ans %= mod;
  if(ans < 0) ans += mod;
  printf("%lld\n",ans);
}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
#define boost_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define num(a) a-'0'
#define charr(a) (a - 'A' + 1)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#define debug(x) cerr<<"["<<#x<<":"<<x<<"] "
#define debug2(a,b) debug(a);debug(b)
#define debug3(a,b,c) debug2(a,b);debug(c)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/(__gcd(a,b))
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<long long>
#define v vector
#define p pair
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
typedef double d;
using namespace std;
int modF=1e9+7;
int INF=1e11;

void solve(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int ans=a*c;
	maxs(ans,a*d);
	maxs(ans,b*c);
	maxs(ans,b*d);
	cout<<ans<<ln;
}

signed main(){
	boost_io;
	solve();
	return 0;
}

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

int N,M,m[100];

void output(){
	int tmp=0;
	for(int n=0; n<M; n++){
		for(int i=0; i<M; i++){
			if(m[tmp]<m[i])
				tmp = i;
		}
		m[tmp] = -1;
		if(n == M-1)
			cout << tmp+1 << endl;
		else
			cout << tmp+1 << ' ';
	}
}

void erace(){
	for(int i=0; i<M; i++)
		m[i]=0;
}

int main(){
	while(true){
		cin >> N >> M;
		if(!N && !M)
			return 0;
		erace();
		int tmp;
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				cin >> tmp;
				m[j] += tmp;
			}
		}
		output();
	}
}

Measured memory_bytes: 864
#include<stdio.h>
	int main(void){
		
		int x;
		int i=1;
		
		while(1){
			scanf("%d",&x);
			if(x!=0){
				printf("Case %d: %d\n",i,x);
				i++;
			}
			if(x==0){
				break;
			}
		}
return 0;
}

Measured memory_bytes: 596
use std::io;

fn main() {
    let mut height: Vec<i32> = Vec::new();
    for	_i in 1..11 {
        let mut input = String::new();
      	let _ = io::stdin().read_line(&mut input);
        let h = input.trim().parse::<i32>().unwrap();
        height.push(h);
    }

    height.sort_by(|a, b| b.cmp(a));

    for i in 0..3 {
        println!("{}", height.get(i).unwrap());
    }
}


Measured memory_bytes: 5024
fn main() {
    let mut buf: String = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let buf: &str = buf.trim();
    let n: u32 = buf.parse::<u32>().unwrap();
    let m: u32 = buf.as_bytes().iter().map(|_| buf.as_bytes()[0] as char)
        .collect::<String>().parse::<u32>().unwrap();    
    println!("{}", if n > m {buf.as_bytes().iter().map(|_| (buf.as_bytes()[0]+1) as char)
        .collect::<String>().parse::<u32>().unwrap()} else {m});
}


Measured memory_bytes: 4352
#include<stdio.h>

int main(void)
{
  int a[10000];
  int n,m;
  int s=0;
  
  scanf("%d%d", &n,&m);
  for(int i=0;i<m;i++){
    scanf("%d", &a[i]);
    s=s+a[i];
  }
  if(s<=n)
    printf("%d",n-s);
  else if(s>n)
    puts("-1");
  
  return 0;
}
  

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

int main() {
  long long K;
  cin >> K;
  
  long long a = 0;
  long long b = 7;
  long long min_ = 1000000000000;
  for (long long i = 0; i < 10000000; i++){
    if (i != 0) b *= 10;
    b %= K;
    a += b;
    a %= K;
    if (a == 0) min_ = min(min_, i + 1);
  }
  
  if (min_ == 1000000000000) cout << -1 << endl;
  else cout << min_ << endl;
}

Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;

namespace AC
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var M = input[1];
            var S = Read();
            var idx = N;
            var ans = new List<int>();
            while (true)
            {
                if (idx <= M)
                {
                    ans.Add(idx);
                    break;
                }
                else
                {
                    var suc = false;
                    for (int i = M; i > 0; i--)
                    {
                        if (S[idx - i] == '0')
                        {
                            ans.Add(i);
                            idx -= i;
                            suc = true;
                            break;
                        }
                    }
                    if (!suc)
                    {
                        Console.WriteLine(-1);
                        return;
                    }
                }
            }

            ans.Reverse();
            Console.WriteLine(string.Join(" ", ans));
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 15968
#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()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

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

Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
    private static final PrintStream so = System.out;
    private static final Scanner     sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sc.nextInt() - 1;
        }
        so.println(sum);
    }
}


Measured memory_bytes: 25624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

struct UnionFind {
    UnionFind() {}
    UnionFind(int n) {
        resize(n);
    }
    
    void resize(int n) {
        par.resize(n, -1);
    }
    
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    
    bool merge(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return false;
        if (par[rx] > par[ry]) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
        return true;
    }
    
    bool is_same(int x, int y) {
        return (root(x) == root(y));
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
private:
    vector<int> par;
};

struct City {
    int id;
    int x, y;
};

struct Edge {
    int from, to;
    int cost;
};

int get_distance(const City &a, const City &b) {
    return min(abs(a.x - b.x), abs(a.y - b.y));
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<City> city(n);
    vector<Edge> e;
    rep(i, n) {
        cin >> city[i].x >> city[i].y;
        city[i].id = i;
    }
    sort(all(city), [&](const City &a, const City &b) { return a.x < b.x; });
    rep(i, n - 1) e.emplace_back((Edge){city[i].id, city[i + 1].id, get_distance(city[i], city[i + 1])});
    sort(all(city), [&](const City &a, const City &b) { return a.y < b.y; });
    rep(i, n - 1) e.emplace_back((Edge){city[i].id, city[i + 1].id, get_distance(city[i], city[i + 1])});
    sort(all(e), [&](const Edge &a, const Edge &b) { return a.cost < b.cost; });
    UnionFind uf(n);
    ll ans = 0;
    rep(i, sz(e)) {
        if (uf.is_same(e[i].from, e[i].to)) continue;
        uf.merge(e[i].from, e[i].to);
        ans = ans + e[i].cost;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int N;
    ll D, A;
    cin >> N >> D >> A;
    vector<ll> X(N), H(N);
    for (int i = 0; i < N; i++) cin >> X[i] >> H[i];
    priority_queue<pair<pair<ll, ll>, int>> pq;
    for (int i = 0; i < N; i++) {
        pq.push({{-X[i], H[i]}, 2});
    }
    ll ans = 0;
    ll bomb = 0;
    while (!pq.empty()) {
        ll x = pq.top().first.first*(-1);
        ll y = pq.top().first.second;
        int op = pq.top().second;
        pq.pop();
        if (op == 1) {
            bomb -= y;
        }
        else if (op == 2) {
            y -= bomb*A;
            if (y > 0) {
                ll add = (y+A-1)/A;
                bomb += add;
                ans += add;
                pq.push({{-(x+2*D), add}, 1});
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11376
#!/usr/bin/env python
# coding: utf-8

# In[16]:


S = input()


# In[19]:


length = len(S)
# if length%2 != 0:
#     S = S + "_"
for i in range(2,length,2):
    s = S[:-i]
#     print(i,s, S[:(length-i)//2]*2)
    if S[:(length-i)//2]*2 == s:
        print(len(s))
        break


# In[ ]:






Measured memory_bytes: 2940
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

int main(void) {
  int n;
  cin >> n;
  double sum = 0;
  REP(i, n) {
    double a;
    cin >> a;
    sum += 1.0 / a;
  }
  double res = 1 / sum;
  printf("%.10f\n", res);
  return 0;
}


Measured memory_bytes: 384
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	
	public static class Person implements Comparable<Person>{
		public int number;
		public double time;
		
		public Person(int n, double t){
			number = n;
			time = t;
		}

		@Override
		public int compareTo(Person another) {	
			return this.time < another.time ? -1
					: this.time == another.time ? 0
							: 1;
		}
		
		public String toString(){
			return number + " " + String.format("%.2f",time);
		}
		
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		ArrayList<Person> one_list = new ArrayList<Person>(8);
		ArrayList<Person> two_list = new ArrayList<Person>(8);
		ArrayList<Person> three_list = new ArrayList<Person>(8);
		ArrayList<Person> other_list = new ArrayList<Person>(24);
		
		for(int i = 0; i < 24; i++){
			Person input = new Person(sc.nextInt(),sc.nextDouble());
			
			switch(i / 8){
			case 0:
				one_list.add(input);
				break;
			case 1:
				two_list.add(input);
				break;
			case 2:
				three_list.add(input);
				break;
			}
			
			other_list.add(input);
		}
		
		Collections.sort(one_list);
		Collections.sort(two_list);
		Collections.sort(three_list);
		
		other_list.remove(one_list.get(0));
		other_list.remove(one_list.get(1));
		other_list.remove(two_list.get(0));
		other_list.remove(two_list.get(1));
		other_list.remove(three_list.get(0));
		other_list.remove(three_list.get(1));
		
		Collections.sort(other_list);
		
		System.out.println(one_list.get(0));
		System.out.println(one_list.get(1));
		System.out.println(two_list.get(0));
		System.out.println(two_list.get(1));
		System.out.println(three_list.get(0));
		System.out.println(three_list.get(1));
		System.out.println(other_list.get(0));
		System.out.println(other_list.get(1));
	}
	
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n,h,w;
  cin>>n;
  cin>>h;
  cin>>w;
  int s = n-h+1;
  int t = n-w+1;
  int ans = s*t;
  cout<<ans<<endl;
  return 0;
}


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;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  while (cin >> n >> m && (n || m)) {
    vector<int> h(n), w(m);
    rep(i, n)
      cin >> h[i];
    rep(i, m)
      cin >> w[i];
    map<int, int> mph, mpw;
    rep(i, n) {
      int sum = 0;
      for (int j = i; j < n; j++) {
        sum += h[j];
        mph[sum]++;
      }
    }
    rep(i, m) {
      int sum = 0;
      for (int j = i; j < m; j++) {
        sum += w[j];
        mpw[sum]++;
      }
    }
    ll ans = 0;
    for (auto e : mph)
      ans += (ll)e.second*mpw[e.first];
    cout << ans << endl;
  }
  return 0;
}


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

int main() {
	int ratingNow, ratingFuture, a;
	cin >> ratingNow;
	cin >> ratingFuture;
	a = (ratingFuture * 2) - ratingNow;
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 384
p['   '];t['   '];n,x,k,j;main(i){for(;i++<1e6;)for(x=i;x<1e6;p[x+=i]=1);for(;*t=scanf("%d%d",&n,&x)*n;memset(t,0,4e6)){for(;n--;)for(i=-scanf("%d",&k);++i<x;)t[i]&&++t[i+k];for(;p[x]|!t[x];x--);printf(x<2?"NA\n":"%d\n",x);}}

Measured memory_bytes: 15000
from collections import deque

n = int(input())
d = deque()
for _i in range(n):
    line = input().split()
    order = line[0]
    if order in ('insert', 'delete'):
        key = line[1]
    if order == 'insert':
        d.appendleft(key)
    elif order == 'delete':
        try:
            d.remove(key)
        except ValueError:
            pass
    elif order == 'deleteFirst':
        d.popleft()
    elif order == 'deleteLast':
        d.pop()
    else:
        raise ValueError('Invalid order: {order}')

print(' '.join(d))



Measured memory_bytes: 69740
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	mp := map[int]int{}
	for i := 0; i < n; i++ {
		a := getNextInt(scanner)
		mp[a] = 1
	}
	m := getNextInt(scanner)
	for i := 0; i < m; i++ {
		b := getNextInt(scanner)
		if mp[b] == 1 {
			fmt.Fprintln(writer, b)
		}
	}
}



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

pair<int, int> or_expr(string &s, int &i);
pair<int, int> and_expr(string &s, int &i);
pair<int, int> term(string &s, int &i);

// 0, 1
pair<int, int> or_expr(string &s, int &i) {
    if(i >= s.size()) return make_pair(0, 0);
//    cout << "or:" << i << endl;
    auto a = and_expr(s, i);
    while(s[i] == '|') {
        i++;
        auto b = and_expr(s, i);
        a = make_pair(a.first + b.first, min(a.first + b.second, a.second));
    }
    return a;
}

pair<int, int> and_expr(string &s, int &i) {
//    cout << "and:" << i << endl;
    auto a = term(s, i);
    while(s[i] == '&') {
        i++;
        auto b = term(s, i);
        a = make_pair(min(a.second + b.first, a.first), a.second + b.second);
    }
    return a;
}

pair<int, int> term(string &s, int &i) {
//    cout << "term:" << i << endl;
    if(s[i] == '?') {
        i++;
        return make_pair(1, 1);
    }
    i++; // (
    auto ret = or_expr(s, i);
    i++; // )
    return ret;
}

int main(){
    string s;
    cin >> s;
    int i = 0;
    auto ans = or_expr(s, i);
    cout << ans.first << " " << ans.second << endl;
}




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

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

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

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

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

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

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

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

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

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    if b % a == 0 {
        println!("{}", a + b);
    } else {
        println!("{}", b - a);
    }
}


Measured memory_bytes: 4352
let () =
  let w = read_line () in
  let rec loop count =
    match read_line () with
      "END_OF_TEXT" -> Printf.printf "%d\n" count
    | s -> loop (Str.split (Str.regexp " ") s
                 |> List.fold_left
                   (fun acc x ->
                      acc +
                      (if String.lowercase x = String.lowercase w then 1 else 0))
                   0
                 |> (+) count)
  in loop 0

Measured memory_bytes: 2300
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;
const int MOD = 1000000007;

struct UnionFind {
	vi data;
	UnionFind(int size) : data(size, -1) {}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool find(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	int N, K, L;
	cin >> N >> K >> L;
	UnionFind uf_road(N), uf_rail(N);

	int p, q;
	REP(i, K) {
		cin >> p >> q;
		uf_road.unite(p - 1, q - 1);
	}

	int r, s;
	REP(i, L) {
		cin >> r >> s;
		uf_rail.unite(r - 1, s - 1);
	}

	map<pii, int> table;
	REP(i, N) {
		table[pii(uf_road.root(i), uf_rail.root(i))]++;
	}
	REP(i, N) {
		cout << table[pii(uf_road.root(i), uf_rail.root(i))];
		if (i != N - 1) {
			cout << " ";
		}
	}
	cout << endl;
	return 0;
}

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

using namespace std;

using ull = unsigned long long;

typedef struct tpl{
  ull a;
  ull b;

  bool operator<( const tpl& right ) const {
    return a == right.a ? b < right.b : a < right.a;
  }
};

template <typename T>
inline std::string to_bin_str(T n) {
  std::string str;
  if(n == 0) return "0";
  else while (n > 0) {
    str.push_back('0' + (n & 1));
    n >>= 1;
  }
  reverse(str.begin(), str.end());
  return str;
}

int main(void) {
  ull n, k;
  cin >> n >> k;
  cin.ignore();
  tpl c[n];
  //ull a[n], b[n];
  int j = 0; // c[i].b <= k
  for (int i = 0; i < n; i++){
    //cin >> a[i] >> b[i];
    cin >> c[i].a >> c[i].b;
    cin.ignore();
  }

  // 1-finder

  string strk = to_bin_str(k);
  //cout << "strk = " << strk << endl;
  unsigned int klen = strk.length(); // kの長さ
  char cstrk[klen];
  strcpy(cstrk, strk.c_str());
  vector<ull> masks;
  ull mask;
  masks.push_back(k);
  unsigned int keta;
  //cout << "klen = " << klen << endl;
  //ncout << "cstrk = " << cstrk << endl;
  for (int i = 0; i < klen; i++){
    if(cstrk[i] == '1'){
      keta = klen - i - 1;
      mask = k - (1 << keta);
      mask |= (1 << keta) - 1;
      //cout << "mask = " << mask << endl;
      masks.push_back(mask);
    }
  }

  vector <ull> anss;
  ull ans = 0;
  ull maxans = 0;
  for (auto itr = masks.begin(); itr != masks.end(); itr++){
    ans = 0;
    for (int m = 0; m < n; m++){
      if(*itr == (*itr | c[m].a)){
        ans+=c[m].b;
        //cout << "ans = " << ans << endl;
        //cout << "cmb = " << c[m].b << endl;
      }
    }
    if(maxans <= ans) maxans = ans;
    anss.push_back(ans);
  }
  cout << maxans << endl;

  return 0;
}


Measured memory_bytes: 1792
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <fstream>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <assert.h>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 998244353LL 
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
 
 
#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
	std::fill((T*)array, (T*)(array + N), val);
}
 
//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define INF 10000000000000000LL
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)
 
struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}
 
};
typedef vector<vector<Edge>> Graph;
typedef unsigned long long ull;

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

ll lcm(ll m, ll n)
{
	return m * n / gcd(m, n);
}
ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = (res * x) % MODU;
		x = (x*x)%MODU;
		n >>= 1;
	}
	return res;
}
ll divmod(ll a, ll b) { // a/b(mod m)
								  // a/b (mod m)
								  // a*b^-1
								  // b^-1 * b = 1
								  // b^(m-1) = 1 
								  // b^(m-2) * b = 1
								  // b^-1 = b^(m-2)

								  // a/b = a * b^(m-2)

	return (a * mod_pow(b, MODU - 2)) % MODU;
}


ll fmemo[10000] = {};
ll factorial(ll n) {//階乗

	if (n > 0) {
    assert(n < 10000);
if(fmemo[n] != 0) return fmemo[n];
		return fmemo[n] = (n * factorial(n - 1))%MODU;
	}
	else {
		return 1;
	}
}

int main(){
  ll sum = 0;
int n;
cin >> n;
  rep(i, 1, n + 1){
    if(i % 3 && i % 5){
      sum += i;
    }
  }
  cout << sum << endl;
  return 0;
} 

Measured memory_bytes: 3636
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int N,M;
	static int[] h,w,sumh,sumw;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		for(;;){
			N=sc.nextInt();
			M=sc.nextInt();
			if(N+M==0)break;
			h=new int[N];
			sumh=new int[N+1];
			w=new int[M];
			sumw=new int[M+1];
			for(int i=0;i<N;i++){
				h[i]=sc.nextInt();
				sumh[i+1]=h[i]+sumh[i];
			}
			for(int i=0;i<M;i++){
				w[i]=sc.nextInt();
				sumw[i+1]=w[i]+sumw[i];
			}
			int cnt=0;
			int[] a = new int[(M+1)*M/2];
			for(int j=0;j<M;j++){
				for(int jj=j+1;jj<=M;jj++){
					a[cnt++]=sumw[jj]-sumw[j];
				}
			}
			Arrays.sort(a);
//			System.out.println(Arrays.toString(sumw));
//			System.out.println(Arrays.toString(a));
			cnt=0;
			for(int i=0;i<N;i++){
				
				for(int ii=i+1;ii<=N;ii++){
					int u = upperBound(a,sumh[ii]-sumh[i]);
					int l = lowerBound(a,sumh[ii]-sumh[i]);
					int d = Arrays.binarySearch(a,sumh[ii]-sumh[i]);
					if(d>=0)cnt+=u-l;
				}
			}
			
			
			System.out.println(cnt);
			
		}
	}
	public static int lowerBound(int[] a, int x){
		int left = 0;
		int right = a.length;
		while(true){
			if(right-left<=1){
				return a[left]>=x?left:right;
			}
			else{
				int m = (left+right)/2;
				if(a[m]>=x){
					right = m;
				}
				else{
					left = m;
				}
			}
		}
	}
	
	/**
	 * テ」ツつステ」ツδシテ」ツδ暗ヲツクツ暗」ツ?ソテゥツ?催・ツ按預テ」ツ?凝」ツつ?x<a[i] テ」ツ?ィテ」ツ?ェテ」ツつ凝」ツつ暗」ツ??」ツ?ェテヲツ慊?・ツーツ湘」ツ?ョ i テ」ツつ津ィツソツ氾」ツ??
	 * テ・ツソツ愿ァツ板ィテッツシツ?
	 * テゥツ?催・ツ按療、ツクツュテ」ツ?ョティツヲツ?ァツエツ?」ツ?ァテ・ツ、ツァテ」ツ?催」ツ?陛」ツ??x テ、ツサツ・テ、ツクツ凝」ツ?ョティツヲツ?ァツエツ?ヲツ閉ーテ」ツつ津・ツ渉姪」ツ?」テ」ツ?ヲテ」ツ?湘」ツつ凝」ツ?ェテ」ツ?ゥ
	 * @param a
	 * @param x
	 * @return
	 */
	public static int upperBound(int[] a, int x){
		int left = 0;
		int right = a.length;
		while(true){
			if(right-left<=1){
				return a[left]>x?left:right;
			}
			else{
				int m = (left+right)/2;
				if(a[m]>x){
					right = m;
				}
				else{
					left = m;
				}
			}
		}
	}
}

Measured memory_bytes: 64032
#include <stdio.h>
#include<limits.h>

int main ( void ) {
	int i , j , n , sum , max1 , max2 , data[5000];
	
	while ( 1 ) {
		scanf("%d",&n);
		if ( n == 0 ) break;
		sum = 0;
		max1 = INT_MIN;
		max2 = INT_MIN; 
		for ( i =0; i < n; i++ )
			scanf("%d",&data[i]);
		for ( i = 0; i < n; i++ ) {
			sum = 0;
			for ( j = i; j < n; j++ ) {
				sum += data[j];
				if ( max1 < sum ) max1 = sum;
			}
			if ( max2 < max1 ) max2 = max1;
		}
		printf("%d\n",max2);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define endl ("\n")


pair<int,int> func(int n)
{
    pair<int, int> sol;
    sol.second = n%10;
    while(n)
    {
        if(n/10 == 0)
        {
            sol.first = n;
        }
        n /= 10;
    }
    return sol;
}
int main()
{

    int n;
    cin >> n;
    map<pair<int, int>, long long> mp;
    for(int i = 1;i <= n;i++)
    {
        pair<int, int> a = func(i);
        if(a.first == 0 or a.second == 0)
        {
            continue;
        }
        mp[a]++;
    }
    long long sol = 0ll;
    for(auto i:mp)
    {
        pair<int, int> a = i.first;
        int t = a.first;
        a.first = a.second;
        a.second = t;
        sol += i.second * mp[a];
    }
    cout << sol;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int sum = A + B;
		if (sum % 2 == 0) {
			System.out.println(sum / 2);
		} else {
			System.out.println("IMPOSSIBLE");
		}
		sc.close();
	}
}

Measured memory_bytes: 23764
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N; cin >> N; ll a[N]; ll sum = 0;
  rep(i, N){
    cin >> a[i];
    sum += a[i];
  }
  ll ans = longinf, tmp = 0;
  rep(i, N){
    tmp += a[i];
    ans = min(ans, abs(sum-2*tmp));
  }
  cout << ans << endl;
}

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

#define ll long long
#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define repr(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define MOD 1000000007
#define pb push_back
#define debug(x) cout << x << endl;

int main() {
	int n; cin >> n;
	vector<int> a(n), order(n);
	rep(i,n) cin >> a[i];
	rep(i,n) order[a[i] - 1] = i;

	set<int> st;
	st.insert(-1);
	st.insert(n);

	ll ans = 0;
	rep(i,n) {
		auto itr = st.lower_bound(order[i]);
		ll right = (*itr) - order[i];
		itr--;
		ll left = order[i] - (*itr);
		ll tmp = a[order[i]] * left * right;
		ans += tmp;
		st.insert(order[i]);
	}

	cout << ans << endl;
}


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

struct Solver {
	void solve() {
		int N, A, B;
		cin >> N >> A >> B;
		cout << min( A, B ) << ' ' << max( A+B-N, 0 ) << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>
   
using namespace std;

int main()
{
    int r, n;
    while(1){
        cin >> r >> n;
        if(r == 0 && n == 0) break;
        int building[42] = {};
        for(int i = 0; i < n; i++){
            int x1, x2, h;
            cin >> x1 >> x2 >> h;
            // cout << (double)r * r - pow(min(abs(x1), abs(x2)), 2) << endl;
            
            x1 += 20;
            x2 += 20;
            for(int i = x1; i < x2; i++){
                building[i] = max(building[i], h);
            }
        }
        double ans = 25.0;
        for(int i = 20 - r; i < 20 + r; i++){
// [cout << i - 20 << " : " << building[i] << (double)building[i] - sqrt(r * r - pow(abs(i - 20) - 1, 2)) + r << endl;
            if(i - 20 < 0) ans = min(ans, (double)building[i] - sqrt(r * r - pow(-i + 20 - 1, 2)) + r);
            else ans = min(ans, (double)building[i] - sqrt(r * r - pow(i - 20, 2)) + r);
        }
        printf("%.10f\n", max(ans, 0.0));
    }
    return 0;
}

Measured memory_bytes: 1200
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)

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

template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
	return left.second > right.second;
}

void init_global() {}

int main_() {
	int W, H, N;
	cin >> W >> H >> N;
	vi x(N), y(N), a(N);
	FOR(i, 0, N) {
		cin >> x[i] >> y[i] >> a[i];
	}

	int l = 0, r = W;
	int d = 0, u = H;
	FOR(i, 0, N) {
		switch (a[i]) {
		case 1:
			l = max(l, x[i]);
			break;
		case 2:
			r = min(r, x[i]);
			break;
		case 3:
			d = max(d, y[i]);
			break;
		default:
			u = min(u, y[i]);
			break;
		}
	}

	int ans = max((r-l), 0) * max((u-d), 0);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;

ll solve(int N) {

  static ll dp[2][1<<16]; zero(dp);

  rep(i, N) {
    int M; ll L; scanf("%d%lld",&M,&L);

    int bit = 0;
    rep(_, M) {
      int s, t; cin >> s >> t; s -= 6, t -= 6;
      bit |= ((1<<t)-1) - ((1<<s)-1);
    }

    rep(S, 1<<16) {
      maximize(dp[(i+1)&1][S], dp[i&1][S]);
      if((S ^ bit) == (S + bit)) {
        int nS = S ^ bit;
        maximize(dp[(i+1)&1][nS], dp[i&1][S] + L);
      }
    }
  }

  return *max_element(dp[N&1], dp[N&1]+(1<<16));
}

int main() {

  for(int N; ~scanf("%d", &N) && N;) {
    printf("%lld\n", solve(N));
  }
  
  return 0;
}

Measured memory_bytes: 4228
#include<bits/stdc++.h>
#define LLI long long int
#define ULTRA 2134567890
#define debug(x) if(MODE==x)
#define MODE 0
using namespace std;

char S[100007];

int main()
{
    int i,j;
    int N,K;

    scanf("%d %d",&N,&K);
    scanf("%s",S);

    for( i=0; i<N && K>0; )
    {
        while(i<N && S[i]==S[0])
        {
            i++;
        }
        while(i<N && S[i]!=S[0])
        {
            S[i] = S[0];
            i++;
        }
        K--;
    }
    int cnt = 0;
    for( i=0;i<N-1; i++)
    {
        debug(1) printf("%c",S[i]);
        if( S[i] == S[i+1])
            cnt++;
    }
    debug(1) printf("\n");
    printf("%d\n",cnt);

    return 0;
}


Measured memory_bytes: 384
package main

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

var r = bufio.NewReader(os.Stdin)

func main() {
    var a, b, c int
    fmt.Fscan(r, &a)
    fmt.Fscan(r, &b)
    fmt.Fscan(r, &c)
    if a < b && b < c {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}


Measured memory_bytes: 1136
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;

const int mod=1e9+7;

int main() {
  int N;
  string S;
  cin >> N >> S;
  map<char, int> c;
  rep(i, S.size()) c[S[i]]++;
  ll ans = 1;
  for(const auto e : c)
    ans = ans*(e.second+1)%mod;
  ans--;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int,int>
#define vi  vector<int>
#define vii vector<pair<int,int>>
#define vll vector<lli>
#define pb  push_back
#define mp  make_pair
#define ss  second
#define ff  first
#define all(x) x.begin(),x.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define testcase() int t;cin>>t;while(t--)
#define clean(x) memset(x,0,sizeof(x))
#define sz size()
const lli mod = 1000000007;
const lli maxn = 1e18;
vector<lli> catlan(int n) {
    vector<lli> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i ++) {
        for (int j = 0; j < i; ++ j) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp;
}
lli b_ex(lli n,lli a){lli res=1;while(n){if(n%2==1)res*=a;n>>=1;a=a*a;}return res;}
lli ncr(lli n,lli k){lli ans=1;if(k>n-k)k=n-k;for(lli i=1;i<=k;i++){ans*=(n-i+1),ans=ans/i;}return ans;}
lli power(lli a , lli n){lli ans = 1;while(n){if(n % 2)ans = (ans * a) % mod;n /= 2;a = (a * a) % mod;}return ans;}
lli set_bits(lli n)
{
    int c=0;
    if(n==0)return 0;
    while(n)
    {
        if((n&1)==1)
        {
           cout<<c<<" ";
        }
        c++;
        n=n>>1;
    }
    return c;
}
lli lcm(lli a,lli b)
{
    lli ans=(a*b)/(__gcd(a,b));
    return ans;
}
///------------------ALWAYS lli-----TEMP TSF99--------------------------------------------------------------------------------------///
void solve()
{
    string a;cin>>a;
    lli sum=0;
    for(int i=0;i<a.size();i++)
    {
        sum+=(a[i]-'0');
    }
    if(sum%9==0)
    {
        cout<<"Yes\n";
    }
    else cout<<"No\n";
}
int main()
{
    solve();
}


Measured memory_bytes: 3752
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;

int check(int x) {
	int cnt = 0;
	while (x % 2 == 0) {
		x /= 2;
		cnt++;
	}
	return cnt;
}

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

	int ans=0;
	for (int i = 0; i < n; i++) {
		ans += check(a[i]);
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
list = list(map(int, input().split()))

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

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

alllcm = 1

for i in range(N):
  alllcm = lcm(alllcm, list[i])

ans = 0

for i in range(N):
  ans += alllcm // list[i]

print(ans % (10**9 + 7))


Measured memory_bytes: 4084
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        Integer N = Integer.parseInt(scanner.next());
        Integer K = Integer.parseInt(scanner.next());

        Integer count = 0;
        Double total = 0.0;
        for (int i = 1; i < N+1; i++) {
            Integer ii = i;
            while(ii < K) {
                ii*=2;
                count++;
            }
            total += (double)1/N * Math.pow((double)1/2,count);

            // 初期化
            ii = i;
            count = 0;
        }


        System.out.println(total);
    }
}


Measured memory_bytes: 27732
primes = [True] * int(1e6)

for i, v in enumerate(primes):
    if i == 0 or i == 1:
        continue
    if v == True:
        multiple = 2
        while (i)*multiple < len(primes):
            primes[(i)*multiple] = False
            multiple += 1

X = int(input())
for i in range(X, len(primes)):
    if primes[i] == True:
        print(i)
        break

Measured memory_bytes: 10868
dn = input().split()
d = int(dn[0])
n = int(dn[1])
if n == 100:
  if d == 0:
    a = 101
  elif d == 1:
    a = 10100
  elif d == 2:
    a = 1010000
else:
  if d == 0:
  	a = n
  elif d == 1:
    a = n * 100
  elif d == 2:
    a = n * 10000
print(a)

Measured memory_bytes: 3060
n,m,x,y = gets.split.map(&:to_i)
xwant = gets.split.map(&:to_i).sort
ywant = gets.split.map(&:to_i).sort
if xwant[-1] < ywant[0]
  hani = [*((xwant[-1] + 1)..ywant[0])]
  if (hani.size == 1 && x < hani[0] && y >= hani[0]) || hani.size >= 2
    puts "No War"
  else
    puts :War
  end
else
  puts :War
end

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

int n;
int X1[2000], Y1[2000], X2[2000], Y2[2000];
bool fld[4000][4000];
int compress(int*X1, int*X2, vector<int>&X) {
	rep(i, n) {
		X.push_back(X1[i]);
		X.push_back(X2[i]);
	}
	sort(X.begin(), X.end());
	auto it = unique(X.begin(), X.end());
	rep(i, n) {
		X1[i] = lower_bound(X.begin(), it, X1[i]) - X.begin();
		X2[i] = lower_bound(X.begin(), it, X2[i]) - X.begin();
	}
	return X.size();
}
int main() {
	scanf("%d", &n);
	rep(i, n)scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
	vector<int>a, b;
	int w = compress(X1, X2, a), h = compress(Y1, Y2, b);
	rep(i, n) {
		for (int j = X1[i]; j < X2[i]; j++)
			for (int k = Y1[i]; k < Y2[i]; k++)fld[j][k] = true;
	}
	ll ans = 0;
	rep(i, w - 1)rep(j, h - 1) {
		if (fld[i][j])ans += ((ll)a[i + 1] - a[i])*(b[j + 1] - b[j]);
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 18924
import bisect
from collections import deque
N = int(input())
S = deque([int(input())])
for _ in range(N-1):
    a = int(input())
    ind = bisect.bisect_right(S,a)
    if S[ind-1]==a:
        ind1 = bisect.bisect_left(S,a)
        if ind1>0 and S[ind1-1]<a:
            S[ind1-1]=a
        else:
            S.appendleft(a)
    elif ind==0:
        S.appendleft(a)
    else:
        S[ind-1]=a
#     print("a,S = {}{}".format(a,S))
print(len(S))

Measured memory_bytes: 7284