akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
using namespace std;

int main(void)
{
	int N, K; cin >> N >> K;
	vector<int> H(N); rep(i, 0, N)cin >> H[i];
	sort(H.begin(), H.end());
	lli ans = 0;
	rep(i, 0, N - K)ans += H[i];
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b,c; cin>>a>>b>>c;
    if(b-a==c-b)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
import numpy as np
N,M = map(int, input().split())
p, S = [], []
for i in range(M):
  tmp = input().split()
  p.append(int(tmp[0]))
  S.append(tmp[1])

past_p = 0
tmp_AC, tmp_WA = 0, 0
total_AC, total_WA = 0, 0
answer_AC = np.zeros(N)
answer_WA = np.zeros(N)
for i in range(M):
  if S[i] == 'AC' and answer_AC[p[i]-1] == 0:
    answer_AC[p[i]-1] += 1
  elif S[i] == 'WA' and answer_AC[p[i]-1] == 0:
    answer_WA[p[i]-1] += 1
#print(answer_AC)
#print(answer_WA)
total_AC, total_WA = 0, 0
for i in range(N):
  if answer_AC[i] == 1:
    total_AC += answer_AC[i]
    total_WA += answer_WA[i]
print(int(total_AC), int(total_WA))

Measured memory_bytes: 23740
from sys import stdin

r, c = [int(x) for x in stdin.readline().rstrip().split()]
table = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(r)]
for row in range(r):
    table[row] += [sum(table[row])]
    print(*table[row])

col_sum = [sum(x) for x in zip(*table)]
print(*col_sum)


Measured memory_bytes: 6248
#include <stdio.h>
int main(void)
{
int a, b, c;
scanf("%d", &a);
scanf("%d", &b);
scanf("%d", &c);

if(a<b){
 if(b<c){
 printf("Yes\n");
 }else if(b>c){
 printf("No\n");
 }
}else  {
printf("No\n");
}

return 0;
}

Measured memory_bytes: 580
#include <stdlib.h> 
#include <stdio.h>
long long Max(long long x,long long y){
    return x>y?x:y;
}
long long Min(long long x,long long y){
    return x<y?x:y;
}
long long p=1000000000,n,a,b,c,l[10];
void dfs(long long i,long long A,long long B,long long C,long long T){
    if(i==n+1){return;}
    if(A>0&&B>0&&C>0){
        p=Min(p,abs(a-A)+abs(b-B)+abs(c-C) + 10*(Max(0,T-3)));
        
    }
        dfs(i+1,A+l[i],B,C,T+1);
        dfs(i+1,A,B+l[i],C,T+1);
        dfs(i+1,A,B,C+l[i],T+1);
        dfs(i+1,A,B,C,T);
}

int main()
{
    
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    for(int i=0;i<n;i++){
        scanf("%lld",&l[i]);
    }
    dfs(0,0,0,0,0);
    printf("%lld",p);
    return 0;
}


Measured memory_bytes: 128
import itertools
n = int(input())
# itertools順列の中身はタプル
p = tuple(list(map(int, input().split())))
q = tuple(list(map(int, input().split())))
# listにする
lista = list(itertools.permutations(range(1, n + 1)))
print(abs(lista.index(p) - lista.index(q)))

Measured memory_bytes: 45168
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL;
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
    string s;cin>>s;
    
    if(s.size()==3)reverse(all(s));
    cout<<s<<endl;
    
    return 0;

}

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

