akhauriyash/Code-Regression huggingface dataset:
h,w,k=map(int,input().split())
s=[[int(j) for j in input()] for i in range(h)]
def popcount(x):
    global h
    ret=0
    for i in range(h-1):
        ret+=(x>>i&1)
    return ret
#できない場合は除く
ans=1000000000000000
for i in range(2**(h-1)):
    p=popcount(i)
    div=[0]*(p+1)
    ans_sub=p
    f=False
    for j in range(w):
        now=0
        div[now]+=s[0][j]
        for l in range(h-1):
            if i>>l&1:
                now+=1
            div[now]+=s[l+1][j]
        if all(i<=k for i in div):
            continue
        else:
            div=[0]*(p+1)
            now=0
            div[now]=s[0][j]
            for l in range(h-1):
                if i>>l&1:
                    now+=1
                div[now]+=s[l+1][j]
            ans_sub+=1
            f=any(i>k for i in div)
    if not f:ans=min(ans,ans_sub)
print(ans)

Measured memory_bytes: 75872
n, m = [int(x) for x in input().split(' ')]
lr = [(int(l), int(r)) for l, r in [input().split(' ') for _ in range(m)]]

l = max([x[0] for x in lr])
r = min([x[1] for x in lr])

print(r-l+1 if l <= r else 0)


Measured memory_bytes: 45792
#include<stdio.h>
int main()
{
	int N, T;
	scanf("%d %d", &N, &T);
	int i;
	int min = 2000;
	int c, t;

	for ( i = 0; i < N; i++)
	{
		scanf("%d %d", &c, &t);
		if (t <= T&&c < min)
			min = c;
	}
	if (min == 2000)
		printf("TLE");
	else
		printf("%d", min);
	return 0;
}

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


int main(){
  
  int n, i = 1, evens = 0;
  scanf("%d",&n);
  
  while(n >= i){
    if(((int)log10(i)%2) == 0)
      evens++;
    i++;
  }
  
  printf("%d",evens);
  
  return 0;
  
  
}

Measured memory_bytes: 128
import java.util.*;

class ProblemC{
  int[] d = null;//sからの最短経路
  ArrayList<ArrayList<Edge>> g = new ArrayList<ArrayList<Edge>>();
  int inf = 1000000000;

  void solve(){
    Scanner scan = new Scanner(System.in);
    int v = scan.nextInt();
    int e = scan.nextInt();
    int r = scan.nextInt();

    d = new int[v];

    for(int i=0 ; i<v ; ++i){
      g.add(new ArrayList<Edge>());
    }

    for(int i=0 ; i<e ; ++i){
      int s = scan.nextInt();
      int t = scan.nextInt();
      int d = scan.nextInt();
      g.get(s).add(new Edge(t, d));
    }

    dijkstra(r, v);

    for(int i=0 ; i<d.length ; ++i){
      if(d[i] == inf) System.out.println("INF");
      else System.out.println(d[i]);
    }

  }

  void dijkstra(int r, int vn){
    PriorityQueue<IntPair> que = new PriorityQueue<IntPair>();
    for(int i=0 ; i<vn ; ++i) d[i] = inf;
    d[r] = 0;
    que.add(new IntPair(0, r));
    while(!que.isEmpty()){
      IntPair p = que.poll();//IntPair(Key:頂点番号, Value:最短距離)
      int v = p.value;//頂点番号
      if(d[v] < p.key) continue;
      for(int i=0 ; i<g.get(v).size() ; ++i){

        Edge e = g.get(v).get(i);
        if(d[e.to] > d[v] + e.cost){
          d[e.to] = d[v] + e.cost;
          que.add(new IntPair(d[e.to], e.to));
        }
      }
    }//----end of while----
  }//----end of dijkstra----
}

class IntPair implements Comparable<IntPair>{
  public int key;
  public int value;

  IntPair(int key, int value){
    this.key = key;
    this.value = value;
  }

  public int compareTo(IntPair other){
    if(key < other.key) return -1;
    if(key > other.key) return 1;

    if(value < other.key) return -1;
    if(value > other.key) return 1;

    return 0;
  }
}

class Edge{
  int to = 0;
  int cost = 0;

  Edge(int to, int cost){
    this.to = to;
    this.cost = cost;
  }
}


public class Main{
  public static void main(String[] args){
    new ProblemC().solve();
  }
}



Measured memory_bytes: 326644
def main():
    a, b, c, k = [int(x) for x in input().split()]
    ans = 0
    # 1
    if a >= k:
        ans += k
        k -= k
    else:
        ans += a
        k -= a
    # 0
    if b >= k:
        k -= k
    else:
        k -= b
    # -1
    ans -= k
    return ans


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 9180
#include <stdio.h>
#include <string.h>

char a[1024][80];
int ap;

