akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

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


signed main(void) {
    int n,m;
    cin >> n >> m;
    vi a(n);
    rep(i,n)cin >> a[i];
    sort(all(a));
    vp v(m);
    rep(i,m)cin >> v[i].second >> v[i].first;
    sort(all(v));
    reverse(all(v));
    int ind = 0;
    rep(i,m){
        //cout << v[i].first << " " << v[i].second << endl;
        rep(j,v[i].second){
            if(ind < n)a[ind] = max(a[ind],v[i].first),ind++;
            else{
                i = m;
                break;
            }
        }
    }
    int ans = 0;
    rep(i,n)ans += a[i];
    cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
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; }
int INF=1e10;
int MOD=1e9+7;
signed main(){
  int a;
  cin>>a;
  int b=0;
  rep1(i,a)rep1(j,a)rep1(k,a){
  b+=__gcd(i,__gcd(j,k));
  }
  cout<<b<<endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int n,num[200005],dp[200005];
int main() {
	cin>>n;
	for (int i=1;i<=n;i++) cin>>num[i];
	dp[1]=0;
	dp[2]=dp[1]+fabs(num[1]-num[2]);
	for (int i=3;i<=n;i++) 
		dp[i]=min(dp[i-1]+fabs(num[i-1]-num[i]),
		dp[i-2]+fabs(num[i-2]-num[i]));
	cout<<dp[n]<<endl;
	return 0;
} 

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<ll> v(n);
    rep(i,n) cin >> v[i];
    ll ans = 0;
    for(int i = 0; i <= min(n,k); ++i){
        for(int j = 0; j <= min(n-i,k-i); ++j){
            priority_queue<ll> pq;
            ll score = 0;
            rep(l,i){
                score += v[l];
                pq.push(-v[l]);
            }
            rep(l,j){
                score += v[n-1-l];
                pq.push(-v[n-1-l]);
            }
            int rest = k - i - j;
            while(rest > 0 && !pq.empty() && pq.top() > 0){
                score += pq.top();
                pq.pop();
                --rest;
            }
            chmax(ans, score);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
import java.util.*;

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

	class AOJ1166{
		int w,h;
		int tate[][];
		int yoko[][];
		void solve(){
			int[][] memo = new int[h][w];
			for(int i=0;i<h;i++)Arrays.fill(memo[i], Integer.MAX_VALUE);
			memo[0][0] = 0;
			PriorityQueue<State> q = new  PriorityQueue<State>();
			q.add(new State(0, 0, 0));
			int sx[] = {0,1,0,-1};
			int sy[] = {-1,0,1,0};
			int result = -1;
			while(q.size()>0){
				State now = q.remove();
				int x = now.x;
				int y = now.y;
				int cost = now.cost;
				if(x==w-1&&y==h-1){
					result = cost;
					break;
				}
				for(int i=0;i<4;i++){
					int nx = x+sx[i];
					int ny = y+sy[i];
					if(nx<0||nx>=w||ny<0||ny>=h)continue;
					if(i==1){
						if(yoko[ny][x]==1)continue;
					}else if(i==3){
						if(yoko[ny][nx]==1)continue;
					}else if(i==2){
						if(tate[y][nx]==1)continue;
					}else if(i==0){
						if(tate[ny][nx]==1)continue;
					}
					if(memo[ny][nx]<=cost+1)continue;
					q.add(new State(nx, ny, cost+1));
					memo[ny][nx] = cost+1;
				}
			}
//			System.out.println();
//			for(int i=0;i<h;i++){
//				for(int s=0;s<w;s++)System.out.print(memo[i][s]+" ");
//				System.out.println();
//			}
			
			System.out.println(result+1);
		}
		
		void doIt(){
			while(in.hasNext()){
				w = in.nextInt();
				h = in.nextInt();
				if(w+h==0)break;
				yoko = new int[h][w-1];
				tate = new int[h+1][w];
				for(int i=0;i<2*h-1;i++){
					if(i%2==0)for(int s=0;s<w-1;s++)yoko[i/2][s] = in.nextInt();
					else if(i%2==1)for(int s=0;s<w;s++)tate[i/2][s] = in.nextInt();
				}
				
//				for(int i=0;i<h;i++){
//					for(int s=0;s<w-1;s++)System.out.print(yoko[i][s]+" ");
//					System.out.println();
//				}
//				System.out.println();
//				for(int i=0;i<=h;i++){
//					for(int s=0;s<w;s++)System.out.print(tate[i][s]+" ");
//					System.out.println();
//				}
				solve();
			}
		}
		
		class State implements Comparable<State>{
			int x,y,cost;
			public State(int x,int y,int cost) {
				this.x = x;
				this.y = y;
				this.cost = cost;
			}
			public int compareTo(State o) {
				return cost - o.cost;
			}
		}
		
	}

}

Measured memory_bytes: 64080
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define INF 1000000000
ll i,j,k,p;

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

int main(){
    ll a,b;cin>>a>>b;
    ll d=gcd(a,b);

    if(d==1){cout<<a*b<<endl;}
    else{
        a/=d;
        b/=d;
        cout<<a*b*d<<endl;
    }

    
    return 0;
}

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

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e2 + 10;

int Dy[MAX_N][10], N, Nr[MAX_N];
int main() {
	cin >> N; for(int i=1; i<=N; i++) scanf("%d", &Nr[i]);
	for(int i=1; i<=N; i++) {
		for(int j=0; j<10; j++)
			Dy[i][j] = Dy[i-1][j];
		for(int j=0; j<10; j++) if(Dy[i-1][j] % 10 == j)
			Dy[i][(j+Nr[i])%10] = max(Dy[i][(j+Nr[i])%10], Dy[i-1][j] + Nr[i]);
	}
	int ans = 0;
	for(int j=1; j<10; j++) ans = max(Dy[N][j], ans);
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

int main(int argc, char **argv)
{
	ll N, H; cin >> N >> H;
	vector<ll> A(N), B(N);
	for (ll i = 0; i < N; ++i)
		cin >> A[i] >> B[i];

	sort(B.begin(), B.end(), greater<ll>());
	ll amax = *max_element(A.begin(), A.end());
	ll res{0};
	for (ll i = 0; (i < N && H > 0); ++i)
	{
		if (B[i] > amax)
		{
			H -= B[i];
			++res;
		}
		else
			break;
	}

	H = max(0ll, H);
	if (H % amax == 0)
		res += H/amax;
	else
		res += H/amax+1;
	std::cout << res << std::endl;
}


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

using namespace std;
typedef long long ll;

ll c[16], x[20000];

ll dp[20001][256];

int main() {
	while (1) {
		int n, m;
		cin >> n >> m;
		if (n + m == 0)break;
		for (int i = 0; i < m; i++)cin >> c[i];
		for (int i = 0; i < n; i++)cin >> x[i];

		for (int i = 0; i <= 20000; i++)for (int j = 0; j < 256; j++)dp[i][j] = 1e18;
		dp[0][128] = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= 255; j++) {
				for (int k = 0; k < m; k++) {
					ll nxt = 0;
					nxt = j + c[k];
					if (nxt < 0)nxt = 0;
					if (nxt > 255)nxt = 255;
					
					dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j] + (x[i] - nxt) * (x[i] - nxt));
				}
			}
		}
		ll ans = 1e18;

		for (int i = 0; i < 256; i++) {
			ans = min(ans, dp[n][i]);
		}
		cout << ans << endl;

	}

	return 0;
}


