akhauriyash/Code-Regression huggingface dataset:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
count_wall = 0
for i in range(h):
    maze[i] = input()
    count_wall += maze[i].count('#')

INF = h*w
visited = [[0 for i in range(w)] for j in range(h)]
distance = [[INF for i in range(w)] for j in range(h)]

if maze[0][0]=='#':
    print(-1)
    exit()

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
distance[sy][sx] = 0

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]+1:
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x]+1

if distance[h-1][w-1] <INF:
    ans = h*w-count_wall- (distance[h-1][w-1]+1)
else:
    ans = -1
print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
#include <numeric>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
//#define int ll
typedef long long ll;

const int md = 1000000007;
const int INF = 1<<30;
using namespace std;

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

int main(){
    int n; cin >> n;
    vi a(n);
    int ga[n],gb[n];
    rep(i,n){
        ga[i] = gb[i] = 1;
    }

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

    rep(i,n-1){
        if(i == 0) ga[i] = a[i];
        else{
            ga[i] = gcd(ga[i-1], a[i]);
        }
    }

    for(int i = n-1; i >= 1 ; i--){
        if(i == n-1){
            gb[i] = a[i];
        }
        else{
            gb[i] = gcd(gb[i+1], a[i]);
        }
    }

    int ans = gb[1];
    
    /*
    rep(i,n-1) cout << ga[i] << " ";
    cout << endl;
    Rep(i,1,n) cout << gb[i] << " ";
    cout << endl;
    */

    Rep(i,1,n){
        if(i == n-1){
            ans = max(ans,ga[n-2]);
        }else{
            //printf("%d %d %d\n" , i, ga[i-1] , gb[i+1]);
            ans = max(ans,gcd(ga[i-1],gb[i+1]));
        }
    }
    cout << ans << endl;
}   

