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

using namespace std;

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

typedef long long ll;

vector<string> V;
string v[20];

ll dp[1<<20][18];
ll cost[18][18];
ll const INF = 1<<29;

string rcon;

inline bool cmp(string const& a, string const& b) {
  if(a.size() != b.size()) return a.size() < b.size();
  return a < b;
}

bool contains(string const& a, string const& b) {
  int asize = a.size(), bsize = b.size();
  
  rep(i, asize) {
    bool ok = 1;
    rep(j, bsize) {
      if(i+j >= asize) { ok = 0; break; }
      if(a[i+j] != b[j]) { ok = 0; break; }
    }
    if(ok) { return true; }
  }
  
  return false;
}

string concat(string const& a, string const& b) {
  string ret = a+b;
   
  int n = a.size(), m = b.size();
  for(int i=n-1; i>=0; i--) { // start
    bool ok = 1;
    rep(j, m) { // len
      if(i+j >= n) { break; }
      if(a[i+j] != b[j]) { ok = 0; break; }
    }
    if(ok) {
      if(n-i < m) {
	ret = min(ret, a+b.substr(n-i), cmp);
      }
    }
  }
  return ret;
}
 
int main() {
  
  int n, N;
  
  while(cin >> n && n) {
    V.resize(n);
    rep(i, n) {
      cin >> V[i];
    }
    
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    n = V.size();
    
    set<int> unuse;
    rep(i, n) {
      rep(j, n) {
	if(i == j) { continue; }
	if(contains(V[i], V[j])) {
	  unuse.insert(j);
	}
      }
    }
    
    N = 0;
    rep(i, n) {
      if(!unuse.count(i)) {
	v[N++] = V[i];
      }
    }
    
    rep(i, N) {
      cost[i][i] = 0;
      rep(j, N) {
	if(i == j) { continue; }
	string re = concat(v[i], v[j]);
	cost[i][j] = (int)re.size()-v[i].size();
      }
    }
    
    rep(i, 1<<N) rep(j, N) dp[i][j] = INF;
    rep(i, N) {
      dp[1<<i][i] = v[i].size();
    }
    
    rep(S, 1<<N) {
      rep(i, N) {
	if(dp[S][i] == INF) { continue; }
	rep(j, N) {
	  if(S >> j & 1) { continue; }
	  int next = S|(1<<j);
	  if(dp[next][j] > dp[S][i]+cost[i][j]) {
	    dp[next][j] = dp[S][i]+cost[i][j];
	  }
	}
      }
    }
    
    ll ans = 1<<29;
    rep(i, N) {
      ans = min(ans, dp[(1<<N)-1][i]);
    }
    
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 5308
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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 (a > b){ a = b; return 1;}return 0;}
template <class T>
void printv(vector<T> v) {for (T t : v) {cout << t << " ";}cout << '\n';}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" <<endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int dp[5050][5050];

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

    RREP(i,N-1) RREP(j,N-1) {
        if (s[i] != s[j]) dp[i][j] = 0;
        else dp[i][j] = dp[i+1][j+1] + 1;
    }

    int ans = 0;
    REP(i,N) REP(j,N) {
        if (i >= j) continue;
        int now = min(dp[i][j], j-i);
        ans = max(ans,now);
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 98944
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	int price = -1;
	for (int i = 1; i <= 10000; i++) {
		if (i * 8 / 100 == A && i / 10 == B) {
			price = i;
			break;
		}
	}
	cout << price << endl;
	return 0;
}

Measured memory_bytes: 3612
#include<stdio.h>
int sum;
int main()
{
	int n;
	scanf("%d",&n);
	s(n);
	if((n%sum)==0)printf("Yes");
	else printf("No");
	return 0;
}
int s(int n)
{
    static int a;
	if(n==0)return;
	a=n%10;
	sum=sum+a;
	return s(((n/10)*10)/10);
}

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	int ct = 0, ma = 0;
	for (char c : s)
	{
		if (c == 'R')
			ct++;
		else
		{
			if (ct > ma)
				ma = ct;
			ct = 0;
		}
	}
	if (ct > ma)
		ma = ct;
	cout << ma;
	return 0;
}


Measured memory_bytes: 3640
#include <stdio.h>
#include <stdlib.h>

int main(void){
	int a[3], b[3];
	int counter[4] = {}, i, dummy = 0;

	for(i=0; i<3; i++){
		scanf("%d %d", &a[i], &b[i]);
		counter[a[i]-1]++;
		counter[b[i]-1]++;
	}
	for(i=0; i<4; i++){
		if(counter[i] > 2 || counter[i] == 0){
			printf("NO\n");
			dummy++;
			break;
		}

	}
	if(dummy == 0){
		printf("YES\n");
	}
	return 0;
}

