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

int main()
{
    int A, B, C, D, E, F;
    vector < int > water, sugar;
    int answ = -1, anss = 0;
    cin >> A >> B >> C >> D >> E >> F;
    A *= 100, B *= 100;
    for(int i = 1; i <= 30; i++) {
        for(int j = 0; j <= 30; j++) {
            if(i * A + j * B <= F) {
                water.push_back(i * A + j * B);
            } else break;
        }
    }

    for(int i = 0; i <= 3000; i++) {
        for(int j = 0; j <= 3000; j++) {
            if(i * C + j * D <= F) {
                sugar.push_back(i * C + j * D);
            } else break;
        }
    }
    sort(water.begin(), water.end());
    sort(sugar.begin(), sugar.end());
    water.erase(unique(water.begin(), water.end()), water.end());
    sugar.erase(unique(sugar.begin(), sugar.end()), sugar.end());
    for(int i = 0; i < water.size(); i++) {
        for(int j = 0; j < sugar.size(); j++) {
            int w = water[i], s = sugar[j];
            if(w + s > F) break;
            if(s > w / 100 * E) break;
            if(answ == -1 || (double)anss / answ < (double)s / (w + s)) {
                answ = w + s;
                anss = s;
            }
        }
    }

    cout << answ << " " << anss << endl;
    return (0);
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long int
#define mem(x) memset(x,0,sizeof(x))
#define setbits(x)  __builtin_popcount(x)
#define ull unsigned long long int
#define all(c) (c).begin(),(c).end()
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define db double
#define endl "\n"
#define  fbo(x) find_by_order(x)
#define  ook(x) order_of_key(x)

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os1;
typedef tree<int, null_type, greater<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os2;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair<ll,ll > ii;
typedef pair<ll,int> li;
inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
const ll pi=31;
const ll MOD[2] = {1187278649, 1149736019};//for double hashing
const ll mod=(ll)(998244353);
ll pmod(ll x,ll n){
  ll r=1;
  while(n)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
  }
  return r;
}

//think recursively also
bool comp(ii &a, ii &b)
{
   return (a.ff-a.ss)>(b.ff-b.ss);
}
void solve()
{   
  
   ll n;
   cin>>n;
   ll to=0,tc=0;
    vector<ii>v;
   for(int i=0;i<n;i++)
   {
     string s;
     cin>>s;
     ll o=0,c=0,t=0;
     for(char y:s)
     {
       if(y=='(')
        t++;
      else
      {
         if(t==0)
          c++;
        else
          t--;
      }
     }
     o=t;
    // debug2(o,c);
     if(o>0 && c>0)
     {
        v.pb({o,c});
     }
     else if(o)
     {
       to+=o;
     }
    else
     {
      tc+=c;
     }
   }
  // debug2(to,tc);
   sort(all(v),comp);
   for(auto it:v)
   {
      to-=it.ss;
      if(to<0)
      {
        cout<<"No"<<endl;
        return;
      }
      to+=it.ff;
   }
   if(to==tc)
   {
    cout<<"Yes"<<endl;
   }
   else
   {
    cout<<"No"<<endl;
   }


  
}
int main()
{
   fast();
  
   // int t;
   // cin>>t;
   // for(int casee=1;casee<=t;casee++)
  {// cout<<"Case #"<<casee<<": ";
    solve();
  }
 
 
 
}


Measured memory_bytes: 7404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int ans = h2 * 60 + m2 - (h1 * 60 + m1) - k;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3596
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 201000

