akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const int nmax = 8;
bool graph[nmax][nmax];
 
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}
 
ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}
int dfs(int v, ll N, bool visited[nmax])
{
    bool all_visited = true;
 
    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            all_visited = false;
        }
    }
 
    if (all_visited)
    {
        return 1;
    }
    int ret = 0;
    for (size_t i = 0; i < N; i++)
    {
        if (!graph[v][i])
        {
            continue;
        }
        if (visited[i])
        {
            continue;
        }
 
        visited[i] = true;
        ret += dfs(i, N, visited);
        visited[i] = false;
    }
 
    return ret;
}

void solve(long long a, long long b, long long h){
    cout << (a + b) * h / 2 << endl;
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long h;
    scanf("%lld",&h);
    solve(a, b, h);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <climits>
#include <iomanip>
#define endl "\n"
#define debug(x) cout << #x << " : " << x << endl;
#define debug2(x, y) cout << #x << " : " << x  << ", " << #y << " : " << y << endl;
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0);
typedef long long ll;
using namespace std;

int main()
{
	FASTIO
	int a;
	cin >> a;
	int ans = a + a * a + a * a * a;
	cout << ans << endl;
}

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

int main(){
	int s;
	int h;
	int m;
	cin >> s;
	h = s / 3600;
	m = s / 60 - 60 * h;
	s = s - h * 3600 - m * 60;
	cout << h << ":" << m << ":" << s << endl;
	return 0;
}

Measured memory_bytes: 3100
#include<stdio.h>
#include<stdlib.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int qsz=1e5;
int qLen,qHead,Q[100000],*cave[100000];
void PUSH(int n){Q[(qHead+qLen)%qsz]=n;qLen++;}
int POP(void){int q=Q[qHead];qLen--;qHead=(qHead+1)%qsz;return q;}
int IN(void)
{
  int x=0;short f=0,c=getchar();
  while(c<48||c>57)f^=c==45,c=getchar();
  while(c>47&&c<58)x=x*10+c-48,c=getchar();
  return f?-x:x;
}
signed main(void)
{
  int A,B,N,M,x,y;
  N=IN(),M=IN();
  int room[N],path[N];
  rep(i,N)path[i]=0,room[i]=-1;
  rep(i,M)
  {
    A=IN()-1,B=IN()-1;
    cave[A]=(int*)realloc(cave[A],sizeof(int)*(path[A]+1));cave[A][path[A]]=B;path[A]++;
    cave[B]=(int*)realloc(cave[B],sizeof(int)*(path[B]+1));cave[B][path[B]]=A;path[B]++;
  }
  room[0]=0;PUSH(0);
  while(qLen)
  {
    x=POP();rep(i,path[x]){y=cave[x][i];if(!(room[y]<0))continue;room[y]=x,PUSH(y);}
  }
  puts("Yes");rep(i,N-1)printf("%d\n",room[i+1]+1);
}

Measured memory_bytes: 8316
function isPrime( x )
{
  if( 2 == x ) return true;
  if( 0 == x%2 ) return false;
  
  for( var i=3; Math.pow( i, 2 )<=x; i+=2 ) {
    if( 0 == x%i ) { return false; }
  }
  return true;
}

var input = '';
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  input += chunk;
});

readable.on( 'end', function() {
  var data = input.split( '\n' ).map( Number );
  var n = data[0];
  var cnt = 0;
  for( var i=1; i<=n; i++ ) {
    if( isPrime( data[i] ) ) {
      cnt++;
    }
  }
  
  console.log( cnt );
});

Measured memory_bytes: 17556
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

// vector<pair<long long, long long> > prime_fac(long long N){
//     vector<pair<long long, long long> > res;
//     for(int i=2; i*i<=N; ++i){
//         if(N%i != 0)continue;

//         long long ex = 0;
//         while(N%i ==0){
//             ex++;
//             N /= i;
//         }

//         res.push_back({i, ex});
//     }

//     if(N != 1){
//         res.push_back({N, 1});
//     }

//     return res;
// } 

