akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

struct SegmentTree{
	int n;
	vector<int> tree;
	SegmentTree() {}
	SegmentTree(int _n) {
		n = _n;
		tree.assign(n, 0);
	}
	void upd(int pos, int val) {
		for (; pos < n; pos |= pos + 1)
			tree[pos] += val;
	}
	void upd(int l, int r, int x) {
		/*for (int i = l; i <= r; i++) {
			tree[i] += x;
		}*/
		upd(l, x);
		upd(r + 1, -x);
	}

	int get(int pos) {
		int ans = 0;
		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) {
			ans += tree[pos];
		}
		return ans;
	}
};

int n,k;
vector<int> a;

void read() {
	cin >> n >> k;
	a.resize(n);
	for (auto &i : a) {
		cin >> i;
	}
}

vector<int> ans;

void run() {
	for (int it = 0; it < k; it++) {
		SegmentTree tree(n);
		ans.resize(n);
		for (int i = 0; i < n; i++) {
			tree.upd(max(0, i - a[i]), min(n - 1, i + a[i]), 1);
		}
		for (int i = 0; i < n; i++) {
			ans[i] = tree.get(i);
		}
		if (a == ans) break;
		a = ans;
		/*cout << "a = ";
		for (auto i : a) cout << i << " ";
			cout << endl;*/
		//cout << "it = " << it << endl;
	}
}