Measured memory_bytes: 128
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    ans = (10 ** n - 2 * (9 ** n) + 8 ** n) % (10 ** 9 + 7)
    print(ans)
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 10924
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define ll long long
 
int main(){
  int n,k,k1,k2,k3,k4,k5,ans=1;
  scanf("%d",&n);
  if(n==1){
    printf("1");
    return 0;
  }
 
  for(int i=1;i<n;i++){
    k1=i*i;
    
    if(n>=32){
      k5=32;
      if(n>=k5 && ans<k5){
        ans=k5;
      }
      k5=64;
      if(n>=k5 && ans<k5){
        ans=k5;
      }
      k5=128;
      if(n>=k5 && ans<k5){
        ans=k5;
      }
      k5=256;
      if(n>=k5 && ans<k5){
        ans=k5;
      }
      k5=512;
      if(n>=k5 && ans<k5){
        ans=k5;
      }
    }
    
    if(n>=243){
      k4=243;
      if(ans<k4){
        ans=k4;
      }
      k4=729;
      if(n>=k4 && ans<k4){
        ans=k4;
      }
    }
    
    if(i<=5){
      k3=i*i*i*i;
      if(n>=k3 && ans<k3){
        ans=k3;
      }
    }
    
    if(i<=10){
      k2=i*i*i;
      if(n>=k2 && ans<k2){
      ans=k2;
      }
    }
    if(n>=k1 && ans<k1){
      ans=k1;
    }
  }
    
      printf("%d",ans);
      return 0;
}

Measured memory_bytes: 128
# ABC061C - Big Array
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    memo = [0] * (10 ** 5 + 1)
    for _ in range(n):
        i, j = map(int, input().split())
        memo[i] += j
    cnt = 0
    for i, j in enumerate(memo):
        cnt += j
        if cnt >= k:
            print(i)
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 5744
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int x = Integer.parseInt(str[0]);
		int y = Integer.parseInt(str[1]);
		int a = Integer.parseInt(str[2]);
		int b = Integer.parseInt(str[3]);
		int c = Integer.parseInt(str[4]);

		PriorityQueue<Long> pq1 = new PriorityQueue<>(Comparator.reverseOrder());
		PriorityQueue<Long> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
		PriorityQueue<Long> pq3 = new PriorityQueue<>(Comparator.reverseOrder());

		str = br.readLine().split(" ");
		for (int i = 0; i < a; i++) {
			long l = Long.parseLong(str[i]);
			pq1.add(l);
		}
		str = br.readLine().split(" ");
		for (int i = 0; i < b; i++) {
			long l = Long.parseLong(str[i]);
			pq2.add(l);
		}
		str = br.readLine().split(" ");
		for (int i = 0; i < c; i++) {
			long l = Long.parseLong(str[i]);
			pq3.add(l);
		}

		PriorityQueue<Long> pq = new PriorityQueue<>(Comparator.reverseOrder());

		for (int i = 0; i < x; i++) {
			pq.add(pq1.poll());
		}

		for (int i = 0; i < y; i++) {
			pq.add(pq2.poll());
		}

		for (long l : pq3) {
			pq.add(l);
		}

		long sum = 0;

		for (int i = 0; i < x + y; i++) {
			sum += pq.poll();
		}

		System.out.println(sum);
	}
}


Measured memory_bytes: 73748
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0; return gcd(a, b, x, y);}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
ll a, b, k;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> a >> b >> k >> k;
  a -= b;
  if(k&1) a *= -1;
  cout << a << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
    using namespace std;
 
    int main(){
      int a[3],k;
      cin >> a[0] >> a[1] >> a[2] >> k;
      sort(a,a+3);
      int ans=a[2];
      for(int i=0;i<k;i++){
       ans*=2; 
      }
      ans+=a[0]+a[1];
      cout << ans << endl;
      return 0;}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int N;
    int A[100];
    int even_num[100];
    int i, j, check_counter = 0;
    int even_num_length;

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

    // 偶数の数をeven_num[100]に入れる
    j = 0;
    for (i = 0; i < N; i++)
    {
        if (A[i] % 2 == 0)
        {
            even_num[j] = A[i];
            j++;
        }
    }
    even_num_length = j;

    // even_numの全ての偶数が3または5で割り切れるか
    for (i = 0; i < even_num_length; i++)
    {
        if (even_num[i] % 3 == 0 || even_num[i] % 5 == 0)
        {
            check_counter++;
        }
    }

    // Approved or Denied
    if (check_counter == even_num_length)
    {
        printf("APPROVED");
    }
    else
    {
        printf("DENIED");
    }
    return (0);
}