int main(){
  int N, L;
  cin >> N >> L;
  vector<int> A(N);
  
  int sum = 0;
  int taste = 0;
  for(int i = 0; i < N; i++){
    taste = L + i; // hidden -1+1
    A[i] = abs(taste);
    sum += taste;
  }
  
  sort(A.begin(), A.end());
  
  int ans = 0;
  if(sum < 0){
    ans = sum + A[0];
  }else if(sum > 0){
    ans = sum - A[0];
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
using LL = long long;

int main()
{
	string s;
	cin >> s;
	if (s == "ABC")
	{
		cout << "ARC" << endl;
	}
	else
	{
		cout << "ABC" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3592
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {

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

  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(in.readLine());
      String line = in.readLine();

      int[] seqA = new int[n/2];
      int[] seqB = new int[n/2];

      List<Integer> listA = new ArrayList<>();
      List<Integer> listB = new ArrayList<>();
      Map<Integer,Integer> mapA = new HashMap<>();
      Map<Integer,Integer> mapB = new HashMap<>();
      int offset=0,next=0;
      char regx = ' ';
      for(int i=0, j=0; i<n; i++, j= i >> 1) {
        if((next = line.indexOf(regx,offset)) == -1)
          next = line.length();
        int num = Integer.parseInt(line.substring(offset, next));
        offset = ++next;

        if((i & 1) == 0) {
          seqA[j] = num;
          if(mapA.containsKey(seqA[j])) {
            mapA.replace(seqA[j], mapA.get(seqA[j]) + 1);
          } else {
            mapA.put(seqA[j], 1);
            listA.add(seqA[j]);
          }
        }
        else {
          seqB[j] = num;
          if(mapB.containsKey(seqB[j])) {
            mapB.replace(seqB[j], mapB.get(seqB[j]) + 1);
          } else {
            mapB.put(seqB[j], 1);
            listB.add(seqB[j]);
          }
        }
      }

      int vma,vmb,xa,xb;
      vma = vmb = xa = xb =0;
      for (Integer var : listA) {
        int ma = mapA.get(var);
        if(vma < ma) {
          vma = ma;
          xa = var;
        }
      }
      for (Integer var : listB) {
        int mb = mapB.get(var);
        if(vmb < mb) {
          vmb = mb;
          xb = var;
        }
      }

      int cca,ccb;
      cca = ccb = 0;
      for (int i : seqA) {
        if(i != xa) cca++;
      }
      for (int i : seqB) {
        if(i != xb) ccb++;
      }

      int vma2,vmb2,xa2,xb2;
      vma2 = vmb2= xa2 = xb2 =0;
      int cca2,ccb2;
      cca2 = ccb2 = 0;
      int ans = 0;
      if(xa == xb) {
        for (Integer var : listA) {
          int ma = mapA.get(var);
          if(var != xa && vma2 < ma) {
            vma2 = ma;
            xa2 = var;
          }
        }
        for (Integer var : listB) {
          int mb = mapB.get(var);
          if(var != xb && vmb2 < mb) {
            vmb2 = mb;
            xb2 = var;
          }
        }
      
        for (int i : seqA) {
          if(i != xa2) cca2++;
        }
        for (int i : seqB) {
          if(i != xb2) ccb2++;
        }

        ans = cca2 > ccb2 ? cca + ccb2 : cca2 + ccb;
      }
      else {
        ans = cca + ccb;
      }

      System.out.println(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 44824
#include<stdio.h>
int main(){double w;int f;char *p[11]={"light fly","fly","bantam","feather","light","light welter","welter","light middle","middle","light heavy","heavy"};while(scanf("%lf",&w)!=EOF){if(w<=48)f=0;else if(w<=51)f=1;else if(w<=54)f=2;else if(w<=57)f=3;else if(w<=60)f=4;else if(w<=64)f=5;else if(w<=69)f=6;else if(w<=75)f=7;else if(w<=81)f=8;else if(w<=91)f=9;else f=10;puts(p[f]);}return 0;}

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

#define what_is(x)    cerr<<#x<<" is "<<x<<"\n";
#define rep(i,a,n)    for(int i=a; i<=n; ++i)
#define rep1(i,a,n)   for(int i=a; i>=n; --i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define M             1000000007
#define MM            998244353
#define PI            3.14159265358979
#define INF           1000000000000000

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,m,ans; string str;

vc<pair<double,double>> v;
int solve(){
    double ans=0.0;
    double n; cin>>n;
    rep(i,1,n){
        double a,b; cin>>a>>b;
        v.pb({a,b});
    }
    rep(i,0,n-1){
        rep(j,i+1,n-1){
            double a=v[i].fr-v[j].fr,b=v[i].sc-v[j].sc;
            double t=a*a+b*b;
            t=sqrt(t);
            ans+=t;
        }
    }
    ans/=(n/2);
    cout<<fixed<<setprecision(10)<<ans;
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    ll a[n];
    
    ll iMin = INF;
    ll cnt = 0;
    //負の数は2個ずつしか減らせない
    //min(abs(a[i]))を引けばいい気がする
    //0があれば min -> 0

    ll res = 0;

    REP(i,n)
    {
        cin >> a[i];
        ll tmp = abs(a[i]);
        res += tmp;
        iMin = min(iMin,tmp);
        if(a[i] < 0)++cnt;
    }

    if(cnt % 2 == 1)
    {
        res -= iMin * 2;
    }

    cout << res << endl;

    return 0;    
}



Measured memory_bytes: 1024
#include<stdio.h>
int gcd(int,int);

int main(){
  int x,y,a;
  scanf("%d%d",&x,&y);
  a=gcd(x,y);
  printf("%d\n",a);
  return 0;
}

int gcd(int x,int y){
  int k,r;

  if(x<y){
    k=x;
    x=y;
    y=k;
  }
  while(y>0){
    r = x % y;
        x = y;
        y = r;
      }
    return x;
}



Measured memory_bytes: 2068
a,b,c,k = map(int,input().split())
S = 0
if k>=a:
    S += a
    k-=a
elif k<a:
    S+=k
    k = 0
# print(k)
if k>=b:
    k-=b
elif k<b:
    k=0
# print(k)
if k>=c:
    S-=c
    k-=c
elif k<c:
    S-= k
# print(k)
print(S)

Measured memory_bytes: 61660
import java.io.InputStream;
import java.util.Scanner;

public class Main {


	public static void main(String args[]) {
        InputStream inputStream = System.in;
        Scanner sc = new Scanner(inputStream);
        String out;
        int check=0;
        String A=sc.next();
        String[] B=new String[A.length()];
        int c=0;
        for(int i=0;i<A.length();i++) {
        		c+=Integer.parseInt(A.substring(i, i+1));
        }
        if(Integer.parseInt(A)%c==0) {System.out.println("Yes");}
        else {System.out.println("No");}

	}

}


Measured memory_bytes: 23764
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define all(v) (v).begin(),(v).end()
#define clr(a,b) memset((a),(b),sizeof(a))
#define sz size()
#define pb push_back
#define print(x) cout << x << endl
int n,m;
int a,b,c,k;
int ans = 0;

int main(){
  vector<int> vec;
  cin >> n >> k;
  rep(i,0,n){
    cin >> a;
    vec.pb(a);
  }
  rep(i,0,n){
    if(vec[i] > abs(vec[i]-k)){
      ans += 2*abs(vec[i]-k);
    }else{
      ans += 2*vec[i];
    }
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args) {
		int n = sc.nextInt();
		
		int[] A = new int[n];
		for(int i=0; i<n; i++) {
			A[i] = sc.nextInt();
		}
		
		int cnt = 0;
		int d = 1;
		ArrayList<Integer> G = new ArrayList<Integer>();
		while(d < n) {
			G.add(d);
			d = d * 3 + 1;
		}
		Collections.reverse(G);
		if(!G.contains(1)){
			G.add(1);
		}
		int m = G.size();
		for(int i=0; i<m; i++) {
			cnt += insertionSort(A, n, G.get(i));
		}
		
		System.out.println(m);
		
		for(int i=0; i<m; i++) {
			System.out.print(G.get(i));
			if(i != m-1) {
				System.out.print(" ");
			}
		}
		System.out.println();
		
		System.out.println(cnt);
		
		for(int i=0; i<n; i++) {
			System.out.println(A[i]);
		}
	}
	
	static int insertionSort(int[] A, int n, int g){
		int cnt = 0;
		for(int i=g; i<n; i++) {
			int v = A[i];
			int j = i - g;
			while(j >= 0 && A[j] > v) {
				A[j+g] = A[j];
				j = j - g;
				cnt++;
			}
			A[j+g] = v;
		}
		return cnt;
	}

	static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 114544
#include <iostream>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

bool r[100001], s[100001], p[100001];

int main() {
    int N, K;
    cin >> N >> K;
    int R, S, P;
    cin >> R >> S >> P;
    string T;
    cin >> T;

    fill(r, r + K, true);
    fill(s, s + K, true);
    fill(p, p + K, true);

    int ans = 0;

    for (int i = 0; i < T.size(); ++i) {
        int index = i % K;

        switch (T[i]) {
            case 'r':
                if (p[index]) ans += P;
                r[index] = true;
                s[index] = true;
                p[index] = !p[index];
                break;
            case 's':
                if (r[index]) ans += R;
                r[index] = !r[index];
                s[index] = true;
                p[index] = true;
                break;
            case 'p':
                if (s[index]) ans += S;
                r[index] = true;
                s[index] = !s[index];
                p[index] = true;
                break;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 768
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		
		if (a>=b && a>=c) {
			System.out.println(a*10 + b + c);
			return;
		}
		if (b>=a && b>=c) {
			System.out.println(b*10 + c + a);
			return;
		}
		if (c>=a && c>=b) {
			System.out.println(c*10 + a + b);
			return;
		}
	
	}
	
}

Measured memory_bytes: 22740
use std::io::*;
use std::str::*;
use std::f64::consts::*;
use std::f64;

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

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

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

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

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

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

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

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

fn main() {
    input!{
        n: i32,
        v: [i32; n],
    }
    let mut sum = 0;
    sum = v.iter().sum();
    let center = (sum as f64 / n as f64).round() as i32;
    let sum: i32 = v.iter().map(|val| (val - center).pow(2)).sum();
    println!("{}", sum);
}

Measured memory_bytes: 4476
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define KMAX (1000)
int s[KMAX + 1][2 * KMAX + 1];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    int n, k, x, y;
    cin >> n >> k;
    REP(i, n) {
        cin >> x >> y >> c;
        if (c == 'W') {
            y += k;
        }
        y %= 2 * k;
        if (y >= k) {
            y -= k;
            x += k;
        }
        x %= 2 * k;
        s[y + 1][x + 1]++;
    }
    // 二次元累積和
    REP(y, k) REP(x, 2 * k) {
        s[y + 1][x + 1] += s[y][x + 1] + s[y + 1][x] - s[y][x];
    }
    int max = 0;
    REP(y, k) {
        int u = s[y][2 * k] - s[y][0] - s[0][2 * k];
        REP(x, k) {
            int t = u - s[0][x] - s[k][x] + s[0][x + k] + s[k][x + k] +
                    2 * s[y][x] - 2 * s[y][x + k];
            t = t < n / 2 ? n - t : t;
            max = t > max ? t : max;
        }
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
 
int w, h, n;
 
int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> w >> h >> n;
	int r = w, l = 0, t = h, b = 0;
	FOR(i, n) {
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1) l = max(l, x);
		else if (a == 2) r = min(r, x);
		else if (a == 3) b = max(b, y);
		else t = min(t, y);
	}
	if (r <= l || t <= b) cout << 0 << endl;
	else cout << (r-l)*(t-b) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int k;

	cin >> k;

	cout << (k % 2 == 0 ? k / 2 : k / 2 + 1) * (k / 2) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD 1000000007
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ull t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<int,int> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m){if(m==0)return 1;ll t=mpowe(n,m/2);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;return logtwo(n/2)+1;}
int main()
{
    fastio();
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    ll h,a;
    cin>>h>>a;
    ll ans = h%a==0?h/a:h/a+1;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-8;
const long double INF = 1e20;

int main(){
	int H;
	while(cin>>H&&H){
		int ar[22][6];CLR(ar);
		bool f[22][5];
		REP(i,H)REP(j,5)cin>>ar[H-i-1][j];//0が一番下
		bool flag=true;
		int res=0;
		while(flag){
			CLR(f);
			flag=false;
			
			REP(i,H){
				int np=ar[i][0];
				int cnt=1;
				FOR(j,1,6){
					if(ar[i][j]==np)cnt++;
					else{
						if(cnt>=3&&np!=0){
							REP(k,cnt)f[i][j-k-1]=true;
							res+=np*cnt;
							flag=true;
						}
						cnt=1;np=ar[i][j];
					}
				}
			}
			REP(i,5){
				int gp=0;
				vector<int>tmp;
				REP(j,H)if(!f[j][i])tmp.PB(ar[j][i]);
				REP(j,SZ(tmp))ar[j][i]=tmp[j];
				FOR(j,SZ(tmp),H)ar[j][i]=0;
				//cout<<"!"<<endl;
			}
			/*REP(i,H){
				REP(j,5)cout<<ar[H-i-1][j];
				cout<<endl;
			}
			cout<<res<<endl;*/
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define _ (*istream_iterator<int>(cin))

using namespace std;
const int N = 1e2+10;
bool g[N][N];

int main() {
    int n = _, cnt = 0;
    for(int i=1; i<=n/2; i++) {
        g[i][n-i+(n&1?0:1)] = true;
        cnt++;
    }
    cout << n*(n-1)/2-cnt << '\n';
    for(int i=2; i<=n; i++) {
        for(int j=1; j<i; j++) {
            if(not g[j][i]) {
                cout << j << ' ' << i << '\n';
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(){
int i=0;
int num = 0;
int n=0,a=0,b=0;
int sum1=0,sum2=0;


 if(scanf("%d",&n)==1){};
 if(scanf("%d",&a)==1){};
 if(scanf("%d",&b)==1){};

 sum1=n*a;
 sum2=b;

if(sum1<sum2){printf("%d\n",sum1);}else{printf("%d\n",sum2);}

return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<char, char> p;
const int INF = (1 << 28);
string s, t;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s>>t;
    int n=s.size();
    s=s.c_str();
    t=t.c_str();
    vector<p> st;
    for(int i=0;i<n;i++){
        st.push_back(make_pair(t[i],s[i]));
    }
    sort(st.begin(),st.end());
    if(n==1) {
        cout << "Yes"<< "\n";
        return 0;
    }
    for(int i=0;i<n-1;i++){
       if(st[i].first==st[i+1].first&&st[i].second!=st[i+1].second){
            cout<<"No"<<"\n";
            return 0;
        }
    }
    for(int i=0;i<n;i++){
        swap(st[i].first,st[i].second);
    }
    sort(st.begin(),st.end());
    for(int i=0;i<n-1;i++){
       if(st[i].first==st[i+1].first&&st[i].second!=st[i+1].second){
            cout<<"No"<<"\n";
            return 0;
        }
    }
    cout << "Yes"<< "\n";
}

Measured memory_bytes: 1428
import sys

d = {}

input()
for q in sys.stdin:
    q = q.split()
    if q[0] == '0':
        d[q[1]] = q[2]
    elif q[0] == '1':
        print(d.get(q[1], 0))
    else:
        if q[1] in d:
            del d[q[1]]


Measured memory_bytes: 41840
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, d;
  cin >> n >> d;
  vector<vector<double>> coord(n, vector<double>(d));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < d; ++j){
      cin >> coord[i][j];
    }
  }
  int check;
  int init;
  int ans = 0;
  for(int i = 0; i < n - 1; ++i){
    for(int j = i + 1; j < n; ++j){
      check = 0;
      init = 1;
      for(int k = 0; k < d; ++k){
        check += pow((coord[i][k] - coord[j][k]), 2);
      }
      while(init * init <= check){
        if(init * init == check) ans++;
        init++;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<queue>
#include<iostream>
#include<fstream>
#include<cstring>

using namespace std;

int main(){
	int x,y,z;
	int n;
	int a,b,c;
	scanf("%d %d %d",&x,&y,&z);
	n=(x-(2*z+y))/(z+y);
	printf("%d\n",n+1);
}

Measured memory_bytes: 256
/**
   Solution by Abil
**/
# include <bits/stdc++.h>

# define fr first
# define sc second
# define pb push_back
# define mk make_pair
# define sz(s) s.size()
# define all(s) s.begin(),s.end()
# define int long long

using namespace std;

const long long N = (1e5 + 10);
const long long mod = (1e9 + 7);
const long long inf = (1e9 + 7);

int dp[N],arr[N];

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1;i <= n; i++){
        cin >> arr[i];
    }
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[1] = 0;
    for(int i = 2;i <= n; i++){
        for(int j = max(1ll,i - k);j <= i + k && i - j >= 1; j++){
            dp[i] = min(abs(arr[j] - arr[i]) + dp[j],dp[i]);
        }
    }
    cout << dp[n];
}


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

using namespace std;

int main() {
  string S;
  cin >> S;
  
  if (S[2] == S[3] && S[4] == S[5]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


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

string a[500], b[500];
signed main() {
	int n, m; cin >> n >> m;
	for (int d = 0; d < n; d++) {
		for (int e = 0; e < m; e++) {
			if (e == 0) {
				a[d] += '#';
				b[d] += '.';
			}
			else if (e + 1 == m) {
				a[d] += '.';
				b[d] += '#';
			}
			else {
				if (d & 1) {
					a[d] += '#';
					b[d] += '.';
				}
				else {
					a[d] += '.';
					b[d] += '#';
				}
			}
		}
	}
	for (int d = 0; d < n; d++) {
		string e; cin >> e;
		for (int f = 0; f < m; f++) {
			if (e[f] == '#') {
				a[d][f] = b[d][f] = '#';
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << endl;
	}
	cout << endl;
	for (int i = 0; i < n; i++) {
		cout << b[i] << endl;
	}
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < (int)(x); i++)
#define pb push_back
#define mp make_pair
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX/4;
const int n_max = 1e5+10;

class node{
    public:
    node(){};
    node(ll id, ll x, ll y){
        m_id = id;
        m_x = x;
        m_y = y;
    }
    // private:
    ll m_id;
    ll m_x;
    ll m_y;
};

// node::node(ll id, ll x, ll y){
//     m_id = id;
//     m_x = x;
//     m_y = y;
// }

int main(){
    ll n; cin >> n;
    vector<node> xy(n);
    rep(i,n){
        ll x,y; cin >> x >> y;
        node t(i,x,y);
        xy[i] = t;
    }    
    vector<vector<Pll>> graph(n);
    sort(all(xy),
    [](const auto &a, const auto &b){
        return a.m_x < b.m_x;
    });
    rep(i,n-1){
        node from = xy[i];
        node to = xy[i+1];
        graph[from.m_id].emplace_back(Pll(to.m_id,to.m_x - from.m_x));
        graph[to.m_id].emplace_back(Pll(from.m_id,to.m_x - from.m_x));
    }
    sort(all(xy),
    [](const auto &a, const auto &b){
        return a.m_y < b.m_y;
    });
    rep(i,n-1){
        node from = xy[i];
        node to = xy[i+1];
        graph[from.m_id].emplace_back(Pll(to.m_id,to.m_y - from.m_y));
        graph[to.m_id].emplace_back(Pll(from.m_id,to.m_y - from.m_y));
    }

    // プリム法
    vector<ll> mincost(n,INF);
    bool used[n];
    fill(used, used + n, false);
    mincost[0] = 0;
    ll res = 0;
    ll cnt = 0;
    auto comp = [](Pll a, Pll b){
        return a.second > b.second;
    };
    priority_queue<Pll, vector<Pll>, decltype(comp)> pq(comp);
    pq.push(Pll(0,0));
    while(1){
        assert(cnt <= n);
        cnt++;
        ll v = -1;
        // rep(u,n){
        //     if(!used[u]){
        //         if(v == -1 || mincost[u] < mincost[v])v = u;
        //     }
        // }
        while(pq.size()){
            Pll temp = pq.top();pq.pop();
            if(!used[temp.first]){
                v = temp.first;
                break;
            }
        }
        debug(v);
        if(v == -1)break;
        used[v] = true;
        res += mincost[v];
        for(auto i : graph[v]){
            ll to = i.first;ll cost = i.second;
            // mincost[to] = min(mincost[to], cost);
            if(cost < mincost[to]){
                pq.push(Pll(to,cost));
                mincost[to] = cost;
            }
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 17012
a=input()
sum=0
if a[0]=='R':
    sum=1
    if a[0]==a[1]:
        sum=2
        if a[1]==a[2]:
            sum=3
else :
    if a[1]=='R':
        sum=1
        if a[2]==a[1]:
            sum =2
    elif a[2]=='R':
        sum=1
print (sum)

    



Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define pb push_back
#define mp make_pair
#define f first
#define s second
int cnt[300];
int main()
{
	int n,i,x,y;
	cin>>n;
	vector<vector<ll>>vec(4,vector<ll>(n));
	for(i=0;i<n;i++)
	{
		cin>>x>>y;
        vec[0][i]=x+y;
        vec[1][i]=x-y;
        vec[2][i]=y-x;
        vec[3][i]=-y-x;
	}
	for(i=0;i<4;i++)
	{
		sort(vec[i].begin(), vec[i].end());
	}
	ll ans=-1e18;
	for(i=0;i<4;i++)
	{
		ans=max(ans,vec[i][n-1]-vec[i][0]);
	}
	cout<<ans<<endl;
	return 0;
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define mod 1000000007LL
#define maxn 100005
#define IN freopen("C.in","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define INF 1000000000
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<int, int> pi;

#define maxn 1000005

i64 dp[maxn] ;

int main()
{
    i64 i , j , k , l , m , n ;

    i64 ret = 0LL ;

    dp[0] = 1LL ;
    for(i64 i =1 ; i<=1000000 ; i++)
    {
        ret =(ret+dp[i-1])%mod ;
        dp[i] = ret ;
        if( i>=2 ) dp[i] = (dp[i]-dp[i-2])%mod ;
    }

    scanf("%lld",&n) ;

    i64 ans = dp[n] ;
    for(i=0 ; i<n ; i++)
    {
        if( i==n-1 ) ans = ( ans + dp[i]*(n-1) )%mod ;
        else ans = ( ans + dp[i]*( ( i+1 + (n-1)*(n-1))%mod  ) )%mod ;
    }

    printf("%lld\n", (ans%mod+ mod)%mod ) ;

    return 0 ;
}


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

using namespace std;

//DP用
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;
}

const long long INF = 1LL << 60;

int main() {
    int n,m;
    cin >> n >> m;
    int a;
    vector<int> oks(n+1,true);
    vector<long long int> dp(n+1);
    for(int i = 0; i < m; i++) {
        cin >> a;
        oks[a] = false;
    }
    dp[0] = 1;
    for(int now = 0; now < n; ++now) {
        for(int next = now+1; next <= min(n,now+2); ++next) {
            if(oks[next]) {
                dp[next] += dp[now];
                dp[next] %= 1000000007;
            }
        }
    }
    cout << dp[n];
    return 0;
}


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

int main(){
  constexpr char sheep= 'S';
  constexpr char wolf = 'W';
  const vector<pair<char, char>> search= {make_pair(sheep, sheep)
                                         ,make_pair(sheep, wolf )
                                         ,make_pair(wolf , sheep)
                                         ,make_pair(wolf , wolf ) };
  int N;
  string S;
  cin >> N >> S;

  auto flip= [&](char animal){
    char ret= (animal==sheep) ? wolf
                              : sheep;
    return ret;
  };
  auto guess= [&](string cand, int pivot){
    int opponent= (pivot==0) ? 1
                             : pivot- 1;
    char ret= (cand.at(pivot)==sheep) ? (S.at(pivot)=='o') ? cand.at(opponent)
                                                           : flip(cand.at(opponent))
                                      : (S.at(pivot)=='o') ? flip(cand.at(opponent))
                                                           : cand.at(opponent)      ;
    return ret;
  };

  string ans= "-1";
  for(auto [a0,a1]:search){
    string cand= string(N, 'X');
    cand.at(0)= a0;
    cand.at(1)= a1;
    char guess_back= guess(cand, 0);
    for(int pivot=1; pivot+1 < N; pivot++){
      cand.at(pivot+1)= guess(cand, pivot);
    }
    char guess_head= guess(cand, N-1);

    if(guess_back==cand.back() && guess_head==cand.at(0)){
      ans= cand;
      break;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3696
#include<stdio.h>
void trace(int A[],int N){
  int i;
 
  for(i=0;i<N;i++){
    if(i>0)printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}

void swap(int *x,int *y)
{
  int a;
  a=*x;
  *x=*y;
  *y=a;
}

int main(){
  int A[100];
  int i,j,n,N;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&A[i]);

  for(i=0,N=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(A[j]<A[j-1]){
	swap(&A[j],&A[j-1]);
	N++;
      }
    }
  }
  trace(A,n);
  printf("%d\n",N);
  return 0;
}

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

using namespace std;

#define x first
#define y second
#define NMAX 100005

int n, t[NMAX], ans[NMAX];
char s[NMAX];

void check(int t1, int t2){
    ans[1] = t1;
    ans[2] = t2;
    for(int i = 2; i < n; i++){
        ans[i + 1] = (ans[i - 1] ^ t[i] ^ ans[i]);
    }
    if(ans[1] == (ans[n - 1] ^ t[n] ^ ans[n]) && (ans[2] == (ans[n] ^ t[1] ^ ans[1]))){
        for(int i = 1; i <= n; i++)
            printf("%c", (ans[i] ? 'W' : 'S'));
        printf("\n");
        exit(0);
    }
}

int main (){
    
    scanf("%d\n",&n);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++)
        t[i] = (s[i] == 'o' ? 0 : 1);
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            check(i,j);
    printf("-1\n");
    
    return 0;
}



Measured memory_bytes: 1152
//***___*********___*****___****___***___*********//
/*  |   \  |   | |   |   |   \  |     |     |   |  **
/*  |   |  |   | |___|   |   _  |__   |___  |___|  **
/*  |   |  |   | |   \   |  | | |         | |   |  **
/*  |___/  |___| |    \  |__| | |___  ____| |   |  **
//*************************************************/
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define ff double
#define endl "\n"
#define M 1000000007
#define forever while(1)
#define ll long long
#define pb push_back
#define vi vector<long long>
#define mii map<int,int>
#define pii pair<int,int>
#define test ll t;cin>>t;while(t--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define buffer cin.ignore(numeric_limits<streamsize>::max(),'\n');
using namespace std;
void fastscan(int &x)
{
        bool neg=false;
        register int c;
        x =0;
        c=getchar();
        if(c=='-')
        {
            neg = true;
            c=getchar();
        }
        for(;(c>47 && c<58);c=getchar())
            x = (x<<1) + (x<<3) +c -48;
        if(neg)
            x *=-1;
}
int main()
{
     string str;
     ll n;
     cin>>n;
     cin>>str;
     ll ans=0;
     for(int i=0;i<n-1;i++)
     {
         if(str[i]!=str[i+1])
            ans++;
     }
     cout<<ans+1<<endl;
  return 0;
}



Measured memory_bytes: 512
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ
        self.blocksize = [0] * N

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def block(self, x, y):
        if not self.has_same_parent(x, y):
            return
        self.blocksize[x] += 1
        self.blocksize[y] += 1

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

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


N, M, K = MI()
uf = UnionFind(N)
nl = [set() for _ in range(N)]
for _ in range(M):
    A, B = MI()
    nl[A - 1].add(B - 1)
    nl[B - 1].add(A - 1)
    uf.unite(A - 1, B - 1)

for _ in range(K):
    C, D = MI()
    uf.block(C - 1, D - 1)


ans = []
for i in range(N):
    a = uf.component_size(i) - len(nl[i]) - uf.blocksize[i] - 1
    ans.append(str(a))
print(' '.join(ans))

Measured memory_bytes: 126368
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const long long mo=1000000007;
const int maxn=200010;

int n,m,x[maxn],y[maxn],f[maxn];
int fa[maxn],dep[maxn];
int tot,nex[maxn*2],las[maxn*2],tov[maxn*2];
bool bz[maxn];
long long ans,X,sum,v[maxn],z[maxn],val[maxn*2];

void insert(int x,int y,long long z)
{
	tot++;
	tov[tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
	val[tot]=z;
}

void qsort(int l,int r)
{
	int i=l;int j=r;
	int m=z[(i+j)/2];
	while (i<=j)
	{
		while (z[i]<m) i++;
		while (z[j]>m) j--;
		if (i<=j)
		{
			swap(x[i],x[j]);
			swap(y[i],y[j]);
			swap(z[i],z[j]);
			i++;j--;
		}
	}
	if (l<j) qsort(l,j);
	if (r>i) qsort(i,r); 
}

int getfather(int x)
{
	if (f[x]==x) return x;
	f[x]=getfather(f[x]);
	return f[x];
}

long long qsm(long long a,long long b)
{
	long long t=1;
	long long y=a;
	while (b>0)
	{
		if ((b&1)==1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}

void dfs(int x,int ff)
{
	fa[x]=ff;
	dep[x]=dep[ff]+1;
	for (int i=las[x];i;i=nex[i])
	{
		if (tov[i]!=ff)
		{
			dfs(tov[i],x);
			v[tov[i]]=val[i];
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	scanf("%lld",&X);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%lld",&x[i],&y[i],&z[i]);
	}
	for (int i=1;i<=n;i++) f[i]=i;
	qsort(1,m);
	for (int i=1;i<=m;i++)
	{
		int xx=getfather(x[i]);
		int yy=getfather(y[i]);
		if (xx!=yy)
		{
			f[xx]=yy;
			bz[i]=true;
			sum+=z[i]; 
			insert(x[i],y[i],z[i]);
			insert(y[i],x[i],z[i]);
		}
	}
	dfs(1,0);
	
	for (int i=1;i<=m;i++)
	{
		if (!bz[i])
		{
			int xx=x[i];
			int yy=y[i];
			long long zd=0;
			while (xx!=yy)
			{
				if (dep[xx]>dep[yy])
				{
					zd=max(zd,v[xx]);
					xx=fa[xx];
				}
				else
				{
					zd=max(zd,v[yy]);
					yy=fa[yy];
				}
			}
			z[i]=z[i]-zd;
		}
	}
	
	if (sum>X)
	{
		printf("0\n");
	}
	else
	if (sum==X)
	{
		long long gs=0;
		for (int i=1;i<=m;i++)
		{
			if (!bz[i])
			{
				if (z[i]==0) gs++;
			}
		}
		ans=(qsm(2,gs+n-1)-2+mo)%mo;
		ans=ans*qsm(2,m-gs-n+1)%mo;
//		ans=(ans+(2*(qsm(2,gs)-1)%mo)%mo)%mo;
//		printf("%0\n");
		printf("%lld\n",ans);
	}
	else
	{
		int op=X-sum;
		long long gsa=0;long long gsb=0;long long gsc=0;
		for (int i=1;i<=m;i++)
		{
			if (!bz[i])
			{
				if (z[i]<op)
				{
					gsa++;
				}
				else
				if (z[i]==op)
				{
					gsb++;
				}
				else 
				{
					gsc++;
				}
			}
		}
		if (gsb==0)
		{
			printf("0\n");
			return 0;
		}
		else
		{
			ans=2;
			ans=ans*((qsm(2,gsb)-1+mo)%mo)%mo;
			ans=ans*qsm(2,gsc)%mo;
			printf("%lld\n",ans);
		}
	}
}













Measured memory_bytes: 12544
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC164
{
    class C
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var S = new string[N];
            //Dictionary<string, int> dict = new Dictionary<string, int>();
            for (int i = 0; i < N; i++)
            {
                S[i] = Console.ReadLine();
            }

            Console.WriteLine(S.Distinct().Count());

        }
    }
}


Measured memory_bytes: 48104
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
//const ll MOD = 1e9+7;
//const double pi = 3.14159265358979;
using vl = vector<ll>;
# define rep(i, n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((ll)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((ll)(n)); i>0; --i)
# define all(x) (x).begin(), (x).end()

ll n;
ll Main() {
    cin >> n;
    string c;
    ll cnt = 0;
    cin >> c;
    ll ptrL = -1;
    rep(i,n) {
        ptrL = i;
        ll ptrR = n-cnt-1;
        if(c[i]=='W') {
            while(ptrR >= 0) {
                if(ptrL >= ptrR) {
                    cout << cnt << endl;
                    return 0;
                }
                if(c[ptrR]=='R') {
                    c[ptrR] = 'W';
                    c[i] = 'R';
                    cnt++;
                    break;
                } else {
                    ptrR--;
                }
            }
        }
    }
    
    cout << cnt << endl;
    return 0;
}
 
int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3676
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=5e3+10;
const int M=220;
ll a[N],b[N][M],cnt[N][N];
int n,m,S[N],top,L[N][M],R[N][M];
inline int rd(){
	int x=0;int f=1;char s=getchar();
	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
	while(isdigit(s)) x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return x*f;
}
int main(){
	n=rd();m=rd();a[0]=a[1]=0;
	for(int i=2;i<=n;i++) a[i]=a[i-1]+1ll*rd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) b[i][j]=1ll*rd();
	for(int j=1;j<=m;j++){
		top=0;
		for(int i=1;i<=n;i++){
			while(top && b[S[top]][j] <b[i][j] ) top--;
			L[i][j]=top?S[top]+1:1;
			S[++top]=i;
		}
		top=0;
		for(int i=n;i>=1;i--){
			while(top && b[S[top]][j]<b[i][j] ) top--;
			R[i][j]=top?S[top]-1:n;
			S[++top]=i;
		}
		for(int i=1;i<=n;i++){
			cnt[L[i][j]][i]+=b[i][j];
			cnt[L[i][j]][R[i][j]+1]-=b[i][j];
			cnt[i+1][i]-=b[i][j];
			cnt[i+1][R[i][j]+1]+=b[i][j];
		}
	}	
	ll ans=0;
	for(int i=1;i<=n;i++){
		
		for(int j=1;j<=n;j++) cnt[i][j]+=cnt[i][j-1];
		for(int j=1;j<=n;j++) cnt[i][j]+=cnt[i-1][j];
		for(int j=i;j<=n;j++) ans=max(ans,cnt[i][j]-a[j]+a[i]); 
	} 
	printf("%lld\n",ans); 
	return 0;
}

Measured memory_bytes: 213632