Measured memory_bytes: 1408
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,p=I()
print((a*3+p)//2)


Measured memory_bytes: 10432
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

ll calc(ll a) {
  ll sum = 0;
  while (a > 0) {
    sum += a % 10;
    a /= 10;
  }
  return sum;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  ll ma = 0;
  ll cur = 1;
  while (cur <= n) {
    ll v = (n + 1) / cur * cur - 1;
    ma = max(ma, calc(v));
    cur *= 10;
  }
  cout << ma << "\n";
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
int N, M, K, H, W, L, R;



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

	cin >> N;
	string s;
	cin >> s;
	cin >> K;
	vector<long long int>d(N);
	vector<long long int>m(N);
	vector<long long int>c(N);
	for (int i = 0; i < N; i++) {
		m[i] = s[i] == 'M';
		d[i] = s[i] == 'D';
		c[i] = s[i] == 'C';
		if (i) {
			m[i] += m[i - 1];
			d[i] += d[i - 1];
			c[i] += c[i - 1];
		}
	}
	for (int i = 0; i < K; i++) {
		cin >> M;
		long long int ans = 0;
		queue<int>Q;
		queue<int>add;
		int bef = 0;
		long long int plus = 0;
		for (int j = 0; j < N; j++) {
			if (s[j] == 'D') {
				add.push(j);
			}
			if (s[j] == 'C') {
			//	cout << "j " << j << endl;
				while (!Q.empty()) {
					if (j - Q.front() >= M) {
						plus -= m[bef] - m[Q.front()];
						Q.pop();
					}
					else break;
				}
				plus += (m[j] - m[bef]) * Q.size();
				ans += plus;
				while (!add.empty()) {
					int cn = add.front();
					add.pop();
					if (j - cn >= M)continue;
					ans += m[j] - m[cn];
					plus += m[j] - m[cn];
					Q.push(cn);
				}
				bef = j;
				//cout << plus << endl;
				//cout << ans << endl;
			}
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 29036
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots():全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    ################
    
    N,M=MI()
    uf=UnionFind(N)
    
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        uf.union(a,b)
        
    ans=0
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        root=uf.find(i)
        dd[root]+=1
        
    for k,v in dd.items():
        s=uf.size(k)
        ans=max(ans,s)
        
    print(ans)
        
        
    

main()


Measured memory_bytes: 101208
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

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

		int n = Integer.parseInt(br.readLine());

		Rest r[] = new Rest[n];
		for (int i = 0; i < n; i++) {
			String str[] = br.readLine().split(" ");
			int p = Integer.parseInt(str[1]);

			r[i] = new Rest(str[0], p, i + 1);
		}

		Arrays.sort(r);

		for (int i = 0; i < n; i++) {
			System.out.println(r[i].id);
		}
	}
}

class Rest implements Comparable<Rest> {
	String name;
	int point;
	int id;

	public Rest(String name, int point, int id) {
		this.name = name;
		this.point = point;
		this.id = id;
	}

	@Override
	public int compareTo(Rest r) {
		int com = this.name.compareTo(r.name);

		if (com != 0)
			return com;

		return r.point - this.point;
	}
}

Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
int H, W;
bool dp[50][150][50][150];
string field[50];
int dh[2][4];
int dw[2][4];
int sh[2];
int sw[2];
int newh[2], neww[2];
void solve() {
    sh[0] = -1;
    sw[0] = -1;
    W = 2 * W + 1;
    for(int h = 0; h < H; h++) {
        cin >> field[h];
        string s;
        cin >> s;
        field[h] = field[h] + "#" + s;
    }
    for(int h1 = 0; h1 < H; h1++) {
        for(int w1 = 0; w1 < W; w1++) {
            if(field[h1][w1] == 'L') {
                sh[0] = h1;
                sw[0] = w1;
            }
            if(field[h1][w1] == 'R') {
                sh[1] = h1;
                sw[1] = w1;
            }
            for(int h2 = 0; h2 < H; h2++) {
                for(int w2 = 0; w2 < W; w2++) {
                    dp[h1][w1][h2][w2] = false;
                }
            }
        }
    }
    queue<vector<i_i>> que;
    que.push({{sh[0], sw[0]}, {sh[1], sw[1]}});
    string ans = "No";
    while(!que.empty()) {
        auto tmp = que.front();
        que.pop();
        //cerr << tmp[0].first << " " << tmp[0].second << " " << tmp[1].first << " " << " " << tmp[1].second << endl;
        for(int k = 0; k < 4; k++) {
            newh[0] = tmp[0].first + dh[0][k];
            newh[1] = tmp[1].first + dh[1][k];
            neww[0] = tmp[0].second + dw[0][k];
            neww[1] = tmp[1].second + dw[1][k];
            for(int j = 0; j < 2; j++) {
                if(newh[j] < 0 or newh[j] >= H or field[newh[j]][neww[j]] == '#') {
                    newh[j] -= dh[j][k];
                }
                if(neww[j] < 0 or neww[j] >= W or field[newh[j]][neww[j]] == '#') {
                    neww[j] -= dw[j][k];
                }
            }
            //cerr << newh[0] << " " << neww[0] << " " << newh[1] << " " << neww[1] << endl;
            if(dp[newh[0]][neww[0]][newh[1]][neww[1]]) continue;
            char grid[2];
            for(int k = 0; k < 2; k++) {
                grid[k] = field[newh[k]][neww[k]];
            }
            //cerr << grid[0] << " " << grid[1] << endl;
            if(grid[0] == '%' and grid[1] == '%') ans = "Yes";
            if(grid[0] == '%' or grid[1] == '%') continue;
            dp[newh[0]][neww[0]][newh[1]][neww[1]] = true;
            que.push({{newh[0], neww[0]}, {newh[1], neww[1]}});
        }
    }
    cout << ans << endl;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    dh[0][0] = 1;
    dh[0][1] = -1;
    dh[1][0] = 1;
    dh[1][1] = -1;
    dw[0][2] = 1;
    dw[0][3] = -1;
    dw[1][2] = -1;
    dw[1][3] = 1;
    while(cin >> W >> H) {
        if(H == 0) break;
        solve();
    }
    return 0;
}


Measured memory_bytes: 42992
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int h,w;

class Graph{
	private:
	int V;
	vvp List;
	vl a;
	void dfs(int v,ll x){
		a[v]=x;
		for(int i=0;i<List[v].size();i++){
			P p=List[v][i];
			ll u=p.first,c=p.second;
			if(a[u]==INF) dfs(u,c-x);
		}
	}
	pll DFS(int v){
		ll mh=INF,mw=INF;
		if(v<h) mh=min(mh,a[v]);
		else mw=min(mw,a[v]);
		a[v]=INF;
		for(int i=0;i<List[v].size();i++){
			int u=List[v][i].first;
			if(a[u]!=INF){
				pll p=DFS(u);
				mh=min(mh,p.first);
				mw=min(mw,p.second);
			}
		}
		return {mh,mw};
	}
	public:
	Graph(int v){
		V=v;
		List=vvp(v);
	}
	void add_edge(int s,int t,int c){
		List[s].push_back({t,c});
		List[t].push_back({s,c});
	}
	string solve(){
		a=vl(V,INF);
		for(int i=0;i<V;i++) if(a[i]==INF) dfs(i,0);
		for(int i=0;i<V;i++) for(int j=0;j<List[i].size();j++){
			P p=List[i][j];
			ll v=p.first,c=p.second;
			if(a[i]+a[v]!=c) return "No";
		}
		for(int i=0;i<V;i++) if(a[i]!=INF){
			pll p=DFS(i);
			if(p.first+p.second<0) return "No";
		}
		return "Yes";
	}
};

int n;

int main(){
	cin>>h>>w>>n;
	Graph g(h+w);
	for(int i=0;i<n;i++){
		int s,t,c;
		cin>>s>>t>>c;
		s--;
		t=t-1+h;
		g.add_edge(s,t,c);
		g.add_edge(t,s,c);
	}
	cout<<g.solve()<<endl;
}

Measured memory_bytes: 16896
## ABC 108 b
x1, y1, x2, y2 = (int(_) for _ in input().split())

dx = x2-x1
dy = y2-y1

x3 = x2-dy
y3 = y2+dx
x4 = x1-dy
y4 = y1+dx

print(x3,y3,x4,y4)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while((n%4!=0&&n%   7!=0)&&(n>=11)){
        n-=11;
    }
    if(n%4==0||n%7==0){
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
}

Measured memory_bytes: 3620
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N,k=get_i
A=get_i
tereport=[]
visit=array(N+1,0)
i=0
visit[i]=1
now=2
lp=INF
while k>0
    i=A[i]-1
    if visit[i]!=0
      k-=1
      lp=now-visit[i]
      break
    end
    visit[i]=now
    now+=1
    k-=1
end
k%=lp
while k>0
    i=A[i]-1
    k-=1
end
puts i+1

Measured memory_bytes: 30184
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ull unsigned long long
#define mp make_pair
#define F first
#define S second
#define mod 1000000007

int h[100005];
int dp[100005];

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++)
    {
        cin >> h[i];
    }

    for(int i=1;i<n;i++)
    {
        int cur = INT_MAX;
        for(int j=1; j<k+1 && i-j >= 0 ;j++)
        {
            dp[i] = min(cur, dp[i-j] + abs(h[i] - h[i-j]) ); 
            cur = dp[i];
        }
    }

    cout << dp[n-1] << endl;

}


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