void write() {
	for (auto i : ans) {
		cout << i << " ";
	}
	cout << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Measured memory_bytes: 5732
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
const int INF = 0x3f3f3f3f;

int main() {
  int x, y;
  cin >> x >> y;
  for (int i = 0; i <= x; i++) {
    if (i * 2 + (x - i) * 4 == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <cassert>
#include <cmath>
#include <iostream>
using namespace std;
int main() {
    long long s; cin >> s;
    long long n = (long long)(sqrt(s));
    while (n*n < s) n++;
    int a, b, c, d;
    if (n * (n-1) < s) { a = n; d = n; b = 1; c = (long long)a*d - s; }
    else { a = n; d = n-1; b = 1; c = (long long)a*d - s; }
    cout << 0 << ' ' << 0 << ' ' << a << ' ' << b << ' ' << c << ' ' << d << endl;
    //if ((long long)a*d - (long long)b*c != s) cout << "NG" << endl;;
}


Measured memory_bytes: 384
#include <stdio.h>
int main()
{
    int d;
    scanf("%d",&d);
    if(d == 25){
        printf("Christmas\n");
    }
    else if(d == 24){
        printf("Christmas Eve\n");
    }
    else if(d == 23){
        printf("Christmas Eve Eve\n");
    }
    else if(d == 22){
        printf("Christmas Eve Eve Eve\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll choose2(ll n){
	return n*(n-1)/2;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
		a[i]--;
	}
	vector<int> cnt(n);
	rep(i,n) cnt[a[i]]++;
	ll tot = 0;
	rep(i,n){
		tot += choose2(cnt[i]);
	}
	rep(i,n){
		ll ans = tot;
		ans -= choose2(cnt[a[i]]);
		ans += choose2(cnt[a[i]]-1);
		cout << ans << endl;
	}
    return 0;
}

Measured memory_bytes: 4096
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod=MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


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



const int N = 5002;
int n, arr[N], DP[N], storage[2][N];
vector<int> adj[N];


void dfs(int v){

	if(adj[v].empty()){
		DP[v] = 0;
		return;
	}


	for(auto vv : adj[v]){
		dfs(vv);
	}

	for(int i=0;i<N;i++)	storage[0][i] = storage[1][i] = MOD;
	storage[0][0] = 0;

	for(auto vv : adj[v]){

		int a = arr[vv], b = DP[vv];
		
		for(int j=arr[v];j>=0;j--){
			if(j-a >= 0)	storage[1][j] = min(storage[1][j], storage[0][j-a] + b);
			if(j-b >= 0)	storage[1][j] = min(storage[1][j], storage[0][j-b] + a);
		}

		for(int i=0;i<N;i++){
			storage[0][i] = storage[1][i];
			storage[1][i] = MOD;
		}
	}

	DP[v] = MOD;
	for(int i=0;i<=arr[v];i++)
		DP[v] = min(DP[v], storage[0][i]);
}



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

    cin>>n;
    for(int i=2;i<=n;i++){
    	int p;
    	cin>>p;
    	adj[p].pb(i);
    }
    for(int i=1;i<=n;i++){
    	cin>>arr[i];
    }


    dfs(1);

// cout<<"DP: ";for(int i=1;i<=n;i++)	cout<<DP[i]<<" ";cout<<endl;

    if(DP[1] == MOD)	cout<<"IMPOSSIBLE";
    else	cout<<"POSSIBLE";
    return 0;
}








Measured memory_bytes: 640
/*   --------------------
    |       LOSER        |
    |     ~NOOBOSS~      |
     --------------------
*/
#include <bits/stdc++.h>
using namespace std;
#define      mxx                 LLONG_MAX
#define      mnn                 LLONG_MIN
#define      Y()                 cout<< "YES" <<endl
#define      N()                 cout << "NO"<<endl
#define      endl                "\n"
#define      max_3(a,b,c)        max(a, max(b,c))
#define      min_3(a,b,c)        min(a, min(b,c))
#define      gcd(a,b)            __gcd(a,b)
#define      lcm(a,b)           (a*b)/gcd(a,b)
#define      loser               return 0
#define      ll                  long long
#define      PI                  acos(-1)
#define      mem(a,v)            memset(a,v,sizeof(a))
#define      SORT(v)             sort(v.begin(),v.end())
#define      REV(v)              reverse(v.begin(),v.end())
#define      B                   begin()
#define      E                   end()
#define      V                   vector
#define      F                   first
#define      S                   second
#define      PSB                 push_back
#define      MP                  make_pair
#define      flash               cout.flush()
#define      InTheNameOfGod      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll MOD = 998244353;
constexpr ll mod = 1e9  + 7;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*-----*/
#define bug1(a)  cerr<<a<<endl;
#define bug2(a,b)  cerr<<a<<" "<<b<<endl;
#define bug3(a,b,c)  cerr<<a<<" "<<b<<" "<<c<<endl;
/*----*/
const ll N=2e5+5;
vector<ll> adj[N];
ll power(ll n,ll p){if(p==0) return 1;if(p==1)return n;if(p%2)return power(n,p-1)*n;else{ll x=power(n,p/2);return x*x;}}
ll modpow(ll a,ll b,ll m){ll ans=1;while(b){if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}return ans;}
ll nsum(ll num){return (num*(num+1))/2;}
void edge (ll u,ll v) {adj[u].PSB(v) ;adj[v].PSB(u);}
/*------------------START---------------------*/


/*-----*/
void solve(){
   ll n;
   string s;
   cin>>n;
   ll pmx,nmx,pmn,nmn;
   for(ll i=0;i<n;i++){
    ll x,y;
    cin>>x>>y;
    if(!i){
        pmx=pmn=x+y;
        nmx=nmn=x-y;
    }
    else{
        ll pos=x+y; ll neg=x-y;
        pmx=max(pmx,pos); nmx=max(nmx,neg);
        pmn=min(pmn,pos); nmn=min(nmn,neg);
    }
   }
   ll ans=pmx-pmn;
   ans=max(ans,nmx-nmn);
   cout<<ans<<endl;


}
/*-----*/
int main(){
   InTheNameOfGod

   ll Test=1;
   //cin>>Test;
   while(Test--){
     solve();
    }
  loser;
}
///////   C O D I N G  I S  L I F E   ///////


Measured memory_bytes: 8340
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin >> N;
  vector<int> P(N); vector<int> Q(N); vector<int> R(N-1);
  for(int i=0; i<N; i++){
    cin >> P[i];
  }
  for(int i=0; i<N; i++){
    cin >> Q[i];
  }
  for(int i=0; i<N-1; i++){
    cin >> R[i];
  }
  int a=0;
  for(int i=0; i<N; i++){
    if(P[i+1]-P[i] ==1){
      a = a+Q[i]+R[P[i]-1];
    }
  
    else{
      a = a + Q[i];
    }
  }
  cout << a << endl;
}
      

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<bitset> 
#include<unordered_map> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include "boost/algorithm/string.hpp"
// RAJJI KI MEHER 
#define fio ios_base::sync_with_stdio(false)
//#define mod 1000000007
#define mod1 mod
#define mod2 100000009
#define li long long int
#define ll int
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define readi(x) scanf("%d",&x)
#define  reads(x)  scanf("%s", x)
#define readl(x) scanf("%lld",&x)
#define rep(i,n) for(i=0;i<n;i++)
#define revp(i,n) for(i=(n-1);i>=0;i--)
#define myrep1(i,a,b) for(i=a;i<=b;i++)
#define myrep2(i,a,b) for(i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define MAXN 100000000000000005
#define MINN -10000000000000000
#define INTMAX 1000001000
#define pii pair<li,li>
#define pdd pair<double,double>
#define pic pair<int,char>
//#define N 5005
#define lgn 20
#define ddouble long double
#define minus minu
#define PI 3.1415926535
#define lgn 20
using namespace std;
map<li,vector<li>>M;li A[100005][3];li mod=1000000007;
li DFS(li i, li j,li k){li ans=1,ans1=1;
if(A[i][k]!=-1) return(A[i][k]);
if(k==0){for(auto x:M[i]){if(x!=j){ans=(ans*(DFS(x,i,0)))%mod;
ans1=(ans1*(DFS(x,i,1)))%mod;}}ans=(ans+ans1)%mod;
if(ans==1) ans=2;}
else{for(auto x:M[i]){if(x!=j){ans=(ans*DFS(x,i,0))%mod;}}}    
A[i][k]=ans;return(ans);
}
int main(){li i,j,n,a,b;readl(n);memset(A,-1,sizeof(A));
for(i=0;i<(n-1);i++){readl(a);readl(b);M[a].pb(b);M[b].pb(a);}
li ans=DFS(1,0,0);cout<<ans;
}


Measured memory_bytes: 24704
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define endl "\n"
ll mod = 1e9 + 7;
//const double pi = acos(-1.0);
/*
ll kmp(string x)
{
    ll n= x.length();
    //cout<<x<<endl;
    vector<ll> lcp(x.length(), 0);
    for(ll i=1;i<n;i++)
    {
        ll j=lcp[i-1];
        while(j>0 && x[j]!=x[i])
            j=lcp[j-1];
        if(x[i]==x[j])
            j++;
        lcp[i]=j;
    }
    return lcp[n-1];
}

int N = 1000002;
int ar[100002];
void sieve()
{
    for(int i=1;i<=N;i++)
        ar[i] = 1;
    ar[0] = 0;
    for(int i=2;i*i<=N;i++)
    {
        if(ar[i] && i*i<=N)
        {
            for(int j = i*i; j<=N;j+=i)
                ar[j] = 0;
        }
    }
}

ll modex(ll a,ll b){
    if(b<=0){
        return 1;
    }
    if(b%2==0)
    {
        ll x = modex(a, b/2);
        return ((x*x)%mod);
    }
    else
        return ((a%mod * modex(a, b-1))%mod);
}

ll c[1010][1010];

ll combina(ll i, ll j){
        for (int i=0;i<=1005;i++)
        for (int j=0;j<=i;j++)
        {
            if (j==i||j==0)
                c[i][j]=1;
            else
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            c[i][j]%=mod;
        }
        return c[i][j];
}
void find_fac(int x){
    vector<ll> di;
    for(ll i = 2; i*i <= x; i++)
    {
        if(x%i==0){
            di.push_back(i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x > 1)
        di.push_back(x);
}
*/
int n, x;
vector<int> w;
vector<int> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout<<fixed;
    cout.precision(12);
    cin>>n>>x;
    w.resize(n);v.resize(n);
    int s = 0;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
        s += v[i];
    }
    vector<vector<ll> > dp(n+1, vector<ll> (x+1));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=x;j++){
            if(i==0 || j==0)
                dp[i][j]=0;
            else if(w[i-1]<=j)
            {
                dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j-w[i-1]]);
            }
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout<<dp[n][x]<<endl;
    //cout<<an<<endl;
    return 0;
}


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