void reverse(char *s, int n)
{
    int i;
    for(i=0;i<n/2;++i) {
        char t=s[i];
        s[i]=s[n-1-i];
        s[n-1-i]=t;
    }
}
void swap(char *s1, char *s2)
{
    int i=0;
    char t[80], *p;
    for(p=s2;*p;++p) t[i++]=*p;
    for(p=s1;p!=s2;++p) t[i++]=*p;
    t[i]=0;
    strcpy(s1, t);
}
int contain(char* s)
{
    int i;
    for(i=0;i<ap;++i) if (!strcmp(a[i], s)) return 1;
    return 0;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    while (n--) {
        int i, len;
        char s[80], t[80];
        scanf("%s", s);

        ap=0;
        len=strlen(s);
        strcpy(t, s);
        for(i=1;i<len;++i) {
            if (!contain(s)) strcpy(a[ap++], s);
            reverse(s, i); if (!contain(s)) strcpy(a[ap++], s);
            reverse(s+i, len-i); if (!contain(s)) strcpy(a[ap++], s);
            reverse(s, i); if (!contain(s)) strcpy(a[ap++], s);
            strcpy(s, t);
            swap(s, s+i);
            if (!contain(s)) strcpy(a[ap++], s);
            reverse(s, len-i); if (!contain(s)) strcpy(a[ap++], s);
            reverse(s+len-i, i); if (!contain(s)) strcpy(a[ap++], s);
            reverse(s, len-i); if (!contain(s)) strcpy(a[ap++], s);
            strcpy(s, t);
        }
        printf("%d\n", ap);
    }
    return 0;
}

Measured memory_bytes: 660
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) ll aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) string aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
		
		int H,W;
		cin>>H>>W;
		vecs(A)
		fx(H){
			vecps(A)
		}
		int ans=0;
		fx(H){
			fy(W){
				if(A.at(x).at(y)=='#'){
				    ans++;
					int black=0;
					if(x-1>=0&&A.at(x-1).at(y)=='#'){black++;}
					if(x+1<H&&A.at(x+1).at(y)=='#'){black++;}
					if(y+1<W&&A.at(x).at(y+1)=='#'){black++;}
					if(y-1>=0&&A.at(x).at(y-1)=='#'){black++;}
					if(black!=2){ans+=100;}
				}
			}
		}
		
		if(ans==H+W+199){
			ce("Possible")
		}else{
			ce("Impossible")
		}
		
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
signed main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int ans=-1e19;
	vector<int>a1,b1;
	if (a!=0) a1.pb(a);
	if (b!=0) a1.pb(b);
	if (a<=0 && b>=0)  ans=0;
	if (c!=0) b1.pb(c);
	if (d!=0) b1.pb(d);
	if (c<=0 && d>=0)  ans=0;
	for (int i:a1)
		for (int j:b1)
			ans=max(ans,i*j);
	cout<<ans;
	re 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main()
{
  char w[200];
  scanf("%s", w);

  int cnt[500] = {};
  int len = strlen(w);
  rep(i, len) {
    cnt[w[i]]++;
  }

  bool isOK = true;
  rep(i, len) {
    if( cnt[w[i]] % 2 != 0 ) {
      isOK = false;
      break;
    }
  }

  if( isOK ) puts("Yes");
  else puts("No");

  return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=0
for i in range(n-1,-1,-1):
  if a[i+1]>=b[i]:
    a[i+1]-=b[i]
    s+=b[i]
    continue
  elif a[i+1]<=b[i]<=a[i]+a[i+1]:
    s+=b[i]
    a[i]=a[i]+a[i+1]-b[i]
    continue
  elif b[i]>=a[i]+a[i+1]:
    s+=a[i]+a[i+1]
    a[i]=0
    continue
print(s)

Measured memory_bytes: 19004
#include<stdio.h>

#define N 8
#define FREE -1
#define NOT_FREE 1

void putQueen(int);
void printboard();
void free();
int n,k;

int row[N],col[N],dpos[2*N-1],dneg[2*N-1];
int X[N][N];

int main(){
  int i,r,c,j;

  free();

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=-1;
    }
  }

  scanf("%d",&k);

  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    X[r][c]=1;
  }

  putQueen(0);

return 0;
}

void free(){
  int i;
  for(i=0;i<N;i++){
    row[i]=FREE;
    col[i]=FREE;
  }

  for(i=0;i<2*N-1;i++){
    dpos[i]=FREE;
    dneg[i]=FREE;
  }
}

void putQueen(int i){
  int j;
  if(i==N){
    printboard();
    return;
  }

  for(j=0;j<N;j++){
    if((col[j]==NOT_FREE)||(dpos[i+j]==NOT_FREE)||(dneg[i-j+N-1]==NOT_FREE)){
      continue;
    }
    row[i]=j;
    col[j]=NOT_FREE;
    dpos[i+j]=NOT_FREE;
    dneg[i-j+N-1]=NOT_FREE;
    putQueen(i+1);
    col[j]=FREE;
    dpos[i+j]=FREE;
    dneg[i-j+N-1]=FREE;
   }
}