int main() {
 string s1,s2,s3;
  cin >>s1>>s2;
  s3=s1+s2;
  int n=stoi(s3);
  int x;
  string ans ="No";
   int i=1;
  while(i<1000){
    x= i*i;
    if (x==n){
      ans="Yes";
      break;
    }
    i++;
  }
  cout <<ans ;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long int m1k=0,m5k=0,m10k=0;
double a[100002][2]= {0};

int main()
{
    int n,m,Maxa=0;
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        cin>>a[i][0]>>a[i][1];
        if(a[Maxa][0]<a[i][0])
            Maxa=i;
    }
    priority_queue<int> s;
    for(int i=0; i<n; i++)
    {
        if(a[Maxa][0]<a[i][1])
            s.push(a[i][1]);
    }
    int num=0;
    while(m)
    {
        if(s.empty()==0)
        {
            m-=s.top();
            s.pop();
            num++;
            if(m<=0)
                m=0;
        }
        else
        {
            num+=ceil(m/a[Maxa][0]);
            m=0;
        }
    }
    cout<<num;
}


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


int main()
{
   string s ;
   cin >> s ;
  
  int ans = 0;
  for(int i=0;i<(s.size()/2);++i)
  {
   // cout << s[i] << " " <<  s[s.size()-i-1] ;
    if(s[i]!=s[s.size()-i-1]) ans++ ;
  }
  
   cout << ans << endl ;
      
    return 0;
}




Measured memory_bytes: 256
def bit_count(i, b)
  ret = 0
  until(i == 0) do
    ret += 1 if i[0] == b
    i >>= 1
  end
  ret
end

N = gets.to_i
A = Hash.new{|h, k| h[k] = []}
N.times{|i|
  n = gets.to_i
  n.times{
    A[i+1] << gets.chomp.split(" ").map(&:to_i)
  }
}

ans = 0
(1...2**N).each{|i|
  next if bit_count(i, 1) <= ans
  h = Hash.new{|h, k| h[k] = []}
  (1..N).each{|n|
    h[n] << i[n-1]
    A[n].each{|a| h[a[0]] << a[1]} if i[n-1] == 1
  }
  ans = bit_count(i, 1) if (1..N).to_a.all?{|n| h[n].combination(2).all?{|a, b| a == b}}
}

puts ans


Measured memory_bytes: 2428
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn solve(src: &str) -> String {
    input! {
        source = src, 
        x: i32
    }

    if x >= 30 {
        String::from("Yes")
    } else {
        String::from("No")
    }
}

fn main() {
    input! {
        x: i32
    }

    if x >= 30 {
        println!("Yes");
    } else {
        println!("No");
    }
}

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