using namespace std;

int calc(string a,int l){
    vector<int> v(l,0);
    for(int i=0;i<(int)a.length();i++){
        v[i]=a[i]-'0';
    }
    sort(v.begin(),v.end());
    int tmp=0;
    for(int i=0;i<l;i++){
        tmp*=10;
        tmp+=v[i];
    }
    sort(v.rbegin(),v.rend());
    int tmp2=0;
    for(int i=0;i<l;i++){
        tmp2*=10;
        tmp2+=v[i];
    }
    return tmp2-tmp;
}

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

    int a,l;
    while(cin>>a>>l,a||l){
        vector<int> v(100);
        v[0]=a;
        for(int i=1;i<=100;i++){
            v[i]=calc(to_string(v[i-1]),l);
        }
        for(int i=1;i<=20;i++){
            for(int j=0;j<i;j++){
                if(v[i]==v[j]){
                    cout<<j<<" "<<v[i]<<" "<<i-j<<endl;
                    goto done;
                }
            }
        }
        done:continue;
    }
}

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

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/


#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int z=1 ; z<=t ; z++)
#define PRINT_CASE printf("Case %d: ",z)
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2



int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;


int arr[6],k;
int main() {
    //CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    f1(i,5){
        cin >> arr[i];
    }

    sort(arr+1, arr+1+5);
    cin >> k;
    if(arr[5]-arr[1]>k){
        cout << ":(" <<endl;
        return 0;
    }
    cout <<"Yay!"<<endl;




    return 0;
}