Measured memory_bytes: 128
n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
b = a.copy()
b.remove(a_max)
a_max_second = max(b)

for a_i in a:
    if a_i != a_max:
        print(a_max)
    else:
        print(a_max_second)

Measured memory_bytes: 14076
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    long long int h,w,n;
    cin>>h>>w>>n;
    cout << min((n + h - 1) / h, (n + w - 1) / w) << endl;

    return 0;
}


Measured memory_bytes: 888
#include <iostream>
using namespace std;
typedef long long int LLI;

string check(int a, int b, string s)
{
	if( s[a] != '-' )
		return "No";
	for(int i = 0; i < a; i++)
		if( s[i] < '0' or s[i] > '9')
			return "No";
	for(int i = a+1; i < s.size(); i++)
		if( s[i] < '0' or s[i] > '9')
			return "No";
	return "Yes";
}
int main()
{
	int a, b;
	string s;
	cin >> a >> b >> s;
	cout << check(a,b,s);
}

Measured memory_bytes: 3576
using System;
public class Hello{
    
    public static int[] lineToInt(){
            string line = Console.ReadLine();
            string[] strArr = line.Split(' ');
            int[] intArr = new int[strArr.Length];
            
            for(int i=0; i<intArr.Length; i++){
                intArr[i] = int.Parse(strArr[i]);
            }
            return intArr;
    }
//=====================================================
    public static void Main(){
        
        int[] RandC = lineToInt();
        int r = RandC[0];
        int c = RandC[1];
        
        int sum = 0;
        int[,] table = new int[r+1,c+1];
        
        for(int i=0; i<r; i++){
            int[] cells = lineToInt();
            for(int j=0; j<c; j++){
                table[i,j]=cells[j];
            }
        }
        for(int i=0;i<r; i++){
            for(int j=0; j<c; j++){
                table[i,c] += table[i,j];
                sum += table[i,j];
            }
        }
        
        for(int i=0;i<c; i++){
            for(int j=0; j<r; j++){
                table[r,i] += table[j,i];
            }
        }

        
        
        table[r,c]=sum;
        
        for(int i=0; i<=r; i++){
            for(int j=0; j<=c; j++){
                if(j==c){
                Console.WriteLine(table[i,j]);
            }else{
                Console.Write(table[i,j]+" ");
            }
        }
        
    }
    
}
}


Measured memory_bytes: 15940
#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {
	int a, b, c; cin >> a >> b >> c;
	int i;
	for (i = 1; i <= 200; i++) {
		if (a*i%b == c) {
			cout << "YES" << endl;
			return 0;
		}
	}

	cout << "NO" << endl;

	return 0;
}



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

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_ON(bit, i) (bit & (1LL << i))

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> using VVVV = std::vector<std::vector<std::vector<std::vector<T>>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<class T> inline std::vector<T> unique(std::vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}

const int INF = 1 << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;


int solve(V<int> &A) {
    int N = A.size();
    VV<int> dp(N + 1, V<int>(N + 1));  // 閉区間

    FOR(w, 2, N + 1) {
        FOR(left, 0, N) {
            int right = left + w - 1;
            if (right >= N) {
                continue;
            }

            // left + 1からright - 1までが取り除けて、left, rightの組で取り除ける
            if (dp[left + 1][right - 1] == w - 2 and abs(A[left] - A[right]) <= 1) {
                dp[left][right] = w;
            }
            // leftからrightの最大値
            FOR(middle, left, right) {
                dp[left][right] = max(dp[left][right], dp[left][middle] + dp[middle + 1][right]);
            }
        }
    }

    return dp[0][N - 1];
}

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

    while (true) {
        int N;
        cin >> N;
        if (N == 0) {
            break;
        }

        V<int> A(N);
        FOR(i, 0, N) {
            cin >> A[i];
        }
        print(solve(A));
    }

    return 0;
}


Measured memory_bytes: 3320
#include <cstdio>
#include <vector>

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<int> a(N);
  int x=0;
  for (size_t i=0; i<N; ++i) {
    scanf("%d", &a[i]);
    x ^= a[i];
  }

  int res=0;
  for (int k=30; k>=1; k--) {
    if (x == 0) break;
    if (!(x>>(k-1) & 1)) continue;

    for (size_t i=0; i<N; ++i) {
      if ((a[i]^(a[i]-1)) == (1<<k)-1) {
        x ^= (1<<k)-1;
        ++res;
        a[i] = 0;  // cannot used later
        break;
      }
    }
  }

  printf("%d\n", x>0? -1:res);
}


