akhauriyash/Code-Regression huggingface dataset:
// AOJ ALDS1_2_D Shell Sort
// 2018.4.27 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cnt;

void insertion_sort(int n, int *a, int g)
{
	int i, j, key;

	for (i = g; i < n; i++) {
		key = a[i];
		j = i-g;
		while (a[j] > key) {
			a[j+g] = a[j];
			j -= g;
cnt++;
			if (j < 0) break;
		}
		a[j+g] = key;
	}
}

int m;
int g[102];

void shell_sort(int n, int *a)
{
	int i, lim;

	lim = n / 9;		// 要素数/9
	if (lim < 40) lim = 40;
	g[0] = 1;
	for (m = 1; ; m++) {
//		g[m] = 3*g[m-1]+1;
		g[m] = (g[m-1] << 1) +1;
		if (g[m] >= n || g[m] > lim) break;
	}

	cnt = 0;
	for (i = m-1; i >= 0; i--) insertion_sort(n, a, g[i]);
}

// バッファを経ずstdinから数値を得る
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int a[1000002];

int main()
{
	int N, i;

	N = in();
	for (i = 0; i < N; i++) a[i] = in();
	shell_sort(N, a);
	printf("%d\n", m);
	printf("%d", g[m-1]);
	for (i = m-2; i >= 0; i--) printf(" %d", g[i]);
	printf("\n%d\n", cnt);
	for (i = 0; i < N; i++) printf("%d\n", a[i]);
	return 0;
}


Measured memory_bytes: 5588
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    int conv[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> conv[i][j];
        }
    }

    for (int k = 0; k < 10; k++)
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                conv[i][j] = min(conv[i][j], conv[i][k] + conv[k][j]);

    int res = 0;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int t;
            cin >> t;
            if (t == -1)
                continue;
            res += conv[t][1];
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int N = 1e5 + 10 , M = 5e5+10 ,  MOD = 1e9+7;
const int OO = 0x3f3f3f3f;
const double EPS = 1e-3;
 
#define clr(arr,val) memset(arr , val , sizeof (arr))
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define ALL(v) ((v).begin()) , ((v).end())
#define SZ(v)  ((int)((v).size()))
typedef pair <int,int> pii ;
typedef vector < pii > vii ;
typedef vector < int > vi;
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 



int x , a;


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


    cin >> x >> a;
    if(x < a)
        cout << "0\n";
    else 
        cout << "10\n";


    


    

 
    
    return 0;
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  ll n, ans = 1;
  cin >> n;
  while (n > 1) ans *= n--;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3096
#include<cctype>
#include<cstdio>

int main(){
  char ch;

  while(1){

    scanf("%c",&ch);

    if ( ch == '\n')break;
    if (isalpha(ch)){
      if(islower(ch)){
	putchar (toupper(ch));
      }
      if(isupper(ch)){
	putchar (tolower(ch));
      }
    }
    else printf("%c",ch);
  }
  printf("\n");
  
  return 0;
}
  

Measured memory_bytes: 948
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
const int MAXN = 100000;
const ll MAX = 2000000001;

int n;
vector<ll> a(MAXN);
vector<ll> w(MAXN);

ll f(ll sw) {
  w[0] = sw;
  for(int i = 0; i < n / 2; i++) {
    w[i + 1] = 2 * a[i] - w[i];
    w[n - i - 1] = 2 * a[(n - i - 1) % n] - w[(n - i) % n];
    if(w[i + 1] < 0) {
      if(i % 2)
        return 1;
      else
        return -1;
    }
    if(w[n - i - 1] < 0) {
      if(i % 2)
        return 1;
      else
        return -1;
    }
    if(i == (n - 3) / 2) {
      if(2 * a[i + 1] > w[i + 1] + w[n - i - 1]) {
        if(i % 2)
          return 1;
        else
          return -1;
      }
      if(2 * a[i + 1] < w[i + 1] + w[n - i - 1]) {
        if(i % 2)
          return -1;
        else
          return 1;
      }
    }
  }
  return 0;
}

int main(void) {
  cin >> n;
  a.resize(n);
  w.resize(n);
  rep(i, n) cin >> a[i];
  ll l = -1, r = MAX;
  while(r - l > 0) {
    ll mid = (l + r) / 2;
    if(f(mid) < 0) {
      r = mid;
    } else if(0 < f(mid)) {
      l = mid;
    } else {
      r = l = mid;
    }
  }
  rep(i, n) {
    printf("%lld%c", w[i], i == n - 1 ? '\n' : ' ');
  }
  return 0;
}