Measured memory_bytes: 256
//Dragon_warrior7(IITK)
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define umap unordered_map
#define uset unordered_set
#define ll long long
#define lll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 1000000000000000000
#define pll pair<ll, ll> 
#define ull unsigned ll
#define vll vector<ll> 
#define rub cout << "\n------------------------------------\n"
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
#define fo(i,a,b) for(int i=a;i<b;i++)
#define Lets_be_precise cout<<fixed<<setprecision(10)
//typedef  tree < int ,  null_type ,  greater<int> ,  rb_tree_tag ,  tree_order_statistics_node_update > oset;
// const int mod=1e9+7;
// ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// ll modInverse(ll a){return power(a,mod-2);}
ll n,m,a,b,c,k,temp,x,y;
const int MAXN=100000+11;
void read(vector<ll> &v)
{
	for (int i = 0; i < v.size(); i++)
	cin>>v[i];
}
#define cerr if(false)cerr//uncomment to remove cerr from program...
map<char,vll> mp;
void solveforthiscase(const int & test)
{//deb(test);
cin>>n;
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
    mp[s[i]].pb(i);
}
int count=0;
for(char a='0';a<='9';a++)
{
    for(char b='0';b<='9';b++)
    {
        for(char c='0';c<='9';c++)
        {
            if(mp[a].size()==0)
            continue;
            int index1=mp[a][0];
            if(a=='0')
            deb(index1);
            auto i2=ub(mp[b],index1);
            if(i2==mp[b].end())
            continue;
            int index2=*i2;
            auto i3=ub(mp[c],index2);
            if(i3==mp[c].end())
            continue;
            count++;
        }
    }
}
cout<<count;










return ;
}

int main()
{
	ios_base::sync_with_stdio(false);
	Lets_be_precise;
	cin.tie(NULL);
	cout.tie(NULL);
	int test=1;
// 	cin>>test;
    for(int i=1;i<=test;i++)
    {
        solveforthiscase(i);
    }
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long double lb;

const int INF=1<<27;
const int MOD=(int)1e9+7;

int main(void)
{
        int n;
        int a[100001]={INF};
        cin >> n;
        rep(i,n) cin >> a[i];

        sort(a,a+n);

        int ans = 0;
        int cnt=0;
        int temp=0;
        rep(i,n){
                if(a[i]==temp) cnt++;
                else{
                        if(cnt>=temp) ans+=cnt-temp;
                        else ans+=cnt;
                        cnt=1;
                        temp=a[i];
                }
        }

        if(cnt>=temp) ans+=cnt-temp;
        else ans+=cnt;

        printf("%d\n",ans);

        return 0;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

import javax.lang.model.util.ElementScanner6;

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a, b;
        String op;
        while (true) {
            a = scan.nextInt();
            op = scan.next();
            b = scan.nextInt();

            if (op.equals("?"))
                return;
            else if (op.equals("+")) {
                System.out.println(a + b);
            } else if (op.equals("-")) {
                System.out.println(a - b);
            } else if (op.equals("*")) {
                System.out.println(a * b);
            } else if (op.equals("/")) {
                System.out.println(a / b);
            } else
                return;
        }
    }
}


Measured memory_bytes: 26320
import sys
#import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
#import math
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n,m,k = rl()
a = rl()
b = rl()
sa=[0]
sb=[]
tmp=0
for i in a:
    tmp+=i
    sa.append(tmp)
tmp=0
for i in b:
    tmp+=i
    sb.append(tmp)
ans=[]
for i,e in enumerate(sa):
    if k-e>=0:
        ans.append(i+bisect.bisect_right(sb, k-e))
print(max(ans))
    

Measured memory_bytes: 132492
#include <iostream>

using namespace std;

using ll = long long;

ll c(ll x)
{
    return x * (x + 1) / 2;
}

int main()
{
    int N;
    cin >> N;
    
    int L = 1, R = N;
    while (R - L > 1) {
        int mid = (L + R) / 2;
        if (c(mid) > N) {
            R = mid;
        } else {
            L = mid;
        }
    }
    
    int K = (c(L) == N ? L : R);

    string res = string(K, ')') + string(K, '(');
    N = c(K) - N;    
    for (int p = K; N > 0; N--, p--) {
        swap(res[p - 1], res[p]);
    }
    
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=2e5+9;
const int mod=1e9+7;

ll fp(ll b,ll p){ 
    if(p==0) return 1;
    if(p&1) return (b*fp(b,p-1))%mod;
    return fp((b*b)%mod,p/2);
}

ll add(ll a, ll b){
    return ((a%mod)+(b%mod))%mod;
}
ll mul(ll a, ll b){
    return ((a%mod)*(b%mod))%mod;
}

ll sub(ll a, ll b){
    return ((a%mod)-(b%mod)+mod)%mod;
}

 ll inv(ll a){ 
    return fp(a,mod-2);
}


ll divv(ll a,ll b){
    return mul(a,inv(b));
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,a[N];
    ll sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum=add(sum,a[i]);
    }
    sum=mul(sum,sum);
    ll c=0;
    for(int i=0;i<n;i++){
       c=add(c,mul(a[i],a[i]));
    }
    cout<<divv(sub(sum,c),(ll)2);
}

