akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

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

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

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

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

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
int main(){
  int d[5];
  rep(i,0,5){
    cin>>d[i];
  }
  rep(i,0,5){
    if(d[i]==0){
      cout<<i+1<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define int long long
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
using namespace std;
signed main(){
    string s; cin>>s;
    reverse(all(s));
    int sc=0,tc=0,ans=s.size();
    rep(i,s.size()){
        if(s.at(i)=='T'){
            tc++;
        }if(s.at(i)=='S'){
            if(tc){
                ans-=2;
                tc--;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
typedef long long ll;

int main(){
    string s; cin >> s;
    int q; cin >> q;
    int revflag = 1;
    string s1,s2;
    rep(i,q){
        int query; cin >> query;
        if(query == 1){
            revflag *= -1;
        }
        else if(query == 2){
            int f; cin >> f;
            char c; cin >> c;
            if(revflag == 1){
                if(f == 1){
                    s1 += c;
                }
                else if(f == 2){
                    s2 += c;
                }
            }
            else{
                if(f == 1){
                    s2 += c;
                }
                else if(f == 2){
                    s1 += c;
                }
            }
        }
    }

    if(revflag == 1){
        reverse(s1.begin(),s1.end());
        cout << s1+s+s2 << endl;
    }

    if(revflag == -1){
        reverse(s2.begin(),s2.end());
        reverse(s.begin(),s.end());
        cout << s2+s+s1 << endl;
    }

    return 0;
}


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

int main()
{
  int m, f, r;

  while(1)
  {
    cin >>m >> f >> r;
    if(m == -1 && f == -1 && r == -1) 
    {
      break;
    }
    if(m == -1 || f == -1)
    {
      cout << "F" << endl;
    }else if(m + f >= 80)
    {
      cout << "A" << endl;
    }else if(m + f >= 65)
    {
      cout << "B" << endl;
    }else if(m + f >= 50)
    {
      cout << "C" << endl;
    }else if(m + f >= 30)
    {
      if(r >= 50)
      {
        cout << "C" << endl;
      }else
      {
        cout << "D" << endl;
      }
    }else
    {
      cout << "F" << endl;
    }
  }
}


Measured memory_bytes: 3020
def decrypt(c):
    if ord(c) <= ord('C'):
        return chr(ord(c) - 3 + 26)
    else:
        return chr(ord(c) - 3)


if __name__ == '__main__':
    # ??????????????\???
    # encrypted_txt = 'FURDWLD'
    encrypted_txt = input()

    # ??????????????????
    result = map(decrypt, encrypted_txt)

    # ???????????¨???
    print('{0}'.format(''.join(result)))

Measured memory_bytes: 7496
# 9:46-
require "prime"

N_MAX = 10 ** 5

is_prime = [false] * (N_MAX+1)
is_number_like_2017 = [false] * (N_MAX+1)
Prime.each(N_MAX).each{ |t| is_prime[t] = true }
(1..N_MAX).each{ |i| is_number_like_2017[i] = true if is_prime[i] && is_prime[(i+1)/2] }
f = [0] * (N_MAX+1)
(1..N_MAX).each do |i|
  f[i] = f[i-1]
  f[i] += 1 if is_number_like_2017[i]
end

q = gets.to_s.to_i
q.times do |i|
  l, r = gets.to_s.split.map{|t| t.to_i }
  puts f[r] - f[l-1]
end

Measured memory_bytes: 5272
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long iinf = 1e9;

typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
struct UnionFind
{
    vector<int> data;

    UnionFind(int sz)
    {
        data.assign(sz, -1);
    }

    bool unite(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return (false);
        if (data[x] > data[y])
            swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k)
    {
        if (data[k] < 0)
            return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k)
    {
        return (-data[find(k)]);
    }
};
int main()
{
    ll n, m, k;
    cin >> n >> m >> k;
    ll a[m], b[m], c[k], d[k];
    rp(i, 0, m) cin >> a[i] >> b[i];
    rp(i, 0, k) cin >> c[i] >> d[i];
    set<ll> bf[n];
    UnionFind uf(n);
    rp(i, 0, m)
    {
        bf[a[i] - 1].insert(b[i] - 1);
        bf[b[i] - 1].insert(a[i] - 1);

        uf.unite(a[i] - 1, b[i] - 1);
    }
    rp(i, 0, k)
    {

        if (uf.find(c[i] - 1) == uf.find(d[i] - 1))
        {
            bf[c[i] - 1].insert(d[i] - 1);
            bf[d[i] - 1].insert(c[i] - 1);
        }
    }
    rp(i, 0, n)
    {
        cout << uf.size(i) - bf[i].size() - 1 << " ";
    }
}


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

inline int gi()
{
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    int sum = 0;
    while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

typedef long long ll;
const int maxn = 55, maxm = 105, mod = 1e9 + 7;

int n, m, col, fac[maxm << 1], ifac[maxm << 1];

struct edge
{
    int to, next;
} e[maxm * 2];
int h[maxn], tot;

inline void add(int u, int v)
{
    e[++tot] = (edge) {v, h[u]}, h[u] = tot;
    e[++tot] = (edge) {u, h[v]}; h[v] = tot;
}

int dfn[maxn], low[maxn], Time, top, bccno[maxn], cnt, siz_p[maxn], siz_e[maxn];
pair<int, int> stk[maxm];
vector<int> vec[maxn];

void dfs(int u, int fa)
{
    dfn[u] = low[u] = ++Time;
    for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
        if (v != fa) {
            if (!dfn[v]) {
                stk[++top] = make_pair(u, v);
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    ++cnt;
                    while (1) {
                        int x = stk[top].first, y = stk[top].second;
                        ++siz_e[cnt];
                        if (bccno[x] != cnt) bccno[x] = cnt, ++siz_p[cnt], vec[cnt].push_back(x);
                        if (bccno[y] != cnt) bccno[y] = cnt, ++siz_p[cnt], vec[cnt].push_back(y);
                        --top;
                        if (x == u && y == v) break;
                    }
                }
            } else if (dfn[v] < dfn[u]) stk[++top] = make_pair(u, v), low[u] = min(low[u], dfn[v]);
        }
}

inline int fpow(int x, int k)
{
    int res = 1;
    while (k) {
        if (k & 1) res = (ll)res * x % mod;
        x = (ll)x * x % mod; k >>= 1;
    }
    return res;
}

inline int C(int n, int m)
{
    return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main()
{
    n = gi(); m = gi(); col = gi();
    
    for (int i = 1; i <= m; ++i) add(gi(), gi());

    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) dfs(i, 0);

    fac[0] = ifac[0] = ifac[1] = 1;
    for (int i = 1; i <= m + col; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
    for (int i = 2; i <= m + col; ++i) ifac[i] = (ll)(mod - mod / i) * ifac[mod % i] % mod;
    for (int i = 2; i <= m + col; ++i) ifac[i] = (ll)ifac[i - 1] * ifac[i] % mod;
    
    int ans1 = 1, ans2 = 1, ans3 = 1;
    for (int i = 1; i <= cnt; ++i)
        if (siz_e[i] == 1) ans1 = (ll)ans1 * col % mod;
        else if (siz_e[i] == siz_p[i]) {
            int sum = 0;
            for (int j = 1; j <= siz_e[i]; ++j) {
                sum += fpow(col, __gcd(j, siz_p[i]));
                if (sum >= mod) sum -= mod;
            }
            ans2 = (ll)ans2 * sum % mod * fpow(siz_e[i], mod - 2) % mod;
        } else ans3 = (ll)ans3 * C(siz_e[i] + col - 1, col - 1) % mod;

    printf("%lld\n", (ll)ans1 * ans2 % mod * ans3 % mod);
    //for(int i = 1; i <= m + col; i++) printf("%d %d\n", fac[i], ifac[i]);
    return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  string S; cin >> S;
  vector<int> a;
  vector<int> b;
  bool flag1 = (S[0] == '1');
  int cnt1 = 0, cnt0 = 0;
  REP(i, N){
    if(S[i] == '0'){
      if(flag1 == false){
        cnt0++;
      }else{
        a.push_back(cnt1);
        b.push_back(1);
        cnt1 = 0;
        flag1 = false;
        cnt0++;
      }
    }else{
      if(flag1){
        cnt1++;
      }else{
        a.push_back(cnt0);
        b.push_back(0);
        cnt0 = 0;
        flag1 = true;
        cnt1++;
      }
    }
  }
  if(flag1){
    a.push_back(cnt1);
    b.push_back(1);
  }else{
    a.push_back(cnt0);
    b.push_back(0);
  }
  int ib = -1, ie = -1, c0 = 0, n = b.size();
  REP(i, n){
    if(b[i] == 0 && ib == -1){
      c0++;
      ib = i;
    }else if(b[i] == 0){
      c0++;
      ie = i;
    }
  }
  if(c0 <= K){
    cout << N << endl;
    return 0;
  }
  int tmp = 0;
  for(int i = ib; i <= ib+(K-1)*2; i++){
    tmp += a[i];
  }
  if(ib != 0) tmp += a[0];
  tmp += a[ib+(K-1)*2+1];
  int ans = tmp;
  for(int i = ib+2; i+(K-1)*2 < n; i += 2){
    tmp -= a[i-2];
    if(i > 2) tmp -= a[i-3];
    tmp += a[i+(K-1)*2];
    if(i+(K-1)*2+1 < n) tmp += a[i+(K-1)*2+1];
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

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

using namespace std;

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

    int sum=0;

   for(int i=0;i<n.length();i++){
     sum+=n[i]-'0';
   }


    if(sum%9==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }


    return 0;
}


Measured memory_bytes: 3744
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      long[] a = new long[n+1];
      for(int k = 0; k < n+1; k++){
         a[k] = Long.parseLong(st.nextToken());
      }
      
      st = new StringTokenizer(f.readLine());
      long[] b = new long[n];
      for(int k = 0; k < n; k++){
         b[k] = Long.parseLong(st.nextToken());
      }
      
      long answer = 0L;
      
      for(int k = 0; k < n; k++){
         answer += Math.min(a[k],b[k]);
         b[k] -= Math.min(a[k],b[k]);
         answer += Math.min(a[k+1],b[k]);
         a[k+1] -= Math.min(a[k+1],b[k]);
      }
      
      out.println(answer);
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 43868
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, a[30];
    while(cin >> n, n){
        int sum = 32;
        rep(i,n){
            cin >> a[i];
        }
        int i = 0;
        while(sum){
            sum -= (sum - 1) % 5;
            cout << sum << endl;
            sum-= a[i % n];
            sum = sum < 0 ? 0 : sum;
            cout << sum << endl;
            i++;
        }
    }
}

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

using namespace std;

const int N = 2e5 + 5;

int dp[N][2], n;
string s;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s; memset(dp, 0x3f, sizeof(dp)); s = "#" + s;
    dp[1][0] = (s[1] != '.'), dp[1][1] = (s[1] != '#');
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + (s[i] != '.');
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] != '#');
    }

    cout << min(dp[n][0], dp[n][1]);
    return 0;
}


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

long long MOD=1000000007;
vector<int> ng(64,-1);

int main(){
	int N;
	cin >> N;
	long long dp[N+1][64];
	for(int i=0;i<N+1;i++)for(int j=0;j<64;j++)dp[i][j]=0;
	for(int j=0;j<64;j++)dp[3][j]=1;
	dp[3][6]=0;dp[3][9]=0;dp[3][17]=0;
	
	ng[1]=6;ng[2]=9;ng[8]=33;ng[9]=37;ng[10]=41;ng[11]=45;
	ng[18]=9;ng[34]=9;ng[50]=9;ng[6]=25;ng[14]=57;ng[17]=6;
	ng[33]=6;ng[49]=6;ng[24]=33;ng[40]=33;ng[56]=33;
	
	for(int i=4;i<=N;i++){
		for(int j=0;j<64;j++){
			int p=j/16;
			int q=(j%16)/4;
			int r=j%4;
			int k=q*16+r*4;
			for(int K=0;K<4;K++){
				if(k!=ng[j]){
					dp[i][k]+=dp[i-1][j];
					if(dp[i][k]>=MOD)dp[i][k]-=MOD;
				}
				k++;
			}
		}
	}
	
	long long ans=0;
	for(int j=0;j<64;j++)ans+=dp[N][j];
	ans%=MOD;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var str string
	fmt.Scan(&str)

	n, w, s, e := 0, 0, 0, 0
	for _, ss := range str {
		switch ss {
		case 'N':
			n = 1
		case 'W':
			w = 1
		case 'S':
			s = 1
		case 'E':
			e = 1
		}
	}

	if n^s == 1 || w^e == 1 {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef long double ld;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    char a;
    
    cin >> a;

    if(a>='a') cout << "a" << endl;
    else cout << "A" << endl;

    return 0;
}

Measured memory_bytes: 3588
# -*- coding: utf-8 -*-

s = input().strip()


flag=0
ans=[]
for flag in [0,1]:
    
    calc=0
    for i in range(len(s)):
        if s[i] != str( (i%2 == flag)*1 ):
            calc += 1

    ans += [calc]
    
print(min(ans))


Measured memory_bytes: 3188
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let h: usize = sc.read();
    let w: usize = sc.read();
    let k: usize = sc.read();
    let board: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let n = h + w;
    let mut ans = 0;
    for mask in 0..(1 << n) {
        let mut board = board.clone();
        for i in 0..h {
            if (1 << i) & mask == 0 {
                continue;
            }
            for j in 0..w {
                board[i][j] = 'r';
            }
        }
        for j in 0..w {
            if (1 << (j + h)) & mask == 0 {
                continue;
            }
            for i in 0..h {
                board[i][j] = 'r';
            }
        }

        let count = board
            .into_iter()
            .flat_map(|v| v.into_iter())
            .filter(|&c| c == '#')
            .count();
        if count == k {
            ans += 1;
        }
    }

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

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 2164
#include <iostream>

using namespace std;

int main()
{
    int x;

    cin >> x;

    if (x == 7 || x == 5 || x == 3)
    {
        cout << "YES" << endl;        
    }
    else 
    {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S; 
  cin >> S;
  
  if(S == "SUN") cout << 7 << endl;
  else if(S == "MON") cout << 6 << endl;
  else if(S == "TUE") cout << 5 << endl;  
  else if(S == "WED") cout << 4 << endl;  
  else if(S == "THU") cout << 3 << endl;  
  else if(S == "FRI") cout << 2 << endl;  
  else cout << 1 << endl; 
 
}

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w, k;
  cin >> h >> w >> k;
 // h = 1000, w = 1000, k = 1;
  
  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  sx--;
  sy--;
  gx--;
  gy--;
 //sx = sy = 0, gx = gy = 999;
  
  vector<vector<char>> c(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> c.at(i).at(j);
      //c[i][j] = '.';
    }
  }
  
  vector<vector<int>> d(h, vector<int>(w, 1e9));
  d[sx][sy] = 0;
  queue<tuple<int, int, int>> q; // i, j, dist
  q.push(make_tuple(sx, sy, 0));
  while (!q.empty()) {
    auto [nowx, nowy, dist] = q.front();
    q.pop();
    if (d[nowx][nowy] < dist) continue;
    for (int i = 1; i <= k; i++) { //up
      int nx = nowx - i, ny = nowy;
      if (nx < 0 || c[nx][ny] == '@' || d[nx][ny] <= dist) break;
      else {
        if (d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          q.push(make_tuple(nx, ny, dist + 1));
        }
      }
    }
    for (int i = 1; i <= k; i++) { //down
      int nx = nowx + i, ny = nowy;
      if (nx >= h || c[nx][ny] == '@' || d[nx][ny] <= dist) break;
      else {
        if (d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          q.push(make_tuple(nx, ny, dist + 1));
        }
      }
    }
    for (int j = 1; j <= k; j++) { //left
      int nx = nowx, ny = nowy - j;
      if (ny < 0 || c[nx][ny] == '@' || d[nx][ny] <= dist) break;
      else {
        if (d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          q.push(make_tuple(nx, ny, dist + 1));
        }
      }
    }
    for (int j = 1; j <= k; j++) { //right
      int nx = nowx, ny = nowy + j;
      if (ny >= w || c[nx][ny] == '@' || d[nx][ny] <= dist) break;
      else {
        if (d[nx][ny] > dist + 1) {
          d[nx][ny] = dist + 1;
          q.push(make_tuple(nx, ny, dist + 1));
        }
      }
    }
  }
  
  if (d[gx][gy] == 1e9) cout << -1 << '\n';
  else cout << d[gx][gy] << '\n';
}

Measured memory_bytes: 11980
#include <bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 2 * 1e5 + 15;
const ll M = 1e9 + 7;
vector <ll> v;
int main() {
#ifdef CitricAcid
    freopen ("input.txt", "rt", stdin);
#endif

    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        v.push_back(x);
    }
    sort(v.begin(), v.end());

    ll ans = 1;
    int l = 0, r = n - 1, op = 1;
    if(k & 1) {
        ans = v[r--];
        k--;
        if(ans < 0) op = -1;
    }

    while(k > 0) {
        ll x = v[l] * v[l + 1];
        ll y = v[r] * v[r - 1];

        if(x * op > y * op) {
            ans = x % M * ans % M;
            l += 2;
        }
        else {
            ans = y % M * ans % M;
            r -= 2;
        }

        k -= 2;
    }
    printf("%lld\n", (ans + M) % M);

    

#ifdef CitricAcid
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
/*
# author : CitricAcid
# date : 2020/07/25
*/

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

typedef long long ll;

int N, M, Q;
ll ans = 0;
int A[51], B[51], C[51], D[51];

void dfs(vector<int> v, int cnt, int las) {

  if(cnt==N) {
    ll res = 0;
    for(int i=0; i<Q; ++i) {
      if(v[B[i]]-v[A[i]] == C[i]) res += D[i];
    }
    ans = max(ans, res);
    return;
  }

  for(int i=las; i<M+1; ++i) {
    vector<int> nv = v;
    nv.push_back(i);
    dfs(nv, cnt+1, i);
  }
}

void solve() {

  cin >> N >> M >> Q;
  for(int i=0; i<Q; ++i) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    --A[i];
    --B[i];
  }

  vector<int> v;
  dfs(v, 0, 1);
  cout << ans << endl;

}

int main() {

  solve();

  return 0;
}


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

using namespace std;

#define int long long

const int maxn=2e5;

int n,m,k;

int a[maxn+1],b[maxn+1];

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        cin>>a[i+1];
        a[i+1]+=a[i];
    }
     for(int i=0;i<m;i++){
        cin>>b[i+1];
        b[i+1]+=b[i];
    }
    int ans=0;
    for(int i=0,j=m;i<=n;i++){
        if(a[i]>k)break;
        while(a[i]+b[j]>k)--j;
        ans=max(i+j,ans);
    }
    cout<<ans<<endl;
}


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

int main(){
  long n;  cin >> n;
  vector<long> a(n);
  for(int i=0; i<n; i++)  cin >> a[i];
  sort(a.begin(), a.end());
  int point = 0, len = 0;
  for(int i=0; i<n-1; i++){
    long tmp = min(a[i], a[n-1]-a[i]);
    if(tmp > len){
      len = tmp;
      point = i;
    }
  }

  cout << a[n-1] << " " << a[point] << endl;

  return 0;
}


Measured memory_bytes: 4060
N = int(input())
A = list(map(int, input().split()))




for i in range(N):
    if A[i] % 2 == 0:
        if A[i] % 3 != 0 and A[i] % 5 != 0:
            print('DENIED')
            exit()

else:
    print('APPROVED')

Measured memory_bytes: 9172
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * 10 ** 6
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if w + d > W:
            continue
        D[i + v] = min(DP[i + v], w + d)
    DP = D
ans = 0
for i, d in enumerate(DP):
    if d == float('inf'):
        continue
    ans = i
print(ans)

Measured memory_bytes: 229832
n, m = map(int, input().split())
py = [[i, list(map(int, input().split()))] for i in range(m)]

py = sorted(py, key=lambda x: (x[1][0],x[1][1]))

cnt = 1
prev_p = 0
for i in py:
    p, y = i[1][0], i[1][1]
    if prev_p == p:
        cnt += 1
    else:
        cnt = 1

    ans = str(p).zfill(6) + str(cnt).zfill(6)
    i.append(ans)
    prev_p = p

py = sorted(py, key=lambda x: x[0])
for i in py:
    print(i[2])

Measured memory_bytes: 47572
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
vector<pair<int,int> > v[maxN];
int dp[maxN];
bool ok;
bool seen[maxN];
inline void dfs(int nod)
{
    if(!ok) return;
    seen[nod]=1;
    for(vector<pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        if(!seen[it->first])
        {
            dp[it->first]=dp[nod]+it->second;
            dfs(it->first);
        }
            else
        if(dp[it->first]!=(dp[nod]+it->second))
        {
            ok=0;
            return;
        }
    }
}
int n,m,x,y,z;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,-z});
    }
    ok=1;
    for(int i=1;i<=n;i++)
    {
        if(!seen[i])
        {
            dp[i]=0;
            dfs(i);
        }
        if(!ok)
        {
            printf("No\n");
            return 0;
        }
    }

    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 11008