void printboard(){
  int i,j;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(X[i][j]==1){
        if(row[i]!=j){
          return;
        }
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j){
        printf("Q");
      }
      else{
        printf(".");
      }
    }
    printf("\n");
  }
}



Measured memory_bytes: 2112
#include<iostream>
#include<cmath>

using namespace std;
 
long long power(long long m, long long n, long long M){
  long long tmp = 1;
 
  if ( n > 0 )
  {
    tmp = power(m, n/2, M);
    if ( n%2 == 0 ) tmp = (tmp*tmp)%M;
    else tmp = (((tmp*tmp)%M)*m)%M;
  }
  return tmp;
}
 
main(){
  int m, n;
  cin >> m >> n;
  cout << power(m, n, 1000000007) << endl;
  return 0;
}

Measured memory_bytes: 3096
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
using P = pair<int,int>;

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

const int MAX_N = 100100;
const int NO = -1;
const int WHITE = 0, GRAY = 1, BLACK = 2;

int n, m;
vector<int> adl[MAX_N]; // 隣接リスト
int color[MAX_N], group[MAX_N];
queue<int> Q;

void init(){
    rep(i,MAX_N){
        color[i] = WHITE;
        group[i] = NO;
    }
}

void bfs(int u, int c){
    color[u] = GRAY;
    group[u] = c;
    Q.push(u);

    while(!Q.empty()){
        u = Q.front(); Q.pop();
        for(auto v: adl[u]){
            if(color[v] == WHITE){
                color[v] = GRAY;
                group[v] = c;
                Q.push(v);
            }
        }
        color[u] = BLACK;
    }
}

void bfs_visit(){
    rep(i,n){
        if(group[i] == NO) bfs(i, i);
    }
}

int main()
{
    cin >> n >> m;
    init();
    rep(i,m){
        int s, t; cin >> s >> t;
        adl[s].push_back(t);
        adl[t].push_back(s);
    }
    bfs_visit();
    int q; cin >> q;
    rep(_,q){
        int s, t; cin >> s >> t;
        if(group[s] == group[t]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    //rep(i,n) cout << group[i] << endl;
}


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

int main()
{
	string S;
	cin >> S;
	int num1, num2;
	

	num1 = stoi(S.substr(5,1));
	num2 = stoi(S.substr(6, 1));

	if (num1 == 0 && num2 <= 4) {
		cout << "Heisei" << endl;
	}

	else {
		cout << "TBD" << endl;
	}
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

string S;
int C[100000][4];
int p3[100001];
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  p3[0] = 1;
  for (int i=1; i<=100000; i++) p3[i] = (3LL*p3[i-1])%MOD;

  cin >> S;
  rep(i, S.length()) {
    if (i > 0) rep(j, 4) C[i][j] = C[i-1][j];
    if (S[i] == '?') C[i][3]++;
    else C[i][S[i]-'A']++;
  }
  int N =S.length();
  int s = 0;
  rep(i, S.length()) if (S[i] == 'B' || S[i] == '?') {
    rep(lq, 2) rep(rq, 2) {
      int num = C[N-1][3]-(S[i]=='?')-lq-rq;
      if (num < 0) continue;
      int left = 0;
      if (i > 0) left = C[i-1][lq?3:0];
      int right = (C[N-1][rq?3:2]+MOD-C[i][rq?3:2])%MOD;
      int e = (1LL*left*right)%MOD;
      e = (1LL*e*p3[num])%MOD;
      s = (s+e)%MOD;
    }
  }
  cout << s << "\n";
  return 0;
}


Measured memory_bytes: 2384
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll q,h,s,d,n,Q,H,S,m,ans=0;
    cin>>q>>h>>s>>d>>n;
    Q=q*8;
    H=h*4;
    S=s*2;
    m=min(Q,min(H,S));
    if(m>=d){
        ans+=(n/2)*d; 
        n%=2;
    }
    if(m==Q){
        ans+=(n*4)*q;
    }
    else if(m==H){
        ans+=(n*2)*h;
    }
    else if(m==S){
        ans+=n*s;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by Harry on 5/10/20.
 */
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        String s = scanner.next();
        String t = scanner.next();
        int n = s.length();
        int m = t.length();
        int res = m;
        for(int i=0; i<n && i+m<=n; i++){
            int cur = 0;
            for(int j=0; j<m; j++){
                if(s.charAt(i+j)!=t.charAt(j)){
                    cur++;
                }
            }
            res = Math.min(res, cur);
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 35596
#include <stdio.h>

int go(int x, int y, int z){
    int ans = 0;
    while(1){
        if(x == z){
            ans = 1;
        }
        if(x == y){
            break;
        }
        x -= 1;
    }
    return ans;
}

int main(void)
{
    int x, y, z;
    int ans = 0;
    char order[30];
    
    fgets(order, 29, stdin);
    sscanf(order, "%d %d %d", &x, &y, &z);
    
    if(x > y){
        ans = go(x, y, z);
    }else if(y > x){
        ans = go(y, x, z);
    }else{
        printf("error");
    }
    
    if(ans == 0){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

int N;
vector<int> a, b;
bitset<50> bit(0x3FFFFFFFFFFFF);

bool used[60];

bool dfs(const int &v, const int &t) {
    used[v] = true;
    if(v == t) return true;
    if(v < t) return false;
    rep(i, v) {
        if(!bit[i] || used[v % (i + 1)]) continue;
        if(dfs(v % (i + 1), t)) return true;
    }
    return false;
}

bool f() {
    rep(i, N) {
        memset(used, 0, sizeof(used));
        if(!dfs(a[i], b[i])) return false;
    }
    return true;
}

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

    cin >> N;
    a.resize(N);
    b.resize(N);
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];

    if(!f()) {
        cout << -1 << endl;
        return 0;
    }
    for(int i = 49; i >= 0; i--) {
        bit.reset(i);
        if(!f()) bit.set(i);
    }

    cout << bit.to_ullong() * 2 << endl;

    return 0;
}

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

int main(){
  int tmp;
  cin >> tmp;
  map<int,int> mp;
  int t;
  int ans = 0;
  for(int i = 0;i < tmp;i++){
    cin >> t;
    if(mp[t] == 0){
      ans++;
    }
    mp[t]++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include <iomanip>
using namespace std;
int main(void){
    int n,i,j,x[8],y[8],nx=1,np=0;
    double ans=0.0;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x[i]>>y[i];
        nx*=i+1;
        np+=i;
    }
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            ans+=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2))*2.0/n;
        }
    }
    cout<<setprecision(10)<<ans;
//    cout<<endl<<nx;
//    cout<<endl<<ans;
}


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

const ll MOD = 1'000'000'007;

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

  vector<ll> a(n), c(n), d(n);
  d[0] = 3;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    ll x = a[i];
    if (d[x] == 0) {
      cout << 0 << endl;
      return 0;
    }
    c[i] = d[x];
    d[x] -= 1;
    d[x + 1] += 1;
  }

  ll ans = 1;
  for (int i = 0; i < n; ++i) {
    ans *= c[i];
    ans %= MOD;
  }

  cout << ans << endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;