Measured memory_bytes: 4420
A,B = gets.split.map(&:to_i)
minA = (A*100+7)/8
minB = (B*100+9)/10
ubA = ((A+1)*100+7)/8
ubB = ((B+1)*100+9)/10
#p [minA,ubA,minB,ubB]
if ubA <= minA or ubB <= minB
	p(-1)
elsif minA == minB
	p minA
elsif minA < minB and minB < ubA
	p minB
elsif minB < minA and minA < ubB
	p minA
else
	p(-1)
end


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int s;
 cin>>s;
 int h,m,se;
 h=s/3600;
 m=(s%3600)/60;
 s=s%60;
 cout<<h<<":"<<m<<":"<<s<<endl;
 return 0;
}



Measured memory_bytes: 3088
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
char field[1000][1000];
struct date{
    int x,y,cnt;
};
int main(){
	int h,w,n;
	cin >> h >> w >> n;
	date start;
	int ans = 0;
	for(int i = 0; i < h; i++){
	    cin >> field[i];
	    for(int j = 0; j < w; j++){
            if(field[i][j] == 'S'){
                start.x = j,start.y = i,start.cnt = 0;
            }
	    }
	}
	for(int i = 1; i <= n; i++){
	    queue<date> Q;
        Q.push(start);
        bool flg[1000][1000] = {{0}};
        while(!Q.empty()){
            date d = Q.front();
            Q.pop();
            if(field[d.y][d.x] == i + '0'){
                start.x = d.x,start.y = d.y,start.cnt = d.cnt;
                break;
            }
            if(flg[d.y][d.x])continue;
            flg[d.y][d.x] = 1;
            int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
            for(int j = 0; j < 4; j++){
                int px = d.x+dx[j],py = d.y + dy[j];
                if(px < 0 || py < 0 || px >= w || py >= h)continue;
                if(field[py][px] == 'X')continue;
                date next = {px,py,d.cnt+1};
                Q.push(next);
            }
        }
        ans = start.cnt;
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3176
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] b = new int[n-1];
        for(int i=0;i<n-1;i++){
            b[i] = Integer.parseInt(sc.next());
        }
        int sum = b[0];
        for(int i=1;i<n-1;i++){
            sum+=Math.min(b[i-1],b[i]);
        }
        sum+=b[n-2];
        System.out.println(sum);
        sc.close();
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
void solve() {
	int64 N, K; cin >> N >> K;
	vector<int64> h(N);
	for (int64 i = 0; i < N; ++i) {
		cin >> h[i];
	}
	sort(all(h));
	int64 ans = MAX_NUM;
	int64 slide = K - 1;
	for (int64 i = 0; i < N - K + 1; ++i) {
		ans = min(ans, h[i + slide] - h[i]);
	}
	cout << ans << endl;
	return;
}
int main() {
	solve();
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main() {

  int n,m,i,j;
  int a,b;
  int A[100][100] = {0};
  int B[100] = {0};
  int c[100] = {0};

  scanf("%d %d " ,&n,&m);

  for(j=0; j<n; j++) {
  for(i=0; i < m; i++) {
    scanf("%d",&a);
    A[j][i] = a;
  }
}

  for(j=0; j<m; j++) {
    scanf("%d",&b);
    B[j] = b;
  }

  for(j=0;j<n ; j++){ 
  for(i = 0; i<m; i++){
     c[j] = c[j] + A[j][i]*B[i];
    }
  }

  for(i=0;i<n;i++) {
    printf("%d\n",c[i]);
  }
  return 0;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/04  Problem: ABC 099 B / Link: http://abc099.contest.atcoder.jp/tasks/abc099_b  ----- */


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

	LL A, B; cin >> A >> B;
	LL ans = 0LL;
	FOR(i, 0, B - A) {
		ans += i;
	}
	ans = ans - A;
	
	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 256
from sys import maxsize

h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])


Measured memory_bytes: 44012
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;
//struct edge{lint to,num;};

int main(void){
    string S;
    cin >> S;
    int cnt[3]={};
    int N=S.length();
    rep(i,N) cnt[S[i]-'a']++;
    sort(cnt,cnt+3);
    int minus=cnt[0];
    rep(i,3) cnt[i]-=minus;
    bool ans=true;
    rep(i,3) if(cnt[i]>1) ans=false;
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int INF=1e9;
const int MOD=1e9+7;
const double pi=acos(-1);

int main(){
  int n;
  cin >> n;
  map<ll,int,greater<ll>>mp;
  rep(i,n){
    ll a;
    cin >> a;
    mp[a]++;
  }
  ll ans=0;
  for(auto p:mp){
    if(p.second>=4){
      if(ans==0){
        ans=p.first*p.first;
        break;
      }
      else{
        ans*=p.first;
        break;
      }
    }
    else if(p.second>=2){
      if(ans==0){
        ans=p.first;
      }
      else{
        ans*=p.first;
        break;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int A[100001], B;
	rep(i, N + 1) A[i] = getint();

	ll kotae = 0;
	rep(i, N) {
		B = getint();
		int k = min(A[i], B);
		B -= k;
		kotae += k;
		k = min(A[i + 1], B);
		A[i + 1] -= k;
		kotae += k;
	}

	co(kotae);


	Would you please return 0;
}


Measured memory_bytes: 768
N = int(input())
N_d = int(N/2)
X1 = list(map(int,input().split()))
X = X1[:]
X1.sort()

def getMed(i):
  if i  < X1[N_d]:
    print(X1[N_d])
  else:
    print( X1[N_d -1])

for i in X:
  getMed(i)

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

#define IOS std::cin.tie(0);std::ios_base::sync_with_stdio(false)

#define ll      long long
#define Fi      first
#define Se      second
#define Pb      push_back
#define vi      vector<int>
#define vp      vector<pair<int,int>>
#define vvi     vector<vector<int>>
#define vvp     vector<vector<pair<int,int>>>
using Graph  =  vector<vector<int>>;

#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define output_s(s) printf("%s\n",(s).c_str())
#define END cout<<"\n"

#define rep(i,n)        for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m)      for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m)     for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m)    for(int i=(int)(n);i>=(int)(m);i--)
#define SRepS(i,n,m)    for(int i=(int)(n);i*i<=(int)(m);i++)
#define RepA(x)         for(auto &item:(x))

void CINT(){} //@shibh308's template
template<class Head,class... Tail> void CINT(Head&& head,Tail&&... tail){cin>>head; CINT(move(tail)...);}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
#define VCIN(x) for(auto &item:x) cin>>item

void OUT(){}
template<class Head,class...Tail> void OUT(Head&& head,Tail&&...tail){cout<<head<<(sizeof...(tail)?" ":"\n"); OUT(move(tail)...);}
#define COUT(...) OUT(__VA_ARGS__)

template<typename TypeInt>TypeInt GCD(TypeInt a,TypeInt b){return a%b==0?b:GCD(b,a%b);} //最大公約数
template<typename TypeInt>TypeInt LCM(TypeInt a,TypeInt b){return a*b/GCD(a,b);} //最小公倍数
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
template<class T>bool comp(T a,T b){return abs(a)<abs(b);} //比較関数

void YES(bool f){printf(f?"YES\n":"NO\n");}
void Yes(bool f){printf(f?"Yes\n":"No\n");}
void Possible(bool f){printf(f?"Possible\n":"Impossible\n");}
void POSSIBLE(bool f){printf(f?"POSSIBLE\n":"IMPOSSIBLE\n");}

//----------------------library------------------------//

//const int dx[4]={1,0,-1,0};
//const int dy[4]={0,1,0,-1};
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int NMAX = 55;
const int INF = 1e9;
const int MOD = 1e9+7;
bool flag;

//----------------------Global-------------------------//

signed main(){
    SCIN(s);
    regex_match(s,regex("(dream|dreamer|erase|eraser)*"))?flag=true:flag=false;
    YES(flag);

    return 0;
}

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

using namespace std;


vector<int> g[9];
int bio[9];
int ans = 0;
int N, M;
int sumbio = 0;

void dfs(int u) {
  bio[u] = 1;
  sumbio++;
  if (sumbio == N) ans++;
  for (auto v : g[u]) {
    if (bio[v]) continue;
    dfs(v);
  }
  bio[u] = 0;
  sumbio--;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//おまじない
//#include <bits/stdc++.h>
//#include <stdio.h>
#include <iostream>
//#include <math.h>
#include<iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define space ' '
#define pll pair<ll,ll>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 200000;

int n;
bool a[maxn+1];
bool ans[maxn+1];
int c = 0;

int main(){
    
    ll n;
    cin >> n;
    cout << (n-1)*n/2<<endl;
    
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias P = Tuple!(long, "l", long, "r");

void main()
{
    auto N = readln.chomp.to!int;
    P[] ps;
    foreach (_; 0..N) {
        auto lr = readln.split.to!(long[]);
        ps ~= P(lr[0], lr[1]);
    }
    sort!"a.l == b.l ? a.r < b.r : a.l < b.l"(ps);

    auto ls = new long[](N);
    ls[0] = ps[0].r;
    foreach (i; 1..N) ls[i] = min(ls[i-1], ps[i].r);

    auto rs = new long[](N);
    rs[$-1] = ps[$-1].r;
    foreach_reverse (i; 0..N-1) rs[i] = min(rs[i+1], ps[i].r);

    long res;
    foreach (i; 0..N-1) {
        res = max(
            res,
            max(0, ls[i] - ps[i].l + 1) + max(0, rs[i+1] - ps[$-1].l + 1),
            max(0, ps[i].r - ps[i].l + 1) + max(0, rs[0] - ps[$-1].l + 1)
        );
    }
    writeln(res);
}

Measured memory_bytes: 5244
import scala.io.StdIn

object Main extends App {
  val n = StdIn.readLine
  val ans = StdIn.readLine.split(" ").map(_.toInt)
    .sorted(Ordering[Int].reverse)
    .zipWithIndex
    .foldLeft(0){ (acc,e) =>
      acc + ( if((e._2 & 1) == 0) e._1 else -e._1 )
    }

  println(ans)
}


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

int abst(int a)
{
	return a<0?-a:a;
}

int main()
{
	string s;
	cin>>s;
	int gco=0,pco=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='g')gco++;
		else pco++;
	}
	if(gco<pco)cout<<"-"<<abs(pco-gco)/2+1<<endl;
	else cout<<abs(gco-pco)/2<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
vector<ll> v;
int main(void){
    ll ans=1e9;
    cin>>s;
    for(int i=0;i<s.size();i++){
        v.push_back(s[i]-'0');
    }
    for(int i=0;i<s.size()-2;i++){
        ll a=v[i]*100+v[i+1]*10+v[i+2];
        ans=min(ans,abs(753-a));
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
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);
        AZeroSumRanges solver = new AZeroSumRanges();
        solver.solve(1, in, out);
        out.close();
    }

    static class AZeroSumRanges {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = new long[n];

            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }

            long sum = 0;
            HashMap<Long, Integer> count = new HashMap<>();
            count.put(0L, 1);
            for (int i = 0; i < n; i++) {
                sum += a[i];
                count.put(sum, count.getOrDefault(sum, 0) + 1);
            }

            long ans = 0;
            for (Map.Entry<Long, Integer> entry : count.entrySet()) {
                long x = entry.getValue();
                ans += x * (x - 1) / 2;
            }

            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 int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 50080
program abc132a
  implicit none
  character(4) :: s
  integer :: i, m
  logical :: flag=.false.

  read(*,*) s

  if ((s(1:1) == s(2:2) .and. s(3:3) == s(4:4)) .and. s(2:2) == s(3:3)) then
    print *, 'No'
    stop
  endif

  if (s(1:1) == s(2:2) .and. s(3:3) == s(4:4)) then
    flag=.True.
  else if (s(1:1) == s(3:3) .and. s(2:2) == s(4:4)) then
    flag=.True.
  else if (s(1:1) == s(4:4) .and. s(2:2) == s(3:3)) then
    flag=.True.
  endif

  if (flag) then
    print *, 'Yes'
  else
    print *, 'No'
  endif

end program abc132a


Measured memory_bytes: 256
x,k,d=list(map(int, input().split()))
y=abs(x)
if y>k*d:
    print(y-k*d)
else:
    if k%2==0:
        e=y//(2*d)
        f=min(abs(y-2*e*d),abs(y-(2*e+2)*d))
        print(f)
    elif k%2==1:
        e=(y+d)//(2*d)
        f=min(abs(y-(2*e-1)*d),abs(y-(2*e+1)*d))
        print(f)        




Measured memory_bytes: 9200
import Control.Applicative( (<$>))
import Control.Monad( replicateM)
import Data.List( group, sort)

main = do
    let
	readLine = map read . words <$> getLine

    [n_, m_] <- readLine
    abs_ <- replicateM m_ readLine

    let
	dummy = [1..n_]::[Int]
	ans = map ((subtract 1).length) . group . sort$(concat abs_)++dummy

    mapM_ print ans


Measured memory_bytes: 1020
package main

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

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt int

func main() {
	var N, D float64
	fmt.Scan(&N, &D)
	fmt.Println(math.Ceil(N / ((D * 2) + 1)))
}

/*  ----------------------------------------  */

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

func lcm(x, y int) int {
	return (x / gcd(x, y)) * y
}

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; i++ {
		fac[i] = fac[i-1] * i % mod
		inv[i] = mod - inv[mod%i]*(mod/i)%mod
		finv[i] = finv[i-1] * inv[i] % mod
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy [][]int

func (a SortBy) Len() int      { return len(a) }
func (a SortBy) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool {
	return a[i][1] < a[j][1]
}

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] < h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 640
n, k = map(int, input().split())
p = list(map(int, input().split()))
q = [0]
m = 0
for i in p:
    m += (1+i)/2
    q.append(m)
ans = 0
for i in range(k, n+1):
    ans = max(q[i]-q[i-k], ans)

#あまり深く事を考えずに
print(ans)

Measured memory_bytes: 32128
N = int(input())
C = [list(map(int, input().split())) for _ in range(N)]
C = sorted(map(lambda x: ((x[0] + x[1]), x), C), reverse=True)
#print(C)
#print(C[::2])
#print(C[1::2])
print(sum(c[1][0] for c in C[::2]) - sum(c[1][1] for c in C[1::2]))


Measured memory_bytes: 38156
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#define rep(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 2e9;



int main() {
	int n; cin >> n;
	vector<P> a(n);
	rep(i, 0, n) {
		int p; cin >> p;
		a[i] = { p,i };
	}
	sort(a.begin(), a.end());
	rep(i, 0, n) {
		a[i].first = a[i].second;
		a[i].second = i;
	}
	sort(a.begin(), a.end()); 
	int cnt = 0;
	rep(i, 0, n) {
		if (a[i].second % 2 != i % 2)cnt++;
	}
	printf("%d", cnt / 2);
	return 0;
}


Measured memory_bytes: 1792
#include <cstring>
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    int n, m; cin >> n >> m;
    int adj[101][101], dist[101][101];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = adj[i][j] = 1 << 25;

    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        adj[a][b] = c; adj[b][a] = c;
    }
    memcpy(dist, adj, sizeof(adj));
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (dist[i][j] < adj[i][j] && adj[i][j] != 1<<25) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 384
from itertools import product

h, w, k = map(int,input().split())

c_map = [list(input()) for _ in range(h)]

ans = 0

for row_bit in list(product([0,1],repeat=h)):
    for col_bit in list(product([0,1],repeat=w)):
        cnt = 0
        for i in range(h):
            for j in range(w):
                # row_bit,col_bitがともに「1」のとき塗りつぶされてないとする
                if c_map[i][j] == "#" and (row_bit[i] and col_bit[j]):
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)
        

Measured memory_bytes: 9196
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
a,b = [list(i) for i in zip(*l)]
x = 0
for i in range(n)[::-1]:
    if (a[i] + x) % b[i] != 0:
        x += b[i] - ((a[i] + x)  % b[i])
print(x)

Measured memory_bytes: 35648
N = int(input())

from collections import defaultdict
d = defaultdict(lambda: -1)		#初期値を「-1」にする

d[0] = 2
d[1] = 1
def f(n):
  if d[n] == -1:
    a = f(n-1) + f(n-2)
    d[n] = a
  return d[n]

print(f(N))

Measured memory_bytes: 9484
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	n := readInt()
	a := make([]int, n)
	for i := range a {
		a[i] = readInt()
	}
	m := make(map[int64]int)
	var s int64 = 0
	m[s]++
	for i := range a {
		s = s + int64(a[i])
		m[s]++
	}
	var ans int64
	for _, v := range m {
		if 1 < v {
			ans += int64(v) * int64(v-1) / int64(2)
		}
	}
	println(ans)
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 14464
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int main()
{
    int N;
    cin >> N;
    int p[10];
    for(int i = 0; i < N; i++) cin >> p[i];
    sort(p, p + N);
    int sum = 0;
    for(int i = 0; i < N - 1; i++) sum += p[i];
    sum += p[N-1] / 2;
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
	int m,k;
	scanf("%d %d",&m,&k);
	int sum = 0;
	for(int i=0;i<(1<<m);i++)if(i!=k)sum^=k;
	if(k==0){
		for(int i=0;i<(1<<m);i++)printf("%d %d ",i,i);
		printf("\n");
		return 0;
	}
	if(m==1){
		if(k>=1)puts("-1");
		else puts("0 0 1 1");
		return 0;
	}
	if((1<<m)<=k)return puts("-1")*0;
	printf("%d ",k);
	for(int i=0;i<(1<<m);i++)if(i!=k)printf("%d ",i);
	printf("%d ",k);
	for(int i=(1<<m)-1;i>=0;i--)if(i!=k)printf("%d ",i); 
}

Measured memory_bytes: 1792
n,m=map(int,raw_input().split())
ans=[False]*n
ans[0]=True
cnt=[1]*n
for i in xrange(m):
    x,y=map(int,raw_input().split())
    x-=1;y-=1
    if cnt[x]==1 and ans[x]:
        ans[x]=False
        ans[y]=True
    elif ans[x]:
        ans[y]=True
    cnt[x]-=1
    cnt[y]+=1
print sum(ans)


Measured memory_bytes: 4228
using System.Linq;
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var ai = int.Parse(line[0]);
        var bi = int.Parse(line[1]);
        var m = int.Parse(line[2]);
        line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        line = Console.ReadLine().Trim().Split(' ');
        var b = Array.ConvertAll(line, int.Parse);
        var ans = int.MaxValue;
        for (int i = 0; i < m; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            var x = int.Parse(line[0]) - 1;
            var y = int.Parse(line[1]) - 1;
            var c = int.Parse(line[2]);
            ans = Min(ans, a[x] + b[y] - c);
        }
        ans = Min(ans, a.Min() + b.Min());
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 34908