akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < k; i++) {
            map.put(sc.nextInt(), sc.nextInt());
        }
        int[][][] dp = new int[n + 1][4][4];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int a = 0; a < 4; a++) {
                for (int b = 0; b < 4; b++) {
                    for (int c = 1; c < 4; c++) {
                        if (map.containsKey(i) && map.get(i) != c) {
                            continue;
                        }
                        if (a == b && b == c) {
                            continue;
                        }
                        dp[i][b][c] += dp[i - 1][a][b];
                        dp[i][b][c] %= 10000;
                    }
                }
            }
        }
        int sum = 0;
        for (int a = 0; a < 4; a++) {
            for (int b = 0; b < 4; b++) {
                sum += dp[n][a][b];
                sum %= 10000;
            }
        }
        System.out.println(sum);
    }
}



Measured memory_bytes: 26792
#include<stdio.h>
int main()
{
    int n,t[101],b[101],i,j,st=0,sb,st2=0,s,max=-1;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&t[i]);
        st=st+t[i];
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    st=st+b[n-1];
    for(i=0;i<n;i++)
    {
        st2=st2+t[i];
        sb=st2;
        for(j=i;j<n;j++)
        {
            sb=sb+b[j];
        }
        if(st>sb) s=st;
        else s=sb;
        if(s>max) max=s;
    }
    printf("%d",max);
    return 0;
}


Measured memory_bytes: 128
a, b, k = [int(x) for x in input().split()]
if a<=k:
    k -= a
    a = 0
    if b<=k:
        k -= b
        b = 0
    elif b>k:
        b -= k
        k = 0
else:
    a -= k
    k = 0
print(str(a)+" "+str(b))

Measured memory_bytes: 3064
#include <stdio.h>
int main(){
  int i,n,j,d[101],t;
  
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&d[i]);
  }
  
  
  /* if(d[1]<d[n]){
    for(i=1;i<=n;i++){
      for(j=1;j<=n-1;j++){
       if(d[j]<d[j+1]){
	 t=d[j];
	 d[j]=d[j+1];
          d[j+1]=t;
       }
     }
    }
  }
  
  else if(d[1]>d[n]){
    for(i=1;i<=n;i++){
      for(j=1;j<=n-1;j++){
       if(d[j]>d[j+1]){
	 t=d[j];
	 d[j]=d[j+1];
	 d[j+1]=t;
       }
      }
    }
  }
  */
 
  for(i=n;i>=1;i--){
    if(i==1)printf("%d",d[i]);
    else printf("%d ",d[i]);
  }
  /* for(i=1;i<=n;i++){
    if(i==n)printf("%d",d[i]);
    else printf("%d ",d[i]);
    }*/
  
  
  printf("\n");
  return 0;
}

Measured memory_bytes: 600
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
const A : u8 = 'a' as u8;
fn rec(n : usize,buf : &mut String,s : String, c : u8){
    if s.len() == n {
        buf.push_str(&*s);
        buf.push('\n');
        return;
    }
    for t in A..(c+1) {
        rec(n, buf,format!("{}{}",s,t as char), if t == c { c + 1 } else {c} );
    }
}

fn main() {
    input!{
        n:usize
    }
    let mut buf = String::new();
    rec(n,&mut buf, String::new(), A);
    print!("{}",&buf);
    return;
}



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

#define N_MAX 100