Measured memory_bytes: 2944
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define double long double
    const int INF=0x3f3f3f3f;
    const ll LLINF=0x3f3f3f3f3f3f3f3fll;
    ll qread()
    {
        ll ans=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) {num=-num;putchar('-');}
        if(num>9) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);puts("");}
    #define FR first
    #define SE second
    #define MP make_pair
    #define pr pair<int,int>
    #define PB push_back
    #define vc vector
    void chmax(int &x,const int y) {x=x>y?x:y;}
    void chmin(ll &x,const int y) {x=x<y?x:y;}
    const int MAX_N=2e5+10;
    const ll MOD=1e9+7;
    void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}

    char type[MAX_N];pr qes[MAX_N];
    void main()
    {
        int n,q;scanf("%d%d%s",&n,&q,type+1);
        for(int i=1;i<=q;i++)
        {
            char str1[10],str2[10];scanf("%s%s",str1,str2);
            qes[i]=MP(str1[0]-'A',str2[0]=='R');
        }
        int fl=1,fr=n;
        for(int i=q;i>=1;i--)
        {
            if(qes[i].SE)
            {
                if(fl>1 and type[fl-1]=='A'+qes[i].FR) fl--;
                if(type[fr]=='A'+qes[i].FR) fr--;
            }
            else
            {
                if(fr<n and type[fr+1]=='A'+qes[i].FR) fr++;
                if(type[fl]=='A'+qes[i].FR) fl++;
            }
            if(fl>fr) break;
        }
        write(fr-fl+1);
    }
};
int main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 2048
import java.util.*;

public class Main{
	public static void main(String[] args){

		Scanner scan=new Scanner(System.in);
		int num=scan.nextInt();
		int[] r=new int[num];
		int v,j;

		for (int i=0;i<=num-1;i++ ) {
			r[i]=scan.nextInt();
		}

			      System.out.printf("%d",r[0]);
	      for(int k=1;k<=num-1;k++ ) {
				System.out.printf(" %d",r[k]);	
		   }
		   System.out.printf("\n");

	    for (int i=1;i<=num-1;i++){
	      v = r[i];
	      j = i - 1;
	      while (j >= 0 &&r[j] > v){
	      r[j+1] = r[j];
	      j--;
	      }
	      r[j+1] = v;
	      

	      System.out.printf("%d",r[0]);
	      for(int k=1;k<=num-1;k++ ) {
				System.out.printf(" %d",r[k]);	
		   }
         System.out.printf("\n");

	    }
		
	}
}



Measured memory_bytes: 44308
#pragma GCC optimize ("O3")
///#include<bits/stdc++.h>
#include <iterator>
#include<algorithm>
#include<vector>
#include<complex>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<math.h>
#include<map>
#include<stack>
#include<sstream>
#include<queue>
#include<list>
#include<iomanip>
#include<bitset>
#include<limits.h>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
#include<math.h>
#include<map>
#include<stack>
#include<sstream>
#include<queue>
#include<list>
#include<iomanip>
#include<bitset>
#include<limits.h>
#include<map>
#include<sstream>
using namespace std;



/// Info.
///****************************************************************************************************************************************///
/// Coder               : BAHAA El_DEEN OSAMA SAYED.
/// Problem name        : D - AcCepted
/// Method              : IM
/// Date                : 4/3/2020
///****************************************************************************************************************************************///


#define rep0(i,x)         for(int i=0; i<x ;++i)
#define all(v)           ((v.begin()),((v.end())
#define mm(v,d)          memset(v,d,sizeof(v))
#define lp(i,v)          for(int i=0;i<sizeof(v);++i)
#define lpi(i,j,n)       for(int i=(j);i>=(int)n;++i)
#define lpd(i,j,n)       for(int i=(j);i>=(int)n;--i)
#define MP               make_pair
#define SZ(v)            ((int) ( (v).size() ) )
#define ull              unsigned long long
#define ll               long long
#define pi               3.1415926536
#define oo               1e9
#define OO               1e18
#define Fx(n)            fixed<<setprecision(n)
#define FasterIO           std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define RE0              return 0
#define RE1              return 1
#define mp(a,b)          make_pair(a,b)
#define X                first
#define Y                second
#define pii              pair(int a, int b)
#define rep1(i,x)        for(int i=1;i<=x;++i)
#define rep2(i,x)        for(int i=2;i<x;++i)
#define RE               return
//#define LD               long double
#define all(v) ((v).begin()),((v).end())


const  int  N   = (int) 1e5+100;
const  int  M   = (int) 1e4+4;
const  int  INF = (int) 0x3f3f3f3f;
///const double ESP = 1e-7;
///const ll MOD=1e8+9;


int cnt=0,cnt_C=0;
string s;

int GalhO0O0O0O0O0M()
{

  cin>>s;
  if(s[0]!='A'){
    cout<<"WA";
    RE0;
  }


  for(int i=1;i<s.length();i++)
  {
    if(islower(s[i]))
        {
          cnt++;
        }
  }

  if(cnt!=s.length()-2)
  {
    cout<<"WA";
    RE0;
  }
  for(int i=2;i<=s.length()-2;i++)
  {
    if(s[i]=='C')
    {
        cnt_C++;
    }
  }

  if(cnt_C!=1)
{
    cout<<"WA";
    RE0;
  }




  cout<<"AC";
}




int main()
{
FasterIO;
GalhO0O0O0O0O0M();
RE0;}


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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()

using ll = std::int64_t;
using vint = std::vector<int>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;

void Main() {
    string s;
    cin >> s;
    int ans = 0;
    int cnt = 0;
    rep(i, s.length()) {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            ++cnt;
        }
        else {
            cnt = 0;
        }
        if (cnt > ans)ans = cnt;
    }
    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    int s; cin >> s;
    int p = s/100, q = s % 100;
    bool pm =  (p>=1 && p <= 12);
    bool qm =  (q>=1 && q <= 12);
    if(pm&&qm) cout << "AMBIGUOUS" << endl;
    else if(pm) cout << "MMYY" << endl;
    else if(qm) cout << "YYMM" << endl;
    else cout << "NA" << endl;
    
    return 0;
}