int main() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int x = i, cnt = 0;
		while (x > 0)
		{
			x /= 10;
			cnt++;
		}
		if (cnt % 2 != 0) ans++;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 384
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, d;

int main(){
	while(scanf("%d%d", &n, &d), n){
		vector<vi> v(n);
		rep(i, n){
			int m, t;
			scanf("%d", &m);
			rep(j, m) scanf("%d", &t), v[i].pb(t);
		}
		vi sz(n), sum(n);
		while(1){
			int mn = *min_element(all(sum)) + d;
			bool update = 0;
			rep(i, n) while(sz[i] < v[i].size() && sum[i] + v[i][sz[i]] <= mn){
				sum[i] += v[i][sz[i]++];
				update = 1;
			}
			
			mn = *min_element(all(sum));
			int idx = -1;
			rep(i, n) if(sum[i] == mn){
				if(idx == -1) idx = i;
				else idx = -2;
			}
			
			if(idx >= 0 && sz[idx] < v[idx].size()){
				int mn2 = inf;
				rep(i, n) if(sum[i] > mn && mn2 > sum[i]) mn2 = sum[i];
				if(mn + v[idx][sz[idx]] <= mn2 + d){
					sum[idx] += v[idx][sz[idx]++];
					update = 1;
				}
			}
			
			if(!update) break;
		}
		bool ok = 1;
		rep(i, n) ok &= sz[i] == v[i].size();
		cout << (ok ? "Yes" : "No") << endl;
	}
	return 0;
}

Measured memory_bytes: 1272
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mod = 1e9 + 7;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N;
	cin >> N;
	int A[200000];
	rep(i, N) cin >> A[i];

	ll kei = 0;
	rep(i, N) kei += A[i];
	kei %= mod;
	kei = kei * kei % mod;

	ll kei2 = 0;
	rep(i, N) kei2 += (ll)A[i] * A[i] % mod;
	kei2 %= mod;
	kei = (kei - kei2 + mod) % mod;

	kei = kei * modpow(2, mod - 2) % mod;

	co(kei);



	Would you please return 0;
}

Measured memory_bytes: 4428
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const double EPS = 1e-10;
string to_binstring(int v) {
	string res;
	rep(i, 0, 5) {
		if (v & 1)res = "1" + res;
		else res = "0" + res;
		v >>= 1;
	}
	return res;
}
string first(char c) {
	if (c == '?')return to_binstring(31);
	else if (c == '\'')return to_binstring(30);
	else if (c == '-')return to_binstring(29);
	else if (c == ',')return to_binstring(28);
	else if (c == '.')return to_binstring(27);
	else if (c == ' ')return to_binstring(26);
	else return to_binstring(c - 'A');
}