Measured memory_bytes: 640
#include<stdio.h>
int main(){
  int f,N[10],j,maxj,a,h;
 
  /*N[a]Élðãü*/

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

 /*ÀÑÖ¦é*/

  for(f=0;f<10;f++)
    {
      maxj=f;

      for(j=f;j<10;j++)
	{

	if(N[maxj]<N[j])
	  {

	  maxj=j;
	}
      }
    /*N[a]ðN[maxj]É*/

      h=N[f];
    N[f]=N[maxj];
    N[maxj]=h;

  }

  /*ãÊRÂðoÍ*/

    printf("%d\n%d\n%d\n",N[0],N[1],N[2]);
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int n,res;
string s[304];
int ok(int a, int b){
  for(int i = 0; i<n; i++)
    for(int j = 0; j<n; j++)
      if(s[(i+a)%n][(j+b)%n] != s[(j+a)%n][(i+b)%n]) return 0;
  return 1;
}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  std::cin >> n;
  for(int i = 0; i<n; i++) std::cin >> s[i];
  for(int a = 0; a<n; a++) res+=n*ok(a,0);
  std::cout << res << '\n';
}


Measured memory_bytes: 512
X,Y = list(map(int,input().split()))
#X, 2X, 4X,...,2^(t-1)*X<=Yとなる最大のt
#10^18 はだいたい2^60だから全部試せそう
for t in range(1,100):
    if 2**(t-1)*X<=Y:
        out = t
    else:
        break
print(out)


Measured memory_bytes: 61824
#include <bits/stdc++.h>
#pragma warning (disable : 4996)
using namespace std;
int main()
{
	char c[1005];
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) for (int j = 0; j < m; j++)
	{
		scanf("%s", c);
		if (!strcmp(c, "snuke")) return !printf("%c%d", j + 'A', i);
	}
}

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

#define MAX 5000000     // 配列の要素数
#define SENTINEL 2000000000     // 番兵用の非常に大きな値

int L[MAX/2+2], R[MAX/2+2];
int cnt;        // 比較回数

void merge(int A[], int left, int mid, int right) {        // mergeSortによって得られたソート済みの部分配列を統合する関数
    int n1 = mid - left;        // 左側の配列の大きさ
    int n2 = right - mid;       // 右側の配列の大きさ (rightは部分配列の末尾+1のインデックス)
    
    // L[0...n1]とR[0...n2]なる配列を生成
    for (int i = 0; i < n1; ++i) {
        L[i] = A[left + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = A[mid + i];
    }
    L[n1] = SENTINEL;
    R[n2] = SENTINEL;

    // ソート済み配列を統合する
    int i = 0, j = 0;
    for (int k = left; k < right; ++k) {
        cnt++;
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
    return;
}

void mergeSort(int A[], int left, int right) {      // 配列をそれぞれ半分半分に分割する関数
    if (left + 1 < right) {     // 分割した部分配列の要素数が1になるまで分割する
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);        // 左半分を分割
        mergeSort(A, mid, right);       // 右半分を分割
        merge(A, left, mid, right);     // mergeで分割した配列を統合
    }

    return;
}

int main() {
    int n, S[MAX];
    cnt = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> S[i];
    }
    mergeSort(S, 0, n);

    for (int i = 0; i < n; ++i) {
        if (i) cout << " ";
        cout << S[i];
    }
    cout << endl;
    
    cout << cnt << endl;

    return 0;
}


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

typedef long long				ll;
typedef unsigned long long 	    ull;

const int N = 20;

ll dp[N][N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		ll r, t = i, fi = 1, f = 0, l = 0;
		while (t) {
			r = t % 10;
			if (fi) 
				l = r, fi = 0;
			t /= 10;
		}
		f = r;
		dp[f][l]++;
	}
	ll ans = 0;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			ans += dp[i][j] * dp[j][i];
	cout << ans << endl;
	return 0;
}


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

using namespace std;

void solve() {
  string S;
  cin >> S;
  unordered_set<char> st;
  for (char c: S) st.insert(c);
  for (char c = 'a'; c <= 'z'; c++) if (st.count(c) == 0) {
    cout << c << endl;
    return;
  }
  cout << "None" << endl;
}

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


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

int main()
{
	int S;
	int h, m, s;
	
	cin >> S;
	
	s = S % 60;
	S /= 60;
	m = S % 60;
	S /= 60;
	h = S;
	
	cout << h << ":" << m << ":" << s << endl;
	
	return 0;
}


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

ll l, r;
int main(){
	cin >> l >> r;
	if(r - l + 1 >= 2019) {
		cout << 0 << endl;
		return 0;
	}
	
	ll ans = 1e18;
	for(ll i = l; i <= r; i++)
		for(ll j = i + 1; j <= r; j++)
			ans = min(ans, i * j % 2019);
	cout << ans << endl;
	return 0;
}




Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int a, b, h;
  cin >> a >> b >> h;
  cout << (a + b) * h / 2 << endl;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
    
    int x, mem;
    int sum=0;
    
    scanf("%d", &x);
    mem=x;
    
    while (x>0) {
        sum+=x%10;
        x=(x-x%10)/10;
    }
    
    if (mem%sum==0) {
        printf("Yes");
    } else {
        printf("No");
    }

    return 0;
}