Measured memory_bytes: 43236
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Map;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;

class Main {
    static In in = new In();
    static Out out = new Out();
    static long mod = 1000000007;
    static long inf = 0xfffffffffffffffL;

    void solve() {
        int n = in.nextInt();
        Map<String, Integer> map = new TreeMap<>();
        int max = 1;
        for (int i = 0; i < n; i++) {
            String s = in.next();
            if (map.containsKey(s)) {
                max = Math.max(max, map.get(s) + 1);
                map.put(s, map.get(s) + 1);
            } else {
                map.put(s, 1);
            }
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() == max) {
                System.out.println(entry.getKey());
            }
        }
    }

    public static void main(String[]$) {
        new Main().solve();
        out.flush();
    }
}

class In {
    private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    char[][] nextCharArray(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }
}

class Out {
    private static PrintWriter out = new PrintWriter(System.out);

    void println(Object... a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (Object obj : a) {
            joiner.add(String.valueOf(obj));
        }
        out.println(joiner);
    }

    void flush() {
        out.flush();
    }
}


Measured memory_bytes: 63900
#![allow(unused_imports)]
#![allow(dead_code)]
use datastructure::*;
use grapth::*;
use input_scanner::*;
use math::*;
use string_algorithm::*;
use util::*;

use std::cmp;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};