vector<pair<long long, long long> > prime_fac(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(){

    long long N, P;
    cin >> N >> P;

    const auto& res = prime_fac(P);
    long long ans = 1;

    for(int i=0; i<res.size(); ++i){
        if(res[i].second >= N){
            long long tmp1 = (res[i].first);
            long long tmp2 = (res[i].second)/N;
            ans *= pow(tmp1, tmp2); 
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadInt();
            var s = Read();
            var a = n / 2;

            var stra = "";
            var strb = "";
            for (int i = 0; i < a; i++)
            {
                stra += s[i];
            }
            for (int i = a; i < n; i++)
            {
                strb += s[i];
            }

            if (stra == strb)
            {
                WriteLine("Yes");
            }
            else
            {
                WriteLine("No");
            }
        }
        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13140
a, b, c, d, e, f = gets.split.map(&:to_i)
a *= 100
b *= 100

ans = [0.0, a, 0]
(0..).each do |i|
    (0..).each do |j|
        water = a * i + b * j
        break if water > f
        max_suger = [water, e * water / 100, f - water].min

        (0..).each do |k|
            suger = c * k
            break if suger > max_suger
            suger += d while suger + d <= max_suger

            rate = suger.fdiv(water + suger)

            if rate > ans[0]
                ans[0] = rate
                ans[1] = water + suger
                ans[2] = suger
            end
        end
    end

    break if a + i > f
end

puts ans[1,2].join(" ")

Measured memory_bytes: 14228
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

bool compare_tuple(tuple<int, string, int> a, tuple<int, string, int> b)
{
  bool ret = false;
  
  if (get<1>(a) < get<1>(b)) {
    ret = true;
  } else if (get<1>(a) == get<1>(b) && get<2>(a) > get<2>(b)) {
    ret = true;
  }

  return ret;
}

int main(int argc, char* argv[])
{
  int N; cin >> N;

  vector<tuple<int, string, int>> R;
  for (int i = 0; i < N; i++) {
    string S;
    int P;
    cin >> S >> P;
    R.push_back(make_tuple(i+1, S, P));
  }

  sort(R.begin(), R.end(), compare_tuple);

  for (int i = 0; i < N; i++) {
    cout << get<0>(R[i]) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
while 1:
    s1 = input().split('"')
    l1 = len(s1)
    if s1[0] == ".": break
    s2 = input().split('"')
    l2 = len(s2)
    if l1 != l2:
        print("DIFFERENT")
        continue
    i = 0
    cnt = 0
#    print(s1,s2)
    while 1:
        if s1[i] != s2[i]:
            print("DIFFERENT")
            break
        if i > l1-2:
            if cnt == 1:
                print("CLOSE")
                break
            else:
                print("IDENTICAL")
                break
        if s1[i+1] != s2[i+1]:
            if cnt == 1:
                print("DIFFERENT")
                break
            else: cnt = 1
        i += 2


Measured memory_bytes: 5580
#!/usr/bin/env python3
h, w = map(int, input().split())
s = [[0 if i == "." else -9 for i in input()] for _ in range(h)]
d = ((1, 0), (1, 1), (1, -1), (-1, 0), (-1, 1), (-1, -1), (0, 1), (0, -1))
for i in range(h):
    for j in range(w):
        if s[i][j] < 0:
            for x, y in d:
                if 0 <= i + x < h and 0 <= j + y < w:
                    s[i + x][j + y] += 1
for i in s:
    print(*["#" if j < 0 else j for j in i], sep="")


Measured memory_bytes: 9304
#include<iostream>
#include<climits>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<functional>
#include<stack>
#include<list>
#include<string>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define PII pair<int,int>
#define PCC pair<char,char>
#define PCI pair<char,int>
#define PIC pair<int,char>
#define MP make_pair
#define DEBUG(x) cout<<#x<<": "<<x<<endl;

int main()
{
	while (1)
	{
		int n, p,ans;
		cin >> n >> p;
		vector<int> S(n, 0);
		if (n == 0)break;
		int c = p;
		for (int i = 0;;)
		{
			if (c > 0)
			{
				S[i]++;
				c--;
			}
			else 
			{
				c = S[i];
				S[i] = 0;
			}
			if (c == 0 && S[i] == p)
			{
				ans = i;
				break;
			}
			if (i == n - 1)i = 0;
			else i++;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define x first
#define y second
#define pii pair<int , int>
#define sz(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000;
const int mod = 998244353;
const int MAX = 1000 * 1000 + 47;
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<pair<int , int> > v;
	for(int i = 0; i < n; i++)
	{
		int x , l;
		cin >> x >> l;
		v.pb({x + l , x - l});
	}
	sort(v.begin() , v.end());
	int ans = 0;
	int mn = -INF - 1;
	for(auto x : v)
	{
		if(x.y >= mn)
		{
			mn = x.x;
			ans++;
		}
		
	}
	cout << ans;
}


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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end



int main(){
    string s; cin>>s;
    int n=0;
    rep(i,0,s.size())n=(n+(s[i]-'0'))%9;
    if(n==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
   return 0;
}

Measured memory_bytes: 3716
def partition(arr,p,r)
    x =arr[r]
    i = p-1
    j = p
    while j < r
        if arr[j] <= x
            i +=1
            arr[i],arr[j] = arr[j],arr[i]
        end
        j +=1
    end
    arr[i+1],arr[r] ="[#{arr[r]}]",arr[i+1]
    return i+1
end

n =gets.to_i
arr =gets.split(" ").map(&:to_i)
partition(arr,0,arr.count-1)
puts arr.join(" ")


Measured memory_bytes: 13944
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, s, e) for(ll i=s; i>=e; i--)
#define reps(i, s, e) for(ll i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
template<typename T> inline bool chmax(T &a, T b){ if(a<b) a=b; return a<b; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a) a=b; return b<a; }
template<typename T> void vdeb(T v){
    cout << "#vector set debug" << endl;
    for(auto vv : v) cout << vv << " ";
    cout << endl;
}
template<typename T1, typename T2> void adeb(T1 arr[], T2 n){
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}
template<typename T1> void mdeb(T1 mp){
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
void ans(bool b){ cout << (b ? "Yes" : "No") << endl; }
void ans2(bool b){ cout << (b ? "YES" : "NO") << endl; }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};


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

    string s;
    cin >> s;
    
    if(s.substr(0, 4) == "YAKI") ans(true);
    else ans(false);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
string s1, s2, s3;
ll n1, k;
ll a[200005], f;
double w[200005] ;
double QWQ(ll n)
{
	double sum = 0;
	for(int i = 1; i <= n; i++) sum += i;
	return sum * 1.0 / n; 
}

struct node
{
	double p, e;	
}b[200005];

int main()
{
	cin >> n1 >> k;
	for(int i = 1; i <= n1; i++) 
	{
		cin >> a[i];
		b[i].p = QWQ(a[i]);
		b[i].e = b[i - 1].e + b[i].p;
	}
	for(int i = k; i <= n1; i++)
	{
		w[++ f] = b[i].e - b[i - k].e;
	}
	sort(w + 1, w + 1 + f);
	printf("%.6f\n",w[f]);
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  string ans = "Yes";
  for(int i=0;i<s.size();++i){
    if((i%2==0&&s[i]=='L')||(i%2==1&&s[i]=='R')){
      ans="No";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
  int n,k,q;
  cin >> n >> k >> q;
  int c[100000]={0};
  int x;
  for(int i=0; i<q; i++){
    cin >> x;
    c[x-1] += 1;
  }
  for(int i=0; i<n; i++){
    if(k-q+c[i] > 0){
      printf("%s\n", "Yes");
    } else {
      printf("%s\n", "No");
    }
  }
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
#define nes ios_base :: sync_with_stdio(0); cin.tie(0);
using namespace std;
int main(){
	nes;
	double dis,tim,vel;
	cin>>dis>>tim>>vel;
	if(tim>=(double)(dis/vel)) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 3736
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<numeric>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//最大公約数
template<class T> T gcd(T a, T b)
{
	while (true)
	{
		T r;
		if (a%b == 0) return b;
		else
		{
			r = a % b;
			a = b;
			b = r;
		}
	}
}
//最小公倍数
template<class T> T lcm(T a, T b)
{
	return a / gcd(a, b)*b;
}
//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn = 1, Kr = 1, Knr = 1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}
//int型10進数をord桁のstring型2進数に変換する
string binary(int x, int ord)
{
	int y;
	string ans = "";
	for (int i = 0; i < ord; i++)
	{
		y = x / (int)pow(2, ord - 1 - i);
		y %= 2;
		if (y == 0) ans += "0";
		else ans += "1";
	}

	return ans;
}
//ord桁のstring型2進数をint型10進数に変換する
int rep_binary(string x, int ord)
{
	int res = 0;
	for (int i = 0; i < ord; i++)
	{
		if (x[i] == '1') res += (int)pow(2, ord - 1 - i);
	}
	return res;
}


/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
{
	int n, R[200005];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> R[i];
	}

	int m = R[0];
	int ans=-1000000005;

	for (int i = 1; i < n; i++)
	{
		ans = max(ans, R[i] - m);
		m = min(m, R[i]);
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3896
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			int N = scan.nextInt();
			int K = scan.nextInt();
			
			double kakuritu= 0;
			
			
			for(int i=1;i<=N;i++){
				if(i>=K) {
					
					kakuritu+=(1.0/(double)N);
					//System.out.println("o-i");
				}else{
					//if(2*i>=K) {
						//kakuritu+=(1.0/(double)N)*(0.5);
					//}else{
					
					int nankai =0;
					int idash=i;
					while(true) {
						idash  = 2*idash;
						nankai++;
						
						//System.out.println(idash);
						//System.out.println();
						//System.out.println(nankai);
						
						if(K<=idash){
							break;
						}
						
						
					}
					
					//System.out.println(BigDecimal.valueOf((1.0/(double)N)*Math.pow(0.5, nankai)).toPlainString());
					//System.out.println();
					kakuritu+=(1.0/(double)N)*Math.pow(0.5, nankai);
				
					
				}
			}
			
			
			System.out.println(BigDecimal.valueOf(kakuritu).toPlainString());
			
			
			
			
			
		}
		
		
	}
		

}


Measured memory_bytes: 22996
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long N, H, W;
  cin >> N >> H >> W;
  long ans = (N - H + 1) * (N - W + 1);
  ans = max(0l, ans);
  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<map>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

typedef long long ll;
typedef pair<ll,int> P;
typedef pair<ll, P> PP;

ll d[55][55];

int n, a, b;
ll v[55];

int main(){

	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v, v + n, greater<ll>());

	for (int i = 0; i <= 50; i++) {
		d[i][0] = 1;
		d[i][i] = 1;
	}
	for (int i=1;i<=50;i++){
		for (int j = 1; j < i; j++) {
			d[i][j] = d[i - 1][j - 1] + d[i - 1][j];
		}
	}
	/*
	for (int i = 0; i <= 10; i++) {
		for (int j = 0; j <= i; j++) {
			cout << d[i][j]<<" ";
		}
		cout << endl;
	}
	*/

	double ans = v[0];
	vector<P> c;
	c.push_back(P(v[0], 1));
	for (int i = 1; i < n; i++) {
		if (i < a)ans += v[i];
		if (v[i] == v[i - 1]) {
			c[c.size() - 1].second++;
		}
		else c.push_back(P(v[i], 1));
	}

	/*
	for (int i = 0; i < c.size(); i++) {
		cout << c[i].first << " " << c[i].second << endl;
	}
	*/
	
	//ll sum = 0;
	ll com = 0;
	
	int k = 0;
	int fk = 0;

	if (c[0].second>=a) {
		//cout << "c" << endl;

		int c0 = c[0].second;
		for (int i = a; i <= b; i++) {
			
			com += d[c0][i];
		}
	}
	else {
		for (int i = 0; i < c.size(); i++) {
			int ci = c[i].second;
			fk = k;
			k += ci;
			if (k >= a) {
				com = d[ci][a-fk];
				//sum += (c[i].first)*(a-fk);
				break;
			}
			//else sum += c[i].first*c[i].second;
		}
	}
	printf("%.11f\n", ans/a);
	printf("%lld\n",com);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int N, A, B, C, D;
   cin >> N >> A >> B >> C >> D;
   string S;
   cin >> S;
   A--;
   B--;
   C--;
   D--;
   for (int i = 0; i < N; i++) {
      if (A > i || i > max(C, D)) continue;
      if (S[i] == '#') {
         if (i + 1 <= max(C, D) && S[i + 1] == '#') {
            cout << "No" << endl;
            return 0;
         }
      }
   }
   if (C < D) {
      cout << "Yes" << endl;
      return 0;
   }

   for (int i = 0; i < N; i++) {
      if (A > i || i > D) continue;
      if (S[i] == '.' && B - 1 <= i && i + 2 <= D + 1 && S[i + 1] == '.' && S[i + 2] == '.') {
         cout << "Yes" << endl;
         return 0;
      }
   }
   cout << "No" << endl;
   return 0;
}


Measured memory_bytes: 640
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int N, H[21], i, j, count;
 
    cin >> N;
 
    count = N;
 
    for(i=1; i<=N; i++){
	cin >> H[i];
    }
 
    for(i=2; i<=N; i++){
	for(j=1; j<=i-1; j++){
	    if(H[j] > H[i]){
		count--;
		break;
	    }
	}
    }
 
    cout << count << endl;
 
    return 0;
}

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

int zohe[100000];
bool ehoz[100000];

int main(void) {
    int n, now = 0, ans = 0;
    bool flag;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> zohe[i];
    while (true) {
        if (ehoz[now]) {
            flag = false;
            break;
        }
        else if (now == 1) {
            flag = true;
            break;
        }
        else {
            ehoz[now] = true;
            now = zohe[now] - 1;
            ans++;
        }
    }
    cout << (flag ? ans : -1) << endl;
}


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

long long a,b,c,k,ans;
long long Max=1e18;
int main(){
	cin>>a>>b>>c>>k;
	k=k%2;
	if(k)ans=b-a;else ans=a-b;
	if(ans>Max||ans<-Max)cout<<"Unfair";else cout<<ans;
}
 

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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int sum_A = 0;
    for (int i=0; i<N; i++){
        cin >> A[i];
        sum_A += A[i];
    }
    sort(A.begin(), A.end(), greater<int>());

    if (A[M-1] * 4 * M < sum_A){
        cout << "No" << endl;
    } else{
        cout << "Yes" << endl;
    }
    return 0;
}


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

string S;
string k = "keyence";

int main() {
    cin >> S;

    int front = 0;
    for (int i = 0; i < 7; i++) {
        if (S[i] == k[i]) front++;
    }

    int back = 0;
    for (int i = 0; i < 7; i++) {
        if (S[S.length()-1-i] == k[6-i]) back++;
    }

    if (front + back >= 7) cout << "YES" << endl;
    else cout << "NO" << endl;


    return 0;
}


Measured memory_bytes: 764
///
// File:  2253.cpp
// Author: ymiyamoto
//
// Created on Mon Nov 20 21:17:57 2017
//

#include <array>
#include <cstdint>
#include <iostream>
#include <queue>
using namespace std;

static void wfs(array<array<int32_t, 200>, 200> &dists, int32_t x, int32_t y)
{
  queue<pair<int32_t, int32_t>> q;
  dists[x][y] = 0;
  q.push({x, y});

  while (!q.empty()) {
    pair<int32_t, int32_t> point = q.front();
    int32_t x = point.first;
    int32_t y = point.second;
    q.pop();

    vector<pair<int32_t, int32_t>> vec({{0, 1}, {1, 1}, {-1, 0}, {1, 0}, {-1, -1}, {0, -1}});
    for (auto iter = vec.begin(); iter < vec.end(); iter++) {
      int32_t posx = x + iter->first;
      int32_t posy = y + iter->second;
      if (0 <= posx && posx < (int32_t)dists.size() && 0 <= posy && posy < (int32_t)dists[0].size() && dists[posx][posy] == INT32_MAX) {
        dists[posx][posy] = dists[x][y] + 1;
        q.push({posx, posy});
      }
    }
  }
}

int32_t main()
{
  while (true) {
    array<array<int32_t, 200>, 200> dists;
    for (uint32_t i = 0; i < dists.size(); i++) {
      for (uint32_t j = 0; j < dists[i].size(); j++) {
        dists[i][j] = INT32_MAX;
      }
    }

    int32_t t, n;
    cin >> t >> n;
    if (t == 0 && n == 0) break;

    for (int32_t i = 0; i < n; i++) {
      int32_t x, y;
      cin >> x >> y;
      dists[x + 100][y + 100] = -1;
    }

    int32_t x, y;
    cin >> x >> y;
    wfs(dists, x + 100, y + 100);

    uint32_t count = 0;
    for (uint32_t i = 0; i < dists.size(); i++) {
      for (uint32_t j = 0; j < dists[i].size(); j++) {
        int32_t dist = dists[i][j];
        if (0 <= dist && dist <= t) {
          count++;
        }
      }
    }
    cout << count << endl;
  }

  return 0;
}

Measured memory_bytes: 3320
#include <stdio.h>
#include <stdlib.h>
 
void quicksort(int,int);
void partitition(int,int);
typedef struct{
 
  int num;
  char m[2];
  int check;
   
} data;
 
data A[100000];
 
int main(){
 
  int n,i,r,a,c=0;
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%s %d",A[i].m,&A[i].num);
    A[i].check=i;
  }
   quicksort(0,n-1);
 
   for(i=0;i<n-1;i++){
     if(A[i].num==A[i+1].num && A[i].check>A[i+1].check) c++;
   }
 
   if(c>0) printf("Not stable\n");
   else printf("Stable\n");
    
  for(i=0;i<n;i++){
    printf("%c %d\n",A[i].m[0],A[i].num);
 
    }
  return 0; 
}
 
int partition(int p,int r){
  int x,j,i;
  data a,b;
  x=A[r].num;
  i=p-1;
  for(j=p;j<r;j++){
   
    if(A[j].num<=x){
      i=i+1;
      a=A[i];
      A[i]=A[j];
      A[j]=a;
    }
  }
  b=A[i+1];
  A[i+1]=A[r];
  A[r]=b;
   
  return i+1;
}
 
void quicksort(p,r){
  int q;
  if(p<r){
    q=partition(p,r);
    quicksort(p,q-1);
    quicksort(q+1,r);
  }
 
}

Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std;
#define N 15
#define M 1005
#define INF 1e9
int n,m,c,tp,ans,mn=INF,st[N],cnt[N],tmp[N];char a[N][M];
int main()
{
	scanf("%d %d %d",&n,&m,&c);for(int i=1;i<=n;++i) scanf("%s",a[i]+1);
	for(int i=0;i<(1<<n-1);++i)
	{
		tp=0;for(int j=1;j<n;++j) if(i&(1<<j-1)) st[++tp]=j;ans=tp;st[++tp]=n;
		for(int j=1;j<=tp;++j) cnt[j]=0;
		for(int j=1;j<=m;++j)
		{
			for(int k=1;k<=tp;++k) {tmp[k]=cnt[k];for(int l=st[k-1]+1;l<=st[k];++l) cnt[k]+=a[l][j]-'0';}
			for(int k=1;k<=tp;++k) if(cnt[k]>c) {++ans;for(int l=1;l<=tp;++l) cnt[l]-=tmp[l];break;}
			for(int k=1;k<=tp;++k) if(cnt[k]>c) {ans=INF;break;}if(ans>=INF) break;
		}mn=min(mn,ans);
	}printf("%d\n",mn);return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <utility>
#include <string>
#include <array>
using namespace std;

#define gcu getchar_unlocked
#define ii inline int in
#define is inline bool scan
ii(int c) {
	int n = 0;
	bool minus = false; if (c == '-') minus = true, c = gcu();
	do {n = 10 * n + (c - '0'), c = gcu();} while (c >= '0');
	//return n; }
	return minus ? -n : n; }
ii() {return in(gcu());}
is(int &n) {int c=gcu();return c==EOF?false:(n=in(c),true);}
is(char &c){c=gcu();gcu();return c!=EOF;}
is(string &s) {int c;for(;;){c=gcu();if(c=='\n'||c==' ')return true;s+=c;}}
#undef ii
#define pcu putchar_unlocked
template <typename T>
void out(T n) {
	static char buf[20];
	char *p = buf;
	if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
void out(const char *s){while(*s)pcu(*s++);}
void out(char c){pcu(c);}
//void out(string &s){for (char c: s) pcu(c);}
template <typename head, typename... tail>
void out(head&& h, tail&&... t){out(h);out(move(t)...);}
//template <typename T>
//void out(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
#undef svo

int main() {
	int n;
	while ((n = in())) {
		array<int, 3> r = {1, 2, 3};
		auto rot = [&](int b, int x){swap(r[b], r[x]);r[x] = 7 - r[x];};
		int sum = 1;
		while (n--) {
			string s;
			scan(s);
			switch (s[0]) {
			case 'N': rot(0, 1); break;
			case 'S': rot(1, 0); break;
			case 'E': rot(2, 0); break;
			case 'W': rot(0, 2); break;
			case 'R': rot(1, 2); break;
			case 'L': rot(2, 1); break;
			}
			sum += r[0];
		}
		out(sum, '\n');
	}
}


Measured memory_bytes: 2520
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    int a,b;
    cin >> a >> b;
    string ans = "";
    if(a >= b) rep(i,0,a) ans = ans + to_string(b);
    else rep(i,0,b) ans = ans + to_string(a);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>
#include<deque>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

ll n,m,a,b,c,x,y,z,aa[200010],ab[200010],ac[1010][1010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc,cd[1010][1010];
vector<ll> va,vb,vc;

int main(){
    cin>>a>>b>>c;
    C min(c,b/a) E;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<ctype.h>
#include<math.h>
#define PI 3.14159265359
#define N_MAX 100
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))

void swap(int *a,int *b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

void Bubblesort(int a[],const int n)
{
  int i , j, count = 0;
  for(i = 1; i <= n; i++)
    {
      for(j = n; j >= i+1; j--)
	{
	  if(a[j] < a[j-1])
	    {
	      swap(&a[j],&a[j-1]);
	      count++;
	    }
	}
    }
  for(i = 1; i <= n; i++)
    {
      printf("%d",a[i]);
      if(i != n) printf(" ");
    }
  printf("\n%d\n",count);
}

int main()
{
  int i,n,a[N_MAX+1];
  scanf("%d",&n);
  for(i = 1; i <= n; i++) scanf("%d",&a[i]);
  Bubblesort(a,n);
  return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <cmath>

using namespace std;

int main(){
  int N, D;
  cin >> N >> D;
  
  int num_points = 0;
  
  long x, y;
  for (int i = 0; i < N; i++){
    cin >> x >> y;
    double edge = sqrt(x*x + y*y);
    if (edge <= D) num_points++;
  }
  
  cout << num_points;
  
  return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include <string.h>
#include <math.h>

int main() {
	int N, T, i, a, old, out = 0;
	scanf("%d%d", &N, &T);
	for (i=0; i < N ;i++) {
		scanf("%d", &a);
		if (i != 0) {
			if (a-old < T) out += a-old;
			else out += T;
		}
		old = a;
	}
	out += T;
	printf("%d\n", out);
	return 0;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

bool pairwiseDistinct(vector<long long>& A)
{
    int N = A.size();
    vector<bool> is_appeared(1e+9+1, false);
    REP(i, N){ 
        if(is_appeared[A[i]]) return false;
        else is_appeared[A[i]] = true;
    }
    return true;
}

int main()
{
    int N;
    cin >> N;
    vector<long long> A(N);
    REP(i, N) cin >> A[i];

    if(pairwiseDistinct(A)) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 123904
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define ll long long int
int main(void)
{
    int s[3][3] = {0};
    int i, j, k, n, m, l;
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            scanf("%d", &m);
            s[i][j] = m;
        }
    }
    scanf("%d", &n);
    for (k = 0; k < n; k++)
    {
        scanf("%d", &l);
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < 3; j++)
            {
                if (s[i][j] == l)
                    s[i][j] = 0;
            }
        }
    }
    if (((s[0][0] == s[0][1]) && (s[0][0] == s[0][2])) || ((s[1][0] == s[1][1]) && (s[1][0] == s[1][2])) || ((s[2][0] == s[2][1]) && (s[2][0] == s[2][2])) || ((s[0][0] == s[1][0]) && (s[0][0] == s[2][0])) || ((s[0][1] == s[1][1]) && (s[0][1] == s[2][1])) || ((s[0][2] == s[1][2]) && (s[0][2] == s[2][2])) || ((s[0][0] == s[1][1]) && (s[0][0] == s[2][2])) || ((s[0][2] == s[1][1]) && (s[0][2] == s[2][0])))
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

Measured memory_bytes: 128
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    public void solve() {
        for(int i=1; i <=9 ; i++)
            for(int j=1; j <=9 ; j++)
                System.out.println(i+"x"+j+"="+(i*j));
    }
}

Measured memory_bytes: 24168
import java.util.*;
import java.util.Arrays;
import java.util.Set;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String S=sc.next();
        boolean ok=true;
        for(int i=0;i<S.length();i++){
            for(int j=i+1;j<S.length();j++){
                if(S.charAt(i)==S.charAt(j)){
                    ok=false;
                }
        }}
        if(ok){
            System.out.println("yes");
        }else{
            System.out.println("no");
        }

}
        
        
    }


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define pr(a,b) cout << a << " " << b << endl
#define pr1(a,b,c) cout << a << " " << b << " "<< c << endl
#define int long long

struct edges
{
	int u, v, w;
};

int32_t main()
{
	fastio;
	// Find out prime divisiors of this number
	int i, l;
	cin >> l;
	
	// Going across 20 bits of this number
	int flag = 0 ,cur = 0;
	vector <edges> v;
	for(i=19;i>=0;i--)
	{
		if((l&(1<<i))!=0)
		{
			if(i!=19)
			v.push_back({1,20-i,cur});
			cur += (1<<i);
			flag = 1;
		}
		if(i!=0 && flag==1){
			v.push_back({20-i,20-i+1,(1<<(i-1))});
			v.push_back({20-i,20-i+1,0});
		}
	}
	cout << "20 " << v.size() << endl;
	for(auto& x:v)
	{
		pr1(x.u, x.v, x.w);
	} 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
using namespace std;
const int INF = 1e9;
typedef long long ll;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
// const lint MOD = 998244353;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
char upper(char c){
	return c-0x20;
}
char lower(char c){
	return c+0x20;
}

int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}
 
int main() {
	int n;
	cin >> n;
	vector<ll>a(n,0);
	rep(i,n) {
		cin >> a[i];
		a[i] -= i+1;
	}
	sort(a.begin(), a.end());
	ll ans;
	if (n % 2 == 1)ans = a[(n - 1) / 2];
	else ans = (a[n / 2] + a[n / 2 - 1]) / 2;
	ll sum = 0;
	rep(i, n ) {
		sum += abs(a[i] - ans);
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1920
n, m, r = map(int, input().split())  # n:頂点数　w:辺の数
r_list = list(map(int, input().split()))
graph = [[float('inf')]*n for i in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0

def warshall_floyd(d):
    # d[i][j] : i から j への最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


from itertools import permutations

adj_m=warshall_floyd(graph)
ans=float('inf')
for path in permutations(r_list):
    tmp_dist=0
    for i in range(r-1):
        tmp_dist+=adj_m[path[i]-1][path[i+1]-1]
    ans=min(ans, tmp_dist)
print(ans)


Measured memory_bytes: 75328
from bisect import bisect_right

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

L.sort()

ans = 0
for i in range(N-1, -1, -1):
    for j in range(i-1, -1, -1):
        m = L[i] - L[j]
        k = bisect_right(L, m)
        n = max(0, j-k)
        ans += n

print(ans)


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

int main() {
    char c;
    cin >> c;
    if (c == 'A') cout << 'T' << endl;
    else if (c == 'G') cout << 'C' << endl;
    else if (c == 'T') cout << 'A' << endl;
    else cout << 'G' << endl;
}


Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())

rem = pow(10,9)+7

#n = ip()                                     #入力整数1つ
x,y= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[input() for i in range(x)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
sa = []
for  i in range(x):
    sa.append([int(i) for i in input().split()])
sb = []
for  i in range(y):
    sb.append([int(i) for i in input().split()])
for i in range(x):
    s = []
    for k in range(y):
        s.append(abs(sa[i][0]-sb[k][0]) + abs(sa[i][1] - sb[k][1]))
    print(s.index(min(s))+1)


Measured memory_bytes: 22824
#include<iostream>
#include <iostream>
#include<vector>
#include <algorithm>
#include <queue>

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




int main() {
	ll N,M;
	cin >> N>>M;
	priority_queue<ll> A;
	rep(i,N) {
		ll a;
		cin >> a;
		A.emplace(a);
	}
	rep(i, M) {
		ll p = A.top()/2; A.pop();
		A.emplace(p);
	}
	ll ans = 0;
	rep(i, N) {
		ans += A.top(); A.pop();
	}
	cout << ans << endl;
		return 0;
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl






const int inf = 1e9;

template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return min(x,y);
    }
    int n;
    vector<int> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void build(int v, int tl, int tr) {
	if (tl==tr) {
	    t[v] = inf;
	} else {
	    int tm = (tl+tr)/2;
	    build(2*v,tl,tm);
	    build(2*v+1,tm+1,tr);
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    void upd(int v, int tl, int tr, int i, T dx) {
	if (tl == tr) {
	    t[v] = merge(t[v], dx);
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,dx);
	    } else {
		upd(2*v+1,tm+1,tr,i,dx);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return inf;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};



const int maxn = 1e6 + 5;
segtree<int> t;

int n;
int b[maxn];
vector<int> iv[maxn];

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

    cin>>n;
    t.init(n+10);
    ++n;
    
    t.build(1,1,n);
    int b0 = 0;
    for (int i=1; i<=n-1; i++) {
	cin>>b[i];
	if (b[i]==0) {
	    b0++;
	    b[i] = -1;
	}
    }

    int q;
    cin>>q;
    while (q--) {
	int l,r;
	cin>>l>>r;
	iv[l].push_back(r+1);
    }


    for (int i=1; i<=n; i++) {
	if (i==1) {
	    t.upd(1,1,n,i,0);
	} else {
	    t.upd(1,1,n, i, t.qry(1,1,n,i-1,i-1)+b[i-1]);
	}
	for (int r: iv[i]) {
	    t.upd(1,1,n,r, t.qry(1,1,n,i,r-1));
	}
    }

    int res = b0 + t.qry(1,1,n,n,n);
    cout<<res<<endl;
    
    return 0;
}


Measured memory_bytes: 34568
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
int main() {
    long long n;
    cin >> n;
    long long a[n], b[n], x, y;
    for (long long i = 0; i < n; i++)
    {
        cin >> x >> y;
        a[i] = x - y;
        b[i] = x + y;
    }
    sort(a, a + n);
    sort(b, b + n);
    cout << max(a[n - 1] - a[0], b[n - 1] - b[0]);
}


Measured memory_bytes: 6768
#include <iostream>

using namespace std;

void Solution()
{
    double v;
    
    while(cin>>v)
    {
        double t = v / 9.8;
        double y = t * t * 4.9;
        
        for (int N = 1; ; N++)
        {
            if (5 * (N - 1) > y)
            {
                cout<<N<<endl;
                break;
            }
        }
    }
}

int main()
{
    Solution();
    return 0;
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define NFOR(i,a,b) for(int i = (int)(a); i >= (int)(b); --i)
#define endl "\n"
#define mp make_pair
#define X first
#define Y second
#define inf 1e9
#define mod 1000000007
#define pb push_back
#define Case cout<<"Case #"<<++cas<<": ";
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) v.begin(),v.end()
#define sz(x) int(x.size())
// #define lli int
typedef long long int lli;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef pair<lli,lli> pll;
typedef vector<lli> vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef complex <long double> complex_t;
const long double PI = acos((long double)-1.0);

#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}

const int NUM = 2000*2000+10;
bitset<NUM> dp[2];
int a[2010];

int main() {
    dp[0].set(0);
    int n; cin >> n;
    int totalSum = 0;
    FOR(i, 1, n) {
        int temp; cin >> temp; a[i] = temp; totalSum += temp;
    }
    FOR(i, 1, n) {
        dp[i%2] = dp[(i-1)%2] | (dp[(i-1)%2]<<a[i]);
    }
    int minAnswer = 0;
    FOR(i, (totalSum+1)/2, NUM) {
        if (dp[n%2][i] == 1) {
            minAnswer = i; break;
        }
    }
    cout << minAnswer << endl;
return 0;}

Measured memory_bytes: 2688
import itertools

while True:
    n,x = [int(i) for i in input().split()]
    if not(n or x):
        break
    s = list(itertools.combinations(list(range(1,n+1)), 3))
    c = 0
    for i in s:
        if sum(i) == x:
            c += 1
    print(c)

Measured memory_bytes: 31432
#include "algorithm"
#include "iostream"
#include "vector"
using namespace std;
typedef long long ll;

int main() {
  ll N;
  cin >> N;
  string s;
  cin >> s;

  ll res = 1;
  char p = s[0];

  for (ll i = 0; i < N; i++) {
    if (s[i] != p) {
      res++;
    }
    p = s[i];
  }

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 512
import java.util.*;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
      
      
public class Main {
	static int[] count = new int[] {1,5,10,50,100,500};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] in = sc.next().toCharArray();
		StringBuilder sbS = new StringBuilder();
		int id = 0;
		for(id = 0; id < in.length; id++) {
			if(in[id] == 'i') break;
			sbS.append(String.valueOf(in[id]));
		}
		String S = sbS.reverse().toString();
		id++;
		id++;
		id++;
		StringBuilder sbT = new StringBuilder();
		
		for(; id < in.length; id++) {
			sbT.append(String.valueOf(in[id]));
		}
		String T = sbT.toString();
		int[][] dp = new int[S.length()+1][T.length()+1];
		dp[0][0] = 3;
		for(int i = 0; i < S.length(); i++) {
			for(int j = 0; j < T.length(); j++) {
				//???????????¨
				for(int k = j; k < T.length(); k++) {
					char A = S.charAt(i);
					char B = T.charAt(k);
					
					boolean ret = check(A,B);
					dp[i+1][k] = Math.max(dp[i][j], dp[i+1][k]);
					dp[i+1][k+1] = Math.max(dp[i][j], dp[i+1][k+1]);
					if(!ret) {
						;
					}
					else {
						dp[i+1][k+1] = Math.max(dp[i][j]+2, dp[i+1][k+1]);
					}
				}
				//???????????¨
				for(int k = i; k < S.length(); k++) {
					char A = S.charAt(k);
					char B = T.charAt(j);
					boolean ret = check(A,B);
					dp[k][j+1]   = Math.max(dp[i][j], dp[k][j+1]);
					dp[k+1][j+1]   = Math.max(dp[i][j], dp[k+1][j+1]);
					if(!ret) {
						;
					}
					else {
						dp[k+1][j+1] = Math.max(dp[i][j]+2, dp[k+1][j+1]);
					}
				}
				dp[i+1][j+1] = Math.max(dp[i][j], dp[i+1][j+1]);
			}
		}
		int MAX = 0;
		for(int i = 0; i < dp.length; i++) {
			MAX = Math.max(MAX, dp[i][dp[0].length-1]);
		}
		for(int j = 0; j < dp[0].length; j++) {
			MAX = Math.max(MAX, dp[dp.length-1][j]);
		}
		System.out.println(MAX);
	}
	static boolean check(char A, char B) {
		if(A == '(' && B == ')') return true;
		if(A == ')' && B == '(') return true;
		if(A == '{' && B == '}') return true;
		if(A == '}' && B == '{') return true;
		if(A == '[' && B == ']') return true;
		if(A == ']' && B == '[') return true;
		return false;
	}
 }

Measured memory_bytes: 26264
function main()
  
  N = parse(Int,readline())
  S = split(chomp(readline()),"")
  
  ans = 0
  
  for i in 1:N
    
    x = Set(S[1:i])
    y = Set(S[i+1:end])
    
    moji = length(intersect(x,y))
    
    ans = max(ans,moji)
    
  end
  
  println(ans)
  
end

main()

Measured memory_bytes: 122176
#include<bits/stdc++.h>
using namespace std;
int N,cc,t[2];
bool visited[1005];
char a[1005][1005];
void dfs(int pos){
  if(visited[pos])return;
  visited[pos]=true;
  cc++;
  for(int i=0;i<N;i++)
    if(a[pos][i]=='Y')
      dfs(i);
}
int main(){ 
  scanf("%d",&N);
  int total=N*(N-1)/2;
  for(int i=0;i<N;i++){
    scanf("%s",a[i]);
    for(int j=0;j<i;j++)
      if(a[i][j]=='Y')total--;
  }
  for(int i=0;i<N;i++){
    if(visited[i])continue;
    cc=0;
    dfs(i);
    t[cc%2]++;    
  }
  if(t[0]==1&&t[1]==2){
    cout<<"Taro"<<endl;
    return 0;
  }
  int f=(t[0]==0&&t[1]==2?0:1);
  if(total%2==f)cout<<"Taro"<<endl;
  else cout<<"Hanako"<<endl;
  return 0;
}

Measured memory_bytes: 4052