Measured memory_bytes: 1708
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define zhfs main
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 1; i <= n; i++)
const int MAXN = 100 * 1000 + 7;
int a[MAXN];
ll solve(int n, int x)
{
	ll sum = 0, res = 0;
	for (int i = 1; i <= n; i++)
	{
		if (x == 1)
		{
			if (sum + a[i] <= 0)
			{
				res += (1 - (sum + a[i]));
				sum = 1;
			}
			else
			{
				sum += a[i];
			}
		}
		else
		{
			if (sum + a[i] >= 0)
			{
				res += (sum + a[i] + 1);
				sum = -1;
			}
			else
			{
				sum += a[i];
			}
		}
		x ^= 1;
	}
	return res;
}
int zhfs()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	ll res = min(solve(n, 1), solve(n, 0));
	printf("%lld\n", res);
}



Measured memory_bytes: 640
#include<iostream>
using namespace std;
 
int main(void){
 int n[3];
 for(int i=0; i<3; i++){
  cin >> n[i];
 }
  
  if((n[0] == n[1] && n[1] != n[2]) || (n[1] == n[2] && n[2] != n[0]) || (n[2] == n[0] && n[0] != n[1])){
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;cin >> n >> k;
	vector<int> a(n);
	rep(i,n) cin >> a.at(i);
	sort(a.begin(),a.end());
	vector<vector<int>> dp(n + 2, vector<int>(5010));
	dp[0][0] = 1;
	int ng = 0,ok = n + 1;
	while(ok - ng > 1){
		int mid = (ok + ng) / 2;
		if(a.at(mid - 1) >= k){
			ok = mid;
			continue;
		}
		rep(i,n + 1){
			rep(j,k + 1){
				dp[i][j] = 0;
			}
		}
		dp[0][0] = 1;
		rep(i,n){
			rep(j,k + 1){
				if(i + 1 != mid && j - a.at(i) >= 0) dp[i + 1][j] |= dp[i][j - a.at(i)];
				dp[i + 1][j] |= dp[i][j];
			}
		}
		bool flg = false;
		for(int i = k - a.at(mid - 1); i < k; i++){
			if(dp[n][i]){
				flg = true;
				break;
			}
		}
		if(flg) ok = mid;
		else ng = mid;
	}
	cout << ng << endl;
}


Measured memory_bytes: 98304
program prob3
	implicit none
    integer(16) :: A
    real(16) :: B
    integer(16) :: intB,ans
    read(*,*) A, B
    intB = int(B*100+0.5,kind=16)
    ans = A*intB
    ans = ans / 100
    write(*,*) ans
	stop
end program prob3


Measured memory_bytes: 2900
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int max = 0;
		Map<String, Integer> mm = new HashMap<>();

		for (int i = 0; i < n; i++) {
			String t = sc.next();
			if (mm.containsKey(t)) {
				mm.put(t, (mm.get(t) + 1));
			} else {
				mm.put(t, 1);
			}

			if (mm.get(t) > max) {
				max = mm.get(t);
			}
		}

		List<String> result = new ArrayList<>();
		for (String str : mm.keySet()) {
			if (mm.get(str) == max) {
				result.add(str);
			}
		}

		Collections.sort(result);

		for (String s : result) {
			System.out.println(s);
		}

		sc.close();

	}
}


Measured memory_bytes: 82180
import java.io.*;

class Main {
  public static void main(String[] args)throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();
      int n = Integer.parseInt(br.readLine());
      String[] data = br.readLine().split(" ");

      for(int i = 0; i < n-1;){
          sb.append(data[n-++i]).append(" ");
      }
      sb.append(data[0]);

      System.out.println(sb.toString());

  }
}

Measured memory_bytes: 24444
#include <iostream>
#include <stdio.h>
#include <math.h> 
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>
#include <numeric>
#include <bitset>
#include <queue>

using namespace std;
vector<int> vec_x;
vector<int> vec_y;
vector<int> vec_st;