#!/usr/bin/env python3
#AGC39 A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
k = I()
n = len(s)
res = 0
i = 0
lst = deque()
while i < n:
    tmp = s[i]
    i += 1
    cnt = 1
    while i < n and tmp == s[i]:
        cnt += 1
        i += 1
    lst.append(cnt)
if len(lst) >= 2:
    if s[0] == s[-1] and k >= 2:
        x = lst.popleft()
        y = lst.pop()
        res = 0
        for i in lst:
            res += (i//2)*k
        res += (x//2) + (y//2)
        res += ((x+y)//2)*(k-1)
        print(res)
    else:
        res = 0
        for i in lst:
            res += (i//2)*k
        print(res)
else:
    print((n*k)//2)

Measured memory_bytes: 38588
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  int N; cin >> N;
  vector<vector<ll>> a(N,vector<ll>(N));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      cin >> a[i][j];
    }
  }

  
  vector<ll> gr((1<<N),0);
  for(int i=1;i<N;i++){
    for(int j=0;j<(1<<i);j++){
      for(int k=0;k<i;k++){
        if((j>>k)&1) gr[(1<<i)+j]+=a[i][k];
      }
      gr[(1<<i)+j]+=gr[j];
      //cout << (1<<i)+j << " " << gr[(1<<i)+j] << endl;
    }
  }

  vector<ll> dp((1<<N),-4e11);
  dp[0]=0;
  for(int i=0;i<(1<<N);i++){
    for (int j = ((~i)&((1<<N)-1)); 0<=j; j--){
      j&=((~i)&((1<<N)-1));
      dp[i|j]=max(dp[i|j],dp[i]+gr[j]);
    }
  }
  
  cout << dp[(1<<N)-1] << endl;
  
  return 0;
}


Measured memory_bytes: 1280
PROGRAM piyo
      IMPLICIT NONE
      INTEGER,PARAMETER :: prec = 16
      integer(prec) :: n,i,awtr(4)=0,num = 1
      character(3) :: s
      
      read*,n
      do i = 1,n
        read*,s(1:3)
        
        select case( s )
          case( 'AC ')
            num = 1
          case( 'WA ' )
            num = 2
          case( 'TLE' )
            num = 3
          case( 'RE' )
            num = 4
        end select
        
        awtr(num) = awtr(num) + 1
      end do
      
      print'(a,i0)','AC x ',awtr(1)
      print'(a,i0)','WA x ',awtr(2)
      print'(a,i0)','TLE x ',awtr(3)
      print'(a,i0)','RE x ',awtr(4)
      
      
      
      stop
      !debugg
      
      
      
      END PROGRAM

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

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

keta = 0
goukei = 0

for i in range(m):
  keta += dc_list[i][1]
  goukei += dc_list[i][0] * dc_list[i][1]


print(keta -1 + (goukei-1) // 9)

Measured memory_bytes: 45360
using System;
using System.Collections.Generic;

namespace AtCoder
{
	public class ProblemA
	{
		public static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());

			int[] buttons = new int[n];

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

			int ans = 0;
			int cur = 1;
			HashSet<int> passed = new HashSet<int>();

			do
			{
				if (passed.Contains(cur))
				{
					ans = -1;
					break;
				}

				passed.Add(cur);
				cur = buttons[cur - 1];
				ans++;
			} while (cur != 2);

			Console.WriteLine(ans);
		}
	}
}


Measured memory_bytes: 34876
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(v)";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var x = o.a();
  var y = o.a();
  var z = o.a();
  var K = o.a();
  var a = o.l().sort((a,b)=>b-a);
  var b = o.l().sort((a,b)=>b-a);
  var c = o.l().sort((a,b)=>b-a);
  var ok = 3, ng = a[0]+b[0]+c[0]+1;
  while(ng-ok>1){
    var m = Math.floor((ok+ng)/2);
    if(solve(m))ok = m;
    else ng = m;
  }
  var ans = [];
  for(var i = 0, j = 1, k; i < x; i++){
    if(j === 0)break;
    for(j = 0 , k = 1; j < y; j++){
      if(k === 0)break;
      for(k = 0; k < z; k++){
        var t = a[i]+b[j]+c[k];
        if(t <= ok)break;
        ans.push(t);
      }
    }
  }
  ans.sort((a,b)=>b-a);
  while(ans.length < K)ans.push(ok);
  return ans.join("\n");

  function solve(p){
    var cnt = 0;
    for(var i = 0, j = 1, k; i < x; i++){
      if(j === 0)return;
      for(j = 0, k = 1; j < y; j++){
        if(k === 0)break;
        for(k = 0; k < z; k++){
          if(a[i]+b[j]+c[k] < p)break;
          cnt++;
          if(K === cnt)return true;
        }
      }
    }
  }
}