fn main() {
    let mut scan = Scanner::new();
    let n: u64 = scan.next();
    let pf = prime_factor(n);

    let mut ans = 0;
    for (_v, mut c) in pf {
        let mut i = 1;
        while i <= c {
            c -= i;
            i += 1;
        }
        ans += i - 1;
    }

    println!("{}", ans);
}

mod datastructure {}
mod grapth {}
mod math {
    pub fn prime_factor(mut n: u64) -> Vec<(u64, usize)> {
        let mut res: Vec<(u64, usize)> = vec![];
        let mut i: u64 = 2;
        while i * i <= n {
            let mut c: usize = 0;
            while n % i == 0 {
                n /= i;
                c += 1;
            }
            if 0 < c {
                res.push((i, c));
            }
            i += 1;
        }
        if 1 < n {
            res.push((n, 1));
        }
        res
    }
}
mod string_algorithm {}
mod util {}
mod input_scanner {
    pub struct Scanner {
        bytes: Vec<u8>,
        begin: usize,
        end: usize,
    }

    impl Scanner {
        pub fn new() -> Self {
            use std::io::Read;
            let mut buffer: Vec<u8> = Vec::new();
            std::io::stdin().read_to_end(&mut buffer).unwrap();
            let end = (0..buffer.len())
                .find(|i| buffer[*i].is_ascii_whitespace())
                .unwrap_or(buffer.len());
            Scanner {
                bytes: buffer,
                begin: 0,
                end: end,
            }
        }
        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            let s: &str =
                unsafe { std::str::from_utf8_unchecked(&self.bytes[self.begin..self.end]) };
            let ret: T = s.parse::<T>().ok().expect("Parse error.");
            self.skip();
            ret
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
        pub fn next_word(&mut self) -> Vec<u8> {
            let r = Vec::from(&self.bytes[self.begin..self.end]);
            self.skip();
            r
        }
        fn skip(&mut self) {
            self.begin = (self.end..self.bytes.len())
                .find(|i| !self.bytes[*i].is_ascii_whitespace())
                .unwrap_or(self.bytes.len());
            self.end = (self.begin..self.bytes.len())
                .find(|i| self.bytes[*i].is_ascii_whitespace())
                .unwrap_or(self.bytes.len());
        }
    }
}


Measured memory_bytes: 2152
n=input()
count=0
if len(n)==1:
  count=int(n)
if len(n)==2:
  count+=9
if len(n)==3:
    count+=(int(n)//100-1)*100+int(n)%100+10
if len(n)==4:
    count+=909
if len(n)==5:
      count+=(int(n)//10000-1)*10000+int(n)%10000+910
if len(n)==6:
      count+=90909
print(count)

Measured memory_bytes: 3064
import java.util.*;

public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int all = sc.nextInt();
      int leg = sc.nextInt();
      for(int i = 0; i<= all; i++){
      	if(((i*2) + (all-i)*4) == leg){
          System.out.println("Yes");
          return;
        }
      }
      System.out.println("No");
    }
}

Measured memory_bytes: 35740
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt(), x = scanner.nextInt();
		int count = 0;
		for(int i=0;i<=c;i++){
			for(int j=0;j<=b;j++){
				for(int k=0;k<=a;k++){
					int sum = (k * 500) + (j * 100) + (i * 50);
					if(sum > x){
						break;
					}
					if(sum == x){
						count++;
					}
				}
			}
		}
		System.out.println(count);
	}

}


Measured memory_bytes: 21712
from collections import defaultdict
import itertools
N = int(input())
D = defaultdict(int)
for _ in range(N):
    D[input()[0]] += 1
A = ['M','A','R','C','H']
A = list(itertools.combinations(A,3))
ans = 0
for x in A:
    s = 1
    for e in x:
        s *= D[e]
    ans += s
print(ans)

Measured memory_bytes: 3316
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	while(scan.hasNext()) {
	    String input = scan.nextLine();
	    String[] inputs = input.split(" ");
	    int a = Integer.parseInt(inputs[0]);
	    int b = Integer.parseInt(inputs[1]);
	    int d = a / b;
	    int r = a % b;
	    double f = (double)a / (double)b;
	    System.out.println(d + " " + r);
	    System.out.println(String.format("%.5f", f));
	}
    }
}

Measured memory_bytes: 26356
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <map>
#include <set>

using namespace std;

