akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

int n, k;
char a[201000], ans[201000];

int main()
{
    n = read(), k = read();
    scanf("%s", a);
    int p = 0, flg = 0, s = 0;
    for (int i = 0; i < k; i++)
    {
        int q = (p + a[p] - 'A') % 2;
        s++;
        if (!q && !flg)
        {
            flg = 1;
            continue;
        }
        p++;
        flg = 0;
        if (p == n) break;
    }
    for (int i = p; i < n; i++)
    {
        ans[i - p] = a[i];
        if (p & 1)
            if (ans[i - p] == 'A')
                ans[i - p] = 'B';
            else
                ans[i - p] = 'A';
    }
    if (flg) ans[0] = 'B';
    for (int i = 0; i < p; i++)
        ans[n - i - 1] = 'A' + (i & 1);
    if (s < k && k % 2 != s % 2 && ans[0] == 'A') ans[0] = 'B';
    printf("%s\n", ans);
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<long long int> L(N);
  for(int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  if(N == 1 || N == 2) cout << 0 << endl;
  else {
    int ans = 0;
    for(int i = 0; i < N - 2; i++) {
      for(int j = i + 1; j < N - 1; j++) {
        for(int k = j + 1; k < N; k++) {
          vector<long long int> vec(3);
          vec.at(0) = L.at(i);
          vec.at(1) = L.at(j);
          vec.at(2) = L.at(k);
          sort(vec.begin(), vec.end());
          if(vec.at(0) != vec.at(1) && vec.at(1) != vec.at(2) &&vec.at(2) < vec.at(0) + vec.at(1)) ans++;
        }
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 3576
//============================================================================
// Name        : Hello.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main() {

	int n;
	cin>>n;

	int L[n];

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

	}

	sort(L,L+n);

int sum=0;
for(int a=0;a<n-1;a++){
	sum+=L[a];
}

if(L[n-1]>=sum){
	cout<<"No"<<endl;
}else{
	cout<<"Yes"<<endl;
}



	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
#define all(v) v.begin(),v.end()

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};


int main() {
  ll N, M;
  cin >> N >> M;

  UnionFind tree(N);

  for(ll i=0;i<M;++i){
    ll a,b;
    cin >> a>> b;a--,b--;
    tree.merge(a,b);
  }
  ll ans=0;
  for(ll i=0;i<N;++i){
    ans = max(ans, ll(tree.size(i)));
  }
  cout << ans << endl;
}


Measured memory_bytes: 4048
#include <bits/stdc++.h> 
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
#define asn ans
using namespace std;
template <typename T> istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;

int main() {
	int a, b, c, x, y; CI a >> b >> c >> x >> y;
	int zero = 0;
	vector<ll> ans;

	REP(i, 100001) {
		ll tmp = (2 * c*i) + (max(zero, x - i)*a) + (max(zero, y - i)*b);
		ans.push_back(tmp);
	}

	sort(all(ans));
	CO ans[0] EN;

	return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  while(true){
    int n;
    cin >> n;
    if(n == 0){
      break;
    }
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
      cin >> a[i];
    }
    int t;
    cin >> t;
    int ans = 0;
    int left = 0, right = n - 1;
    while(left <= right){
      ++ans;
      int mid = (left + right) / 2;
      if(a[mid] == t){
	break;
      }
      if(a[mid] > t){
	right = mid - 1;
      }
      else{
	left = mid + 1;
      }       
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1192
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))

def linearSearch(t):
  i = 0
  tmp = S + [t]
  while tmp[i] != t:
    i += 1
  if i == n:
    return "Not Found"
  return i

cnt = 0
for t in T:
  idx = linearSearch(t)
  if idx != 'Not Found':
    cnt += 1
    
print(cnt)


Measured memory_bytes: 6552
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}
int n,t;
const int n_max = 3005;
int cost[n_max];
int value[n_max];

int dp1[n_max][n_max];
int dp2[n_max][n_max];
signed main(){
    cin >> n >> t;
    REP(i,n) cin >> cost[i] >> value[i];
    REP(i,n_max) REP(j,n_max){
        dp1[i][j] = 0;
        dp2[i][j] = 0;
    }
    REP(i,n){
        REP(j,3001){
            if(j - cost[i] >= 0){
                dp1[i+1][j] = max(dp1[i][j],dp1[i][j - cost[i]] + value[i]);
            }
            else{
                dp1[i+1][j] = dp1[i][j];
            }
        }
    }
    reverse(cost,cost + n);
    reverse(value,value + n);
    REP(i,n){
        REP(j,3001){
            if(j - cost[i] >= 0){
                dp2[i+1][j] = max(dp2[i][j],dp2[i][j - cost[i]] + value[i]);
            }
            else{
                dp2[i+1][j] = dp2[i][j];
            }
        }
    }
    reverse(cost,cost + n);
    reverse(value,value + n);
    int ans = 0;
    /*
    REP(i,n+1){
        debug(dp1[i][2999]);
        debug(dp2[i][2999]);
    }
    */


    REP(i,n){
        int tmp = 0;
        REP(j,t){
            chmax(dp1[i][j + 1],dp1[i][j]);
            chmax(dp2[n-i-1][j+1] , dp2[n-i-1][j]);  
        }
        REP(j,t){
            chmax(tmp,dp1[i][j] + dp2[n - i - 1][t - j - 1]);
        }

        chmax(ans,tmp + value[i]);
    }
    cout << ans << endl;

}

Measured memory_bytes: 141568
using System;
using System.Linq;

namespace HelloWorld
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int[] data = new int[2];
                data = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                int h = data[0];
                int w = data[1];

                if (h == 0 && w == 0) break;
                else
                for (int i = 0; i < h; i++)
                {
                    if (i == 0 || i == h - 1)
                    {
                        for (int j = 0; j < w; j++)
                        {
                            Console.Write("#");
                        }
                        Console.WriteLine();
                    }
                    else
                    {
                        Console.Write("#");
                        for (int j = 0; j < w - 2; j++)
                        {
                            Console.Write(".");
                        }
                        Console.Write("#");
                        Console.WriteLine();
                    }
                }
                Console.WriteLine();
            }

        }
    }
}