signed main() {
	map<string, char>m;

	m["101"] = ' ';
	m["000000"] = '\'';
	m["000011"] = ',';
	m["10010001"] = '-';
	m["010001"] = '.';
	m["000001"] = '?';
	m["100101"] = 'A';
	m["10011010"] = 'B';
	m["0101"] = 'C';
	m["0001"] = 'D';
	m["110"] = 'E';
	m["01001"] = 'F';
	m["10011011"] = 'G';
	m["010000"] = 'H';
	m["0111"] = 'I';
	m["10011000"] = 'J';
	m["0110"] = 'K';
	m["00100"] = 'L';
	m["10011001"] = 'M';
	m["10011110"] = 'N';
	m["00101"] = 'O';
	m["111"] = 'P';
	m["10011111"] = 'Q';
	m["1000"] = 'R';
	m["00110"] = 'S';
	m["00111"] = 'T';
	m["10011100"] = 'U';
	m["10011101"] = 'V';
	m["000010"] = 'W';
	m["10010010"] = 'X';
	m["10010011"] = 'Y';
	m["10010000"] = 'Z';
	string s;
	while (getline(cin, s)) {
		string t;
		rep(i, 0, s.size())t += first(s[i]);
		dump(t);
		dump(t.size());
		string ans;

		for (int i = 0; i < t.size();i++) {
			dump(i); dump(ans);
			for (int j = 1; j<=8; j++) {
				if (m.find(t.substr(i, j)) != m.end()) {
					ans += m[t.substr(i, j)];
					i += j-1;
					break;
				}
			}
		}

		cout << ans << endl;



	}
	return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int n;
    cin >> n;
    map<ll, int> mp;
    ll S = 0;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        ++mp[a];
        S += a;
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        ll b, c;
        cin >> b >> c;
        int cnt = mp[b];
        mp[b] = 0;
        S -= b * cnt;
        S += c * cnt;
        mp[c] += cnt;
        cout << S << '\n';
    }
}

Measured memory_bytes: 9564
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;

char a[1005][1005];

int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};

int n, m, srcr, srcc, tor, toc;
int dis[1005][1005];

bool valid(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m && a[r][c] == '.';
}

void dij(int srcr, int srcc){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dis[i][j] = 1e9;
        }
    }
    priority_queue< pair < int, pair<int, int>>> pq;
    pq.push({0, {srcr, srcc}});
    dis[srcr][srcc] = 0;
    while(pq.size()){
        int r = pq.top().second.first;
        int c = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();
        if(cost != dis[r][c]) continue;
        for(int i = 0; i < 4; i++){
            int rr = r + dr[i], cc = c + dc[i];
            if(valid(rr, cc) && dis[rr][cc] > dis[r][c]){
                dis[rr][cc] = dis[r][c];
                pq.push({-dis[rr][cc], {rr, cc}});
            }
        }
        for(int i = -2; i < 3; i++){
            for(int j = -2; j < 3; j++){
                int rr = r + i, cc = c + j;
                if(valid(rr, cc) && dis[rr][cc] > dis[r][c] + 1){
                    dis[rr][cc] = dis[r][c] + 1;
                    pq.push({-dis[rr][cc], {rr, cc}});
                }
            }
        }
        // cout << r << ' ' << c << '\n';
    }
    if(dis[tor - 1][toc - 1] < 1e9) cout << dis[tor - 1][toc - 1];
    else cout << -1;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> srcr >> srcc >> tor >> toc;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    dij(srcr - 1, srcc - 1);


    return 0;
}


Measured memory_bytes: 8536
test = False
if test:
    import time
    start = time.time()

import sys
import random


def solve(c_list, days, now):
    r = sum(c_list[i]*(now-days[i]) for i in range(26))
    return r


if test == True:
    #seed = 94
    #random.seed(seed)
    d = 365
    c = [random.randrange(0, 101) for _ in range(26)]
    s = [[random.randrange(0, 20001) for _ in range(26)] for _ in range(d)]
    c_ = ' '.join(map(str, c))
    s_ = '\n'.join([' '.join(map(str, i)) for i in s])
    with open('./input.txt', 'w') as f:
        f.write('\n'.join([str(d), c_, s_]))
else:
    d = int(input())
    c = list(map(int, input().split()))
    s = [list(map(int, input().split())) for _i in range(d)]


last_days = [-1 for _i in range(26)]
result = []
score = 0
for today in range(d):
    checker = [c[j]*(today-last_days[j]) for j in range(26)]
    y = sum(checker)

    finder = [s[today][j]-(y-checker[j]) for j in range(26)]
    x = finder.index(max(finder))

    if today < d-1:
        second_checker = [c[j]*(today+1-last_days[j]) for j in range(26)]
        second_finder = [s[today+1][j]-(y-checker[j]) for j in range(26)]
        second_x = second_finder.index(max(second_finder))
        if x == second_finder:
            x = finder.index(sorted(finder)[-2])
    

    last_days[x] = today
    result.append(x+1)
    score += s[today][x] - solve(c, last_days, today)
if test:
    print(score)