int main() {
    string s;
    cin >> s;
    string divide[4] = {"dream","dreamer","erase","eraser"};
    
    // 対象の文字列を全て逆順にする
    reverse(s.begin(),s.end());
    for(int i = 0; i < 4; i++) {
        reverse(divide[i].begin(),divide[i].end());
    }
    
    //端から考えていく
    bool can = true;
    for(int i = 0; i < s.size();) {
        bool possible = false;
        for(int j = 0; j < 4; j++) {
            string d = divide[j];
            if(s.substr(i,d.size()) == d) {
                possible = true;
                i += d.size();
            }
        }
        if(!possible) {
            can = false;
            break;
        }
    }
    if(can) {
        cout << "YES";
    }else {
        cout << "NO";
    }
    return 0;
}


Measured memory_bytes: 512
from itertools import product
import copy

H, W, K = map(int, input().split())
d = [list(input()) for i in range(H)]

ans = 0
cnt = 0

for Hbit in product([0,1], repeat = H):
    c = copy.deepcopy(d)
    for x,name in enumerate(Hbit):
        if name == 1:
            for j in range(W):
                c[x][j] = "r"
    e = copy.deepcopy(c)
    for Wbit in product([0,1], repeat = W):
        c = copy.deepcopy(e)
        for x,name in enumerate(Wbit):
            if name == 1:
                for j in range(H):
                    c[j][x] = "r"
        
        for i in range(H):
            for j in range(W):
                if c[i][j] == "#":
                    cnt += 1
        
        if cnt == K:
            ans += 1
        
        cnt = 0

print(ans)

#bit全探索
#2^10の例

Measured memory_bytes: 9360
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

n, k = map(int, input().split())

d = []
flags = [0 for i in range(n + 1)]

for i in range(k):
    d.append(int(input()))
    line = list(map(int, input().split()))
    for l in line:
        flags[l] += 1

count = 0
for i in range(1, n + 1):
    if flags[i] == 0:
        count += 1

print(count)


Measured memory_bytes: 68652
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int X=stdIn.nextInt();
		int A[]=new int[N];
		int B[]=new int[N-1];
		int z=0,y=0,x=0;
		long ans=0;
		while(z<N){
			A[z]=stdIn.nextInt();
			z++;
		}z=0;
		while(z<N-1){
			B[z]=A[z]+A[z+1];
			z++;
		}z=0;
		while(z<N-1){
			if(B[z]>X){
				y=B[z]-X;
				if(y>A[z+1]){
					x=y-A[z+1];y=A[z+1];
				}
				A[z]-=x;
				A[z+1]-=y;
				if(z!=N-2)
					B[z+1]-=y;
				ans+=x+y;
			}
			x=0;y=0;z++;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 59972
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int h;
		cin>>h;
		if(h>=m)
		sum++;
	}
	cout<<sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define fix(n) cout<<fixed<<setprecision(n)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const double pi=3.1415926535;

int main(){
  ll n,c,x,y,r=1;
  cin>>n>>c;
  ll a[n];
  rep(i,0,n){
    cin>>a[i];
    a[i]=abs(c-a[i]);
  }
  x=a[0];
  rep(i,0,n-1){
    y=a[i+1];
    while(1){
      if(x%y!=0){r=x%y; x=y; y=r;}
      else{x=y; break;}
    }
  }
  co(x);
  
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
void QuickSort(int arr[],int l,int h)

{

         if(!(l<h))

                   return;

         int m,tmp=arr[l];

         int low=l,high=h;

         while(low<high)

         {

                   while(arr[high]<=tmp&&high>low)high--;

                   if(high>low)

                            arr[low++]=arr[high];

                   while(arr[low]>=tmp&&high>low) low++;

                   if(high>low)

                            arr[high--]=arr[low];

         }

         m=low;

         arr[m]=tmp;

         QuickSort(arr,l,m-1);

         QuickSort(arr,m+1,h);

}

int main()
{
	int i,n,a[101],s=0,min=101;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	QuickSort(a,1,n);
	for(i=1;i<=n;i++)
	{
		if(a[i]<min)
		{
			min=a[i];
			s++;	
		}
	}
	printf("%d",s);
} 

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<bits/stdc++.h>
#define ll long long int
#define hell 1000000007LL
using namespace std;
ll power(ll x, ll y, ll z){ 
    if(y==0)
     return 1;
    else
    {
        ll p=power(x,y/2,z);
        if(y%2==0)
         return (p*p)%z;
        else
        return (x*((p*p)%z))%z;
    }}
ll gcd(ll x,ll y)
{
    if(y==0)
     return x;
    else
    return gcd(y,x%y);
}
ll po(ll x)
{
    ll c=0;
    while(x>0)
    {
        x=x&(x-1);
        c++;
    }
    return c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
    ll n,a,b;
    cin>>n>>a>>b;
    ll x=(n/(a+b))*a;
    if(n%(a+b)<a)
    x=x+n%(a+b);
    else
    x=x+a;
    cout<<x;}

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    ll n,k;cin>>n>>k;
    vector<P> v(n);
    for(int i=0;i<n;i++){
      ll a,b;cin>>a>>b;
      v[i]=P(a,b);
    }
    ll res=0;
    for(int i=0;i<n;i++){
      ll a=v[i].first,b=v[i].second;
      if((k | a) != k) continue;
      res += b;
    }
    for(int i=0;i<30;i++){
      if((k&(1<<i))==0) continue;
      ll num=k>>(i+1);
      num = num<<(i+1);
      num+=(1<<i)-1;
      ll tmp=0;
      for(int j=0;j<n;j++){
        ll a=v[j].first,b=v[j].second;
        if((num | a )!= num) continue;
        tmp += b;
      }
      res=max(res,tmp); 
    }
    cout<<res<<endl;
}