int main() {
	//input
	int n,m,x,y;
	cin >> n >> m >> x >> y;

	vec_st.push_back(x);
	vec_st.push_back(y);

	sort(vec_st.begin(), vec_st.end());

	for (int i = 0; i < n; ++i) {
		int tmp = 0;
		cin >> tmp;
		vec_x.push_back(tmp);
	}

	for (int i = 0; i < m; ++i) {
		int tmp = 0;
		cin >> tmp;
		vec_y.push_back(tmp);
	}

	sort(vec_x.begin(), vec_x.end(), greater<int>());
	sort(vec_y.begin(), vec_y.end());

	int cnt = 0;

	for (int i = vec_st[0] + 1; i <= vec_st[1]; ++i) {
		if (vec_x[0] < i && vec_y[0] >= i) {
			cnt++;
		}
	}

	if (cnt > 0) {
		cout << "No War" << endl;
	}
	else {
		cout << "War" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N;
  cin >> N;
  vector<ll> X(N);
  ll a;
  map<ll, ll> count_map;
  for (int i = 0; i < N; i++) {
    cin >> a;
    X[i] = a - i;
  }
  sort(X.begin(), X.end());
  ll mid = X[N / 2];
  ll ans = 0;
  for (auto x : X) {
    ans += abs(x - mid);
  }
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;

int main(){
	ll n, w;
	cin >> n >> w;
	ll weight[n+1], val[n+1], sum = 0LL;
	for(int i=1; i<=n; i++){
	       cin >> weight[i] >> val[i];
	       sum += val[i];
	}
	ll dp[n+1][100007];
	for(int i=0; i<n+1; i++){
		for(int j=0; j<100007; j++)
			dp[i][j] = INT_MAX;
	}
	dp[0][0] = 0;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=100005; j++){
			if(j - val[i] >= 0)
				dp[i][j] = min(dp[i-1][j], weight[i]+dp[i-1][j-val[i]]);
			else
				dp[i][j] = min(dp[i][j],dp[i-1][j]);
		}
	}
	ll mx = -1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=sum; j++){
			if(dp[i][j] <= w){
				mx = max(mx, 1LL*j);}
		}
	}
	cout << mx << endl;
	return 0;
}


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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX/3

const double EPS = 1e-14;
const double PI  = acos(-1.0);


struct Ball {
  int num;
  bool flag;

  Ball(int n, int f) : num(n), flag(f){}
};

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

  vector<Ball> v(n, Ball {1, false});
  v[0].flag = true;

  REP (i, m) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--;y--;
    if (v[x].flag) {
      v[x].num--;
      if (v[x].num == 0) v[x].flag = false;
      v[y].num++;
      v[y].flag = true;
    } else {
      v[x].num--;
      v[y].num++;
    }
  }

  int sum = 0;
  REP (i, n) if (v[i].flag) sum++;
  printf("%d\n", sum);
}


Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<iterator>
#include<set>
#include<stack>
#include<queue>
#include<fstream>
#include<iomanip>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include<cmath>
#include<list>
#include <sstream>
#include<unordered_map>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)a.size()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 2000 + 47;
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	LL n, x;
	cin >> n >> x;
	LL res = n;
	LL tmp = x;
	x = n - x;
	n = tmp;
	while (1)
	{
		if (n % x == 0)
		{
			res += (n / x) * 2 * x - x;
			break;
		}

		res += (n / x) * 2 * x;
		tmp = x;
		x = n % x;
		n = tmp;
	}

	cout << res << endl;
}


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

int main(){
	string s;
	cin>>s;
	// 0-end black
	int dp[100005][2];
	if(s[0]=='0'){
		dp[0][0]=0;
		dp[0][1]=1;
	}
	else{
		dp[0][0]=1;
		dp[0][1]=0;	
	}
	for(int a1=1;a1<s.size();++a1){
		if(s[a1]=='0'){
			dp[a1][0]=dp[a1-1][1];
			dp[a1][1]=1+dp[a1-1][0];
		}
		else{
			dp[a1][1]=dp[a1-1][0];
			dp[a1][0]=1+dp[a1-1][1];	
		}
	}
	cout<<min(dp[s.size()-1][0],dp[s.size()-1][1]);
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
    string s;
    int i, j;
    int a, z;
    int ans = 0;
    
    cin >> s;
    
    for(i = 0; i < s.length() - 1; i++){
        if(s[i] == 'A')     {
            a = i;
            break;
        }
    }
    
    for(i = 1; i < s.length(); i++){
        if(s[i] == 'Z')     z = i;
    }
    
    ans = z - a + 1;
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 640
<?php
$N=trim(fgets(STDIN));
$W=explode(" ",trim(fgets(STDIN)));
$S=0;
$T=0;
for($i=0;$i<$N;$i++){
$S+=$W[$i];
}
$abs=$S;
for($i=0;$i<$N;$i++){
$T+=$W[$i];
if($abs>abs($S-2*$T)){
  $abs=abs($S-2*$T);
}else{
echo $abs;
exit;
}
}
echo $abs;



Measured memory_bytes: 4856
N = int(raw_input())

# Note the numbers are 1 indexed
A = dict([(i, int(j) - 1) for i, j in enumerate(raw_input().split(' '))])

count = 0

# Beware of scope leak
for i in A.keys():
    j = A[i]
    if A[j] == i:
        count += 1

count = count/2
print(count)


Measured memory_bytes: 25624
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int (x); SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long (x); SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x,y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1000000007;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
int N;
map<ll, map<string,ll> > f;

bool chk(string last){
    REP(i,4){
        string con = last;
        if (i != 3) swap(con[i],con[i+1]);
        if (con.find("AGC") != string::npos){
            return false;
        }
    }

    return true;
}


ll dfs(ll depth,string last){
    if (f[depth][last] != 0) return f[depth][last];
    if (depth == N+1) return 1;
    ll ret = 0;
    string C[4] = {"A","C","G","T"};

    REP(i,4){
        if (chk(last + C[i])){
            string next = last.substr(1,2) + C[i];
            ret = ret + dfs(depth+1,next) % MOD;
        }
    }

    f[depth][last] = ret;
    return ret;

}
/*（๑•﹏•๑｀) */
int main() {

    cin >> N;
    // 'A' = 0
    // 'C' = 1
    // 'G' = 2
    // 'T' = 3

    dfs(1,"TTT");
    cout << f[1]["TTT"] % MOD << "\n";


}


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

using namespace std;
#define ll long long

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}