LL a[maxn];
LL myabs(LL x){return (x<0)?-x:x;}
LL mymin(LL x,LL y){return (x<y)?x:y;}
LL mymax(LL x,LL y){return (x>y)?x:y;}
int main()
{
	int n,i,l,r;LL ans;
	scanf("%d",&n);a[0]=0;
	for (i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	l=1;r=3;ans=a[n];
	//1~l    l+1~i   i+1~r   r+1~n
	for (i=2;i<n-1;i++)
	{
		while (l+1<i && myabs(a[i]-a[l+1]-a[l+1])<myabs(a[i]-a[l]-a[l])) l++;
		while (r+1<n && myabs(a[n]-a[r+1]-(a[r+1]-a[i]))<myabs(a[n]-a[r]-(a[r]-a[i]))) r++;
		//p=a[l],q=a[i]-a[l],R=a[r]-a[i],s=a[n]-a[r]
		LL mx=mymax(mymax(a[l],a[i]-a[l]),mymax(a[r]-a[i],a[n]-a[r]));
		LL mn=mymin(mymin(a[l],a[i]-a[l]),mymin(a[r]-a[i],a[n]-a[r]));
		ans=mymin(ans,mx-mn);
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

double net_of_tax(int n , int rate){
	double ret , tmp1 , tmp2;
	ret=(double)(n*100)/(rate+100);
	tmp1=floor(ret);
	tmp2=ceil(ret);
	if((floor((double)(tmp1*(rate+100)/100)))!=(double)n) {
		if((floor((double)(tmp2*(rate+100)/100)))!=(double)n){ 
			return ret-1.;
		} else {
			ret=tmp2;
		}
	} else {
		ret=tmp1;
	}
	return ret;
}

int main(){
	double n1 , n2 , tmp, max=0.;
	int x , y , s;
	while(1){
		cin >> x >> y >> s;
		if(x==0&&y==0&&s==0) break;
		for(int i=1 ; i<=s/2 ; ++i){
				n1=net_of_tax(i,x);
				n2=net_of_tax((s-i),x);
				n1=floor((double)((n1*(y+100))/100));
				n2=floor((double)((n2*(y+100))/100));
				if((n1+n2)>max) max=n1+n2;
			}
			cout << max << endl;
			n1=n2=max=0;
		}
	return 0; 
}

Measured memory_bytes: 1232
n = int(input())
s = input()

before = [[-1] * 10]

before
for i in range(n):
    c = s[i]
    num = ord(c) - ord("0")
    hoge = before[-1][::]
    hoge[num] = i
    before.append(hoge)

ans = 0
for i in range(10):
    now = before[-1][i]
    if now == -1: continue
    for j in range(10):
        now2 = before[now][j]
        if now2 == -1: continue
        for k in range(10):
            now3 = before[now2][k]
            if now3 == -1: continue
            ans += 1
print(ans)

Measured memory_bytes: 8948
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<list>
#include<vector>
#include<stdio.h>
#include<iomanip>
using namespace std;

int main(){

	int a[3][3];
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			
		cin >> a[i][j];
		}
	}

	int maa=0,mab=0,mac=0,mad=0,mae=0,maf=0;
	maa= min(min(a[0][0],a[0][1]),a[0][2]);

	for(int k=0;k<=maa;k++){
		mad = a[0][0]-k;
		mab = a[1][0]-mad;
		mac = a[2][0]-mad;
		mae = a[1][1]-mab;
		maf = a[2][2]-mac;

	if(k+mae==a[0][1]&&k+maf==a[0][2]&&mab+maf==a[1][2]&&mac+mae==a[2][1]){
							cout << "Yes" << endl;
							return 0;
							}

	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import random
random.seed(0)

D = int(input())
C = list(map(int, input().split()))
list_S = [list(map(int, input().split())) for _ in range(D)]

answer = []

def manzoku(A):
  score = 0
  L = [0 for _ in range(26)]
  for i in range(D):
    S = list_S[i]
    contest_index = A[i]
    for j in range(26):
      if j==contest_index:
        L[j] = 0
        score += S[j]
      else:
        L[j] += C[j]
        score -= L[j] 
  return score

L = [0 for _ in range(26)]
for S in list_S:
  contest_index = -1
  contest_manzoku = -10**9
  for i in range(26):
    i_manzoku = S[i]+C[i]+L[i]
    if i_manzoku > contest_manzoku:
      contest_index = i
      contest_manzoku = i_manzoku
  answer.append(contest_index)
  for i in range(26):
    if i==contest_index:
      L[i] = 0
    else:
      L[i] += C[i]

answer = [0 for _ in range(D)]
manzoku_now = manzoku(answer)

answer_tmp = [answer[i] for i in range(D)]
for j in range(365):
  day = j%D
  contest = random.randrange(26)
  answer_tmp = [answer[i] for i in range(D)]
  answer_tmp[day] = contest
  if manzoku_now < manzoku(answer_tmp):
    manzoku_now = manzoku(answer_tmp)
    answer[day] = contest
  else:
    answer_tmp[day] = answer[day]

for index in answer:
  print(index+1)

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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector<long long> a(n + 1), ps(n + 1), s(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ps[i] = ps[i - 1] + (a[i] > 0 ? a[i] : 0);
    s[i] = s[i - 1] + a[i];
  }
  long long best = 0;
  for (int i = 1; i <= n - k + 1; ++i) {
    best = max(best, ps[i - 1] + ps[n] - ps[i + k - 1] + max(0ll, s[i + k - 1] - s[i - 1]));
  }
  cout << best << endl;
  return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 100005

const int INF = 1e9 + 7;


ll n, m;
vector<int> G[ARRAY_MAX];
int color[ARRAY_MAX];//各頂点の色(1:黒、2;白,0:まだ塗られていない)
bool ans = true;//二部グラフかどうか


void dfs(int now) {


	for (auto to : G[now])
	{
		if (color[now] == color[to])
		{
			//二部グラフではない
			//ループができている
			ans = false;
			return;
		}
		if (color[to] == 0)
		{
			//まだ塗られていない
			color[to] = 3 - color[now];//color[now]==1なら2が、color[now]==2なら1が入る(隣同士で違う色が塗られる)
			dfs(to);
		}


	}
}



int main() {


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

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

	color[0] = 1;//1は黒を表す
	dfs(0);
	
	if (ans)
	{
		//二部グラフなら完全二部グラフにできる
		int black = 0, white = 0;
		for (int i = 0; i < n; i++)
		{
			if (color[i] == 1)
			{
				black++;
			}
			else
			{
				white++;
			}
		}
		ll ans = 1LL * black * white - m;
		cout << ans << endl;
	}
	else
	{
		//二部グラフではないなら完全グラフにできる
		ll ans = 1LL * n * (n - 1) / 2 - m;
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 6912
#include<stdio.h>
int main(){
	int a;
	int b;
	scanf("%d %d\n", &a, &b);
	if ( a < b){
		printf("a < b\n");
	}
	else if(a > b){
		printf("a > b\n");
	}
	else {
		printf("a == b\n");
	}
	return 0;
}

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

const int mod = 998244353;
const int maxn = 1e6 + 5;

int fac[maxn], inv[maxn];

int qpow(int a, int n){
    int ret = 1;
    while(n > 0){
        if(n & 1){
            ret = 1LL * ret * a % mod;
        }
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return ret;
}

void pre_comb(){
    fac[0] = 1;
    for(int i = 1;i < maxn;i++){
        fac[i] = 1LL * fac[i - 1] * i % mod;
    }
    inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
    for(int i = maxn - 2;i >= 0;i--){
        inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
    }
}

int comb(int n, int m){
    if(m > n or m < 0) return 0;
    return 1LL * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int N, K;

int compute(int X, int Y, int T){
    int ans = comb(X + Y, X);
    int ans1 = comb(X + Y, Y - T);
    ans = (ans - ans1 + mod) % mod;
    return ans;
}

void add(int &a, int b){
    a += b;
    if(a >= mod)
        a -= mod;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pre_comb();
    cin >> N >> K;
    int ans = 0;
    for(int Red = 0;Red <= K;Red++){
        int Blue = K - Red;
        if(Blue > Red){
            continue;
        }else if(Blue == Red){
            if(Blue - N + 1 <= 0)
                continue;
            else{
                int X = Red, Y = Blue - 1;
                int T = Blue - N + 1;
                add(ans, compute(X, Y, T));
            }
        }else{
            int T = Red - N + 1;
            if(T <= 0)
                continue;
            else{
                int X = Red, Y = Blue;
                add(ans, compute(X, Y, T));
            }
        }
    }    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8192
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

vector<long long int> fac;
const int mod = 1e9 + 7;

long long int mypow(long long int a, long long int b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    long long int res = mypow(a, b / 2);
    res = res * res % mod;
    if (b % 2 == 1) res = res * a % mod;
    return res;
}


long long int myc(long long int a, long long int b) {
    return fac[a] * mypow(fac[b], mod - 2) % mod * mypow(fac[a - b], mod - 2) % mod;
}

int main() {
    long long int h, w, a, b;
    cin >> h >> w >> a >> b;
    fac.push_back(1);
    for (int i = 1; i <= h + w; i++) {
        fac.push_back(fac.back() * i % mod);
    }
    long long int res = 0;
    for (int i = b; i < w && i <= h - a - 1 + b; i++) {
        res += myc(h - a - 1 + b, i) * myc(w - 1 + h - 1 - (h - a - 1 + b), w - 1 - i) % mod;
        // cout << myc(h - a - 1 + b, i) * myc(w - 1 + h - 1 - (h - a - 1 + b), w - 1 - i) << endl;
        res %= mod;
    }
    cout << res << endl;
}


Measured memory_bytes: 5276
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int main()
{
int a[3][3];
for(int i=0;i<3;i++)
{
    for(int o=0;o<3;o++)
    {

    cin>>a[i][o];
    }
}
int n;cin>>n;
int b;
for(int i=0;i<n;i++)
{
cin>>b;
for(int i=0;i<3;i++)
{
    for(int o=0;o<3;o++)
    {
        if(a[i][o]==b)
        {
    a[i][o]=0;
        }
    }
}
}
bool ok=false;
for(int i=0;i<3;i++)
{
    if((a[i][0]==0 && a[i][1]==0 && a[i][2]==0) || (a[0][i]==0 && a[1][i]==0 && a[2][i]==0))
    {
        ok=true;
    }
}
if(!ok)
{
if((a[0][0]==0 && a[1][1]==0 && a[2][2]==0 )|| (a[2][0]==0 && a[1][1]==0 && a[0][2]==0 ))
{
ok=true;
}
}
cout<<((ok) ? "Yes" : "No");
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

int main() {
  int N;
  cin >> N;
  vector<ll> a(N), b(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> b[i];
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  vector<int> sum(N + 1, 0);
  for (int i = 0; i < N; i++) {
    sum[i + 1] = sum[i] + (b[i] < a[i]);
  }
  ll res = 1;
  int i = 0, j = 0;
  for (int k = 0; k < N; k++) {
    ll c = 1;
    if (b[k] < a[k]) {
      while (i < N && a[i] < b[k]) ++i;
      if (i < k) {
        c += sum[k] - sum[i];
      }
    } else {
      while (j < N && b[j] < a[k]) ++j;
      if (j < k) {
        c += (k - j) - (sum[k] - sum[j]);
      }
    }
    res = res * c % MOD;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e18)
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
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; }

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

ll lcm(ll a, ll b){
    ll c = gcd(a, b);
    return a*b/c;
}

int main()
{
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll ans = 1;
    rep(i, n) ans *= a[i];
    rep(i, n-1) a[i+1] = lcm(a[i+1], a[i]); 
    pr(a[n-1]);
    return 0;}


Measured memory_bytes: 3116
#include<iostream>
using namespace std;
int main(){
  int H, N;
  cin>>H>>N;
  int A[N];
  for (int i=0; i<N; i++){
  cin>>A[i];}
    int sum=0;
    for (int i=0; i<N; i++){
      sum+=A[i];
    }
  if (sum>=H) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <cmath>
#include <algorithm>

#define NUM 1000500

int main(){
	int* table = new int[NUM];
	int limit;

	for(int i=0; i < NUM;i++)table[i] = 1;
	table[0] = 0;
	table[1] = 0;

	limit = sqrt(NUM);

	for(int i=2;i<=limit;i++){
		if(table[i] == 1){
			for(int k=2*i;k < NUM; k += i){
				table[k] = 0;
			}
		}
	}

	int a,b,index,array[1000],sum,a_key,b_key;

	while(true){
		scanf("%d %d",&a,&b);
		if(a == 0 && b == 0)break;

		limit = a/2 + 100;
		index = 0;

		for(int i = 2; i <= limit; i++){
			if(table[i] == 1 && a%i == 0){
				array[index++] = i;
				while(a%i == 0){
					a /= i;
				}
			}
		}

		sum = 0;

		if(index == 0 && table[a] == 1){
			a_key = a;
		}else{

			for(int i = 0; i <= index-2; i++){
				sum += array[i];
			}

			a_key = array[index-1] - sum;
		}


		limit = b/2 + 100;
		index = 0;

		for(int i = 2; i <= limit; i++){
			if(table[i] == 1 && b%i == 0){
				array[index++] = i;
				while(b%i == 0){
					b /= i;
				}
			}
		}

		sum = 0;

		if(index == 0 && table[b] == 1){
			b_key = b;
		}else{

			for(int i = 0; i <= index-2; i++){
				sum += array[i];
			}

			b_key = array[index-1] - sum;
		}

		if(a_key > b_key)printf("a\n");
		else{
			printf("b\n");
		}

	}
	return 0;
}

Measured memory_bytes: 6484
#include <bits/stdc++.h>
 
using namespace std;
 
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
 
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
 
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
 
typedef long long ll;
 
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555;
const double PI = acos(-1.0); 
void solve()
{
	vector<string> v;
	v = {"Sunny", "Cloudy", "Rainy", "Sunny"};
	string s;
	cin >> s;
	rep(i, sz(v)){
		if(s == v[i]){
			cout << v[i + 1];
			return;
		}
	}
}	

 
 
int main()
{
	Red;
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(void){
    ll M;
    cin >> M;
    int d; ll c, keta = 0, sum = 0; 
    for(ll i=0;i < M;i++){
        cin >> d >> c;
        keta += c;
        sum += d*c;
    }
    ll ans = sum/9+keta-1;
    if(sum%9 == 0) ans--;
    cout << ans;
}

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

#define MAX 1010
#define INF 1000000010
#define EXP 1024*4 + 10

using namespace std;

int n, m;
int n1, n2;

int c[MAX];
int boxes[MAX];
int dp[MAX][EXP];

int solve(int i, int mask)
{
	int& ans = dp[i][mask];

	if(ans != -1) return ans;

	if(mask == (1 << n) - 1) return ans = 0;
	if(i == 0) return ans = INF;

	ans = min(solve(i - 1 , mask) , solve(i - 1 , mask | boxes[ i ]) + c[ i ]);

	return ans;
}

int main()
{
	scanf("%d %d",&n,&m);

	memset(dp , -1 , sizeof(dp));

	for(int i = 1 ; i <= m ; i++)
	{
		scanf("%d %d",&c[i],&n1);

		for(int j = 1 ; j <= n1 ; j++)
		{
			scanf("%d",&n2);

			boxes[ i ] += 1 << (n2 - 1);
		}
	}

	int ans = solve(m , 0);

	if(ans == INF) printf("-1\n");
	else printf("%d\n",ans);
}

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

#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

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

#ifdef LOCAL//compile with -DLOCAL
#define debug(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<(x)<<endl
#define debug_vec(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = ";\
  rep(i,sz(x)){cerr<<x[i]<<" ";}cerr<<endl
#define debug_mat(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<endl;\
  rep(i,sz(x)){rep(j,sz(x[i])){cerr<<x[i][j]<<" ";}cerr<<endl;}cerr<<endl
#else
#define debug(x) void(0)
#define debug_vec(x) void(0)
#define debug_mat(x) void(0)
#endif

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


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

  int ans=N*(N-1)/2 - N/2;
  cout << ans << endl;
  REP(i,1,N+1){
    REP(j,i+1,N+1){
      if(N%2==1 && i+j==N)  continue;
      if(N%2==0 && i+j==N+1)  continue;
      cout << i << " " << j << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int n,k;
  cin>>n>>k;
  vin a(n);
  rep(i,0,n)cin>>a[i];
  
  rep(i,k,n){
    bool ans=true;
    if(a[i]<=a[i-k])ans=false;
    
    
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  
  
}

Measured memory_bytes: 3904
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		 //sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }


using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;


const int MOD = 1e9+7;
const int INF = 1e9;
vi v;
int N;
void dfs(ll x, int a, int b, int c){
	if(x > N){
		return;
	}
	if(a>0&&b>0&&c>0){
		v.push_back(x);
	}
	if(x == 0){
		dfs(x+3,a+1,b,c);
		dfs(x+5,a,b+1,c);
		dfs(x+7,a,b,c+1);
	}
	else{
		dfs(10*x+3,a+1,b,c);
		dfs(10*x+5,a,b+1,c);
		dfs(10*x+7,a,b,c+1);
	}
}
int main() {
	cin>>N;
	dfs(0,0,0,0);
	int ans = v.size();
	cout<<ans<<endl;

}

Measured memory_bytes: 512
n = int(input())
a = [[0 for _ in range(10)] for _ in range(10)]
for i in range(1,n+1):
	j = i%10
	while i>9:
		i//=10
	a[i][j]+=1
ans = 0
for i in range(1,10):
	for j in range(1,10):
		ans += a[i][j]*a[j][i]
print(ans)

Measured memory_bytes: 3060
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

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

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI(N);
    GVI(V,N);
    GVI(C,N);
    vector<int> x(N);
    FOR(i,N)x[i]=V[i]-C[i];
    sort(ALL(x));
    int ans=0;
    for(int i=N-1;i>=0;i--){
        if(x[i]<=0)break;
        ans+=x[i];
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
 
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main()
{
    int n;
    int a;
    int sum=0;
    int max=0;
    scanf("%d\n",&n);
    REP(i,n)
    {
        scanf("%d\n",&a);
        sum+=a;
        if(max<a)max=a;
    }
    sum-=max/2;
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 256
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int a, b;

int main() {
    while (scanf("%d%d", &a, &b) != EOF) {
		int curr=1,ans=0;
		while (curr<b){
			curr+=a-1;
			ans++;
		}
		printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<std::pair<int,int>> ps(N);
  for(int i = 0; i < N; ++i) {
    std::cin >> ps[i].first;
    --ps[i].first;
    ps[i].second = i+1;
  }
  std::sort(ps.begin(), ps.end());
  std::vector<int> ans(N*N, -1);
  int t = 0;
  for(auto const& p: ps) {
    int x = p.first, i = p.second;
    ans[x] = i;
    for(int c = 0; c < i-1; ++c) {
      while(t < x && ans[t] != -1) ++t;
      if(t >= x) fin("No");
      ans[t] = i;
      ++t;
    }
  }
  t = N*N-1;
  for(auto it = ps.rbegin(); it != ps.rend(); ++it) {
    int x = it->first, i = it->second;
    for(int c = 0; c < N-i; ++c) {
      while(t > x && ans[t] != -1) --t;
      if(t <= x) fin("No");
      ans[t] = i;
      --t;
    }
  }
  std::cout << "Yes\n";
  for(int i = 0; i < N*N-1; ++i) std::cout << ans[i] << " ";
  std::cout << ans[N*N-1] << std::endl;
  return 0;
}


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

class Program
{
	static void Main(string[] args)
	{
		var NT = Console.ReadLine().Split(' ');
		var t = Console.ReadLine().Split(' ').Select(var => int.Parse(var)).ToArray();

		var N = int.Parse(NT[0]);
		var T = int.Parse(NT[1]);

		int TotalTime = 0;

		if(N == 0)
		{
			Console.WriteLine(T);
			return;
		}

		for (int i = 0; i < N-1; i++)
			TotalTime += (t[i + 1] - t[i] >= T) ? T : t[i+1]-t[i];

		TotalTime += T;
		Console.WriteLine(TotalTime);
	}
}


Measured memory_bytes: 28256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>

using namespace std;

using P = pair<int, int>;
using i64 = int64_t;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;

int main(int argc, char **argv) {
    int a, b;
    cin >> a >> b;
    int ab = abs(a-b);
    int sm = min(a,b);
    int ans = sm + ab/2;
    if (ab % 2)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
count = gets.to_i

arr = []
room_arr = []

count.times do
  arr << gets.split(" ").map(&:to_i)
end

4.times do
  ar = []
  3.times do
    ar << Array.new(10, 0)
  end
  room_arr << ar
end

arr.each do |val|
  int = room_arr[val[0] - 1][val[1] - 1][val[2] - 1]
  int += val[3]
  room_arr[val[0] - 1][val[1] - 1][val[2] - 1] = int
end

str = ""

room_arr.each_with_index do |arr, ind|
  arr.each do |arr2|
    arr2.each do |val|
      str += " " + val.to_s
    end
    str += "\n"
  end
  break if ind == 3
  str += "####################\n"
end

puts str

Measured memory_bytes: 6108
#include <iostream>
#include <vector>
#include <cstdio> 
using namespace std;

typedef long long LL;

const int MAXN = 320;
const int INF = 1e9 + 100;

int n, dis[MAXN][MAXN];

namespace Part1 {
	struct Edge {
		int u, v;
	}; 
	bool tag[MAXN * MAXN];
	vector<Edge> e;
	int G[MAXN][MAXN];
	LL ans(2e18);
	void Judge() {
		LL cost = 0LL;
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n; j ++)
				G[i][j] = i == j ? 0 : INF;
		for(int i = 0; i < e.size(); i ++) 
			if(tag[i]) {
				cost += dis[ e[i].u ][ e[i].v ];
				if(cost > ans) return ;
				G[ e[i].u ][ e[i].v ] = G[ e[i].v ][ e[i].u ] = dis[ e[i].u ][ e[i].v ];
			}
		for(int k = 1; k <= n; k ++)
			for(int i = 1; i <= n; i ++)
				for(int j = 1; j <= n; j ++)
					if(G[i][k] < INF && G[k][j] < INF)
						G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
		for(int i = 1; i <= n; i ++)
			for(int j = i + 1; j <= n; j ++)
				if(dis[i][j] != G[i][j]) return ;
		if(ans > cost) ans = cost;
	}
	
	void dfs(int k, int m) {
		if(k == m) {
			Judge() ;
			return ;
		}
		tag[k] = true, dfs(k + 1, m);
		tag[k] = false, dfs(k + 1, m);
	}
	
	int main() {
		for(int i = 1; i <= n; i ++)
			for(int j = i + 1; j <= n; j ++)
				e.push_back((Edge) {i, j});
		for(int i = 0; i < e.size(); i ++) tag[i] = false;
		dfs(0, (int) e.size());
		printf("%lld\n", ans == 2e18 ? -1 : ans);
		return 0;
	}
}

namespace Part2 {
	int main() {
		LL ans = 0;
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= n; j ++) {
				bool flag = false;
				for(int k = 1; k <= n; k ++) {
					if(k == i || k == j) continue ;
					if(dis[i][k] + dis[k][j] == dis[i][j]) {
						flag = true;
						break ;
					}
				}
				if(!flag) ans += dis[i][j];
			}
		}
		printf("%lld\n", ans / 2LL);
		return 0;
	}
}

bool error__() {
	for(int k = 1; k <= n; k ++)
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n; j ++)
				if(dis[i][j] > dis[i][k] + dis[k][j]) return true;
	return false;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			scanf("%d", &dis[i][j]);
		}
	}
	if(error__()) return puts("-1"), 0;

	if(n <= 6) Part1 :: main();
	else Part2 :: main(); 
	return 0;
}

Measured memory_bytes: 640
char*s,T['   '],*r=T;U[1<<27];n;k;main(i){for(;gets(r+1);k=!--n)for(;*++r&=31;)U[r-T]=k|=!!n<<*r;for(;~i--;)for(s=r;s-->T;k=U[k]=U[k-=~-~*s<<21]?:*s?s-T:0)n+=__builtin_popcount(U[s-T]&(U[k+'   ']^=!s[-1]<<*s));printf("%d",n+1);}

Measured memory_bytes: 135156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<ll> d(n);
    rep(i,n) cin>>d[i];
    sort(begin(d),end(d));
    ll c=n/2;
    ll a=d[c-1],b=d[c];
    //cout<<a<<' '<<b<<endl;
    cout<<b-a<<endl;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(void){
    
    int X;
    int N;
    int p[1000];
    int i;
    int dir=1;
    int tmp;
    int cnt=1;
    int loop=2;

    scanf("%d %d", &X, &N);
    tmp = X;

    if(N==0){
        printf("%d", X);
        return 0;
    }

    for(i=0; i<N; i++){
        scanf("%d", &p[i]);
    }

    while(cnt!=0){
        
        cnt = 0;

        for(i=0; i<N; i++){
            if(tmp==p[i] && dir==1){
                tmp = X - loop / 2;
                dir = -1;
                cnt++;
                break;
            }
            if(tmp==p[i] && dir==-1){
                tmp = X + (loop-1) / 2;
                dir = 1;
                cnt++;
                break;
            }
        }
        loop++;
    }
    
    printf("%d", tmp);

    return 0;
}

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

int main() {

int N;
cin >> N;
//int *num=new int[3];

//int num[]={300000,200000,100000,0};
//string *name=new string[N+1];
int flag=0;
if(N%2==1)flag=1;
N/=2;

cout << N-1+flag << endl;

}


Measured memory_bytes: 256
#input
N=int(input())
An=list(int(i) for i in input().split())
x=0
point=0
flag=True
while(flag):
  x=0
  for x in range(N):
    if x==N-1:
      point+=1

    elif An[x]%2==0:
      An[x]/=2

    else:
      flag=False
      break
print(point) 


Measured memory_bytes: 3060
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define vv vector< vector< int > >
#define ll long long
#define ALL(a) (a).begin(), (a).end()
const long long mod = 1000000000 + 7;
const long long INF = 9e18;
const double PI = 3.14159265358979323846;

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

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

int digsum(int n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int ans = 0, tmp, sum;
    for(int i = 1; i <= N; ++i){
        sum = digsum(i);
        if((A <= sum) && (sum <= B)) ans += i;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3608
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>

using namespace std;

int main() {
    int n,a;
    cin >> n >> a;
    if( n % 500 <= a) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
// ITP1_5_A:   Print a Rectangle
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
 
int main()
{
    int H, W;
    int h, w;
 
    while (1) {
        scanf("%d%d", &H, &W);
        if (H == 0 && W == 0) break;
        for (h = 0; h < H; h++) {
            for (w = 0; w < W; w++) putchar('#');
            putchar('\n');
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 2696
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;
    bool ans = false;
    for(int i = 0; i < T.length(); i++){
        bool result = true;
        for(int j = 0; j < S.length(); j++){
            if(S.at(j) != T.at((j+i)%T.length())){
                result = false;
                break;
            }
        }
        if(result){
            ans = true;
            break;
        }
    }
    if(ans){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
d8 = {}
d10 = {}
for i in range(1, 10000):
    if int(i * 0.08) not in d8:
        d8[int(i * 0.08)] = i
    if int(i * 0.1) not in d10:
        d10[int(i * 0.1)] = i

A, B = map(int, input().rstrip().split())
a = d8.get(A, None)
aa = d8.get(A + 1, None)
b = d10.get(B, None)
bb = d10.get(B + 1, None)
if a is None or b is None:
    print(-1)
elif max(a, b) < min(aa, bb):
    print(max(a, b))
else:
    print(-1)


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

int main() {
    int n;
    cin >> n;
    vector<int> c(n), s(n), f(n);
    rep(i, n - 1) cin >> c[i] >> s[i] >> f[i];

    rep(i, n) {
        ll now = 0;
        for (int j = i; j < n - 1; ++j) {
            if (now < s[j])
                now = s[j] + c[j];
            else {
                if (now % f[j] == 0)
                    now += c[j];
                else
                    now += (f[j] - now % f[j]) + c[j];
            }
        }
        cout << now << "\n";
    }

    return 0;
}

Measured memory_bytes: 3604
import java.util.Scanner;


public class Main {
	public static int count;
	public static int m;
	public static int[] G = new int[100];
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = stdIn.nextInt();
		
		shellSort(a, n);
		
		System.out.println(m);
		for (int i = m - 1; i >= 0; i--) {
			if (i != 0)
				System.out.print(G[i] + " ");
			else
				System.out.println(G[i]);
		}
		System.out.println(count);
		for (int i = 0; i < n; i++)
			System.out.println(a[i]);
	}
	
	public static void insertionSort(int[] a, int n, int g) {
		for (int i = g; i < n; i++) {
			int v = a[i];
			int j = i - g;
			while (j >= 0 && a[j] > v) {
				a[j+g] = a[j];
				j -= g;
				count++;
			}
			a[j+g] = v;
		}
	}
	
	public static void shellSort(int[] a, int n) {
		
		count = 0;
		m = 0;
		
		for (int i = 1; ;i = 3 * i + 1) {
			if (i > n) break;
			G[m] = i;
			m++;
		}
		
		
		for (int i = m - 1; i >= 0; i--)
			insertionSort(a, n, G[i]);

	}
}

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

int W,H;
vector<vector<char>> s;
vector<vector<int>> cost;

int bfs(){
  int dx[]={0,1,0,-1}, dy[]={1,0,-1,0};
  queue<pair<int,int>> que;
  que.push(make_pair(0,0));
  cost[0][0]=0;
  while(!que.empty()){
    pair<int,int> p=que.front();
    que.pop();
    if(p==make_pair(H-1,W-1)){return cost[p.first][p.second];}
    for(int i=0;i<4;i++){
      int ny=p.first+dy[i], nx=p.second+dx[i];
      //マスの外
      if(nx<0 || ny<0 || nx>=W || ny>=H)continue;
      //壁
      if(s[ny][nx]=='#')continue;
      //既に探索済み
      if(cost[ny][nx]!=-1)continue;
      
      cost[ny][nx]=cost[p.first][p.second]+1;
      que.push(make_pair(ny,nx));
    }
  }
  return -1;
}

int main(){
  cin >> H >> W;
  s=vector<vector<char>>(H,vector<char>(W));
  int white=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> s[i][j];
      if(s[i][j]=='.')white++;
    }
  }
  cost=vector<vector<int>>(H,vector<int>(W,-1));
  int min=bfs();
  if(min==-1){cout << min << endl;}
  else{cout << white-min-1 << endl;}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
inline void update(pair<int, int>& x, const pair<int, int>& y){
    if(x > y) x = y;
}
int calc(const vector<int>& w, int MAX){
    const int INF = 100000000;
    int n = w.size();
    pair<int, int> dp[1 << 15];
    REP(s, 1 << n) dp[s] = make_pair(INF, INF);
    dp[0] = make_pair(0, 0);
    for(int s = 0; s < (1 << n); s++){
        for(int i = 0; i < n; i++){
            if(!(s >> i & 1)){
                if(dp[s].second + w[i] > MAX){
                    update(dp[s | (1 << i)], make_pair(dp[s].first + 1, w[i]));
                }else{
                    update(dp[s | (1 << i)], make_pair(dp[s].first, dp[s].second + w[i]));
                }
            }
        }
    }
    int times = dp[(1 << n) - 1].first + (dp[(1 << n) - 1].second > 0 ? 1 : 0);
    return 2 * (times - 1) + 1;
}

int main(){
    int N, M, W;
    while(cin >> N >> M >> W){
        vector<int> w[10000];
        REP(i, N){
            int K;
            cin >> K;
            while(K--){
                int t;
                cin >> t;
                w[i].push_back(t);
            }
        }
        vector<int> have;
        int cost = 0;
        int last_calc = 0;
        for(int i = N - 1; i > 0; i--){
            if(w[i].empty()){
                cost += last_calc;
            }else{
                if(have.empty()) cost += abs((i + 1) - M);
                have.insert(have.end(), w[i].begin(), w[i].end());
                cost += (last_calc = calc(have, W));
            }
        }
        cout << cost << endl;
    }
    return 0;
}

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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  int ab, bc, ac;
  if(a < b) ab = b - a;
  else ab = a - b;
  
  if(b < c) bc = c - b;
  else bc = b - c;
  
  if(a < c) ac = c - a;
  else ac = a - c;
  
  if(ac <= d || (ab <= d && bc <= d)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
A = [int(i) for i in input().split()]

flag = 1
count = 0
while flag:
    flag = 0
    for j in range(n-1,0,-1):
        if A[j] < A[j-1]:
            A[j],A[j-1] = A[j-1],A[j]
            flag = 1
            count += 1
print(" ".join(map(str,A)))
print(count)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int maxn=200005;
inline int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
int n,m,cur=0,now;
typedef pair<int,int> P;
P a[maxn];
priority_queue<int,vector<int>,greater<int> > que;
vector<int> vec;
int main(){
	n=read(),m=read();now=m+1;
	for (int i=1;i<=n;++i) a[i].fi=read(),a[i].se=read();
	sort(a+1,a+n+1);
	for (int i=1;i<=n;++i){
		que.push(a[i].se);
		if (cur==a[i].fi){
			vec.push_back(que.top());
			que.pop();
		}
		else ++cur;
	}
	sort(vec.begin(),vec.end());
	for (int i=vec.size()-1;i>=0&&now>cur+1;--i){
		if (now==vec[i]) continue;
		--now;
	}
	printf ("%d\n",n-m+now-cur-1);
	return 0;
}


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

int main() {
  const int D = 1e9 + 7;
  
  int N, M;
  cin >> N >> M;

  vector<int> fac(M + 1, 1); {
    for (int i = 1; i <= M; ++i) {
      fac[i] = (int64_t) fac[i - 1] * i % D;
    }
  }

  vector<int> ifac(M + 1); {
    auto inv = [D](int v) {
      int r = 1;
      for (int p = D - 2; p; p >>= 1) {
        if (p & 1) r = (int64_t) r * v % D;
        v = (int64_t) v * v % D;
      }
      return r;
    };
    ifac[M] = inv(fac[M]);
    for (int i = M; i; --i) {
      ifac[i - 1] = (int64_t) ifac[i] * i % D;
    }
    assert(ifac[0] == 1);
  };

  int res = 0;
  for (int k = 0; k <= N; ++k) {
    int s = k & 1 ? -1 : 1;
    int c = (int64_t) fac[N] * ifac[k] % D * ifac[N - k] % D;
    int p = (int64_t) fac[M] * ifac[M - k] % D;
    int q = (int64_t) fac[M - k] * ifac[(M - k) - (N - k)] % D;
    (res += (int64_t) s * c % D * p % D * q % D * q % D) %= D;
  }

  if (res < 0) res += D;
  cout << res << endl;

  return 0;
}



Measured memory_bytes: 7188
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int cnt=0,cn=0;
	for(int i=1;i<=n+1;i++)
	{
		if(a[i]!=a[i-1])
		{
			if(cn>=a[i-1]) cnt+=cn-a[i-1];
			else cnt+=cn;
			cn=1;
		}
		else cn++;
	}
	cout<<cnt<<endl;
	return 0;
} 

Measured memory_bytes: 640
a, b, k = map(int, input().split())
if b-a <= k:
    for i in range(a, b+1):
        print(i)
    exit()
for i in range(a, a+k):
    print(i)
for i in range(max(a+k, b-k+1), b+1):
    print(i)


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

using namespace std;

int main(void){
    int n;

    cin >> n;

    vector<int>   a(n,0);
    map<int, long long> am, ansm;
    long long ans_all = 0;

    for(int i=0; i<n; i++){
        cin >> a[i];
        if(am.find(a[i]) == am.end())
            am[a[i]] = 0;
        am[a[i]]++;
    }

    for(auto i=am.begin(); i!=am.end(); i++){
        int k=i->first;
        long long v=i->second;
        ansm[k] = v*(v-1)/2;
        ans_all += ansm[k];
    }

    for(int i=0; i<n;i++){
        long long ans;
        long long b=a[i];
        long long bk=am[b]-1;
        
        ans = ans_all - ansm[b] + (bk*(bk-1)/2);
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 18176
import sys
sys.setrecursionlimit(10000000)
import itertools


def calc_distance(cord1, cord2):
    x1, y1 = cord1
    x2, y2 = cord2

    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


def main():
    N = int(input())
    cords = []
    for _ in range(N):
        x, y = map(int,input().split())
        cords.append((x, y))
    
    n_lists = [i for i in range(N)]
    sum_distance = 0
    num = 0
    for order in itertools.permutations(n_lists):
        distance = 0
        for i in range(1, N):
            from_, to_ = order[i - 1], order[i]
            distance += calc_distance(cords[from_], cords[to_])
        sum_distance += distance
        num += 1
    
    sum_distance /= num
    print(sum_distance)

    




if __name__ == '__main__':
    main()


Measured memory_bytes: 40944
import java.util.Scanner;

public class Main {
    void run(String[] args){
        Scanner scan=new Scanner(System.in);
        long a=scan.nextLong();
        long b=scan.nextLong();
        long c=scan.nextLong();
        long d=scan.nextLong();
        long max=Long.MIN_VALUE;
        long answer;
        answer=a*c;
        if(max<answer){
            max=answer;
        }
        answer=a*d;
        if(max<answer){
            max=answer;
        }
        answer=b*c;
        if(max<answer){
            max=answer;
        }
        answer=b*d;
        if(max<answer){
            max=answer;
        }
        System.out.println(max);
    }
    public static void main(String args[]){
        Main printer = new Main();
        printer.run(args);
    }
}

Measured memory_bytes: 35668
N = int(input())
L = [int(x) for x in input().split()]

import bisect
L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in reversed(range(i + 1, N - 1)):
        k = bisect.bisect_left(L, L[i] + L[j], j)
        ans += k - j - 1
print(ans)

Measured memory_bytes: 3188