Measured memory_bytes: 16164
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}



int n,k,a[505],sum=0,ans=1;

void solve(int x){

    int tot = 0;
    priority_queue<pair<int,int>> q;
    for(int i=1;i<=n;i++){
        int rem = a[i]%x;
        if(rem==0)continue;
        int neg = -rem;
        int pos = x-rem;
        q.push({neg,pos});
        tot+=pos;
    }
    int cnt = 0;
    while(tot>0){
        pi p = q.top();q.pop();
        tot-=p.second;
        tot+=p.first;
        cnt+=abs(p.first);
    }
    //cout << cnt << " " << x << endl;
    if(cnt<=k){
        ans = max(ans,x);
    }

}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);


    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum+=a[i];
    }
    //cout << sum << endl;
    for(int i=1;i*i<=sum;i++){
        if(sum%i==0){
            solve(i);
            if(sum/i!=i){
                solve(sum/i);
            }
        }
    }
    cout << ans << endl;




return 0;
}
///....




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

  struct input{
   public long D;
   public long N;
  }

class MainClass {
  static input input; 

  public static void Main (string[] args) {
    input.N = long.Parse(Console.ReadLine());
    var list = Console.ReadLine().Split(' ').Select(long.Parse).ToList();
    var c = (long)0;
   
    for(var i = 0; i < input.N; i++){
      var cc = 0;
        if(list[i] % 2 == 0){
          var temp = list[i];
          while(temp % 2 == 0){
            temp = temp / 2;
            cc++;
          }
        }
        c += cc;
    }

    var ans = c;
 
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 14176
//-------All power is within you,you can do Anything and Everything.---------//
 
    #include <bits/stdc++.h>
    using namespace std;
  
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ M $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
 
    #define pb push_back
    #define MP make_pair
    #define F first
    #define S second
    #define sc(x) scanf("%lld",&x)
    #define pf(x) printf("%lld\n",x)
    #define int long long
    #define all(x) x.begin(),x.end() 
    #define fo(i,a,b) for(int i=a;i<b;i++)
    #define rfo(i,b,a) for(int i=b;i>=a;i--)
    #define mem( a, val ) memset(a, val, sizeof( a ) )
    #define deci( x ) cout<<fixed<<setprecision( x );
    #define bitcount( x ) __builtin_popcountll( x )
    #define endl "\n" 
    
    #define XOX 
    
    typedef vector<int> vi;
    typedef pair<int,int> pi; 
    
    const int MOD =  1000000007 ;
    const int MAX = 2e6 + 7;
    const int INF = 1e15;
    const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ DEB $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
    
    #define deb(x) cout<<#x<<" "<<x<<endl;

//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ V $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//  
    
    int i,j,k,t,n,q,l,r,mid;

//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ F $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//

    int pre[MAX],suf[MAX],sum=1;
    void solve()
    {
        cin>>n>>k;
        fo(i,0,n+1)
        {
            if(i)
            pre[i]+=pre[i-1]+i;
        }
        rfo(i,n,0)
        {
            suf[i]+=suf[i+1]+i;
        }
        reverse(suf,suf+n+1);

        fo(i,k,n+1)
        {
            // deb(pre[i-1])
            // deb(suf[i-1])
            sum=(sum+(suf[i-1]-pre[i-1]+1))%MOD;
        }
        cout<<sum<<endl;
    }
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
//                          GAME STARTS FROM HERE                            //
 
    int32_t main() 
    {
    
        // int start,stop=clock();
        // cout<<"time:"<<(stop-start)/double(CLOCKS_PER_SEC)*1000<<endl;
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);

        // sc(t);while(t--)
        // cin>>t;while(t--)
            solve();
    
        return 0;
    }

Measured memory_bytes: 6640
#include<iostream>
using namespace std;
int main() {
    int n,i,j,oishisa = 0;
    cin >> n;
    int d[n+1];
    for(i = 0 ; i < n; i++) {
        cin >> d[i];
    }
    for (i = 0; i < n; i++) {
        for(j = i+1; j < n; j++) {
            
            oishisa += d[i]*d[j];
            
        }
    }
    cout << oishisa << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 2e5+5;
ll n, maks=-1, arr[nax], rra[nax];
unordered_map<ll, ll>cnt;

bool cmp(ll s1, ll s2){
		return s1>s2;
	}

int main(){
	IOS
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> rra[i];
		arr[i]=rra[i];
		cnt[rra[i]]++;
	}
	sort(arr+1, arr+n+1, cmp);  
	for(int i=1;i<=n;i++){
		if(rra[i]==arr[1]){
			if(cnt[rra[i]]>1){
				cout << rra[i] << '\n';
			}
			else{
				cout << arr[2] << '\n';
			}
		}
		else{
			cout << arr[1] << '\n';
		}
	}
}


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

void insertionSort(int* A, int N);

int main()
{
	int n;
	int* a;

	cin >> n;

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

	insertionSort(a, n);

	delete[] a;
}

void insertionSort(int* A, int N)
{
	for (int i = 0; i < N; ++i) {
		int v = A[i];
		int j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
		for (int k = 0; k < N; ++k) {
			cout << A[k];
			if (k != N - 1) { cout << ' '; }
		}
		cout << endl;
	}
}

Measured memory_bytes: 1196
import java.util.*;class Main{public static void main(String[]z){int n=1001,i,j,k,c,t;int[]a=new int[n*n];for(i=1;i<n;i++)for(j=i+2;j<n;a[i*n+j++]=c)for(c=0,k=i;k<j;k++)c+=k;Scanner s=new Scanner(System.in);for(c=0;(t=s.nextInt())>0;System.out.println(c),c=0)for(int b:a)c+=b==t?1:0;}}

Measured memory_bytes: 16000
#include <stdio.h>

int main()
{
	int i,j,k,l,n,cnt;
	
	while(scanf("%d",&n)!=EOF){
		cnt=0;
		for(i=9;i>=0;i--){
			for(j=9;j>=0;j--){
				for(k=9;k>=0;k--){
					for(l=9;l>=0;l--){
						if(i+j+k+l==n){
							cnt++;
						}
					}
				}
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

template <class T>
T inf = numeric_limits<T>::max();

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

  int N,M;
  cin >> N >> M;
  vector<int> H(N);
  repr(i, N, 0) {
    cin >> H[i];
  }

  vector<vector<int>> G(N+1);
  for (int i = 0; i < M; ++i) {
    int a,b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    int h = H[i-1];
    bool flag = true;
    for (auto& t : G[i]) {
      if (H[t-1] >= h) {
        flag = false;
      }
    }

    if (flag) ans += 1;
  }

  cout << ans << endl;
}


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

typedef long long int llint;

int main()
{
  llint l[100];
  int n;
  cin>> n;

  l[0] = 2;
  l[1] = 1;

  for(int i = 2; i <= 86; i++) l[i] = l[i - 1] + l[i - 2];

  cout<< l[n] <<endl;

  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.function.BiConsumer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			long n = in.nextLong();
			long ans = Long.MAX_VALUE;
			for (long i = 1; i <= Math.sqrt(n); i++) {
				long a = i;
				long b = n / i;
				if (a * b == n) {
					ans = Math.min(ans, (a - 1) + (b - 1));
				}
			}
			out.println(ans);
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public char nextChar() {
			return next().charAt(0);
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

	}
}


Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

void solve(long long H, long long W){
    if(H==1||W==1){
        cout<<1<<endl;
        return;
    }
    cout<<((H*W+1)/2)<<endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    solve(H, W);
}


Measured memory_bytes: 256
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    X, Y = map(int, input().split())

    ans = "No"
    for a in range(X+1):
        for b in range(X+1):
            if a + b == X and a*2 + b*4 == Y:
                ans = "Yes"
    
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 77580
#include <bits/stdc++.h>
 
#define REP(i, a, b) for (int i = (int)a; i <= (int)b; i++)
#define fi first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
 
using namespace std;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<int, int> pii;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const i64 MOD = 1000000007;
const int INF = 2000000000;

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

    vi a(n);
    REP(i, 0, n-1) {
		cin >> a[i];    	
    }

    sort(all(a));                    

    int b = a[n/2], v = a[n/2-1];

    cout << b - v << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(void){
    int n, k;
    string s;
    cin >> n >> s >> k;
    for(int i=0; i<n; ++i){
        if(char(s[i]) != char(s[k-1])){
            s[i] = '*';
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)

const int N = 1e5 + 5, mod = 0;
int a[N];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    for (int i = 0; i < n + n; ++i)
        cin >> a[i];
    sort(a, a + n + n);
    int res = 0;
    for (int i = 0; i < n + n; i += 2)
        res += a[i];
    cout << res << '\n';




}








Measured memory_bytes: 256
/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define Str(x) to_string(x)
#define len(s) (int)s.size()

typedef long long ll;
typedef long double lld;
typedef string str;
typedef unsigned long long ull;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, a;
    cin >> n >> a;
    cout << (n + a - 1) / a;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define arr array
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b;
	cin >> a >> b;

	for (int i=1; i<1e4; ++i) {
		int a2=i*8/100, b2=i*10/100;
		if(a2==a && b2==b) {
			cout << i;
			return 0;
		}
	}
	cout << -1;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdint>
#include<queue>
#include<algorithm>

int main() {
  int N, K; std::cin >> N >> K;
  int64_t sum = 0;
  std::queue<int64_t> q;
  for(int i = 0; i < K; ++i) {
    int64_t p; std::cin >> p;
    sum += p+1;
    q.push(p+1);
  }
  int64_t ans = sum;
  for(int i = K; i < N; ++i) {
    int64_t p; std::cin >> p;
    sum += p+1;
    q.push(p+1);
    sum -= q.front();
    q.pop();
    ans = std::max(ans, sum);
  }
  std::cout << ans/2 << "." << (ans%2? 5: 0) << std::endl;
  return 0;
}



Measured memory_bytes: 1920
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cstdlib>
using namespace std;
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
inline void Yeah(){puts("Yes");exit(0);}
int main(){ 
	int n=read(),m=read(),k=read();
	for(int i=1;i<=n;++i){
		int kk=(k-i*m),a=n-i-i;
		if(!kk || a && (kk>>31&1)==(a>>31&1) && kk%a==0 && kk/a<=m)Yeah();
	}
	puts("No");
	return 0;
}


Measured memory_bytes: 256
import sys
N,K = map(int,raw_input().split())
nums = list(map(int,raw_input().split()))
f = 0
f2 = 0
for i in range(N):
    if nums[i]<0:
        f = 1
    if nums[i]>0:
        f2 = 1
if not f or not f2:
    if nums[0]<0:
        print -nums[N-K]
    else:
        print nums[K-1]
    sys.exit()
ans = pow(10,15)
for i in range(N-1):
    if nums[i]<0 and nums[i+1]>=0:
        cnt = 0
        l = i
        r = i
        for j in range(i,-1,-1):
            cnt += 1
            if cnt==K or l==0:
                break
            l -= 1
        for j in range(i+1,N):
            if cnt==K or r==N-1:
                break
            cnt += 1
            r += 1
        for j in range(K):
            if l>i or r>N-1:
                break
            cur = nums[l]
            cur2 = nums[r]
            l += 1
            r += 1
            if cur>=0:
                break
            ans = min(ans,abs(cur*2)+cur2,abs(cur)+cur2*2)
print ans

Measured memory_bytes: 42900
#ABC121D
A,B=map(int,input().split())
ruijo=[]
now=1
for j in range(51):
    ruijo.append(now)
    now*=2
if A==B:print(A)
else:
    if A>0:A-=1
    from collections import defaultdict
    data=defaultdict(int)
    one=[[0,1,1,0],[0,0,1,1]]
    data[1]=one[int(bin(A)[-1])][(B-A)%4]
    for i in range(2,1+len(bin(B)[2:])):
        Aidx=A%ruijo[i]
        Bidx=B%ruijo[i]
        if Aidx==Bidx:data[i]=0
        elif Aidx<Bidx:
            data[i]=(max(Bidx,ruijo[i-1]-1)-max(Aidx,ruijo[i-1]-1))%2
        elif Bidx<Aidx:
            data[i]=(max(ruijo[i-1]-1,Bidx)-(ruijo[i-1]-1)+ruijo[i]-1-max(ruijo[i-1]-1,Aidx))%2
    ans=0
    for x,y in data.items():
        ans+=ruijo[x-1]*y
    print(ans)

Measured memory_bytes: 3316
#include <stdio.h>

int main(void){
    int n,i,j,u,k,l;
    int a[100][100];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            a[i][j] = 0;
        }
    }
    for(i=0;i<n;i++){
        scanf("%d",&u);
        scanf("%d",&k);
        for(j=0;j<k;j++){
            scanf("%d",&l);
            a[u-1][l-1] = 1;
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("%d",a[i][j]);
            if(j!=n-1){
                printf(" ");
            }
        }
        printf("\n");
    }
}


Measured memory_bytes: 2036
#include<iostream>
#include<vector>
#include <unordered_map>  
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <sstream>
#include <cmath>
#include <float.h>
using namespace std;


#define N 200000

int main(){
	unsigned int n, x[N], xc[N], middle;
	cin >> n;
	for (unsigned int i = 0; i < n; ++i) {
		cin >> x[i];
		xc[i] = x[i];
	}
	sort(xc, xc + n);
	middle = xc[n / 2];
	for (unsigned int i = 0; i < n; ++i) {
		if (x[i] == middle) {
			cout << xc[n/2-1]  << endl;
		}
		else if (x[i] < middle) {
			cout << middle << endl;
		}
		else {
			cout << xc[n / 2 - 1] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3712
def main():
    N, M, K = map(int, input().split())

    MAX_N = 2000000

    s = [0] * MAX_N
    t = [0] * MAX_N
    for i, c in zip(range(N - 1, -1, -1), input()):
        s[i] = int(c)
    for i, c in zip(range(M - 1, -1, -1), input()):
        t[i] = int(c)

    len_max = max(N, M) - 1

    for i in range(len_max, -1, -1):
        j = i
        z = K
        while s[j] and t[j] and z:
            s[j] = t[j] = 0
            s[j + 1] += 1
            t[j + 1] += 1
            j += 1
            z -= 1
            js = jt = j

            while s[js] == 2:
                s[js] = 0
                s[js + 1] += 1
                js += 1

            while t[jt] == 2:
                t[jt] = 0
                t[jt + 1] += 1
                jt += 1

            j = max(js, jt)
            
        len_max = max(len_max, j)

    s = s[:len_max + 1]
    t = t[:len_max + 1]

    while not s[-1]:
        s.pop()
    while not t[-1]:
        t.pop()

    print(*reversed(s), sep='')
    print(*reversed(t), sep='')
    
main()

Measured memory_bytes: 199904
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;
const ll INF=1e16;
int main()
{
    int n, m; ll p; cin>>n>>m>>p;
    vector<P> g[2510], gr[2510];
    for(int i=0; i<m; i++){
        int a, b; ll c; cin>>a>>b>>c;
        a--; b--; c-=p;
        g[a].push_back({b, c});
        gr[b].push_back({a, c});
    }
    bool ok[2510]={};
    ok[n-1]=1;
    queue<int> que;
    que.push(n-1);
    while(!que.empty()){
        int x=que.front();
        que.pop();
        for(auto p:gr[x]){
            int y=p.first;
            if(!ok[y]){
                ok[y]=1;
                que.push(y);
            }
        }
    }
    ll d[2510];
    fill(d, d+n, -INF);
    d[0]=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(auto p:g[j]){
                int k=p.first;
                if(d[k]<d[j]+p.second){
                    d[k]=d[j]+p.second;
                }
            }
        }
    }
    int cnt=0;
    for(int j=0; j<n; j++){
        for(auto p:g[j]){
            int k=p.first;
            if(d[k]<d[j]+p.second){
                if(d[k]>-INF/2 && ok[k]) cnt++;
            }
        }
    }
    if(cnt>0){
        cout<<-1<<endl;
        return 0;
    }
    cout<<max(0ll, d[n-1])<<endl;
    return 0;
}

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

const int maxn = 100005, Inf = 1 << 30;

inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

int n;
queue<int> q;
vector<int> vec[maxn];
int eu[maxn], ev[maxn], vis[maxn];

struct edge
{
	int to, next, cap;
} e[maxn << 3];
int s, t, h[maxn << 1], cur[maxn << 1], dis[maxn << 1], mat[maxn << 1], tot = 1;

inline void add(int u, int v, int w)
{
	e[++tot] = (edge) {v, h[u], w}; h[u] = tot;
	e[++tot] = (edge) {u, h[v], 0}; h[v] = tot;
}

bool bfs()
{
	static int l, r, q[maxn << 1];
	memset(dis + 1, 0, sizeof(int) * t);
	l = 0; q[r = 1] = s; dis[s] = 1;
	while (l < r) {
		int u = q[++l];
		for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
			if (!dis[v] && e[i].cap) dis[v] = dis[u] + 1, q[++r] = v;
	}
	return dis[t];
}

int dfs(int u, int a)
{
	if (u == t || !a) return a;
	int f, flow = 0;
	for (int &i = cur[u], v; v = e[i].to, i; i = e[i].next)
		if (dis[v] == dis[u] + 1 && (f = dfs(v, min(a, e[i].cap)))) {
			flow += f; a -= f;
			e[i].cap -= f; e[i ^ 1].cap += f;
			if (!a) break;
		}
	return flow;
}

int max_flow()
{
	int res = 0;
	while (bfs()) {
		memcpy(cur + 1, h + 1, sizeof(int) * t);
		res += dfs(s, Inf);
	}
	for (int u = 1; u < n; ++u)
		for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
			if (!e[i].cap && v != s) {mat[u] = v; mat[v] = u; break;}
	return res;
}

int main()
{
	n = gi();
	for (int c, w, i = 1; i < n; ++i) {
		c = gi();
		while (c--) {
			w = gi(); vec[w].push_back(i);
			if (w != n) add(w, i + n - 1, 1);
		}
	}
	s = n * 2 - 1; t = s + 1;
	for (int i = 1; i < n; ++i) add(s, i, 1), add(i + n - 1, t, 1);
	
	if (max_flow() != n - 1) return puts("-1"), 0;
	int cnt = 0; q.push(n);
	while (!q.empty()) {
		int u = q.front(); q.pop(); ++cnt;
		for (int e : vec[u])
			if (!vis[e]) vis[e] = 1, q.push(mat[e + n - 1]), eu[e] = u, ev[e] = mat[e + n - 1];
	}
	if (cnt != n) return puts("-1"), 0;
	for (int i = 1; i < n; ++i) printf("%d %d\n", eu[i], ev[i]);
	
	return 0;
}


Measured memory_bytes: 22008
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, a[100009];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    a[0]--;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            cout << "No" << E;
            return 0;
        }
        else if (a[i] > a[i - 1]) {
            a[i]--;
        }
    }
    cout << "Yes" << E;
    //system("pause");
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include<stdio.h>
using namespace std;

int main()
{
    int Max=0,c=0,n,x,y=0;
    scanf("%d",&n);
    scanf("%d",&y);
    n--;
    while(n--){
      scanf("%d",&x);
      if(x<=y){
        c++;
      }
      else{
        if(Max<c){
            Max=c;
        }
        c=0;
      }
      y=x;
    }
    if(Max<c){
        Max=c;
        }
    printf("%d",Max);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);

template<class T> inline T sqr(T x) {return x*x;}

int a[100000+1];

int main() {
	int n,l;
	cin >> n >> l;
	REP(i,0,n) {
		cin >> a[i];
	}
	REP(i,0,n-1) {
		int len = a[i] + a[i+1];
		if (len >= l) {
			cout << "Possible" << endl;
			REP(j,1,i+1) cout << j << endl;
			for(int j = n - 1; j > i + 1; --j) cout << j << endl;
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << "Impossible" << endl;
	
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


ll n,k;
ll v[110];

int main(){
	cin>>n>>k;
	REP(i,n)
		cin>>v[i];
	
	ll ans=0;
	priority_queue<ll,vector<ll>,greater<ll> > que;
	for(int i=0;i<=k;i++){
		for(int j=0;j+i<=k&&i+j<=n;j++){
			ll t=0;
			for(int ii=0;ii<i;ii++){
				t+=v[ii];
				if(v[ii]<0){
					que.push(v[ii]);
				}
			}
			for(int jj=0;jj<j;jj++){
				t+=v[n-jj-1];
				if(v[n-jj-1]<0){
					que.push(v[n-jj-1]);
				}
			}
			
			for(int kk=0;kk<k-i-j&&que.size();kk++){
				ll ss=que.top();que.pop();
				t-=ss;
			}
			ans=max(t,ans);
			while(que.size()){
				que.pop();
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
ans = 0
if n < 10:
    ans = n
else:
    ans += 9
if n >= 100 and n <= 999:
    ans += n - 99
if n >= 1000:
    ans += 900
if n >= 10000 and n <= 99999:
    ans += n - 9999
if n == 100000:
    ans += n - 10000
    
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define F(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define FD(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define pii pair<int,int>
#define reset(x,y) memset(x, y,sizeof(x))
#define MIN(x,y) if (x > (y)) x = (y)
#define MAX(x,y) if (x < (y)) x = (y)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define EL putchar('\n');
#define mod 1000000007
#define oo 1000006
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
void write(int x)
{
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int n,k;
int a[oo];
int dp[100005][105];
void ReadInPut()
{
    n=read();
    k=read();
    F(i,0,n-1)a[i]=read();
}
void Solve()
{
    F(i,0,n-1){
        dp[0][i] = 1;
        F(j,1,k){
            if(i!=0){
                dp[j][i] = dp[j-1][i];
                dp[j][i] += dp[j][i-1];
                if (j >= a[i] + 1) dp[j][i] -= dp[j-a[i]-1][i-1];
                if(dp[j][i]<0)dp[j][i]+=mod;
                dp[j][i] %= mod;
            }
            else{
                dp[j][i] = j<=a[i];
            }
        }
    }
    cout<<dp[k][n-1];
}
main()
{
//    freopen("t.INP","r",stdin);
  //  freopen(".OUT","w",stdout);
    int sotest=1;
    //cin>>sotest;
    for(int i=1;i<=sotest;i++)
    {
        ReadInPut();
        Solve();
    }
}


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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n;
	cin>>n;
	int ans = 0;
	for(int i = 0; i < n; i++){
		int x; cin>>x;
		ans += x - 1;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <assert.h>
using namespace std;

typedef pair<double, double> Pdd;

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef L Segment;

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

bool intersectSS(const Segment &s, const Segment &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}

P crosspoint(const L &l, const L &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m[0] + B / A * (m[1] - m[0]);
}

int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    vector<pair<Pdd, int> > vec;
    double xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    Segment express(P(xa, ya), P(xb, yb));
    int N; cin >> N;
    int O, I;
    for(int i=0; i<N; i++) {
      cin >> xa >> ya >> xb >> yb >> O >> I;
      Segment line(P(xa, ya), P(xb, yb));
      if(intersectSS(express, line)) {
	P crs = crosspoint(express, line);
	vec.push_back(make_pair(Pdd(crs.real(), crs.imag()), (O+I)%2));
      }
    }
    
    sort(vec.begin(), vec.end());
    
    int ans = 1<<29;
    for(int s=0; s<2; s++) {
      int cnt = 0, now = s;
      for(int i=0; i<vec.size(); i++) {
	if(now == vec[i].second) {
	  cnt ++; now = 1-now;
	}
      }
      ans = min(ans, cnt);
    }
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1260
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    cout << n * (n + 1) / 2 << endl;
}


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


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 200010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n;

int fa[maxn],vi[maxn],Is[maxn];

vector<int> G[maxn];

set<int> has[maxn];

int f[maxn],f2[maxn],tmp[maxn];

void dfs(int u){
	for(auto v:G[u])if(!Is[v]){
		dfs(v);
		has[u].insert(f[v]);
	}
	for(int i=0;;i++)if(!has[u].count(i)){
		f[u]=i;
		break;
	}
}

void Work(){
	int x=1;
	while(!vi[x])vi[x]=1,x=fa[x];
	memset(vi,0,sizeof(vi));
	while(!Is[x])Is[x]=1,x=fa[x];
	REP(i,1,n)if(Is[i]){
		dfs(i);
		f2[i]=f[i]+1;
		while(has[i].count(f2[i]))f2[i]++;
	}
	int t=x;
	tmp[x]=f[x];
	while(fa[x]!=t){
		if(f[fa[x]]==tmp[x])tmp[fa[x]]=f2[x];else tmp[fa[x]]=f[x];
		x=fa[x];
	}
	if(tmp[t]!=tmp[x])return void(puts("POSSIBLE"));
	x=t;tmp[x]=f2[x];
	while(fa[x]!=t){
		if(f[fa[x]]==tmp[x])tmp[fa[x]]=f2[x];else tmp[fa[x]]=f[x];
		x=fa[x];
	}
	if(f[t]==tmp[x])puts("POSSIBLE");else puts("IMPOSSIBLE");
}

void Init(){
	read(n);
	REP(i,1,n){
		int x;read(x);
		G[x].PB(i);
		fa[i]=x;
	}
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 30592
def otoshidama(x, y):
    minus = 0
    tenthousand = range(x+1)
    for i in tenthousand:
        for p in range(x+1-minus):
            o = x - (i+p)
            if y == (i*10000+p*5000+o*1000):
                return str(i)+' '+str(p)+' '+str(o)
        minus += 1
    return '-1 -1 -1'
N, Y = map(int,input().split())
print(otoshidama(N, Y))

Measured memory_bytes: 3064
n = int(input())

if n == 0:
  print(2)
elif n == 1:
  print(1)
else:

    l0 = 2
    l1 = 1
    result = 0
    for i in range(n-1):
      result = l0+l1
      l0 = l1
      l1 = result

    print(result)


Measured memory_bytes: 3060
n = int(input())
b = list(map(int, input().split()))

a = [0]*n
for i in range(n-1):
    if i == 0:
        a[0] = b[0]
        a[1] = b[0]
    elif b[i] >= b[i-1]:
        a[i+1] = b[i]
    elif b[i] < b[i-1]:
        a[i+1] = b[i]
        a[i] = b[i]
print(sum(a))

Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
  Scanner sc;

  void run() {
    for ( ;; ) {
      int n = ni();
      int m = ni();
      int l = ni();
      if ( ( n | m | l ) == 0 ) {
        break;
      }

      int[][] dm = new int[n + 1][n + 1];
      int[][] em = new int[n + 1][n + 1];
      boolean[][] lk = new boolean[n + 1][n + 1];

      for ( int i = 0; i < m; ++i ) {
        int a = ni();
        int b = ni();
        int d = ni();
        int e = ni();
        dm[ a ][ b ] = dm[ b ][ a ] = d;
        em[ a ][ b ] = em[ b ][ a ] = e;
        lk[ a ][ b ] = lk[ b ][ a ] = true;
      }

      boolean[][] ok = new boolean[n + 1][l + 1];
      int[][] dp = new int[n + 1][l + 1];
      for ( int[] v : dp )
        Arrays.fill( v, 1 << 28 );
      dp[ 1 ][ l ] = 0;
      ok[ 1 ][ l ] = true;
      for ( int h = 0; h < n; ++h ) {
        for ( int i = 1; i <= n; ++i ) {
          for ( int j = 1; j <= n; ++j ) {
            if ( lk[ i ][ j ] ) {
              for ( int k = 0; k <= l; ++k ) {
                if ( ok[ i ][ k ] ) {
                  if ( k - dm[ i ][ j ] >= 0 ) {
                    dp[ j ][ k - dm[ i ][ j ] ] = Math.min( dp[ j ][ k
                        - dm[ i ][ j ] ], dp[ i ][ k ] );
                    ok[ j ][ k - dm[ i ][ j ] ] = true;
//                    debug( i, j, k - dm[ i ][ j ], dp[ j ][ k - dm[ i ][ j ] ] );
                  }
                  dp[ j ][ k ] = Math.min( dp[ j ][ k ], dp[ i ][ k ]
                      + em[ i ][ j ] );
                  ok[ j ][ k ] = true;
//                  debug( "a", i, j, k, dp[ j ][ k ] );
                }
              }
            }
          }
        }
      }

      int min = 1 << 28;
      for ( int k = 0; k <= l; ++k ) {
        min = Math.min( min, dp[ n ][ k ] );
      }

      System.out.println( min );
    }
  }

  Main() {
    sc = new Scanner( System.in );
  }

  int ni() {
    return sc.nextInt();
  }

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

  void debug(Object... os) {
    System.err.println( Arrays.deepToString( os ) );
  }
}

Measured memory_bytes: 61184