Measured memory_bytes: 256
N, W = [int(i) for i in input().split(" ")]

vw = []
for i in range(N):
    vw.append([int(i) for i in input().split(" ")])
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-weight[i]] + value[i])
        else :
            dp[i+1][j] = dp[i][j]

print(dp[N][W])


Measured memory_bytes: 16136
n=int(input())
c=[0]*(n-1)
s=[0]*(n-1)
f=[0]*(n-1)
for i in range(n-1):
    c[i],s[i],f[i]=map(int,input().split())
for i in range(n-1):
    t=s[i]+c[i]
    for j in range(i+1,n-1):
        if t<s[j]:
            t=s[j]+c[j]
        elif t%f[j]==0:
            t+=c[j]
        else:
            t+=f[j]-t%f[j]+c[j]
    print(t)
print('0')

Measured memory_bytes: 41708
#include "bits/stdc++.h"
using namespace std ;


bool a[305][305] ;
int  b[305][305] ;
int h , w , k ;
int cnt = 0 ;
bool fun( int r  ){
	int i = 1 ;
	while( i <= w && a[r][i] == 0 ){
		i++ ;
	}
	if( i > w ) return false ;
	cnt++ ;
	for( int j = 1 ; j <= i ; j++ ){
		b[r][j] = cnt ;
	}
	for( int j = i+1 ; j <= w ; j++  ){
		if( a[r][j] == 0) b[r][j] = cnt ;
		else{
			cnt ++ ;
			b[r][j] = cnt ;
		}
	}
	return true ;
}
int main(){
	
	cin >> h >> w >> k ;
	string s ;
	for( int i =1 ; i <= h ; i++ ){
		cin >> s ; 
		for( int j = 1 ; j <= w ; j++ ){
			if(s[j-1] == '.' ) a[i][j] = 0 ;
			else a[i][j] = 1 ;
		}
	}
	int fr  = -1 ;
	for( int i = 1 ; i <= h ; i++ ){
		if(fun(i)){
			if( fr == -1 ) fr = i ;
		}
		else{
			if( fr != -1 ){
				for( int j = 1 ; j <= w ; j++ ){
					b[i][j] = b[i-1][j] ;
				}
			}
		}
	}
	for( int i = fr-1 ; i >= 1 ; i-- ){
		for( int j = 1 ; j <= w ; j++ ){
			b[i][j] = b[i+1][j] ;
		}
	}
	for( int i = 1 ; i <= h ; i++ ){
		for( int j = 1 ; j <= w ; j++ ){
			cout << b[i][j] <<" " ;
		}
		cout << endl ;
	}
	return 0 ;
}

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

using namespace std;
typedef long long int ll;
ll mod = 1e9+7;

ll gcd(ll a, ll b){
	return b ? gcd(b,a%b) : a;
}

int N=1e3+10;

int main(){
	int n, ti=0, xi=0, yi=0;
	cin>>n;
	bool f=true;
	while(n--){
		int t,x,y;
		cin>>t>>x>>y;
		int T=abs(xi-x)+abs(yi-y), tt=abs(t-ti);

		if(T==0){
			if(tt%2!=0) f=false;
		}else{
			if(tt<T) f=false;
			else if(tt>T){
				tt-=(T-1);
				if(tt%2==0) f=false;
			}
		}

		ti=t;
		xi=x;
		yi=y;
	}

	if(f) cout<<"Yes\n";
	else cout<<"No\n";
}

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

namespace Atcoder
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }
        private static object GetResult()
        {
            var input = ReadTexts();

            long a = input[0].ToLong();
            long b = input[1].ToLong();
            long c = input[2].ToLong();
            long k = input[3].ToLong();

            if (k <= a)
            {
                return k;
            }
            else if (k <= a + b)
            {
                return a;
            }
            else
            {
                return a - (k - a - b);
            }
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }

        #endregion
    }

    public static class CastExtention
    {
        public static long ToLong(this string a) { return long.Parse(a); }
    }
}

Measured memory_bytes: 28256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  long long k; cin >> k;
  deque<ll> q;
  for (ll i = 1; i <= 9; i++) q.push_back(i);
  ll ans;
  for (ll i = k; k--;) {
    ans = q.front(); q.pop_front();
    for (ll d = max(0LL, ans%10-1), e = min(9LL, ans%10+1); d <= e; d++) {
      q.push_back(ans*10+d);
    }
  }
  cout << ans << endl;
}


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

int main(void){
    int A, B, C, D;
    int standard_left = 0, standard_right = 0;
    int answer = 0;
    cin >> A >> B >> C >> D;
    if(A >= C){
        standard_left = A;
    } else if(A < C){
        standard_left = C;
    }
    if(D <= B){
        standard_right = D;
    } else if(B < D){
        standard_right = B;
    }
    answer = standard_right - standard_left;
    if(answer < 0){
        answer = 0;
    }
    cout << answer << endl;

}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <utility>
#include <functional>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