#ifdef LOCAL
#define lcout(a) cout << a;
#define lcoutln(a) cout << a << endl;
#define lcerr(a) cerr << a;
#define lcerrln(a) cerr << a << endl;
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif

#define MOD 1000000007

void init();
void solve();

signed main()
{
	init();
	solve();
}

int N;
vector<int> x;
vector<int> y;
vector<int> h;

void init()
{
	cin >> N;
	x.resize(N);
	y.resize(N);
	h.resize(N);
	rep(i, N) cin >> x[i] >> y[i] >> h[i];
}

int culch(int cx, int cy, int i)
{
	if (h[i] == 0) return 0;
	return h[i] + abs(x[i] - cx) + abs(y[i] - cy);
}

bool ch(int cx, int cy, int H)
{
	rep(i, N) {
		if (max(H-abs(x[i]-cx)-abs(y[i]-cy), 0) != h[i]) {
			return false;
		}
	}
	return true;
}

int culc(int cx, int cy)
{
	int H = 0;
	rep(i, N) {
		H = max(H, culch(cx, cy, i));
	}
	if (H == 0) return 0;
	if (ch(cx, cy, H)) {
		return H;
	}
	return 0;
}

void solve()
{
	rep(cx, 101) {
		rep(cy, 101) {
			int H;
			if ((H = culc(cx, cy)) != 0) {
				cout << cx << " " << cy << " " << H << endl;
				return;
			}
		}
	}
}

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

int n, *d;
int cnt = 0;

void sort(int length){
    for(int i = 0; i < length; i++){
        for(int k = i + length; k < n; k += length){
            int now = d[k];
            int m = k - length;
            for(; m >= 0; m -= length){
                d[m + length] = d[m];
                if(d[m] <= now) break;
                cnt++;
            }
            d[m + length] = now;
        }
    }
}

int main() {
    cin >> n;
    d = new int[n];
    for(int i = 0; i < n; i++){
        cin >> d[i];
    }
    
    vector<int> v;
    for(int i = 1; i <= n; i = 3*i + 1) v.push_back(i);
    
    
    cout << v.size() << endl;
    for(long i = v.size()-1; i  >= 0; i--){
        sort(v[i]);
        cout << (i == v.size()-1 ? "" : " ") << v[i];
    }
    cout << endl << cnt << endl;
    
    for(int i = 0; i < n; i++){
        cout << (!i ? "" : "\n") << d[i];
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 5124
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());

typedef long long ll;

int main(){
  
  int n;
  cin >> n;
  cout << n/3 << endl;

}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u):
        lu, ru = chi[u]
        pre.append(u)
        if lu != -1: dfs(lu)
        ino.append(u)
        if ru != -1: dfs(ru)
        pos.append(u)

    n = int(input())
    par = [-1] * n
    chi = [[] for _ in range(n)]
    for _ in range(n):
        u, l, r = map(int, input().split())
        if l != -1: par[l] = u
        if r != -1: par[r] = u
        chi[u] += [l]
        chi[u] += [r]

    root = par.index(-1)
    pre = []
    ino = []
    pos = []
    dfs(root)

    print("Preorder")
    print("", *pre)
    print("Inorder")
    print("", *ino)
    print("Postorder")
    print("", *pos)

main()