Measured memory_bytes: 1792
import sys, re
import math
import numpy as np
from decimal import Decimal
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul	# 
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd	# 最大公約数
from heapq import heappush, heappop
 
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.maxsize = 10 ** 15
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
# -*- coding: utf-8 -*-
 
n = INT()
 
if n == 0:
    print(1)
else:
    print(0)

Measured memory_bytes: 27288
N = int(input())
dp = [ -1 for x in range(50)]
def fib(n):
    if n == 0 or n == 1:
        dp[n] = 1
        return dp[n]
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib(n-1)+fib(n-2)
    return dp[n]
print(fib(N))


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, k;
    cin >> a >> b >> k;
    for (int x = min(a, b); x >= 1; --x)
    {
        if (a % x == 0 && b % x == 0)
            k--;
        if (k == 0)
            return cout << x, 0;
    }
}


Measured memory_bytes: 256
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

import copy

n=int(input())
root = []
for _ in range(n):
    a = list(map(int,input().split()))
    root.append(a)

flag = True

for i in range(n):
    if root[i][i] != 0:
        flag = False
        break

search_distance = copy.deepcopy(root)

search_distance = warshall_floyd(search_distance)

ans = 0

for i in range(n):
    for j in range(n):
        if search_distance[i][j] != root[i][j]:
            flag = False
            break
        else:
            judge = 1
            for h in range(n):
                if h != i and h != j and root[i][h]+root[h][j] == root[i][j]:
                    judge = -1
            if judge == 1:
                ans += root[i][j]
if flag:
    print(ans//2)
else:
    print(-1)

Measured memory_bytes: 72004
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>v[501];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m,q;
    cin>>n>>m>>q;
    ll l,r;
    while(m--)
    {
        cin>>l>>r;
        v[l].push_back(r);
    }
    for(ll i=1;i<=500;i++)
    {
        sort((v[i].begin()),(v[i].end()));
    }
    //cout<<q<<endl;
    while(q--)
    {
        //cout<<q<<endl;
        cin>>l>>r;
        ll sum=0;
        for(ll i=l;i<=r;i++)
        {
            auto it=upper_bound(v[i].begin(),v[i].end(),r);
            ll num=it-v[i].begin();
            sum+=num;
        }
        cout<<sum<<endl;
    }
	return 0;
}

Measured memory_bytes: 3456
from math import sqrt
from collections import Counter

def prime_factorization(n):
    counter = Counter()
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            counter[i] += 1

    if n != 1:
        counter[n] += 1

    return list(counter.items())

N = int(input())

candinates = []

for p, c in prime_factorization(N):
    # print(p, c)
    i = 1
    while i <= c:
        candinates.append(pow(p, i))
        c -= i
        i += 1


candinates.sort()

# print(candinates)

count = 0
for z in candinates:
    N, r = divmod(N, z)
    if r != 0:
        break
    count += 1

print(count)


Measured memory_bytes: 9508
N,M = map(int, input().split())
A = list(map(int, input().split()))
a = [0]*M
count = 0
weight = 0
while count != N:
    #print("count=",count)
    for i in range(M):
        if N-1 < count:
            count = 0
        a[i] = A[count]
        count += 1 
    sa = max(a) - min (a)
    #print("a=",a," sa=",sa)
    weight += sa