def change(problems, days):
    last_days = [-1 for _i in range(26)]
    score = 0
    for i in range(d):
        score += s[i][problems[i]-1]
        last_days[problems[i]-1] = i
        score -= sum([c[j]*(i-last_days[j]) for j in range(26)])
    return score

change_list = result.copy()
for i in range(9200):
    if random.randrange(2)<1:
        x, y = random.randrange(0, d), random.randrange(0, d)
        while x == y:
            y = random.randrange(0, d)
        change_list[x], change_list[y] = change_list[y], change_list[x]
        next_score = change(change_list, d)
        if next_score >= score:
            if test:print(i, score, next_score, abs(next_score-score), 'two')
            score = next_score
            result[x], result[y] = result[y], result[x]
        
        else:
            change_list[x], change_list[y] = change_list[y], change_list[x]
    else:
        x = random.randrange(0, d)
        y = random.randrange(1, 27)
        while change_list[x] == y:
            x = random.randrange(0, d)
            y = random.randrange(1, 27)    
        change_list[x], z = y, change_list[x]
        next_score = change(change_list, d)
        if next_score >= score:
            if test:print(i, score, next_score, abs(next_score-score), 'one')
            score = next_score
            result[x] = y
        else:
            change_list[x] = z

if test == True:
    with open('./output.txt', 'w') as f:
        f.write('\n'.join(map(str, result)))
else:
    for i in result:
        print(i)

if test:
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Measured memory_bytes: 92640
program ABC164B
    implicit none
    integer(8)::A,B,C,D,flg
    read*,A,B,C,D
    flg=0
    do
        C=C-B
        if(C<=0)then
            flg=1
            exit
        end if
        A=A-D
        if(A<=0)exit
    end do

    if(flg==0)print'(A)',"No"
    if(flg==1)print'(A)',"Yes"
end program ABC164B

Measured memory_bytes: 2924
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl;
#define INF 1ll << 60;
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

int main()
{
    string s;
    cin >> s;
    if (s[s.size() - 1] == 's')
    {
        cout << s + "es" << endl;
    }
    else
    {
        cout << s + "s" << endl;
    }
}

Measured memory_bytes: 3632
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char arr[] = s.toCharArray();
		int N = arr.length;
		if(N == 1){
			System.out.println(1);
			return ;
		}
//		System.err.println(N);
		int dp[][] = new int[N][2];
		dp[0][0] = 1;
		dp[0][1] = 1;
		for(int i = 1; i < N ; ++i){
			// i番目の1文字のみ利用する場合
			int ret = 0;
			if(arr[i - 1] != arr[i]){
				ret = dp[i - 1][0] + 1;				
			}
			if(i >= 2){
				ret = Math.max(ret, dp[i - 2][1] + 1);
			}
			dp[i][0] = ret;
			if(i < N -1){
				ret = dp[i - 1][0] + 1;
				dp[i][1] = ret;
			}
		}
		int ret = Math.max(dp[N - 1][0], dp[N - 2][1]);
		System.out.println(ret);
//		System.out.println(Arrays.deepToString(dp));
	}
}


Measured memory_bytes: 32996
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  int count=0,min=n+1;
  for(int i=0;i<n;i++)
  {
    if(a[i]<min)
    {
      count++;
      min=a[i];
    }
    if(a[i]==1)break;
  }
  cout<<count<<endl;
  return 0;
}
    

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct Edge {
    ll from;
    ll to;
    ll cost;
};

Edge E[2005];
ll C[1005];