int gcd(int a, int b){
    if(a < b){
        swap(a, b);
    }

    int r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

signed main(){
    int n;
    cin >> n;

    rep(i, n){
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        if(a < b || b > d){
            cout << "No" << endl;
            continue;
        }
        if(b <= c){
            cout << "Yes" << endl;
            continue;
        }

        a %= b;
        int g = gcd(b, d);
        a = b - g + a % g;
        if(a > c){
            cout << "No" << endl;
            continue;
        }
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int h,w;
	int a[55][55]={};
	int s[55][55]={};
	int di[4]={-1,0,1,0};
	int dj[4]={0,1,0,-1};

	cin>>h>>w;
	int all=0;
	FORQ(i,1,h){
		FORQ(j,1,w){
			a[i][j]=0;
			s[i][j]=mod;
		}
	}
	//s[1][1]=1;
	FORQ(i,1,h){
		FORQ(j,1,w){
			char ch;
			cin>>ch;
			if(ch=='.'){
				a[i][j]=1;
				all++;
			}
		}
	}
	//cout<<all<<endl;
	priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int>>>> pq;
	pq.push(make_pair(1,make_pair(1,1)));
	while(!pq.empty()){
		pair<int,pair<int,int>> pr=pq.top();
		pq.pop();
		int nx=pr.ND.ST,ny=pr.ND.ND,dist=pr.ST;
		if(dist<s[nx][ny])s[nx][ny]=dist;
		else continue;
		if(nx==h&&ny==w)break;
		//cout<<nx<<" "<<ny<<" "<<dist<<endl;
		FOR(i,0,4){
			int x=pr.ND.ST+di[i],y=pr.ND.ND+dj[i];
			if(a[x][y]){
				pq.push(make_pair(pr.ST+1,make_pair(x,y)));
			}
		}
	}
	if(s[h][w]==mod){
		cout<<-1<<endl;
	}else cout<<all-s[h][w]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

const int64_t MOD = 1e9+7;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int64_t> X(N), Y(M);
	for (int64_t& e : X) {
		cin >> e;
	}
	for (int64_t& e : Y) {
		cin >> e;
	}
	int64_t xsum = 0, prev = 0, num = 1;
	for (int i = N - 2; i >= 0; --i) {
		xsum += (((X[i + 1] - X[i])*num + prev))%MOD;
		xsum %= MOD;
		prev = (X[i + 1] - X[i])*num + prev;
		prev %= MOD;
		++num;
	}
	int64_t ysum = 0;
	prev = 0;
	num = 1;
	for (int i = M - 2; i >= 0; --i) {
		ysum += ((((Y[i + 1] - Y[i])*num + prev)%MOD)*xsum)%MOD;
		ysum %= MOD;
		prev = (Y[i + 1] - Y[i])*num + prev;
		prev %= MOD;
		++num;
	}
	cout << ysum << endl;
	cin >> ws;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using ll = int_fast64_t;

int main(){
        ll n, a, b;
        scanf("%ld %ld %ld", &n, &a, &b);
        std::vector<ll> h(n);
        for(ll i=0; i<n; i++) scanf("%ld", &h[i]);

        ll l=-1, r=1e9;
        while(r-l>1){
                ll mid = (r-l)/2 + l;

                ll cnt = 0;
                for(ll i: h){
                        cnt += (std::max(0l, i-b*mid) + (a-b-1)) / (a-b);
                }
                if(cnt>mid) l = mid;
                else r = mid;
        }

        printf("%ld\n", r);
        return 0;
}

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

int main() {
    int a, b, c, d, e, f, x, y, liquid = 0, sugar = 0;
    double maximum = 0.0;
    cin >> a >> b >> c >> d >> e >> f;
    liquid = 100 * a;
    set<int> water;
    rep(i, f / a / 100 + 1) rep(j, f / b / 100 + 1) {
        x = 100 * a * i + 100 * b * j;
        if(x > f) break;
        water.insert(x);
    }
    for(int t : water) {
        rep(i, (f - t) / c + 1) rep(j, (f - t) / d + 1) {
            y = c * i + d * j;
            if(t + y > f || 100 * y > t * e) break;
            if(100 * y > maximum * (t + y)) {
                maximum = 100.0 * y / (t + y);
                sugar = y;
                liquid = t + y;
            }
        }
    }
    cout << liquid << " " << sugar << endl;
}

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

#define y1 aklsdja
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define pb push_back
#define t top()
#define fr front()

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , x) for(int i = 0 ; i < x ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define oo 1e17 + 5
#define ll long long
#define int long long
#define pow poww

const int N = 1e5 + 5;
int n;
int dp[N][4] , a[N][4];

main()
{
    //freopen("C.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i , 1 , n)
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    dp[1][1] = a[1][1];
    dp[1][2] = a[1][2];
    dp[1][3] = a[1][3];
    FOR(i , 2 , n)
    {
        FOR(j , 1 , 3)
            FOR(k , 1 , 3)
                if(j != k)
                    dp[i][j] = max(dp[i][j] , dp[i - 1][k] + a[i][j]);
    }
    cout << max(dp[n][1] , max(dp[n][2] , dp[n][3]));
}


Measured memory_bytes: 6528
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
#N = 4
#A = [2,2,4,4,4,4,12,12,12]

A.sort()
cnt = Counter(A)
keys = sorted(cnt.keys(), reverse=True)

ans = 0
for a in keys:
    p = len(bin(a)) - 2
    t = (1 << p) - a
    if a == t:
        d = cnt[a]//2
        ans += d
        cnt[a] -= 2*d
        continue
    if t in cnt:
        d = min(cnt[t],cnt[a])
        ans += d
        cnt[t] -= d
        cnt[a] -= d
print(ans)





Measured memory_bytes: 123352
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define print(x) cout << to_string(x) << '\n'
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vi>
#define vvb vector<vb>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define mii map<int,int>
#define vpii vector<pii>
#define vt3i vector<t3i>
#define sq(x) (x)*(x)
#define inv(x) powa(x, MOD-2)
 
long long INF = 1LL<<60;
long long MOD = 1e9+7;

string to_string(char &c) {string x(1, c); return x;}
string to_string(const char s[]) {return (string)s;}
string to_string(string &s) {return s;}
string to_string(vb &v) {string res; for (const bool &x : v) res += to_string(x) + ' '; return res;}
template <class C> string to_string(C &v) {string res; for (auto &x : v) res += to_string(x) + ' '; return res;}
template <typename A, typename B> istream &operator>>(istream &is, pair<A, B> &pr) {is >> pr.first >> pr.second; return is;}
template <typename A> istream &operator>>(istream &is, vector<A> &v) {for (auto &x : v) is >> x; return is;}
ostream &operator<<(ostream &os, char &c) {os << (char)c; return os;}
ostream &operator<<(ostream &os, const char s[]) {os << (string)s; return os;}
ostream &operator<<(ostream &os, string &s) {for (char &c : s) os << (char)c; return os;}
template <typename A, typename B> ostream &operator<<(ostream &os, pair<A, B> pr) {os << '(' << pr.first << ", " << pr.second << ')'; return os;}
ostream &operator<<(ostream &os, vb &v) {
    bool first = true;
    os << '[';
    for (const bool &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
template <class C> ostream &operator<<(ostream &os, C &v) {
    bool first = true;
    os << '[';
    for (auto &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
string bin_string(int x) {
    const int d = 32;
    string res(d, ' ');
    REP(i, 0, d) res[d-1-i] = '0'+(x>>i & 1LL);
    return res;
}
int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    vi a(n);
    cin >> a;

    int BIG = 1000010;
    vi sieve(BIG);
    REP(p, 2, BIG) if (!sieve[p]) for (int u=p*p; u<BIG; u+=p) sieve[u] = p;

    mii lcm;
    REP(i, 0, n) {
        mii facts;
        int x = a[i];
        while (sieve[x]) {
            ++facts[sieve[x]];
            x /= sieve[x];
        }
        ++facts[x];
        for (auto pr : facts) {
            lcm[pr.first] = max(lcm[pr.first], pr.second);
        }
    }
    int res = 1;
    for (auto pr : lcm) res = res * powa(pr.first, pr.second) % MOD;
    int temp = 0;
    REP(i, 0, n) temp = (temp + inv(a[i])) % MOD;
    res = res * temp % MOD;
    print(res);
}


Measured memory_bytes: 8832
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

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

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	LL N, P;
	cin >> N >> P;
	string s;
	cin >> s;

	if(P == 2 || P == 5){
		LL ret = 0;
		REP(i, N){
			if((s[i] - '0') % P == 0) ret += i + 1;
		}
		cout << ret << endl;
	}
	else{
		LL ret = 0;
		LL a = 0, b = 1;
		vector<int> count(P + 1, 0);
		count[0] = 1;
		REP(i, N){
			a += (s[N - 1 - i] - '0') * b;
			a %= P;
			b *= 10;
			b %= P;
			ret += count[a]++;
		}
		cout << ret << endl;
	}


	return 0;
}


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

int main(){
    int D; cin >> D;
    vector<int> c(26);
    rep(i,26) cin >> c[i];
    vector<vector<int>> s(D,vector<int>(26));
    rep(i,D){
        rep(j,26){
            cin >> s[i][j];
        }
    }

    rep(z,D){
        int contest=-1;
        int score=0;
        rep(i,26){
            if(score < s[z][i]){
                score = s[z][i];
                contest = i+1;
            }
        }
        cout << contest << endl;
    }
}


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

const int maxn = 200010, P = 1000000007;
int n, a[maxn], pre[maxn], f[maxn];

int main() {
    scanf("%d", &n);
    for (int i = f[0] = 1; i <= n; i++) {
        scanf("%d", &a[i]), f[i] = f[i - 1];
        if (pre[a[i]] && pre[a[i]] < i - 1) (f[i] += f[pre[a[i]]]) %= P;
        pre[a[i]] = i;
    }
    printf("%d\n", f[n]);
    return 0;
}

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

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()

ll mod = 1000000007;

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

ll inv(ll x){
  ll res = 1;
  ll k = mod - 2;
  ll y = x;
  while(k){
    if(k&1)res = (res*y)%mod;
    y = (y*y) % mod;
    k /= 2;
  }
  return res;
}

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

  int s;
  cin >> s;
  vvll ret(s,vll(3));

  rep(i,s){
    if(i == 0){
      ret[i][0] = 1;
    }else {
      ret[i][0] = ret[i-1][2];
      ret[i][1] = ret[i-1][0];
      ret[i][2] = (ret[i-1][1] + ret[i-1][2]) % mod;
    }
  }

  cout << ret[s-1][2] << endl;
}

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

int main(){
  int n, d;
  cin >> n >> d;
  int xy[n][d];
  for(int i=0; i<n; ++i){
    for(int j=0; j<d; ++j){
      cin >> xy[i][j];
    }
  }
  int ans=0;
  for(int i=0; i<n; ++i){
    for(int j=i+1; j<n; ++j){
      int dis=0;
      for(int k=0; k<d; ++k){
        dis += abs(xy[i][k] - xy[j][k]) * abs(xy[i][k] - xy[j][k]);
      }
      double rdis = sqrt(dis);
      //cout << dis << " " << rdis << endl;
      if(dis == (int)rdis * (int)rdis) ++ans;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int (i)=0 ;(i)<(n);(i)++)
#define REPR(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(x) x.begin(),x.end()
#define REVERSE(x) reverse(x.begin(),x.end())
#define SORT(x,n) sort(x,x)
#define P pair<int,int>
typedef long long LL;
const int INF=1000000007;
using namespace std;
int gcd(int a,int b){
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}

int main(){
int N;
cin>>N;
vector<int> a(N);
REP(i,N){
    cin>>a[i];
}
int ans=0;
for(int i=0;i<N;i++){
    if(a[i]!=-1){
        ans++;
        int index=i;
        int counter=i+1;
        while(index<N){
            while(a[index]>=a[counter]){
            counter++;
            }
          a[index]=-1;
          index=counter;
        }
}
}
cout<<ans;
}

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

using namespace std;
#define ll long long int

int main()
{
    ll t;
    t = 1;
    //cin t;
    while (t--)
    {
        ll n, m, k;
        cin >> n >> m >> k;
        ll x, y, x1, y1;
        cin >> x >> y >> x1 >> y1;
        int dx[4] = {0, 0, -1, 1};
        int dy[4] = {-1, 1, 0, 0};
        char a[n][m];
        ll dist[n][m];
        bool visited[n][m];
        x--;
        y--;
        x1--;
        y1--;
        if (a[x1][y1] == '@')
        {
            cout << "-1" << endl;
            return 0;
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                dist[i][j] = INT_MAX;
                visited[i][j] = false;
                cin >> a[i][j];
            }
        }
        queue<pair<int, int>> q;
        q.push({x, y});
        visited[x][y] = true;
        dist[x][y] = 0;
        while (!q.empty())
        {
            pair<int, int> temp = q.front();
            q.pop();
            if(temp.first == x1 && temp.second == y1)
            break;
            for (int i = 0; i < 4; i++)
            {
                int x2 = temp.first;
                int y2 = temp.second;
                for (int j = 0; j < k; j++)
                {
                    x2 += dx[i];
                    y2 += dy[i];
                    if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && a[x2][y2] != '@')
                    {
                        if (!visited[x2][y2])
                        {
                            visited[x2][y2] = true;
                            q.push({x2, y2});
                            dist[x2][y2] = 1 + dist[temp.first][temp.second];
                        }
                        else
                        {
                            if(dist[x2][y2] < 1 + dist[temp.first][temp.second])
                            break;
                            dist[x2][y2] = min((ll)dist[x2][y2], (ll)1 + dist[temp.first][temp.second]);
                        }
                            
                    }
                    else
                        break;
                }
            }
        }
        if (dist[x1][y1] == INT_MAX)
            cout << "-1" << endl;
        else
            cout << dist[x1][y1] << endl;
    }
}



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

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

class DisjointSet
{
public:
    vector<int> p;

    DisjointSet() {}
    DisjointSet(int size)
    : p(vector<int>(size, -1))
    {}

    bool same(int x, int y)
    {
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y)
    {
        x = findSet(x); y = findSet(y);
        if (x == y) return;

        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
    }

    int findSet(int x)
    {
        if (p[x] < 0) return x;
        else p[x] = findSet(p[x]);
        return p[x];
    }
};

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

    int N, M;
    cin >> N >> M;

    vector<int> p(N);
    rep (i, N) cin >> p[i];

    int x, y;
    DisjointSet ds{N + 1};
    rep (i, M)
    {
        cin >> x >> y;
        ds.unite(x, y);
    }

    int ans = 0;
    rep (i, N)
    {
        if (ds.same(p[i], i + 1))
        {
            ++ans;
        }
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vpll vector<pair<ll,ll>>
#define pqi priority_queue<int>
#define pql priority_queue<ll>
#define fi first
#define se second
#define pb push_back
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mib map<int,bool>
#define mlb map<ll,bool>
#define f(i,k,n) for(ll i=k;i<n;i++)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll mod=1e9+7;
const ld pii=3.141592653589793238;
int main()
{
    IOS
    ld r;
    cin>>r;
    ld ans=2*pii*r;
    cout<<ans<<endl;
}

Measured memory_bytes: 3824
#include <iostream>
#include <string>
using namespace std;
using ll = long long;

ll pow(ll b, ll p, ll m) {
    b = b%m;
    ll ans = 1;
    while(p) {
        if(p & 1) {
            ans = (ans*b)%m;
        }
        p >>= 1;
        b = (b*b)%m;
    }
    return ans;
}

int main() {
    ll n;
    cin >> n;
    ll ans = 0;
    const ll m = 1e9+7;

    ans += pow(10, n, m);
    ans %= m;
    ans += pow(8, n, m);
    ans %= m;
    ans -= 2*pow(9, n, m);
    ans %= m;

    while(ans < 0) {
        ans += m;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3612
#include<iostream>

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

int main()
{
  int A,B,C;
  
  cin>>A>>B>>C;
  
  if(A==B&&A==C)
  {
    cout<<"No";
    goto end;
  }
  else if(A!=B&&C!=A&&B!=C)
  {
    cout<<"No";
    goto end;
  }
  else
  {
    cout<<"Yes";
  }
  end:;
}

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

using namespace std;

typedef unsigned long long int ULL;
typedef long long LL;
typedef long double LD;

LL pm(LL n)  
{  
    LL cnt = 0;
	if (n%2 == 0) {
		n /= 2;
		cnt++;
		while (n % 2 == 0)  
		{  
			n = n/2;  
		} 
	}
  
    for (LL i = 3; i <= sqrt(n); i = i + 2)  
    {   
		if (n%i == 0) {
			cnt++;
			n/= i;
			while (n % i == 0)  
			{  
				n = n/i;  
			}  
		}
    }  
    if (n > 2)  
        cnt++;
	
	return cnt;
} 

int main()
{
	LL a, b;
	cin >> a >> b;

	LL gc = __gcd(a, b);
	cout << pm(gc)+1 << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#define MAX 1000000000000000000
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<unsigned long long int> v(n);
	//bool zeroes=false;
	unsigned long long int mul = 1,prev=1,flag=0;

	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
		if (v[i] == 0)
		{
			flag=1;
			break;
		}
		
	}
	if (flag)
	{
		cout << "0" << endl;
		return 0;
	}
	for (int i = 0; i < n; ++i)
	{
		mul *= v[i];
		if (mul/v[i]!=prev || mul>MAX)
		{
			cout << "-1" << endl;
			return 0;
		}
		prev = mul;
	}
	cout << mul << endl;
	return 0;
}


Measured memory_bytes: 4048
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
   
    char c;
    cin>>c;
    
    if(c=='a' || c=='i' || c=='u' || c=='e' || c=='o'){
        
        cout<<"vowel"<<endl;
        
    }else{
        cout<<"consonant"<<endl;
        
    }
    
    
    return 0;
   
}






Measured memory_bytes: 256
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	ll n; cin >> n;
	deque<char> res;
	while (n > 0)
	{
		--n;
		res.push_front(char('a' + (n % 26)));
		n /= 26;
	}
	while (!res.empty())
	{
		cout << res.front();
		res.pop_front();
	}
}

Measured memory_bytes: 3608
#include<stdio.h>
int main(){
  int i;
  int a,b,c;
  int cnt;

  scanf("%d %d %d",&a,&b,&c);
  cnt=0;
  for(i=a;i<=b;i++){
    if(c%i==0) cnt++;
  }

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

  return 0;
}


Measured memory_bytes: 2044
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define db double
#define zero(x) (fabs(x)<eps)
#define sgn(x) (zero(x)?0:((x)>0?1:-1))
const db eps=1e-10;
struct point{
    db x,y;
    point(){}
    point(db x,db y):x(x),y(y){}
    point operator + (point B){ return point(x+B.x,y+B.y); }
    point operator - (point B){ return point(x-B.x,y-B.y); }
    point operator * (db k){ return point(k*x,k*y); }
    db operator * (point B){ return x*B.y-y*B.x; }
    db operator ^ (point B){ return x*B.x+y*B.y; }
    bool operator < (point B){ return (y>0)!=(B.y>0)?y>0:((*this)*B)>0; }
};
db dis2(point A,point B){ return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y); }
struct line{
    point A,B;
    line(){}
    line(point A,point B):A(A),B(B){}
};
point projection(line l,point P){
    point dir=l.B-l.A; P=P-l.A;
    return dir*((P^dir)/dis2(l.A,l.B))+l.A;
}
point reflection(line l,point P){
    return projection(l,P)*2-P;
}
int direction(point P0,point P1,point P2){
    db det=(P2-P0)*(P1-P0); return sgn(det);
}
bool parallel(line l1,line l2){
    return zero((l1.B-l1.A)*(l2.B-l2.A));
}
bool orthogonal(line l1,line l2){
    return zero((l1.B-l1.A)^(l2.B-l2.A));
}
bool intersect(line l1,line l2){
    int d1=direction(l1.A,l1.B,l2.A),d2=direction(l1.A,l1.B,l2.B);
    int d3=direction(l2.A,l2.B,l1.A),d4=direction(l2.A,l2.B,l1.B);
    if (d1>0&&d2>0||d1<0&&d2<0||d3>0&&d4>0||d3<0&&d4<0) return false;
    if (l1.A.x>l1.B.x) swap(l1.A.x,l1.B.x);
    if (l1.A.y>l1.B.y) swap(l1.A.y,l1.B.y);
    if (l2.A.x>l2.B.x) swap(l2.A.x,l2.B.x);
    if (l2.A.y>l2.B.y) swap(l2.A.y,l2.B.y);
    return !(l1.B.x<l2.A.x||l2.B.x<l1.A.x||l1.B.y<l2.A.y||l2.B.y<l1.A.y);
}
point cross_point(line l1, line l2){
    db s1=fabs((l2.B-l2.A)*(l1.A-l2.A)),s2=fabs((l2.B-l2.A)*(l1.B-l2.A));
    return l1.A+(l1.B-l1.A)*(s1/(s1+s2));
}
int main(){
    int q; scanf("%d",&q);
    while (q--){
        db x1,y1,x2,y2; line l1,l2;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); l1=line(point(x1,y1),point(x2,y2));
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); l2=line(point(x1,y1),point(x2,y2));
        point P=cross_point(l1,l2);
        printf("%.9f %.9f\n",P.x,P.y);
    }
}



Measured memory_bytes: 3252
#include<iostream>
#include<iomanip>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N, K;
	cin >> N >> K;
	vector<ll> H(N);
	REP(i, N) cin >> H[i];
	sort(H.begin(), H.end());
	ll res = 0;
	REP(i, N - K) res += H[i];
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 1792
// Etavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define file(s) freopen(s".in" ,"r",stdin),freopen(s".out","w",stdout)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
	register char ch;int f=1;
	while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
	register int x=ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}