int main() {
    long n, v, deg_out, e;
    cin >> n;

    long G[N_MAX][N_MAX] = {};

    for (long i = 0; i < n; i++) {
        cin >> v >> deg_out;
        for (long j = 0; j < deg_out; j++) {
            cin >> e;
            G[v - 1][e - 1] = 1;
        }
    }

    for (long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            if (j != 0) { cout << " "; }
            cout << G[i][j];
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;




int main()
{
    int N;
    ll x;
    cin >> N >> x;
    vl a(N);
    in(N,a);
    sort(all(a));
    int ans = 0;
    rep(i,N){
        if(x >= a[i]){
            x-=a[i];
            ans++;
            if(i == N-1 && x > 0){
                ans--;
            }
        }else{
            break;
        }
    }
    
    cout << ans << endl;
    
    
    
    

    return 0;
}


Measured memory_bytes: 256
#define _CRT_NONSTDC_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define NL << endl
#define REP(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define Yes cout << "Yes" NL
#define No cout << "No" NL

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int INTMAX = numeric_limits<int>::max();
constexpr int INTMIN = numeric_limits<int>::min();
constexpr ll LLMAX = numeric_limits<long long>::max();
constexpr ll LLMIN = numeric_limits<long long>::min();
constexpr int MOD = 1000000007;



signed main() {
	int N;
	cin >> N;
	string s1, s2;
	cin >> s1 >> s2;

	ll comb = 1;
	int b = 0;
	for (int i = 0; i < s1.size(); i++) {
		if (s1[i] == s2[i]) {
			if (i == 0) comb = comb * 3 % MOD;
			else if (b == 1) comb = comb * 2 % MOD;
			b = 1;
		} else {
			if (i == 0) comb = comb * 6 % MOD;
			else if (b == 1) comb = comb * 2 % MOD;
			else comb = comb * 3 % MOD;
			b = 2;
			i++;
		}
	}

	cout << comb NL;

	return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
	long long mod_exp(int base,int exp,long long mod)
	{
		if(exp<1) return 1;
		if (exp%2) return (base%mod * mod_exp(base,exp-1,mod)%mod)%mod;
		else {
			long long y = mod_exp(base,exp/2,mod)%mod;
			return (y*y)%mod;
		}
	}

	long long exponentiation(int base,int exp)
	{
		if(exp<1) return 1;
			if (exp%2) return base * exponentiation(base,exp-1);
		else {
			long long y = exponentiation(base,exp/2);
			return y*y;
	}
	}

int main(){
	int a ;
	cin >> a;
	long long mod=1e9+7;
	long long res =mod_exp(10,a,mod);
	
	res=res-2*mod_exp(9,a,mod);
	
	while(res<0)res+=mod;
	
	res=(res+mod_exp(8,a,mod))%mod;
	
	cout << res;
	return 0;
}

Measured memory_bytes: 3600
from collections import deque

n,x,y=map(int,input().split())
map=[[] for _ in range(n+1)]
for i in range(1,n):
    map[i].append(i+1)
    map[i+1].append(i)
map[x].append(y)
map[y].append(x)

ans=[0]*n

for j in range(1,n+1):
    dict=[-1]*(n+1)
    que=deque()
    que.append(j)
    dict[j]=0
    while que:
        t=que.popleft()
        for k in map[t]:
            if dict[k]==-1:
                dict[k]=dict[t]+1
                que.append(k)
    for l in range(1,n+1):
        ans[dict[l]]+=1
for m in range(1,n):
    print(ans[m]//2)

Measured memory_bytes: 75024
N = gets.chomp.to_i
d = Array.new(N)
e = Array.new(N,0)
max = 0
str = gets.split
for i in 0...N do
    d[i] = str[i].to_i
    x = d[i]
    max = max < x ? x : max
    e[x] += 1
end
if d[0] != 0 || e[0] != 1
    puts 0
    exit
end
answer = 1
for i in 2..max do
    x = e[i]
    y = e[i-1]
    while x > 0
        answer *= y
        x -= 1
    end
    answer %= 998244353
end
puts answer

Measured memory_bytes: 98216
w,h,n=map(int,input().split())
minx,maxx=0,w
miny,maxy=0,h

for i in range(n):
  x,y,a=map(int,input().split())
  if a==1:
    minx=max(minx,x)
  if a==2:
    maxx=min(maxx,x)
  if a==3:
    miny=max(miny,y)
  if a==4:
    maxy=min(maxy,y)
xx=(maxx-minx)
yy=(maxy-miny)
if xx>0 and yy>0:
  print(xx*yy)
else:
  print(0)

Measured memory_bytes: 9192
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(void) {
    int n;
    int s[1000] = {};
    double m, a;
    
    while(true) {
        m = 0;
        a = 0;
        cin >> n;
        
        if(n == 0)   break;
        
        for(int i = 0; i < n; ++i) {
            cin >> s[i];
            m += s[i];
        }
        m /= n;
        
        for(int i = 0; i < n; ++i) {
            a += (s[i] - m)*(s[i] - m);
        }
        a = sqrt(a / n);
        
        printf("%lf\n", a);
    }
    
    return 0;
}


Measured memory_bytes: 3204
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 1LL << 61;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222



ll a[MAX], dp[MAX];


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



  cin >> n >> m;
  rep(i, m) {
    cin >> tmp;
    a[tmp]++;
  }
  dp[0] = 1;
  rep(i, n + 1) {
    if (a[i]) continue;
    (dp[i + 1] += dp[i]) %= mod;
    (dp[i + 2] += dp[i]) %= mod;
  }
  cout << dp[n] << endl;


  return 0;
}

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

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int a, b;
  cin >> a >> b;
  cout << a * b / 3.305785 << endl;

  return 0;
}


Measured memory_bytes: 3276
#include<stdio.h>
#include<math.h>

int main(){
    int N,A[200000],B[200000],i,j;
    int ANS[200000];
    int M = 0;
    int B_Num = 0;
    int mag = 0;
    scanf("%d",&N);
    
    
    for(i=1;i<=N;i++){
        scanf("%d",&A[i]);
    }
    for(i=N;i>=1;i--){
        mag = N/i;
    
        for(j=2;j<= mag  ;j++){
            
            B_Num += B[j*i];
        }
    
        if(B_Num % 2 == A[i])
            B[i] = 0;
        else{
            B[i] = 1;
            M++;
            ANS[M] = i;
        }
        
        B_Num   =   0;
    }

    printf("%d\n",M);
    for(i = 1 ;i <= M ; i++){
        printf("%d ",ANS[i]);
    }

    
    return 0;
}


Measured memory_bytes: 2944
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.bitmanip;
import std.bigint;

BigInt[] tbl;
static this () {
  tbl = new BigInt[100];
  tbl[0] = BigInt (1);
  foreach (i; 1 .. tbl.length) {
    tbl[i] = tbl[i-1] << 1;
  }
}

BigInt go (const ref BigInt a, int p) {
  BigInt b = a;
  b <<= p;
  b |= a >> p;
  foreach (i; 0 .. p + 1) {
    if ((tbl[i] & a) != 0) {
      b |= tbl[p - i];
    }
  }
  return b;
}

void main() {
  int h, w;
  readf (" %d %d", &h, &w);
  auto a = new int[][](h, w);
  auto b = new int[][](h, w);
  foreach (j; 0 .. h) foreach (i; 0 .. w) {
    readf (" %d", &a[j][i]);
  }
  foreach (j; 0 .. h) foreach (i; 0 .. w) {
    readf (" %d", &b[j][i]);
  }
  int d (int j, int i) {
    return abs (a[j][i] - b[j][i]);
  }
  auto c = new BigInt[w];
  c[0] = BigInt (1);
  c[0] <<= d (0, 0);
  foreach (i; 1 .. w) {
    c[i] = go (c[i-1], d (0, i));  
  }
  foreach (j; 1 .. h) {
    auto e = new BigInt[w];
    e[0] = go (c[0], d (j, 0));
    foreach (i; 1 .. w) {
      int p = d (j, i);
      auto tmp = e[i - 1] | c[i];
      e[i] = go (tmp, p); 
    }
    c = e;
  }
  auto x = c[w - 1];
  foreach (k; 0 .. int.max) {
    if ((x & tbl[0]) != 0) {
      writeln (k);
      break;
    }
    x >>= 1;
  }
}



Measured memory_bytes: 8700
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int N;
    while(cin >> N){
        vector<int> a(N);
        for(auto& t : a) cin >> t;
        sort(a.begin(), a.end());
        vector<pair<int,int>> res;
        for(int i=1;i<a.size()-1;i++){
            if(a[i] < 0){
                res.emplace_back(a.back(), a[i]);
                a.back() -= a[i]; 
            } else {
                res.emplace_back(a[0], a[i]);
                a[0] -= a[i];
            }
        }
        res.emplace_back(a.back(), a[0]);
        cout << a.back() - a[0] << endl;
        for(auto& p : res) cout << p.first << " " << p.second << endl;
    }
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n,k;
  cin >> n >> k;
  if(n>=2*k-1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


x = inp()
if x >= 30:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 68472
N = int(input())
a = list(map(int, input().split()))
a = [0] + a
b = [0 for n in range(N + 1)]

for n in range(N):
    m = N - n
    q = N // m
    r = 0
    for q0 in range(2, q + 1):
        r += b[m * q0] % 2
    b[m] = (a[m] - r) % 2
print(sum(b))
ans = []
for n in range(N):
    m = N - n
    if b[m] == 1:
        ans.append(m)
print(*ans)


Measured memory_bytes: 14124
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
//cout << fixed << setprecision(20) << *** << endl;
#define rep(i,N) for(int i=0;i<(int)N;++i)
typedef long long ll;
using namespace std;
//ユークリッド
ll gcd(ll a,ll b){
	ll t;
	if(a<b){
		t=a;
		a=b;
		b=t;
	}
	if(a%b==0)return b;
	return gcd(b,a%b);
}
//階乗
ll Factorial(ll a){
	ll b=1;
	for(ll i=a;i>=1;i--){
		b=b*i;
	}
	return b;
}
//素数判定
bool prime(ll n){
	for(ll i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return true;
}
int main()
{
	ll N;
	vector<ll>BASE;
	cin>>N;
	rep(i,N){
		ll t;
		cin>>t;
		BASE.push_back(t-1);
	}
	ll sum=0;
	rep(i,N){
		sum=sum+BASE[i];
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
def d(x):
    b, c = 0, 0
    for a in x:
        if b < a:
             b = a
        elif c < a:
             c = a
        else:
             return False
    return True
 
n = int(raw_input())
for i in range(n):
    all = map(int, raw_input().split())
    print "YES" if d(all) else "NO"

Measured memory_bytes: 4204
#include<bits/stdc++.h>
using namespace std;
int main(){
	double w,h,x,y,area;
	cin>>w>>h>>x>>y;
	cout<<(w*h)/2;
	if(x==w/2&&y==h/2){
		cout<<" 1"<<endl;
	}
	else
	cout<<" 0"<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    while(getline(cin,str)){
            while(1){
                if(str.find("the")!=-1||str.find("that")!=-1||str.find("this")!=-1)break;
                for(int i=0;i<str.size();i++){
                    if(str[i]=='.'||str[i]==' '){}
                    else if(str[i]=='a')str[i]='z';
                    else str[i]--;
                }
            }
            cout<<str<<endl;
    }
    return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;

int main() {

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = 1; i < n-1; i++)
	{
		if ((a[i - 1] < a[i] and a[i] < a[i + 1]) or (a[i - 1] > a[i] and a[i] > a[i + 1])) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main () {

int n;
cin>>n;
int maxi=-1;
int br=0;
for (int i=1; i<=n; i++) {
	int a=i;
	int k=0;
	while (a%2==0) {
		a=a/2;
		k++;
	}
	if (k>maxi) {maxi=k; br=i;}
}
cout<<br<<endl;

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    constexpr int INF = 1200001;
    int N, M, X, ans = INF;
    cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        cin >> C[i];
        for (auto& j : A[i]) cin >> j;
    }
    for (int i = 0; i < (1 << N); i++) {
        vector<int> cnt(M, 0);
        int c = 0;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                c += C[j];
                for (int k = 0; k < M; k++) {
                    cnt[k] += A[j][k];
                }
            }
        }
        if (all_of(cnt.begin(), cnt.end(), [X](int x) { return x >= X; }) && c < ans) ans = c;
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

Measured memory_bytes: 3596
#include <stdio.h>          // putchar(), scanf()
#include <string.h>         // strlen()

int
main(int argc, char** argv)
{
	char str[21];
	int i;

	scanf("%s", str);
	for (i = strlen(str) - 1; i >= 0; --i)
		putchar(str[i]);

	putchar('\n');
	return 0;
}

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

using namespace std;

struct query{
    int c, x, u, v, id;
    bool operator < (query q) const{
        return c < q.c;
    }
};

struct edge{
    int e, c, v;
};

int N, Q, B = 315;
vector<edge> graph[100005];
vector<edge> typ[100005];
vector<query> qu;
int dist[100005], clr[100005], wt[100005], dep[100005];
int clrv[100005], clrc[100005];
int par[100005][18];
int ans[100005];

void dfs1(int n){
    for(auto e : graph[n]){
        if(e.e != par[n][0]){
            par[e.e][0] = n;
            dist[e.e] = dist[n] + e.v;
            clr[e.e] = e.c;
            wt[e.e] = e.v;
            dep[e.e] = dep[n] + 1;
            typ[e.c].push_back(e);
            dfs1(e.e);
        }
    }
}

void dfs2(int n, int c){
    if(clr[n] == c){
        clrv[n] += wt[n];
        clrc[n]++;
    }
    for(auto e : graph[n]){
        if(e.e != par[n][0]){
            clrv[e.e] = clrv[n];
            clrc[e.e] = clrc[n];
            dfs2(e.e, c);
        }
    }
}

void build(){
    for(int d = 1; d<17; d++){
        for(int n = 1; n<=N; n++){
            par[n][d] = par[par[n][d-1]][d-1];
        }
    }
}

int lca(int u, int v){
    if(dep[u] < dep[v]){
        swap(u, v);
    }
    for(int d = 16; d>=0; d--){
        if(dep[par[u][d]] >= dep[v]){
            u = par[u][d];
        }
    }
    if(u == v){
        return u;
    }
    for(int d = 16; d>=0; d--){
        if(par[u][d] != par[v][d]){
            u = par[u][d];
            v = par[v][d];
        }
    }
    return par[u][0];
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> Q;
    for(int i = 1; i<N; i++){
        int a, b, c, v;
        cin >> a >> b >> c >> v;
        graph[a].push_back({b, c, v});
        graph[b].push_back({a, c, v});
    }
    dep[1] = 1;
    dfs1(1);
    build();
    for(int q = 1; q<=Q; q++){
        int c, x, u, v;
        cin >> c >> x >> u >> v;
        qu.push_back({c, x, u, v, q});
    }
    sort(qu.begin(), qu.end());
    int crntc = 0;
    for(auto q : qu){
        int top = lca(q.u, q.v);
        ans[q.id] = dist[q.u] + dist[q.v] - 2*dist[top];
        if(typ[q.c].size() <= B){
            for(auto e : typ[q.c]){
                if(dep[e.e] > dep[top] && (lca(e.e, q.u) == e.e || lca(e.e, q.v) == e.e)){
                    ans[q.id] -= wt[e.e];
                    ans[q.id] += q.x;
                }
            }
            continue;
        }
        if(q.c != crntc){
            crntc = q.c;
            dfs2(1, q.c);
        }
        ans[q.id] -= clrv[q.u] + clrv[q.v] - 2*clrv[top];
        ans[q.id] += q.x*(clrc[q.u] + clrc[q.v] - 2*clrc[top]);
    }
    for(int q = 1; q<=Q; q++){
        cout << ans[q] << "\n";
    }
}


Measured memory_bytes: 27696
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

const int maxN = 2e5 + 10, modP = 1e9 + 7;

#define FORU(i, l, r) for (int i = l; i <= r; ++i)
#define FORD(i, r, l) for (int i = r; i >= l; --i)
#define REPU(i, r) for (int i = 0; i < r; ++i)
#define LL long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define PINT pair < int, int >
#define NUM_SET_BIT __builtin_popcountll
#define BIT(x, i) ((x >> i) & 1)

struct cmp {
    bool operator () (PINT a, PINT b) {
        return b.S < a.S;
    }
};

priority_queue < PINT, vector < PINT >, cmp > heap;
LL sum, sum_l, res, reduce[maxN];
vector < PINT > b;
int a[maxN], n, m;

int main() {
    cin >> n >> m;
    FORU(i, 1, n) {
        cin >> a[i];
        if (i != 1) {
            int l = a[i - 1], r = a[i];
            if (l > r) r += m;
            b.PB(MP(l, r));
            sum += (r - l);
        }
    }
    sort(b.begin(), b.end());
    int j = 0;
    FORU(i, 1, m * 2) {
        while (j < b.size() && b[j].F < i) {
            heap.push(b[j]);
            sum_l += b[j].F;
            ++j;
        }
        while (!heap.empty()) {
            auto p = heap.top();
            if (p.S >= i) break;
            heap.pop();
            sum_l -= p.F;
        }
        reduce[i] = 1ll * i * heap.size() - sum_l - heap.size();
    }
    res = -1;
    FORU(i, 1, m) 
        if (res == -1 || res > sum - reduce[i] - reduce[i + m])
            res = sum - reduce[i] - reduce[i + m];
    cout << res;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

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

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
  llong N;
  cin >> N;

  llong ans = inf<llong>;
  for (llong i = 1; i * i <= N; ++i) {
    if (N % i == 0) {
      ans = min(ans, i + N/i - 2);
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
#define MAX (int)1e6 + 5

int N, K, X, Y;

signed main() {
	cin >> N >> K >> X >> Y;
	int cnt = 0; 
	rep(i, N) {
		if (i < K) cnt += X;
		else cnt += Y;
	}
	int ans = cnt;
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
s = input()
ans = True
if s[0]!='A':
    ans = False
if s[2:-1].count('C')!=1:
    ans = False
upper = 0
for i in  s:
    if i.isupper():
        upper += 1

if upper != 2:
    ans = False

if ans:
    print('AC')
else:
    print('WA')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, T;
    cin >> N >> T;
    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];
    vector<int> mi(N), ma(N);
    mi[0] = v[0];
    ma[N-1] = v[N-1];
    for (int i = 0; i < N - 1; i++) mi[i+1] = min(mi[i], v[i+1]);
    for (int i = N - 1; i > 0; i--) ma[i-1] = max(ma[i], v[i-1]);

    int maxD = 0;
    for (int i = 0; i < N-1; i++) { maxD = max(maxD, ma[i+1] - mi[i]); }

    set<int> st;
    for (int i = 0; i < N-1; i++) if (maxD == (ma[i+1] - mi[i])) st.insert(ma[i+1]);
    cout << st.size() << '\n';
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

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

	int N;
	cin>>N;
	vector<long long> a(N);
	vector<long long> pre(N);
	for(int i = 0;i < N;i++) cin>>a[i], pre[i] = a[i] + (i?pre[i-1]:0);
	long long res = LLONG_MAX;
	for(int h = 1;h < N-2;h++) {
		long long f = pre[h];
		long long s = pre[N-1] - pre[h];
		int f1 = upper_bound(pre.begin(),pre.end(),(f+1)/2) - pre.begin()-1;
		int s1 = upper_bound(pre.begin(),pre.end(),pre[h] + (s+1)/2) - pre.begin()-1;
		for(int f2 = f1;f2 < f1 + 2;f2++) {
			if(f2 < 0 || f2 == h) continue;
			for(int s2 = s1;s2 < s1 + 2;s2++) {
				if(s2 <= h || s2 >= N-1) continue;
				long long mn = min(pre[f2],pre[h] - pre[f2]);
				mn = min(mn,min(pre[s2]-pre[h],pre[N-1] - pre[s2]));

				long long mx = max(pre[f2],pre[h] - pre[f2]);
				mx = max(mx,max(pre[s2]-pre[h],pre[N-1] - pre[s2]));
				
//				cerr<<f2<<' '<<h<<' '<<s2<<": "<<mn<<' '<<mx<<'\n';
				res = min(res,mx-mn);
			}
		}
	}
	cout<<res<<'\n';
	return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#include <cmath>
#include <string>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
using namespace std;
//================================================

int a = 0, b = 0, c, d, n, k = 0;
string s, t;



int main()
{
	cin >> s; int sum = 700;
	rep(i, 3)
	{
		if (s[i] == 'o')
			sum += 100;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
  char S[5];
  scanf("%s",&S);
  int i = 0;
  while (S[i])
  {
    if (S[i] == S[i+1])
    {
      printf("Bad");
      return (0);
    }
    i++;
  }
  printf("Good");
}

Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	A, B, X := nextInt(), nextInt(), nextInt()
	if A > X || X-A > B {
		fmt.Println("NO")
	} else {
		fmt.Println("YES")
	}
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


Measured memory_bytes: 640
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<stdio.h>
#include<set>
using namespace std;
int main(){


    int n;
    cin>>n;
    double T,A;
    cin>>T>>A;
    double mi=100000;
    int ans=0;
    
    for(int i=0;i<n;i++){
        int h;
        cin>>h;
       double u=fabs((T-h*0.006)-A);
        if(mi>u){
            ans=i+1;
            mi=u;
        }
    }
    cout<<ans<<endl;
    




return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <queue>
#define rep(i,n) for(int i = 0; i < n ; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef pair<int,int> P;
const int INF = 1000000000;

int main(){
	int N,K,P;
	scanf("%d",&N);
	rep(i,N){
		scanf("%d %d", &K, &P);
		printf("%d\n",K%P==0?P:K%P);
	}
	
	return 0;
}

Measured memory_bytes: 1028
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
};

int main(){
    Stream io;
    
    int T, X;
    io.read(T, X);
    cout << fixed << setprecision(3) << (double)T / X;
    return 0;
}

Measured memory_bytes: 256
void main() {
	auto A = readMatrix!int(3, 3).join.array;
	auto N = ri;
	auto arr2 = new bool[](9);
	foreach(i; 0..N) {
		auto b = ri;
		foreach(j; 0..9) {
			if(A[j] == b) arr2[j] = true;
		}
	}
	auto arr = [
		[0,1,2],
		[3,4,5],
		[6,7,8],
		[0,3,6],
		[1,4,7],
		[2,5,8],
		[0,4,8],
		[2,4,6]
	];
	foreach(v; arr) {
		bool flag = true;
		foreach(k; v) {
			if(!arr2[k]) flag = false;
		}
		if(flag) {
			writeln("Yes");
			return;
		}
	}
	writeln("No");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

const ll MAXN = 200000;

ll N, K, ans=0, tmp=0, tmp2=0, pre=1;
vector<ll> A, B;
string S;

signed main(){
    cin >> N >> K >> S;
    for(int i=0;i<N;i++) {
        if(pre==S[i]-'0') {
            tmp++;
        }
        else {
            A.push_back(tmp);
            pre = 1-pre;
            tmp=1;
        }
    }
    A.push_back(tmp);
    if(pre==0) A.push_back(0);
    /*
    for(int i=0;i<A.size();i+=2) {
        cout << A[i] << endl;
        ans = max(ans, A[i]);
    }
    */
    for(int i=1;i<A.size();i++) {
        A[i] = A[i] + A[i-1];
    }
    for(int i=2*K;i<A.size();i+=2) {
        if(i==2*K) ans = max(ans, A[i]);
        else ans = max(ans, A[i]-A[i-2*K-1]);
    }
    if(2*K>=A.size()) ans = A.back();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1528
import sys
input=sys.stdin.readline
a,b,c,x,y=map(int,input().split())
money1=a*x+b*y
money2=min(x,y)*2*c+(x-min(x,y))*a+(y-min(x,y))*b
money3=max(x,y)*c*2
print(min(money1,money2,money3))

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

typedef long long ll;

int main() {

  ll n;
  cin >> n;

  ll ans = 0;

  for(ll i=1; i<n; ++i) {
    ll tmp = n/i;
    if(n%i==0) --tmp;
    ans += tmp;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3488
N,K = map(int,input().split())
A = list(map(int,input().split()))
check = [-1]*N
cnt = 0
check[0] = cnt
index = A[0]

while True:
    if check[index-1] != -1:
        break
    cnt += 1
    if K-1 == cnt:
        print(A[index-1])
        exit()
    check[index-1] = cnt
    index = A[index-1]

length = cnt - check[index-1] + 1
K -= (len(A) - check.count(-1) -length)
l = []
for _ in range(length):
    l.append(A[index-1])
    index = A[index-1]
ans = K % len(l)
print(l[ans-1])

Measured memory_bytes: 32384
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define maxs(x,y) x = max(x, y)
#define mins(x,y) x = min(x, y)
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int N;
    cin >> N;
    
    REP(i, 50001) {
        if (i * 108 /100 == N) {
            cout << i << endl;
            return 0;
        } 
    }

    cout << ":(" << endl;
    

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

Measured memory_bytes: 256
from collections import deque

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

sx=0
gx=n-1

tree=[[] for i in range(n)]
for i in l:
    tree[i[0]-1].append(i[1]-1)
    tree[i[1]-1].append(i[0]-1)

dist=[-1 for i in range(n)]
dist[sx]=0

que=deque()
que.append(sx)

while que:
    x=que.popleft()

    if x==gx and dist[gx]==2:
        print('POSSIBLE')
        exit()
    elif x==gx and dist[gx]!=2:
        print('IMPOSSIBLE')
        exit()

    for j in tree[x]:
        if dist[j]==-1:
            que.append(j)
            dist[j]=dist[x]+1

print('IMPOSSIBLE')

Measured memory_bytes: 81584
#include <bits/stdc++.h>
#include<assert.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = b - 1; i >= a; i--)
#define int ll
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

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

signed main() {
    int n;
    cin >> n;
    int a[n];
    rep(i, 0, n) cin >> a[i];
    bool p = 1, s = 1;

    set<int> st;
    rep(i, 0, n) {
        int q = a[i];
        for (int j = 2; j * j <= q; j++) {
            if (q % j == 0) {
                //if (*st.find(j) == j) {
                if(st.count(j)>0){
                    p = 0;
                    break;
                }
                st.insert(j);
                while (q % j == 0) {
                    q /= j;
                }
            }
        }
        assert(q>=1);
        if (q != 1) {
            //assert((*st.find(q)==q)==(st.count(q)>0));
            //if (*st.find(q) == q) p = 0;
            //if(st.count(q)>0)p=0;
            if(st.find(q)!=st.end())p=0;
        }
        st.insert(q);
        if (!p) break;
    }

    // for (auto p : st) cout << p << " ";

    int now = a[0];
    rep(i, 0, n) { now = gcd(now, a[i]); }
    if (now != 1) s = 0;

    if (p) {
        cout << "pairwise coprime\n";
    } else if (s) {
        cout << "setwise coprime\n";
    } else {
        cout << "not coprime\n";
    }
}


Measured memory_bytes: 11372
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<limits>
#include<deque>
#include<string>
#include<map>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>

using namespace std;

int main(){
	long long int n; cin >> n;
	long long int k; cin >> k;
	int a[n], b[n];
	map<int, long long int> mp;

	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		mp[a[i]] += b[i];
	}

	for (pair<int, long long int> x : mp) {
		k -= x.second;
		if (k <= 0) { cout << x.first << endl; break; }
	}

	return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> des(m);
  for (int i=0; i<m; ++i) cin >> des.at(i);
  
  sort(des.begin(), des.end());
  vector<int> dif(m-1);
  for (int i=0; i<m-1; ++i) {
    dif.at(i) = des.at(i+1) - des.at(i);
  }
  sort(dif.begin(), dif.end());
  int res = 0;
  for (int i=0; i<m-n; ++i) {
    res += dif.at(i);
  }
  cout << res << endl;
  return 0;
}


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

using namespace std;

/*
1   1   1   1   1
1   2   3   4   5
1   3   6   10  15
1   4   10  20  35

右にB回進むまでの間に、
下に0〜(H-A-1)回進める
*/

// MOD逆元 非再帰拡張ユークリッド
long modinv(long a){long M=MOD,b=M,u=1,v=0;while(b)u-=a/b*v,swap(u,v),a%=b,swap(a,b);return (u%M+M)%M;}

vector<long> kaijou(200010);

// all個からchoice個選ぶ組み合わせ
long comb(long n, long r) {
  long ret = kaijou[n];
  ret *= modinv(kaijou[n-r]);
  ret %= MOD;
  ret *= modinv(kaijou[r]);
  ret %= MOD;
  return ret;
}

void solve() {
  long H, W, A, B;
  cin >> H >> W >> A >> B;

  kaijou[0] = 1;
  for (long i = 1; i < 200010; i++) kaijou[i] = (kaijou[i-1] * i) % MOD;

  long ans = 0;

  for (long i = 0; i <= H-A-1; i++) {
    long before = comb(B - 1 + i, i);
    long after = comb(W - B - 1 + H - 1 - i, H - 1 - i);
    ans += before * after;
    ans %= MOD;
  }

  cout << ans << endl;
}

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


Measured memory_bytes: 1792
import string
INF = 1 << 30

def conv(base, num):
    ret = 0
    for n in str(num):
        if n in string.ascii_letters:
            n = ord(n) - ord("A") + 10
        else:
            n = int(n)
        ret = ret * base + n
    return ret

def get_fact(n):
    ret = []
    for i in xrange(2, n + 1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n /= i
        if cnt != 0:
            ret.append((i, cnt))
    return ret

while True:
    base, num = raw_input().split()
    if (base, num) == ("0", "0"):
        break
    base = int(base)
    num = conv(base, num)
    fact = get_fact(base)
    ans = [] #tmp
    for f,n in fact:
        ff = f
        cnt = 0
        while ff <= num:
            cnt += num / ff
            ff *= f
        ans.append(cnt / n)
    print min(ans)

Measured memory_bytes: 4396
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cmath>
#include <functional>
#include <set>
#include <string>
#include <stdlib.h>
#include <iomanip>
#include <utility>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define ii pair<int,int>
#define mp make_pair
#define pb push_back
#define iii pair<ii,int >
#define ff first
#define ss second
#define vi vector<int>
#define vc vector<char>
 
using namespace std;

ll* pref;
ll* arr;
const ll MOD = 1000000007;
const int MAXN = 401;
const ll INF = (ll)1e18;
ll dp[401][401];

inline ll cost(int left,int right){
	return (pref[right] - ((left>0)?pref[left-1]:0) );
}

ll DP(int left,int right){
	if(left == right){
		return 0;
	}
	if(dp[left][right] != -1)return dp[left][right];
	ll mnCST = INF;
	FORE(i,left,right-1){
		mnCST = min(mnCST,DP(left,i) + DP(i+1,right) + cost(left,right));
		
		//if(mnCST != INF)mnCST %= MOD;
	}

	dp[left][right] = mnCST;
	return mnCST;
}


int main(){
	int n;
	cin >> n;
	arr = new ll[n];
	pref = new ll[n];
	FOR(i,n)cin >> arr[i];
	pref[0] = arr[0];
	FOR(i,n){
		if(i == 0)continue;
		pref[i] = pref[i-1] + arr[i];
		//pref[i] %= MOD;
	}
	//FOR(i,n)cout << pref[i] << " ";cout << endl;
	//cout << cost(0,1) << endl;
	FOR(i,MAXN){
		FOR(j,MAXN){
			dp[i][j] = -1;
		}
	}	
	ll ans = DP(0,n-1);
	//ans %= MOD;
	FOR(i,n){
		FOR(j,n){
		//	cout << "left : " << i << " :: right : " << j << " :::: " << dp[i][j] << endl;
		}
	}

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


Measured memory_bytes: 1536
use std::fmt::Debug;
use std::str::FromStr;

pub struct TokenReader {
    reader: std::io::Stdin,
    tokens: Vec<String>,
    index: usize,
}

impl TokenReader {
    pub fn new() -> Self {
        Self {
            reader: std::io::stdin(),
            tokens: Vec::new(),
            index: 0,
        }
    }

    pub fn next<T>(&mut self) -> T
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index += 1;
        self.tokens[self.index - 1].parse().unwrap()
    }

    pub fn vector<T>(&mut self) -> Vec<T>
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index = self.tokens.len();
        self.tokens.iter().map(|tok| tok.parse().unwrap()).collect()
    }

    pub fn load_next_line(&mut self) {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();

        self.tokens = line
            .split_whitespace()
            .map(String::from)
            .collect();
        self.index = 0;
    }
}

fn solve(s: &Vec<char>) -> usize {
    let rs = s.iter().filter(|&ch| *ch == 'R').count();
    let mut mistakes = 0;

    for i in 0..s.len() {
        if i < rs && s[i] != 'R' {
            mistakes += 1;
        } else if i >= rs && s[i] == 'R' {
            mistakes += 1;
        }
    }
    (mistakes + 1) / 2
}

fn main() {
    let mut reader = TokenReader::new();
    let _ = reader.next::<usize>();
    let s = reader.next::<String>().chars().collect();

    let res = solve(&s);
    println!("{}", res);
}


Measured memory_bytes: 3280
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>>&g,vector<bool>&visited,vector<int>&dp,int i)
{
    visited[i]=true;
    for(auto edge:g[i])
    {
        if(!visited[edge])
            dfs(g,visited,dp,edge);
        dp[i]=max(dp[i],dp[edge]+1);
    }
}
int main() {
    int m,n;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    for(int i=0;i<m;i++)
    {
       int u,v;
       cin>>u>>v;
       g[u].push_back(v);
    }
    vector<int>dp(n+1,0);
    vector<bool>visited(n+1,false);
    for(int i=1;i<=n;i++)
    {
        if(!visited[i])
            dfs(g,visited,dp,i);
    }
    int ans = 0; 
    for (int i = 1; i <= n; i++) { 
        ans = max(ans, dp[i]); 
    } 
    cout<<ans;
    return 0;
}


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

int main()
{
  int h, w ,k;
  cin >> h >> w >> k;
  string s[h];
  for(int i = 0 ; i<h;++i){
    cin >> s[i];
  }
  int hc[h];
  int wc[w];
  int f = 1;
  for(int i = 0 ; i<h;++i){
    hc[i]=f;
    f*=2;
  }
  f = 1;
  for(int i = 0 ; i<w;++i){
    wc[i]=f;
    f*=2;
  }
  int black = 0;
  int count = 0;
  for(int i = 0 ; i<(hc[h-1]*2);++i){
    for(int j = 0 ; j<(wc[w-1]*2);++j){
      black = 0;
      for(int k = 0 ; k < h;++k){
        for(int l = 0 ; l < w;++l){
          if(((i & hc[k]) == 0)&&((j & wc[l]) == 0)) {
            if(s[k][l] == '#') black++;
          }
        }
      }
      //cout <<  black << endl;
      if(black == k) count++;
    }
  }
  
  cout << count << endl;
}


Measured memory_bytes: 3628