int main() {
    ll N, M, R;
    cin >> N >> M >> R;
    REP(i, M) {
        cin >> E[i].from >> E[i].to >> E[i].cost;
    }
    REP(i, N) {
        C[i] = INF;
    }
    C[R] = 0;

    bool cycle = false;
    REP(i, N + 1) {
        bool update = false;
        REP(e, M) {
            if (C[E[e].from] == INF)
                continue;
            ll c = C[E[e].from] + E[e].cost;
            if (C[E[e].to] > c) {
                C[E[e].to] = c;
                update = true;
            }
        }
        cycle = update;
        if (!update)
            break;
    }

    if (cycle)
        cout << "NEGATIVE CYCLE" << endl;
    else {
        REP(i, N) {
            if (C[i] == INF)
                cout << "INF" << endl;
            else
                cout << C[i] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3128
// https://atcoder.jp/contests/abc174/tasks/abc174_f

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;

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

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

template <typename T>
inline ll len(V<T> arr) {
  return arr.size();
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}

const ll INF = 1e18;

void solve();

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

struct Fenwick {
  vector<ll> tree;

  Fenwick(ll n) : tree(vector<ll>(n, 0)) {}

  // sum of [0, i)
  ll sum(ll i) {
    ll res = 0;

    for (i--; i >= 0; i = (i & (i + 1)) - 1) {
      res += tree[i];
    }

    return res;
  }

  void add(ll i, ll n) {
    for (ll len = tree.size(); i < len; i |= i + 1) {
      tree[i] += n;
    }
  }
};

void solve() {
  ll N, Q;
  cin >> N >> Q;

  VL cs(N);
  rep(i, N) cin >> cs[i];

  VL last_i(N + 1, -1);     // 各数字の最後に現れた index
  VVL non_last_indices(N);  // 各数字の最後以外の index

  rep(i, N) {
    ll last = last_i[cs[i]];
    if (last != -1) non_last_indices[last].emplace_back(i);
    last_i[cs[i]] = i;
  }

  V<VPL> qs(N);
  rep(qi, Q) {
    ll l, r;
    cin >> l >> r;
    --l, --r;
    qs[l].emplace_back(r, qi);
  }

  Fenwick bit(N);
  VL res(Q);

  // その範囲 (r - l + 1) から重複分を引く
  // 重複分になるのは non_last_indices
  repr(l, N) {
    for (ll r : non_last_indices[l]) bit.add(r, 1);

    for (auto [r, qi] : qs[l]) {
      res[qi] = r - l + 1 - bit.sum(r + 1);
    }
  }

  rep(i, Q) cout << res[i] << "\n";
}


Measured memory_bytes: 70956
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) x.begin(),x.end()
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

void Main(){

  int a,b;
  char c;

  cin >> a>>c>>b;

  cout << (c=='+' ? (a+b) : (a-b)) <<"\n";

}
//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 256
n = int(input())
s = input()
l = list(s)
m = 0
for i in range(n - 1):
    l1 = l[:i+1]
    l2 = l[i+1:]
    l1 = list(set(l1))
    l2 = list(set(l2))
    l1.sort()
    l2.sort()
    x = 0
    for j in range(len(l1)):
        if l1[j] in l2:
            x += 1
    if x > m:
        m = x
print(m)


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;


void solve(std::string S, std::string T){
  int ans = 0;
  for (int i = 0; i < 3; i++) {
    if (S[i] == T[i]) {
      ans++;
    }
  }
  std::cout << ans << std::endl;
}

int main(){
  std::string S;
  std::cin >> S;
  std::string T;
  std::cin >> T;
  solve(S, T);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
						
#define fast_cin() ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long
				
int32_t main() {
	fast_cin();  

	int k, n; cin >> k >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int sum = 0;
	int mx = 0;
	for (int i = 0; i + 1 < n; i++) {
		sum += abs(a[i] - a[i + 1]);
		mx = max(abs(a[i] - a[i + 1]), mx);
	}
	sum += abs(k - a[n - 1] + a[0]);
	mx = max(abs(k - a[n - 1] + a[0]), mx);
	cout << sum - mx << endl;

	
	return 0;
}

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

int main(){
    vector<int> a(4);
    int i;
    int s1=0;
    int s2=0;
    int s3=0;
    int s4=0;
    for(i=0;i<4;i++){
        cin >> a.at(i);
        if(a.at(i)==1){
            s1++;
        }
        else if(a.at(i)==9){
            s2++;
        }
        else if(a.at(i)==7){
            s3++;
        }
        else if(a.at(i)==4){
            s4++;
        }
    }

    if((s1==1)&&(s2==1)&&(s3==1)&&(s4==1)){
        cout << "YES" << endl;
    }
    else{
        cout << "NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define INF 1e9+7
#define LLINF 1e18
using namespace std;
const int MOD = 1e9 +7;

int main(){
    ll N,M,x[100010],t[100010],ans;
    ans =0;
    cin >>N>>M;
    rep(i,M) cin >>x[i];
    sort(x,x+M);
    if(N>=M) cout <<0<<endl;
    else{
        rep(i,M-1){
            t[i] =x[i+1]-x[i];
        }
        sort(t,t+M-1);
        for(int i=M-2;i>=M-N;i--){
            ans+=t[i];
        }
        cout <<x[M-1]-x[0]-ans<<endl;
    }
    return 0;
}

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

int main()
{  
  char s[4];
  cin >> s[0] >> s[1] >> s[2] >> s[3];
  if(
  (s[0]==s[1]&&s[1]!=s[2]&&s[2]==s[3])||
  (s[0]!=s[1]&&s[0]==s[2]&&s[1]==s[3])||
  (s[0]!=s[1]&&s[0]==s[3]&&s[1]==s[2])){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//#define int long long


int main() {
  int  a,b;
  cin >> a>>b;
  
  cout << (a*b%2==1?"Odd":"Even") << endl;

  
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define MOD 1000000007
#define ar array
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);

int32_t main() {
	fast_io;

	// int t; cin >> t;
	// while (t--) {
		
	// }
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	vector<int> dp(n, 1e9 + 5);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j : {i + 1, i + 2}) {
			if (j < n) {
				dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]));
			}
		}
	}
	cout << dp[n - 1] << endl;

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int A[N];
  for(int k=0;k<N;k++){
    cin >> A[k];
  }

  int count = 0;
  for(int i=0;i<N;i++){
    int minj = i;
    for(int j=i;j<N;j++){
      if(A[j] < A[minj]) minj = j;
    }
    if(minj != i){
      int temp;
      temp = A[i];
      A[i] = A[minj];
      A[minj] = temp;
      count++;
    }
  }

  for(int l=0;l<N-1;l++){
    cout << A[l] << " ";
  }
  cout << A[N-1] << endl;
  
  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 1160
var weekdays = new Map([['SUN',7],['MON',6],['TUE',5],['WED',4],['THU',3],['FRI',2],['SAT',1]]);

function check(target) {
  return weekdays.get(target);
}

function Main(inp) {
  var input = inp.split("\n");
  var target = input[0];

  console.log(check(target));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
S = input()
N = len(S)


AGTC = ['A', 'G', 'T', 'C']
part_l = []
for i in range(N):

        if S[i] in AGTC:
                if i == 0:
                        part = [S[i]]
                elif S[i-1] in AGTC:
                        part.append(S[i])
                else:
                        part = [S[i]]
        else:
                if i == 0:
                        part = []
                elif S[i-1] in AGTC:
                        part_l.append(part)
                        part = []
part_l.append(part)

max_part = []          
for part in part_l:
        if len(part) > len(max_part):
                max_part = part

print(len(max_part))

Measured memory_bytes: 3064
import math
A,B=map(int,input().split())

def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if a==b:
    return a
  else:
    if a%b==0:
      return b
    return gcd(b,a%b)
  
v=gcd(A,B)

def bunnkai(N):
  lst=[1]
  tmp=N
  for i in range(2,int(math.sqrt(N)+1)):
    if tmp%i==0:
      while tmp%i==0:
        tmp//=i
      lst.append(i)
  if tmp!=1:
    lst.append(tmp)
  if lst==[]:
    lst.append(N)
  return lst

print(len(bunnkai(v)))

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

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

    long long max = -1000000, min = 1000000, sum = 0;

    for (int i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }

        sum += a[i];
    }

    cout << min << " " << max << " " << sum << endl;
    return 0;
}




Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000
#define int long long
int n, a[maxn], sum;

int read() {
	int x = 0, k = 1;
	char c; c = getchar();
	while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } 
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * k;
}

signed main() {
	n = read(); a[n + 1] = 0; 
	for(int i = 1; i <= n; i ++) a[i] = read(), sum += abs(a[i] - a[i - 1]);
	sum += abs(a[n + 1] - a[n]);
	for(int i = 1; i <= n; i ++) {
		printf("%lld\n", sum - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]));
	}
	return 0;
} 

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#pragma region Macros
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);
#define VEC(type, name, size)\
    V<type> name(size);\
    IN(name)