int main(){
	double n; scanf("%lf",&n);
	printf("%.10lf\n",pow(n/3,3));
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<set>
#define rep(i,n) for(ll i=1;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,ll>P;

const ll mod = 1e9+7;
const ll INF = ll(1e18)+1;
const ll MAXN = 1e6;

int main()
{
    
    string s;
    cin>>s;
    int prev=s[0]-'0';
    int ans=0;
    int ans2=1;
    int prev2=prev?0:1;
    rep(i,s.size())
    {
        int a=s[i]-'0';
        int a2=a;
        if(prev==a)
        {
            ans++;
            prev=a?0:1;
        }
        else
        {
            prev=a;
        }
        if(prev2==a2)
        {
            ans2++;
            prev2=a2?0:1;
        }
        else
        {
            prev2=a2;
        }

    }
    cout<<min(ans,ans2);
}

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <vector>
#define N 1000001
using namespace std;
int main(){  
  vector<int> V;
  int t,n,k,x[N],ans;
  cin >> t;
  while(t--){
    cin >> n >> k;
    V.clear();
    for(int i=0;i<n;i++){
      cin >> x[i];
      if(i!=0) V.push_back(x[i]-x[i-1]);
    }
    if(k>=n){
      cout << 0 << endl;
      continue;
    }
    sort(V.begin(),V.end());
    k--;
    ans=x[n-1]-x[0];
    int l=1;
    while(k--){
      ans-=V[V.size()-l];
      l++;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2120
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class CharDict{
		List<Integer> pos;
		public CharDict() {
			pos = new ArrayList<Integer>();
		}
		int posArr[];
		void toArray(){
			posArr = new int[pos.size()];
			for(int i = 0 ; i < posArr.length ; ++i){
				posArr[i] = pos.get(i);
			}
		}
		int nextPosition(int currentPosition){
			int last = posArr[posArr.length - 1];
			if(last < currentPosition){
				return posArr[0];
			}
			if(last == currentPosition){
				return currentPosition;
			}
			int insertPoint = Arrays.binarySearch(posArr, currentPosition);
			if(insertPoint >= 0){
				return posArr[insertPoint];
			}
			insertPoint = ~insertPoint;
			return posArr[insertPoint];
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		CharDict dicts[] = new CharDict[26];
		char sarr[] = s.toCharArray();
		for(int i = 0 ; i < sarr.length ; ++i){
			int c = sarr[i] - 'a';
			if(dicts[c] == null){
				dicts[c] = new CharDict();
			}
			dicts[c].pos.add(i);
		}
		for(CharDict dict : dicts){
			if(dict != null){
				dict.toArray();				
			}
		}
		int N = s.length();
		char tarr[] = t.toCharArray();
		long ret = 0;
		int pos = 0;
		for(int i = 0 ; i < tarr.length ; ++i){
			int c = tarr[i] - 'a';
			if(dicts[c] == null){
				System.out.println(-1);
				return ;
			}
			CharDict dict = dicts[c];
			int nextP = dict.nextPosition(pos);
			if(nextP >= pos){
				ret += nextP - pos + 1;
			}else{
				ret += nextP + N - pos + 1;
			}
//			System.out.println(nextP);
			pos = nextP + 1;
			if(pos == N){
				pos = 0;
			}
		}
		System.out.println(ret);
	}
}


Measured memory_bytes: 32716
#include<bits/stdc++.h>
#define MAX (int)(2e6+5)
#define PB push_back
#define MP make_pair
#define ll long long
#define pii pair<long long,long long>
#define sz(a) (int)a.size()
#define sl(a) scanf("%lld",&a)
#define sll(a,b) scanf("%lld%lld",&a,&b)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d%d",&a,&b)
#define p1(a) cout<<"Check "<<a<<endl;
#define p2(a,b) cout<<"Check "<<a<<' '<<b<<endl;
#define p3(a,b,c) cout<<"Check "<<a<<' '<<b<<' '<<c<<endl;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define fore(i,l,n) for(int i=int(l);i<int(n);i++)
#define clr(a) memset(a,0,sizeof(a))
#define MOD (int)(1e7+7)
#define INF (long long)(1e18)

using namespace std;

int main()
{
    //freopen("tt.txt","r",stdin);
    int test=1,i=0,n,m;
    //si(test);
    while(test--){
        int n;
        si(n);
        int a,b;
        sii(a,b);
        a--;
        if(b/n-a/n>0) cout<<"OK"<<endl;
        else cout<<"NG"<<endl;
    }
}


Measured memory_bytes: 3688