print(weight)


Measured memory_bytes: 5620
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
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;}
ll ceilll(ll a, ll b) {return (a + b-1) / b;} // if(a%b == 0) (a/b) + 1
ll get_digit(ll a) {ll digit = 0; while(a != 0){a /= 10; digit++;} return digit;} // a != 0
template<typename T> void vecdbg(vector<T>& v){ rep(i, v.size()){cout << v[i] << " ";} br;}
template<typename T> void vecvecdbg(vector<vector<T>>& v){ rep(i, v.size()){rep(j, v[i].size()){cout << v[i][j] << " ";} br;}}

// 0 false, 1 true 
// string number to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp
// global vector -> 0 initialization

struct UnionFind
{
    vector<long long> d;
    UnionFind(long long n = 0) : d(n, -1)
    {
    }

    //root : -size, not root: root
    long long root(long long x){
        if(d[x] < 0){
            return x; 
        }
        return d[x] = root(d[x]);
    }

    bool unite(long long x, long long y){
        x = root(x);
        y = root(y);
        if(x == y){
            return false;
        }
        if(d[x] > d[y]){
            swap(x, y);
        }
        d[x] += d[y];
        d[y] = x;
        return true;
    }

    long long size(long long x){
        return -d[root(x)];
    }

    bool issame(long long a, long long b){
        return root(a) == root(b);
    }
};

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n, m; cin >> n >> m;

    UnionFind u(n);

    rep(i, m){
        ll a, b; cin >> a >> b; a--; b--;
        u.unite(a, b);
    }

    ll x = 0;
    rep(i, n){
        //cout << u.root(i) << " " << u.size(i) << endl;
        x = max(x, u.size(i));
    }

    cout << x << endl;



}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  bool boo=true;
  cin >> N;
  vector<long long>vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  for(int i=N-2; i>=0; i--){
    if(vec[i+1] < vec[i]){
      if(vec[i]-1 != vec[i+1]){
        boo=false;
      }
      else{
        vec[i]--;
      }
    }
  }
  if(boo){
    cout << "Yes" << endl;
    return 0;
  }
    cout<<"No"<<endl;
}


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

int main() {
  int N;
  cin >> N;
  //string S;
  int x = 0;
  
  for(int i = 0; i < N; i++){
    string S;
    cin >> S;
    
    if(S == "Y"){
      x++;
      break;
    }
    //else{
      //continue;
    //}
  }
  if(x != 0){
    cout << "Four" << endl;
  }
  else{
    cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

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

        Map<Integer, List<Integer>> graph = new HashMap<>();
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }

        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            List<Integer> edges = graph.get(x);
            edges.add(y);
        }

        Integer[] maxes = new Integer[n+1];
        int maxPath = 0;
        for (int i = 1; i <= n; i++) {
            maxPath = Math.max(maxPath, maxPath(graph, i, maxes));
        }

        System.out.println(maxPath);
    }

    private static int maxPath(Map<Integer, List<Integer>> graph, int i, Integer[] maxes) {
        List<Integer> edges = graph.get(i);
        if(edges == null || edges.isEmpty()) {
            return 0;
        }

        if(maxes[i] != null) {
            return maxes[i];
        }

        int max = 0;
        for (int edge: edges) {
            int path = maxPath(graph, edge, maxes);
            max = Math.max(path, max);
        }

        max++;
        maxes[i] = max;
        return max;
    }

}