#define VVEC(type, name, h, w)\
    VV<type> name(h, V<type>(w));\
    IN(name)
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHAR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DOUBLE(...)\
    DOUBLE __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LD(...)\
    LD __VA_ARGS__;\
    IN(__VA_ARGS__)
template <class T> void scan(T &a) { cin >> a; }
template <class T> void scan(vector<T> &a) { for(auto &i : a) scan(i); }
template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); }
template <class T> inline void print(T x){ cout << x << '\n';}
#define ll long long
#define ld long double
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
const ll INF = 1e18;
#pragma endregion

int main(){
    ios;
    INT(x);
    Yes(x >= 30);
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define setNil(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
#define setNegINF(x) memset((x),192,sizeof(x)) //NegINF=-INF-1
#define setNeg1(x) memset((x),255,sizeof(x))
#define MP make_pair
using namespace std;
typedef long long ll;
int n,mx[105];
vector<int> g[105];
void dfs(int x,int p,int d){
	int cnt=0;
	for(int i=0;i<g[x].size();i++){
		int u=g[x][i];
		if(u==p)continue;
		dfs(u,x,d+1);
		cnt++;
	}
	mx[d]=max(mx[d],cnt);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	pair<ll,ll> ans=MP(1e18,1e18);
	for(int i=1;i<=n;i++){
		setNil(mx);
		dfs(i,0,1);
		long long mxd=1,res=1;
		for(;mx[mxd];mxd++)res*=mx[mxd];
		ans=min(ans,MP(mxd,res));
	}
	for(int i=1;i<=n;i++){
		for(int u=0;u<g[i].size();u++){
			setNil(mx);
			int j=g[i][u];
			dfs(i,j,1);
			dfs(j,i,1);
			long long mxd=1,res=2;
			for(;mx[mxd];mxd++)res*=mx[mxd];
			ans=min(ans,MP(mxd,res));
		}
	}
	cout<<ans.first<<' '<<ans.second<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v;
pair<int,int> p;
map<int,int> m;
deque<int> d;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int x,y,z;
cin>>x>>y>>z;
int i=0;
while(x>=y+z ){
    if(i==0)
        x-=z;
        x-=(y+z);
        i++;
    }

cout<<i<<endl;
return 0;
}


Measured memory_bytes: 3664