Measured memory_bytes: 10332
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define ll long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bs binary_search
#define mp make_pair
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ld long double
#define meme(a,no)  memset(a,no,sizeof(a))
using namespace std; 

const int INF=1e9+7;

/*const int N=1000+5;

int x;

//const int mod=998244353;

//const int N=100000+9;

vector<vector<int>>v(N);

int vis[N]={0};

int level[N];*/

long long binpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}

long long binpow_mod(ll a,ll b,ll c){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a%c;
        }
        a=a*a%c;
        b>>=1;
    }
    return res;
}

/*void dfs(int a){
    vis[a]=1;
    for(auto x:v[a]){
        if(!vis[x]){
            sz++;
            dfs(x);
        }
    }
}*/

int32_t main(){
    ios
    int T;
    //cin>>T;
    T=1;
    while(T--){
        int n;
        cin>>n;
        int a[n+1],b[n+1],c[n+1];
        int i,j,k,l;
        for(i=1;i<=n;i++){
            cin>>a[i]>>b[i]>>c[i];
        }
        int mat[3][n+1];
        meme(mat,0);
        mat[0][1]=a[1];
        mat[1][1]=b[1];
        mat[2][1]=c[1];
        for(i=2;i<=n;i++){
            mat[0][i]=max(max(mat[1][i-1]+a[i],mat[2][i-1]+a[i]),mat[0][i-2]+a[i]);
            mat[1][i]=max(max(mat[0][i-1]+b[i],mat[2][i-1]+b[i]),mat[1][i-2]+b[i]);
            mat[2][i]=max(max(mat[0][i-1]+c[i],mat[1][i-1]+c[i]),mat[2][i-2]+c[i]);
        }
        cout<<max(max(mat[0][n],mat[1][n]),mat[2][n])<<endl;
    }
    
    
}