Measured memory_bytes: 5624
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int N = sc.nextInt();
	int B[] = new int[N - 1];
	for (int i = 0; i < N - 1; i++)
	    B[i] = sc.nextInt();

	int count = B[0];
	for (int i = 0; i < N - 2; i++) {
	    if (B[i] < B[i + 1])
		count += B[i];
	    else
		count += B[i + 1];
	}
	count += B[N - 2];

	System.out.println(count);
    }
}

Measured memory_bytes: 21844
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [[0]*3 for i in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][j] = max(dp[i-1][k]+ABC[i-1][j],dp[i][j])

print(max(dp[N]))

Measured memory_bytes: 69724
# -coding: utf-8 -

a, b = map(int, input().split())
s = input()

isNo = False
if s[a] != "-":
    isNo = True
else:
    try:
        int(s[:a])
    except:
        isNo = True

    try:
        int(s[a+1:])
    except:
        isNo = True

if isNo:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 1e2+17;
int a[MAXN],b[MAXN],l[MAXN],r[MAXN];
int main(int argc ,char const *argv[])
{
   	 #ifdef GoodbyeMonkeyKing
    freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
    	cin>>a[i];
    }
    for (int i = 0; i < n; ++i)
    {
    	cin>>b[i];
    }
    l[0] = a[0];
    r[n-1] = b[n-1];
    for (int i = 1; i < n; ++i)
    {
    	l[i] = a[i]+l[i-1];
    }
    for (int i = n-2; i > -1; --i)
    {
    	r[i] = b[i]+r[i+1];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
    	debug(i);
    	debug(l[i]);
    	debug(r[i]);
    	ans = max(ans,l[i]+r[i]);
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
char field[21][21];
char visit[21][21];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int W,H;
void dfs(int y, int x){
  visit[y][x] = 1;
  rep(i,4){
    int ny = y+dy[i];
    int nx = x+dx[i];
    if(field[ny][nx] == '.'
       && visit[ny][nx] == 0
       && nx >= 0
       && nx < W
       && ny >= 0
       && ny < H){
          dfs(ny,nx);
        }
  }
}
int main(){
  while(cin >> W >> H && W){
    int y,x;
    rep(i,H){
      rep(j,W){
        cin >> field[i][j];
        if(field[i][j] == '@') y=i,x=j;
      }
    }
    memset(visit,0,sizeof(visit));
    dfs(y,x);
    int ans = 0;
    rep(i,H){
      rep(j,W){
        ans += visit[i][j];
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3000
/*
 Author : Bisma
 @ copy from bisma template 1.0
 */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <climits>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define repn(a,b,c) for(int a=b; a>=c; a--)
#define ll long long
#define mem(a, b) memset(a, (b), sizeof(a))
#define loop(a,b,c) for(int a = b ;a<c;a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define FOR(a,b,c) for(int a = b ; a<c ; a++ )
ll max(ll a, ll b){
    if(a>b) return a;
    return b;
}

ll min(ll a, ll b){
    if(a>b) return b;
    return a;
}

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

ll a[(int)1e5 * 2 + 10];

int main(){

	fast();
	ll n;
	cin>>n;

	rep(i,1,n) cin>>a[i];

	rep(i,1,n) a[i] = a[i] - i;


	sort(a+1 , a+n+1);

	ll mid = n / 2;

	if(n % 2 == 1) mid += 1;

	ll tot = 0;

	ll num = a[mid];

	rep(i,1,n){
		tot += abs(a[i] - num);
	}

	cout<<tot<<endl;

return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
// template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }




int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> sum(n + 1);
    rep(i, n) sum[i + 1] = sum[i] + a[i];
    // rep(i, n + 1) cout << sum[i] << " "; cout << endl;
    
    rep(i, q) {
        ll x;
        cin >> x;
        
        ll ans = 0;
        rep(l, n) {
            auto it = upper_bound(all(sum), x + sum[l]) - sum.begin();
            // cout << l << " " << it << endl;
            ans += it - l - 1;
        }
        cout << ans << endl;
    }
}



Measured memory_bytes: 3848
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)
#define chmax(x, a)  do { x = max(x, a); } while(0)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main(void) {
  ll x;
  cin >> x;
  x %= 1000;
  if (x == 0)
    cout << 0 << endl;
  else
    cout << 1000 - x << endl;
  return 0;
}


Measured memory_bytes: 3624
n, a, b = map(int, input().split())

ret = 0
d = [0, 0, 0, 0, 0]
for i in range(1, n+1):
 div = i
 for k in range(5):
  div, d[k] = divmod(div, 10)
 if sum(d)>=a and sum(d)<=b:
  ret += i

print(ret)

Measured memory_bytes: 3060