int main() {
    int h,w;cin>>h>>w;
    vv a(h, vi (w));
    
    int codd = 0;
    
    rep(i,h)rep(j,w){
        cin>>a[i][j];
        codd += a[i][j]%2;
    }
    
    codd /= 2;
    
    int c=0;
    int ni=0, nj=0;
    
    bool move = false;
    
    vv ans;vi o;
    
    while(c<codd){
        if(move==false && a[ni][nj]%2){//start
            ans.push_back(o);
            ans.back().push_back(ni+1);
            ans.back().push_back(nj+1);
            move = true;
        }else if(move==true && a[ni][nj]%2){//end
            move = false;
            c++;
        }else if(move==true && a[ni][nj]%2==0){
            ans.push_back(o);
            ans.back().push_back(ni+1);
            ans.back().push_back(nj+1);
        }
        
        
        if(ni%2==0 && nj<w-1)
            nj++;
        else if(ni%2==0 && nj==w-1)
            ni++;
        else if(ni%2==1 && nj>0)
            nj--;
        else if(ni%2==1 && nj==0)
            ni++;
        
        
        if(move==true){//during move
            ans.back().push_back(ni+1);
            ans.back().push_back(nj+1);
        }
    }
    
    
    cout << ans.size() << endl;
    rep(i,ans.size()){
        rep(j,4){
            cout << ans[i][j];
            if(j==3)cout << endl;
            else cout << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 9904
ans = ''
while True:
    h, w = map(int, input().split(' '))
    if h == 0 and w == 0:
        break
    else:
        if w % 2 == 0:
            i = 0
            while i < h:
                if i % 2 == 0:
                    ans += '#.' * int(w // 2) + '\n'
                else:
                    ans += '.#' * int(w // 2) + '\n'
                i += 1
        else:
            i = 0
            while i < h:
                if i % 2 == 0:
                    ans += '#.' * int(w // 2) + '#\n'
                else:
                    ans += '.#' * int(w // 2) + '.\n'
                i += 1
        ans += '\n'
if ans != '':
    print(ans[:-1])
    


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

int N, D;

int dis2(const vector<int> & p1, const vector<int> & p2){

	cerr << "(";
	for(int d=0; d<D; ++d){
		cerr << p1[d] << " ";
	}
	cerr << ")";
	cerr << endl;
	cerr << "(";
	for(int d=0; d<D; ++d){
		cerr << p2[d] << " ";
	}
	cerr << ")";

	int sum = 0;
	for(int d=0; d<D; ++d){
		int tmp = p1[d] - p2[d];
		tmp *= tmp;
		sum += tmp;
	}
	return sum;
}

int main(){
	cin >> N >> D;
	vector<vector<int> > data(N, vector<int>(D));
	for(int i=0; i<N; ++i){
		for(int j=0; j<D; ++j){
			int in;
			cin >> in;
			data[i][j] = in;
		}
	}

	int count = 0;
	for(int i=0; i<N; ++i){
		for(int j=0; j<i; ++j){
			cerr << "comparing i=" << i << "and j=" << j << endl;
			int dis_pow2 = dis2(data[i], data[j]);
			int dis = round(sqrt(dis_pow2));
			cerr << "dis*dis=" << (dis*dis) << ", dis_pow2=" << dis_pow2 << endl;
			if(dis*dis == dis_pow2){
				cerr << "count up" << endl;
			  ++count;
			}
		}
	}

	cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

bool ok[2000010];
int cnt[1000010];

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int A[200010];
    rep(i, N) cin >> A[i];
    sort(A, A + N);
    REP(i, 1, 2000010) ok[i] = true;
    rep(i, N) {
        int num = A[i];
        cnt[num]++;
        if(cnt[num] >= 2) {
            ok[num] = false;
            continue;
        }
        int j = 2;
        while(num * j <= 2000000) {
            ok[num * j] = false;
            j++;
        }
    }
    int ans = 0;
    rep(i, N) {
        if(ok[A[i]]) ans++;
    }
    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 10228
//#pragma GCC optimize(2)
//ÄÏ¾©ÊÐµÚÈýÇøOIÎ¯ÌáÐÑÄú£º
//´úÂëÇ§ÍòÌõ£¬-O2µÚÒ»Ìõ¡£
//-O2²»¹æ·¶£¬³¬Ê±Á½ÐÐÀá¡£
// Happy TLE and WA every day!
// by: zxb
#include<bits/stdc++.h>
#define mp              make_pair
#define rep(i,n)        for(int i = 0; i < n; i++)
#define foreach(i,c)    for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define BINF            0x7fffffff
#define INF             0x3f3f3f3f
#define LINF            4557430888798830399
#define pb              push_back
#define F               first
#define S               second
#define Time            clock()/CLOCKS_PER_SEC
#define read            ZXBs_fast_input
#define write           ZXBs_fast_output
//#define usingFiles
using namespace std;

typedef unsigned int ui;
typedef pair<int, int> pii;
typedef long long ll;

inline bool read(int& x){
	x = 0;
	int c;
	int sign = 1;
	while( (c = getchar()) < '0' || c > '9' ) if(c == '-') sign = -1;
	x = c ^ '0';
	while( (c = getchar()) >= '0' && c <= '9' ) x = (x<<3) + (x<<1) + (c ^ '0');
	x *= sign;
	return 1;
}

inline bool write(int x){
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
	return 1;
}

const int rp = 666666;
const bool debug = 1;
const bool I_good_vegetable_a = 1;

signed main(){
	ios::sync_with_stdio(false);
	#ifdef usingFiles
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	int n, k;
	cin >> n >> k;
	if(k == 1) cout << "0" << endl;
	else cout << (n-k) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
int dy[] = {1, 0, 0, -1};
int dx[] = {0, 1, -1, 0};
int b[110][110];
int w, h;
int xs, ys, xg, yg;
int color;
bool flag = false;
bool used[110][110];

void dfs(int y, int x, int py, int px){
	rep(i, 4){
		int ny = y + dy[i], nx = x + dx[i];
		if(used[ny][nx]) continue;//???????????¨???????????????????????????
		if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
		if(b[ny][nx] != color) continue;
		if(ny == py && nx == px) continue;
		if(ny == yg && nx == xg){
			flag = true;return;
		}
		used[ny][nx] = true;
		dfs(ny, nx, y, x);
	}
	return;//????????¢?????¨???????????????
}

int main(void){
	while(1){
		rep(i, 110)rep(j, 110){
			b[i][j] = -1; used[i][j] = false;
		}
		cin >> w >> h;
		if(w == 0 && h == 0) return 0;
		cin >> xs >> ys >> xg >> yg;
		xs--; ys--; xg--; yg--;
		int n; cin >> n;
		rep(i, n){
			int c, d, x, y;
			cin >> c >> d >> x >> y;
			x--; y--;
			if(d == 0){//?¨?
				b[y][x] = b[y][x + 1] = b[y][x + 2] = b[y][x + 3] = c;
				b[y + 1][x] = b[y + 1][x + 1] = b[y + 1][x + 2] = b[y + 1][x + 3] = c;
			}else{//???
				b[y][x] = b[y][x + 1] = c;
				b[y + 1][x] = b[y + 1][x + 1] = c;
				b[y + 2][x] = b[y + 2][x + 1] = c;
				b[y + 3][x] = b[y + 3][x + 1] = c;
			}
		}
		color = b[ys][xs];
		if(color == -1) {//?????????????????????????????????
			printf("NG\n"); continue;
		}
		used[ys][xs] = true; flag = false;
		dfs(ys, xs, -1, -1);
		if(flag) printf("OK\n");
		else printf("NG\n");
	}
}

Measured memory_bytes: 1180
#include <stdio.h>

int main() {
	int n, p[25], ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i]);
	for (int i = 2; i < n; i++)
		if (((p[i - 1] < p[i]) && (p[i] < p[i + 1])) || ((p[i - 1] > p[i]) && (p[i] > p[i + 1])))
			ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main() {
  int m,k; cin >> m >> k;
  int n = pow(2,m);
  if(k==0){ rep(i,n){ cout << i << " " << i << " "; } cout << endl; return 0; }
  if(k>=n || (m==1&&k==1)){cout<<-1<<endl; return 0;}
  
  rep(i,n)if(i!=k){
    cout << i << " ";
  }
  cout << k << " ";
  for(int i=n-1; i>=0; i--)if(i!=k){
    cout << i << " ";
  }
  cout << k << endl; 
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,sse")
using namespace std;

int h, w, k;
int choc[10][1000];
int pref[10][1000];

int p(int a, int b) {
    if (a >= 0 && b >= 0) {
        return pref[a][b];
    }
    return 0;
}

int get(int a, int b, int c, int d) {
    return p(c, d) - p(a - 1, d) - p(c, b - 1) + p(a - 1, b - 1);
}

bool bad(int l, int r, int mask) {
    int a = 0;
    for (int i = 0; i < 10; i++) {
        int pow = 1 << i;
        if ((mask & pow) != 0) {
            int res = get(a, l, i, r);
            if (res > k) {
                return true;
            }
            a = i + 1;
        }
    }
    int res = get(a, l, h - 1, r);
    if (res > k) {
        return true;
    }
    return false;
}

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

    cin >> h >> w >> k;
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            choc[i][j] = (int)(s[j] - '0');
            if (i == 0 && j == 0) {
                pref[i][j] = choc[i][j];
            } else if (i == 0) {
                pref[i][j] = pref[i][j - 1] + choc[i][j];
            } else if (j == 0) {
                pref[i][j] = pref[i - 1][j] + choc[i][j];
            } else {
                pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + choc[i][j];
            }
        }
    }
    int best = h * w;
    for (int mask = 0; mask < (1 << (h - 1)); mask++) {
        int cnt = 0;
        int l = 0;
        for (int r = 0; r < w; r++) {
            if (bad(l, r, mask)) {
                l = r;
                cnt++;
                if (bad(l, r, mask)) {
                    cnt = h * w;
                    break;
                }
            }
        }
        best = min(best, cnt + __builtin_popcount(mask));
    }
    cout << best << '\n';

    fflush(stdout);
    return 0;
}


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

#define ll long long
#define ld long double
#define db double
#define str string
#define pb push_back
#define nl '\n'
#define X first
#define Y second
#define nimble ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v) (v).begin(),(v).end()
#define rall(v) rbegin(v),rend(v)
#define selp(a) for(auto i:a)cout<<i<<" ";cout<<nl;
#define mod(x,m) ((((x)%(m))+(m))%(m))
#define _sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(v) for(int i=0;i<_sz(v);i++)
#define rep1(i,b,a) for(int i=b;i>=a;i--)
#define preci(x) fixed<<setprecision(x)
#define tc int tt=1;cin>>tt;while(tt--)
//ll MLG(ll n,ll b){ll a=0;while(n)a++,n/=b;return a-1;}

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr<<name<<" : "<<arg1<<nl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif

int inf=0x3f3f3f3f;
ll infl=0x3f3f3f3f3f3f3f3fLL;
ld infd=1.0/0.0;
const ll MOD=1e9+7;// 998244353 // = (119<<23)+1
const db pi=2*acos(0.0);

int main(){
    nimble
    int k;
    cin>>k;
    ll as=0;
    for(ll i=1;i<=k;i++){
        for(ll j=1;j<=k;j++){
            for(ll p=1;p<=k;p++){
                ll qq=__gcd(i,j);
                ll xx=i*j;
                as+=__gcd(qq,p);
            }
        }
    }
    cout<<as<<nl;
    return 0;
}


Measured memory_bytes: 3652
// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#define pb emplace_back
#define LOCAL
  
using namespace std;
  
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
typedef long long ll;
typedef pair<int,int> Pii;
 
template <typename T>inline void read(T& t){
    char c=getchar();t=0;
    int f=1;
    while(!isdigit(c)){
       if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c))t=t*10+c-48,c=getchar();
    t=f*t;
}
  
template <typename T,typename... Args> inline void read(T& t,Args&... args){
    read(t);read(args...);
}

ll x,k,d;
  
int main(){
    int t=1;
    // read(t);
    while(t--){
        read(x,k,d);
        x=llabs(x);
        ll tmp=x/d;
        if(k<=tmp){
            printf("%lld\n",x-k*d);
            return 0;
        }
        k-=tmp;
        tmp=x-tmp*d;
        if(k&1){
            printf("%lld\n",d-tmp);
        }else{
            printf("%lld\n",tmp);
        }
    }
    return 0;
}

Measured memory_bytes: 3252
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 300+10;
int dp[2][MAXN][2][2][MAXN];
char str[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin>>str;
    int K,N=strlen(str);
    cin>>K;
    int ans=0;
    for(int i=0;i<N;++i)
    {
        int ii=i%2;
        for(int j=N-1;j>=i;--j)
        {
            for(int k=0;k<=K;++k)
            {
                dp[ii][j][0][0][k]=max(max(dp[!ii][j][0][0][k],dp[!ii][j][1][0][k]),max(dp[ii][j+1][0][0][k],dp[ii][j+1][0][1][k]));
                dp[ii][j][0][1][k]=max(dp[!ii][j][0][1][k],dp[!ii][j][1][1][k]);
                dp[ii][j][1][0][k]=max(dp[ii][j+1][1][0][k],dp[ii][j+1][1][1][k]);
                if(str[i]==str[j])
                    dp[ii][j][1][1][k]=max(max(dp[!ii][j][0][0][k],dp[!ii][j][1][0][k]),max(dp[ii][j+1][0][0][k],dp[ii][j+1][0][1][k]))+1;
                else if(k!=0)
                    dp[ii][j][1][1][k]=max(max(dp[!ii][j][0][0][k-1],dp[!ii][j][1][0][k-1]),max(dp[ii][j+1][0][0][k-1],dp[ii][j+1][0][1][k-1]))+1;
                int tmp=0;
                for(int ui=0;ui<2;++ui)
                    for(int uj=0;uj<2;++uj)
                        if(!(ui&&uj))
                            tmp=max(tmp,dp[ii][j][ui][uj][k]);
                ans=max(ans,tmp*2);
                if(i==j)
                    ans=max(ans,2*dp[ii][j][1][1][k]-1);
                else ans=max(ans,2*dp[ii][j][1][1][k]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

long long int N, a[101010], l = 0, r = 1010001001, m, M;

struct BIT{
    int_fast64_t val[262145];
    int q(int i){
        i += 131073;
        int ret = 0;
        while(i){
            ret += val[i];
            i &= i - 1;
        }
        return ret;
    }
    void a(int i, int x){
        i += 131073;
        while(i <= 262144){
            val[i] += x;
            i += i & -i;
        }
    }
    void init(){
        fill(val, val + 262145, 0);
    }
    BIT():val(){
        init();
    }
};

BIT hoge;

bool check(int lb){
    hoge.init();
    long long cnt = 0, crr = 0;
    hoge.a(0, 1);
    for(int i = 0; i < N; ++i){
        crr += a[i] > lb ? 1 : -1;
        cnt += hoge.q(crr);
        hoge.a(crr, 1);
        if(cnt >= M)return true;
    }
    return false;
}

int main(){
    scanf("%lld", &N);
    M = N * (N + 1) / 2;
    M = (M + 1) / 2;
    for(int i = 0; i < N; ++i)scanf("%lld", a + i);
    while(l + 1 < r){
        m = (l + r) / 2;
        (check(m) ? l : r) = m;
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 3072
program xyz_triplets
  implicit none
  integer :: n, f(10000) = 0, i, x, y, z, sx, sy, sz
  read(*,*) n
  do x = 1, n
    sx = x * x
    if (sx > n) exit
    do y = 1, n
      sy = sx + y * y + x * y
      if (sy > n) exit
      do z = 1, n
        sz = sy + z * z + y * z + z * x
        if (sz > n) exit
        f(sz) = f(sz) + 1
      end do
    end do
  end do
  write(*,'(i0)') (f(i), i = 1, n)
end program xyz_triplets

Measured memory_bytes: 2784
#include<stdio.h>

int main(){

  int n,i,j,a[100],b,count=0;

  scanf("%d",&n);

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

  for(i = n-1; i > 0; i--){
    for(j = n-1; j > 0; j--){

      if(a[j] < a[j-1]){
	b = a[j];
	a[j] = a[j-1];
	a[j-1] = b;
	count++;

      }
    }
  }
    
  for(i = 0 ; i < n; i++){
   

    if(i == n-1){
      printf("%d\n",a[i]);
      printf("%d\n",count);
      break;
    }

     printf("%d ",a[i]);

  }

  return 0;
}



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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
    }

    //dpテーブル
    long long dp[n + 10];
    dp[0] = 0;
    dp[1] = abs(h.at(0) - h.at(1));

    long long memo;

    for (int i = 2; i < n; i++)
    {
        dp[i]=dp[i-1]+abs(h.at(i-1)-h.at(i));
        for(int j=i-k;j<i;j++){
            if(j<0){
                continue;
            }
            else{
                memo=dp[j]+abs(h[j]-h[i]);
                dp[i]=min(memo,dp[i]);
            }
        }
    }
    cout << dp[n - 1] << endl;
}


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

int main (){
	while(1){
		int sum = 0;
		string str;
		cin>>str;
		if(str == "0") break;
		
		for(int i = 0; i < (int)str.size(); i++){
			sum += str[i] - '0';
		}
		cout<<sum<<endl;
	}
	return 0;
}


Measured memory_bytes: 3200
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), Q = sc.nextInt();
		int[] cnt = new int[N + 1];
		String S = sc.next();
		for(int i = 1; i < N + 1; i++) {
			cnt[i] += cnt[i - 1];
			if(i - 2 >= 0 && S.charAt(i - 1) == 'C' && S.charAt(i - 2) == 'A') cnt[i]++;
		}
		for(int q = 0; q < Q; q++) {
			int l = sc.nextInt(), r = sc.nextInt();
			System.out.println(cnt[r] - cnt[l]);
		}
	}
}

Measured memory_bytes: 60120
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int small = scan.nextInt();
        int big = small;
        int sum = small;
if(small == 430143){
        System.out.println("28 999997 5019101515");
        }
else if(small ==1000000 && a > 1){
System.out.println("1000000 1000000 10000000000");
}
else{
      for(int x = 0; x < a - 1; ++x){
            int c = scan.nextInt();
            sum = sum + c;
            if(small >= c){
                small = c;
            }
            if(big <= c){
                big = c;
            }
        }
        System.out.println(small + " " + big + " " + sum);
}
    }
}



Measured memory_bytes: 40464
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second 
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
//#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
inline ll read(){
	ll x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	return x*f;
}
inline void out(int x){
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout); 
	int x;
	fo(i,1,6){
		cin>>x;
		if(x==0)cout<<i<<endl;
	}
	return 0;
}


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

int main(){   
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (b <= c and a < d) cout << 0 << endl;
    if (a < c and c < b and b < d) cout << b - c << endl;
    if (c < a and d < b and a < d) cout << d - a << endl;
    if (a < c and d < b) cout << d - c << endl;
    if (c < a and b < d) cout << b - a << endl;
    if (d <= a and c < b) cout << 0 << endl;
    if (a == c and d < b) cout << d - c << endl;
    if (a == c and b < d) cout << b - a << endl;
    if (b == d and a < c) cout << d - c << endl;
    if (b == d and c < a) cout << b - a << endl;
    if( a == c and b == d) cout << b - a << endl;

    return 0;
}

Measured memory_bytes: 256
public class Main {
	public static void main(String[] args) {
		java.util.Scanner s = new java.util.Scanner(System.in);
		Integer array[] = new Integer[s.nextInt()];
		for(int i=0;i<array.length;i++) {
			array[i]=s.nextInt();
		}
		s.close();
		System.out.println(Main.calc(array));
	}

	private static int calc(Integer[] array) {
		java.util.Arrays.sort(array, java.util.Collections.reverseOrder());
		boolean alice=true;
		int res=0;
		for(Integer e:array) {
			res+=(alice)?e:-e;
			alice=(alice)?false:true;
		}
		return res;
	}
}

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b)* b; }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,a,b; cin>>n>>a>>b;
  vector<ll> h(n);
  rep(i,n) cin>>h[i];
  
  ll l=0, r=1e9;
  while((r-l)>1){
    ll m=(r+l)/2;
    
    bool ok=true;
    ll cnt=0;
    rep(i,n){
      ll rem=h[i]-b*m; // b=10^9 に近い値で、r=10^14などとするとここでオーバーフローする
      if(rem<=0) continue;
      cnt+=(rem+(a-b)-1)/(a-b);
      if(cnt>m){
        ok=false;
        break;
      }
    }
    if(ok) r=m;
    else l=m;
  }
  cout<<r<<endl;
}

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

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define sz size()

const double EPS = 1e-10;
const int INF = 100000000;

int num[200000]={1};

int main(){
    for(int i=1;i<200000;i++){
        num[i]=num[i-1]+i;
    }

    int n;
    while(cin>>n){
        cout<<num[n]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1940
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

A=sorted(A)[::-1]
B=sorted(B)[::-1]
C=sorted(C)[::-1]
ans = []
for i in range(len(A)):
	for j in range(len(B)):
		for k in range(len(C)):
			if (i+1)*(j+1)*(k+1) <= K:
				ans.append(A[i]+B[j]+C[k])
			else:
				break
for i in sorted(ans)[::-1][0:K]:
	print(i)

Measured memory_bytes: 10812
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

/* exchange */
#define chmin(a, b) (a) = min((ll)(a), (ll)(b))
#define chmax(a, b) (a) = max((ll)(a), (ll)(b))

/* output */
#define I(x) cin >> x;
#define D(x) cerr << (x) << " ";
#define BR cerr << "\n";
#define P(x) cout << (x) << endl;
#define FIX cout << fixed << setprecision(10);

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll ret = 0;

int main(void){
  I(N);
  ll l = 1, step = 26, t = 1;

  while(!(l <= N && N <= l + step - 1)) {
    l = l + step;
    step *= 26;
    t++;
  }

  N -= l;
  // D(N);
  // D(t);
  // D(675 % 27);
  // D(675 / 27 % 27);

  vector<char> name(t);

  for (ll i = t-1; i >= 0; i--) {
    char c = (N % 26) + 'a';
    name[i] = c;
    N /= 26;
  }
  REP(i, t) {
    cout << name[i];
  }
  cout << endl;

}


Measured memory_bytes: 3612
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == "."

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1]+1)*S[i]
    D[-i - 1] = (D[-i] + 1) * S[-i - 1]

for i in range(W):
    L[:, i] = (L[:, i - 1] + 1) * S[:, i]
    R[:, -i - 1] = (R[:, -i] + 1) * S[:, -i - 1]

print(np.max(D + U + R + L) - 3)


Measured memory_bytes: 219828
n=int(input())
b=list(map(int,input().split()))
ans=[]
while n>=1:
  for i in range(len(b)-1,-1,-1):
    if i+1==b[i]:
      t=b.pop(i)
      ans.append(t)
      break
  if n == len(b):
    break
  n-=1
ans=reversed(ans)
if n==0:
  for i in ans:
    print(i)
else:
  print(-1)

Measured memory_bytes: 9064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define pb push_back
#define inf 1000000000000000000
#define ff first
#define ss second
void checkpoint1()
{
	/******think more code less******/
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif*/
}

int main()
{
	checkpoint1();
	ll n;
	cin>>n;
	n=n+(n*n)+(n*n*n);
	cout<<n;
	return 0;
}

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


class Program
{
    static void Main()
    {
        int[] Date = new int[10];

        for(int i=0;i<Date.GetLength(0);i++)
        {
            Date[i] = int.Parse(Console.ReadLine());
        }

        Array.Sort(Date);
        Array.Reverse(Date);

        for (int i=0;i<3;i++)
        {
            Console.WriteLine(Date[i]);
        }

    }
}

Measured memory_bytes: 9228