Measured memory_bytes: 8348
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
if N > M:
    N, M = M, N
if N == 1:
    if M == 1:
        answer = 1
    else:
        answer = M - 2
else:
    answer = (N-2) * (M-2)

print(answer)


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

int a[35] = {0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", a[n]);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef dbg
#include "./printer.hpp"
#else
#define dump(x) void(0)
#endif


#define MOD 1000000007
#define INF MOD*MOD
using namespace std;
#define ll long long
inline long  toInt(string s) {long  v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios_base::sync_with_stdio(0);
  ll n,a,b;
  cin >> n >> a >> b;
  ll cnt = 0;
  for(ll i = 0; i < n; i++){
    ll temp;
    cin >> temp;
    if(a <= temp && temp < b){

    }else{
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 256
//author Eterna King
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\in.txt", "r", stdin)
#define FROUT freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\out.txt", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%lld\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 1e5;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const double eps = 1e-7;
const double Pi = acos(-1.0);
il int read_int() {
	char c;
	int ret = 0, sgn = 1;
	do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
	if (c == '-') sgn = -1; else ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
	return sgn * ret;
}
il ll read_ll() {
	char c;
	ll ret = 0, sgn = 1;
	do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
	if (c == '-') sgn = -1; else ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
	return sgn * ret;
}
int n, k;
int main()
{
	cin >> n >> k;
	cout << n - k + 1 << endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (a, b) = readInputLine().split(" ").map { it.toInt() }
    
    if (b % a == 0) {
        println(a + b)
    } else {
        println(b - a)
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37744
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void) {
	int N;
	scanf("%d", &N);
	int ans = 0;
	int i = 0;
	while (1) {
		if (i * i <= N) {
			ans = i * i;
		} else {
			break;
		}
		i++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3844
#include <iostream>

using namespace std;

static const int MAX = 250;

class BinaryHeap {
private:
    int heap[MAX + 1];
    int size;

    void set()
    {
        int value;
        for(int i = 1; i <= size; i++)
        {
            cin >> value;
            heap[i] = value;
        }
    }

public:
    BinaryHeap(int size)
    {
        this->size = size;
        set();
    }

    int parent(int index)
    {
        return index / 2;
    }

    int left(int index)
    {
        return 2 * index;
    }

    int right(int index)
    {
        return 2 * index + 1;
    }

    void print()
    {
        for(int i = 1; i <= size; i++)
        {
            cout << "node " << i << ": key = " << heap[i] << ", ";
            int parent_id = parent(i);
            int left_id = left(i);
            int right_id = right(i);
            if(parent_id <= size && parent_id >= 1)
                cout << "parent key = " << heap[parent_id] << ", ";
            if(left_id <= size && left_id >= 1)
                cout << "left key = " << heap[left_id] << ", ";
            if(right_id <= size && right_id >= 1)
                cout << "right key = " << heap[right_id] << ", ";
            cout << endl;
        }
    }
};

int main()
{
    int H_size;
    cin >> H_size;
    BinaryHeap heap(H_size);
    heap.print();
}


Measured memory_bytes: 3096
#include<bits/stdc++.h> 
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=2011;
#define pii pair<int,int>
#define x first
#define y second
int n,K,len[N];
bitset<N*5> ok[N];
string s[N],ans;
pii f[2][N*20];
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>K;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		len[i]=s[i].size();
	}
	ok[n+1][0]=1;
	for(int i=n;i>0;i--){
		ok[i]=ok[i+1]|(ok[i+1]<<len[i]);
//		cout<<i<<' ';
//		for(int j=0;j<=K;j++){
//			ok[i][j]|=ok[i+1][j];
//			if(j+len[i]<=K)ok[i][j+len[i]]|=ok[i+1][j];
//			printf("%d ",ok[i][j]);
//		}
//		cout<<endl;
	}
	int qcnt=0,tcnt=0;
	for(int i=1;i<=n;i++)
	  if(ok[i+1][K-len[i]])
	    f[1][++qcnt]=pii(i,0);
	for(int t=1;t<=K;t++)
	{
		int i=t&1;
//		cout<<' '<<i<<endl;
		qcnt=min(qcnt,K*2);
//		cout<<qcnt<<"  ";
		char ch='z';
		for(int j=1;j<=qcnt;j++)
		  ch=min(ch,s[f[i][j].x][f[i][j].y]);//cout<<f[i][j].x<<' '<<f[i][j].y<<"  ";
//		cout<<endl;
		ans.push_back(ch);
		int head=n+1;
		for(int j=1;j<=qcnt;j++)
		{
			if(s[f[i][j].x][f[i][j].y]!=ch) continue;
			if(f[i][j].y==len[f[i][j].x]-1)
			  head=min(head,f[i][j].x);
			else
			  f[i^1][++tcnt]=pii(f[i][j].x,f[i][j].y+1);
		}
//		cout<<head<<endl;
		for(int j=head+1;j<=n;j++)
		  if(K-t-len[j]>=0&&ok[j+1][K-t-len[j]])
		    f[i^1][++tcnt]=pii(j,0);
		qcnt=tcnt; tcnt=0;
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N, M;
    cin >> N >> M;
    vector<ll> X(M);
    for (int i = 0; i < M; i++) {
        cin >> X[i];
    }
    sort(all(X));
    ll sum = X.back() - X[0];

    vector<ll> d(M - 1);
    for (int i = 0; i < M - 1; i++) {
        d[i] = X[i + 1] - X[i];
    }
    sort(all(d));
    reverse(all(d));
    for (int i = 0; i < N - 1; i++) {
        if (i >= d.size()) break;
        sum -= d[i];
    }
    cout << sum << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

Measured memory_bytes: 1792
import collections as cl
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=cl.Counter(a)
a_=np.array(list(b.values()))
c=np.sum(a_*(a_-1)/2)
for k in range(n):
    x=b[a[k]]
    if x==2:
        print(int(c-1))
    elif x==1:
        print(int(c))
    else:
        print(int(c-(x-1)))

Measured memory_bytes: 34152
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System;
using System.Collections;
using System.Threading.Tasks.Dataflow;
using System.Runtime.InteropServices.ComTypes;

class Program
{
    #region Reader
    static string ReadStr => Console.ReadLine();
    static string[] ReadStrs => Console.ReadLine().Split(' ');
    static int ReadInt => Convert.ToInt32(Console.ReadLine().Trim());
    static int[] ReadInts => Console.ReadLine().Trim().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
    static long ReadLong => Convert.ToInt64(Console.ReadLine().Trim());
    static long[] ReadLongs => Console.ReadLine().Trim().Split(' ').Select(s => Convert.ToInt64(s)).ToArray();
    #endregion
    #region Method
    const int mod = 1000000007;
    public static int Mod(int a, int mod) { return a % mod >= 0 ? a % mod : a % mod + mod; }
    public static long Mod(long a, long mod = mod) { return a % mod >= 0 ? a % mod : a % mod + mod; }
    #endregion

    static void Main()
    {
        int[] As = ReadInts;

        if(As[0] % As[1] == 0)        WriteLine(As[2]*(As[0]/As[1]));
        else WriteLine(As[2] * (As[0] / As[1]+1));
    }
}



Measured memory_bytes: 28260
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 100005
#define LOG_MAX 20
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)

using namespace std;

inline void inp( int &n ) { 
	n=0;    int ch=getcx();int sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

inline void inp1( LL &n ) { 
	n=0;    LL ch=getcx();LL sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

int main() {
	int a, b;
	cin>>a>>b;
	cout<<a*b<<endl;

    return 0;
}



Measured memory_bytes: 3636
N=int(input())
abcetc=input()
abli=abcetc.split()
abli=[int(s) for s in abli]
ctr=0
while all(i%2==0 for i in abli):
    for i in range(0,N):
        abli[i]=abli[i]/2
    ctr+=1
print(ctr)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, M, K;
vector<int> Ng[100003];
int par[100003]; //親
int tree_rank[100003]; //木の深さ
int siz[100003]; //木の深さ

void init(int n){
  rep(i, n){
    par[i] = i;
    tree_rank[i] = 0;
    siz[i] = 1;
  }
}

// 木の根を求める
int find(int x){
  if (par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (tree_rank[x] < tree_rank[y]) {
    par[x] = y;
    int tmp = siz[x];
    siz[x] += siz[y];
    siz[y] = siz[x];
  }
  else{
    par[y] = x;
    int tmp = siz[x];
    siz[x] += siz[y];
    siz[y] = siz[x];
    if (tree_rank[x] == tree_rank[y]) tree_rank[x]++;
  }
}

// xとyが同じ要素に属するかどうか
bool same(int x, int y){
  return find(x) == find(y);
}

int size(int x) { // 素集合のサイズ
  return siz[find(x)];
}

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

  cin >> N >> M >> K;
  int a, b;
  init(N);
  rep(i, M) {
    cin >> a >> b;
    a--;b--;
    unite(a,b);
    Ng[a].push_back(b);
    Ng[b].push_back(a);
  }
  rep(i, K) {
    cin >> a >> b;
    a--; b--;
    if (same(a, b)) {
      Ng[a].push_back(b);
      Ng[b].push_back(a);
    }
  }
  rep(i, N) cout << size(i) - Ng[i].size() - 1<< ' ';
  cout << "\n";
  return 0;
}

Measured memory_bytes: 8704
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n,T;
  cin>>n>>T;
  int t[n];
  rep(i,n) cin>>t[i];
  ll ans = 0;
  ll last = 0;
  rep(i,n) {
    if(last >= t[i]) {
      ans += T - last + t[i];
      last = t[i] + T;
    } else {
      ans += T;
      last = t[i] + T;
    }
  }
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
    int a,ans,t;
    while(cin>>a)
    {
        ans=0;
        for (int i = 1; i < a; i++)
        {
            if(a%i==0) ans+=(a/i-1);
            else ans+=(a/i);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
	ll n, p[1000001],count=0;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		cin >> p[i];
	}
	for (ll i = 0; i < n; i++) {
		if (i + 1 == p[i]) {
			swap(p[i], p[i + 1]); count++;
		}
	}
	cout << count << endl;
	getchar();
	getchar();
}

Measured memory_bytes: 3072