Measured memory_bytes: 112816
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
using Pair = System.Tuple<int, int>;
using Edge = System.Tuple<int, int, long>;
//using Debug;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
        Solve();
        //WriteLine(Solve());
    }
    static void Solve()
    {
        var abcedk = Enumerable.Repeat(0, 6).Select(v => Input.num).ToArray();
        if (abcedk[4] - abcedk[0] > abcedk[5]) WriteLine(":(");
        else WriteLine("Yay!");
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read.ToCharArray()).ToArray();
    public static int[][] ar2D(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] arL2D(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 13396
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define MAXN ((int)3e3+5)
#define MOD ((int)1e9 + 7) 
#define ll long long
#define _ << " " <<
#define TRACE(x) cout << #x << " = " << x << endl;
#define pb push_back
#define MP make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vii vector<pi>
#define all(x) x.begin(), x.end()
#define INF (LLONG_MAX-1LL)

ll n,m,t,k;
//     L  ,   R  , turn
ll d[MAXN];
ll dp[MAXN][MAXN][2];

ll rec(ll L, ll R, bool turn)
{
	if(dp[L][R][turn])
		return dp[L][R][turn];
	if(L == R) return dp[L][R][turn] = (d[L] * (1-turn)) + (-d[L])*(turn);

	if(turn) // sira 1 de
	{
		return dp[L][R][turn] = min(
			rec(L+1,R,!turn) - d[L] ,
			rec(L,R-1,!turn) - d[R]
		);
	}
	else
	{
		return dp[L][R][turn] = max(
			rec(L+1,R,!turn) + d[L] ,
			rec(L,R-1,!turn) + d[R]
		);
	} 
	return 0;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> d[i];
	ll ans = rec(0,n-1,0);
	cout << fixed << ans << endl;	
	return 0;
}


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

int main()
{
    int N,i,w[200],l,r=0;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&w[i]);
        r+=w[i];
    }
    l=0;
    for(i=0;i<N;i++){
        if(abs((r-w[i])-(l+w[i]))< abs (l-r)){
            r=r-w[i];
            l=l+w[i];
        }
        else
            break;
    }
    printf("%d\n",abs(r-l));
return 0;
}

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

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

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

/* -----  2019/07/07  Problem: ABC 133 B / Link: http://abc133.contest.atcoder.jp/tasks/abc133_b  ----- */

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vector<vector<int>> a(N, vector<int>(D));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < D; ++j) {
			cin >> a[i][j];
		}
	}
	auto isSquare=[](LL n) {
		LL d = (LL)sqrt(n) - 1;
		while (d*d < n) ++d;
		return d * d == n;
	};
	int ans = 0;
	FOR(i, 0, N) {
		FOR(j, i + 1, N) {
			int sum = 0;
			FOR(d, 0, D) {
				int b = (a[i][d] - a[j][d]);
				sum += b * b;
			}
			if (isSquare(sum))ans++;
		}
	}
	cout << ans << endl;


	return 0;
}




Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
 int main(){
 long long a, b, k;
 cin >> a >> b >> k;
 
 if(k <= a){
 cout << a - k << ' ' << b <<endl;
 }else if(k <= a+b){
 cout << 0 << ' ' << b - (k-a) <<endl;
 }else{
 cout << 0 << ' ' << 0 <<endl;
 }
 }


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	for (;;) {
		int N, M; cin >> N >> M;
		if (N == 0) break;
		vector< vector<short> > a(M, vector<short>(1300));
		int r; cin >> r;
		while (r--) {
			int t, n, m, s; cin >> t >> n >> m >> s;
			m--;
			a[m][t] += (s ? 1 : -1);
		}
		vector< vector<short> > s(M, vector<short>(1300));
		for (int m = 0; m < M; m++)
			for (int t = 1; t < 1300; t++)
				s[m][t] = s[m][t - 1] + a[m][t - 1];
		int q; cin >> q;
		while (q--) {
			int ts, te, m; cin >> ts >> te >> m;
			m--;
			int cnt = 0;
			for (int t = ts + 1; t <= te; t++)
				if (s[m][t]) cnt++;
			cout << cnt << endl;
		}
	}
}

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

int gcd(int x, int y);

const int INF = 1001001001;

/*struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }*/


int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> xy(d, vector<int> (n));
    rep(i, n)rep(j, d) {
        cin >> xy[j][i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int num = 0;
            for (int k = 0; k < d; k++) {
                num += (xy[k][i] - xy[k][j]) * (xy[k][i] - xy[k][j]);
            }
            int i_d = sqrt(num);
            double d_d = sqrt(num);
            if (i_d == d_d)
                ans++;
        }
    }

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

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

Measured memory_bytes: 256
S=int(input())
mod=10**9+7
M=S//3
ans=0

fac=[1,1]
inv_t=[0,1]
finv=[1,1]
for i in range(2,S):
    fac.append(fac[-1]*i%mod)
    inv_t += [inv_t[mod % i] * (mod - mod // i) % mod]
    finv.append(finv[i-1]*inv_t[i]%mod)

def cmb(n,r,mod):
    return (fac[n]*finv[r]*finv[n-r])%mod

for i in range(1,M+1): #i個に分ける
    ans+=cmb(S-3*i+i-1,i-1,mod)
    ans%=mod

print(ans%mod)

Measured memory_bytes: 9304
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=5e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const double PI = acos(-1);

void solve(){
    int n;
    cin>>n;
    int arr[n];
    loop(n,i,0)
        cin>>arr[i];
    int res=0;
    sort(all(arr,n),greater<int>());
    loop(n,i,0){
        if(i%2)
            res-=arr[i];
        else
            res+=arr[i];
    }
    cout<<res<<endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


Measured memory_bytes: 3640
n = int(input())
a = list(map(int, input().split()))
import math
mean = sum(a) / n
smaller = math.floor(mean)
larger = math.ceil(mean)
a_smaller = [(i - smaller) ** 2 for i in a]
a_larger = [(i - larger) ** 2 for i in a]
if sum(a_smaller) <= sum(a_larger) :
    print(sum(a_smaller))
elif sum(a_smaller) > sum(a_larger) :
    print(sum(a_larger))

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int input1,input2;
		int[] roots = new int[n+1];
		Calc calc = new Calc();

		//1行ずつ読み込み
		for(int i=0;i<m;i++) {
			input1 = sc.nextInt();
			input2 = sc.nextInt();
			sc.nextLine();

			if(roots[input1] == 0) {
				if(calc.searchRoot(roots,input2) != input1)
					roots[input1] = input2;
			}else {
				if(roots[input2] == 0) {
					if(calc.searchRoot(roots,input1) != input2)
						roots[input2] = input1;
				}else {
					int root1 = calc.searchRoot(roots,input1);
					if(root1 != calc.searchRoot(roots,input2)) {
						roots[root1] = input2;
					}
				}
			}
		}
		sc.close();

		int count = 0;
		for(int i=1;i<=n;i++) {
			count += (roots[i] == 0) ? 1:0;
		}
		System.out.println(count);
	}
}



class Calc{
	int searchRoot(int[] roots,int x) {
		if(roots[x]==0)
			return x;
		else
			return searchRoot(roots,roots[x]);
	}
}

Measured memory_bytes: 154504
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

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

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> m(n);
    int ans = 0;
    rep(i, n) {
        int mi;
        cin >> mi;
        x -= mi;
        m[i] = mi;
        ans += 1;
    }
    sort(m.begin(), m.end());
    ans += x / m[0];
    cout << ans << endl;
}



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

typedef vector<int> veci;
typedef pair<int, int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9 + 7)
#define fi first
#define se second
#define endl '\n'


void solve() {
    const int INF = int(1e9);
    int h, n;
    cin >> h >> n;

    vecii v(n);
    for (int i=0; i<n; ++i) {
        cin >> v[i].fi >> v[i].se;
    }

    vector<int> dp(h+1,INF);
    dp[0] = 0;

    for (int j=1; j<=h; ++j) {
        for (int i=0; i<n; ++i) {
            int idx = max(0, j - v[i].fi);
            dp[j] = min(dp[j], dp[idx]+v[i].se);
        }
    }
    cout << dp[h] << endl;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST
    (void)argc;
    const string strpath = string(argv[0]) + string("-test.in");
    freopen(strpath.c_str(), "r", stdin);
    int tcs;
    cin >> tcs;
    while (tcs-- > 0)
#endif
        solve();
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 1e18
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define PI (acos(-1))
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
//ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int n,d;
int ball[214514];
vi a,b;

int main(){
	cin>>n;
	rep(i,n){
		int x;
		cin>>x;
		a.pb(x);
	}
	for(int i=n;i>=1;i--){
		int x=a[i-1];
		int res=x;
		for(int j=2;j*i<=n;j++){
			res+=ball[j*i];
			res%=2;
		}
		ball[i]=res;
	}
	vi ans;
	for(int i=1;i<=n;i++){
		if(ball[i]==1)ans.pb(i);
	}
	cout<<ans.size()<<endl;
	if(ans.size()!=0){
		int m=ans.size();
		rep(i,m){
			cout<<ans[i];
			if(i!=m-1){
				cout<<" ";
			}else{
				cout<<endl;
			}
			
		}
	}
}

Measured memory_bytes: 3572
n = int(input())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))

#P=1のとき
D1 = 0
for x, y in zip(X, Y):
  D1 += abs(x-y)
print(D1)

#P=2のとき
D2 = 0
for x, y in zip(X, Y):
  D2 += (abs(x-y))**2
print(D2**(1/2))

#P=3のとき
D3 = 0
for x, y in zip(X, Y):
  D3 += (abs(x-y))**3
print(D3**(1/3))  

#P=∞のとき
D4 = []
for x, y in zip(X, Y):
  D4.append(abs(x-y))
print(max(D4))  


Measured memory_bytes: 5640