akhauriyash/Code-Regression huggingface dataset:
import math
X, K, D = map(int, input().split())
ans = 0
if K * D < abs(X):
    ans = abs(X) - K * D
elif (K - math.floor(abs(X) / D)) % 2 == 0:
    ans = abs(X) - (math.floor(abs(X) / D)) * D
else:
    ans = abs(X) - (math.floor(abs(X) / D)) * D - D

print(abs(int(ans)))


Measured memory_bytes: 9148
//============================================================================
// Name        : ITP_1_2_A.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int a,b;
	cin >> a >> b;
	if (a==b) {
		cout << "a == b" << endl;
	} else if (a > b) {
		cout << "a > b" << endl;
	} else {
		cout << "a < b" << endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
pair<double,int> Pair;
   
bool eq(double a,double b){
  return ( fabs(a-b) < eps );
}
   
struct Point{
  double x,y,z;     
  Point operator + (Point p){ return (Point){x+p.x,y+p.y,z+p.z}; }     
  Point operator - (Point p){ return (Point){x-p.x,y-p.y,z-p.z}; }     
  Point operator * (double k){ return (Point){x*k,y*k,z*k}; }
};

typedef Point Vector;
   
   
void pr(Point p){
  printf("%.5f %.5f %.5f\n",p.x,p.y,p.z);
}
   
double norm(Point p){
  return p.x*p.x+p.y*p.y+p.z*p.z;
}
   
double abs(Point p){
  return sqrt( p.x*p.x + p.y*p.y + p.z*p.z );
}
double dot(Point a,Point b){
  return a.x*b.x + a.y*b.y + a.z*b.z;
}
   
Point cross(Point a,Point b){
  double nx=a.y*b.z-b.y*a.z;
  double ny=a.z*b.x-b.z*a.x;
  double nz=a.x*b.y-b.x*a.y;
  return (Point){nx,ny,nz};
}

// line a,b point c
Point project(Point a,Point b,Point c){
  double t=dot(b-a,c-a)/abs(b-a)/abs(b-a);
  return a+(b-a)*t;
}

// segment a,b point c
double dist(Point a,Point b,Point c){
  if( dot(c-a,b-a) < 0 ) return abs(c-a);
  if( dot(c-b,a-b) < 0 ) return abs(c-b);
  return abs(c-project(a,b,c));
}

bool check(Point p,double r,Point a,Point b){
  double A=abs(p-a),B=abs(p-b),C=dist(a,b,p);
  if(r<A&&r<B&&C<r)return true;
  if(A<r&&r<B)return true;
  if(r<A&&B<r)return true;
  return false;
}

int m,t,cnt=0;
double PI=acos(-1);

bool solve(double x){
  x/=10.0;
  double R=380000;
  double nm=(double)m+(x/2500000.0*360.0);
  nm=fmod(nm,360.0);
  
  double px=cos(nm/360.0*PI*2.0)*R,py=sin(nm/360.0*2.0*PI)*R,pz=0;
  
  nm=(double)x/(120.0*60.0)*360.0;
  nm=fmod(nm,360.0);
  
  double npz=pz+cos(nm/360.0*PI*2.0)*1900.0;
  double npx=px-sin(nm/360.0*PI*2.0)*1900.0;
  
  return check( (Point){px,py,pz} , 1800.0 , (Point){0.0,0.0,0.0} , (Point){npx,py,npz} );
}

int main(){
  cin>>m>>t;
  for(int i=0;i<t*600;i++)if(solve(i))cnt++;
  printf("%.8f\n",(double)cnt/600.0);
  return 0;
}

Measured memory_bytes: 1260
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

int query(int a, int b, int c, int d){
  int res;
  cout << "? " << a << " " << b << " " << c << " " << d << endl;
  cin >> res;
  return res;
}


ll power(int k,int n,int M){
  if(n==0) return 1;
  if(n==1) return (ll)k;
  
  ll ret = power(k,n/2,M);
  
  ret=(ret*ret)%M;
  
  if(n%2==1)
    ret=(ret*k)%M;
  
  return ret;
}


int main(){
  int h,w,n,K;
  ll ans = 0;

  cin >> h >> w >> n >> K;

  for(int i=0;i<50;i++){
    for(int j=0;j<5;j++){
      int res;
      res = query(i,j*10,i,j*10+9);

      if(res > 0){
        int res2;
        res2 = query(i,j*10,i,j*10+4);

        if(res2 > 0){
          for(int k=0;k<5;k++){
            res2 = query(i,j*10+k,i,j*10+k);

            if(res2 > 0) ans = (ans + res2 * power(2,i*w+(j*10+k),K))%K;
          }
        }

        res2 = query(i,j*10+5,i,j*10+9);

        if(res2 > 0){
          for(int k=5;k<10;k++){
            res2 = query(i,j*10+k,i,j*10+k);

            if(res2 > 0) ans = (ans + res2 * power(2,i*w+(j*10+k),K))%K;
          }
        }
        
      }
    }
  }

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


Measured memory_bytes: 724
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
using Graph=vector<vector<int>>;
template<class T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main(){
    int a;
    cin>>a;
    cout<<a+a*a+a*a*a<<endl;
}

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

int main(){
  vector<vector<int>> c(3,vector<int>(3));
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      cin >> c.at(i).at(j);
    }
  }
  bool can = false;
  bool can2 = false;
  int a1,a2,a3,b1,b2,b3;
  for(int i=0; i<=c.at(0).at(0); i++){
    a1 = i;
    b1 = c.at(0).at(0) -a1;
    b2 = c.at(0).at(1) -a1;
    b3 = c.at(0).at(2) -a1;
    if(b1-c.at(1).at(0) == b2-c.at(1).at(1)
    && b1-c.at(1).at(0) == b3-c.at(1).at(2)
    && b1-c.at(2).at(0) == b2-c.at(2).at(1)
    && b1-c.at(2).at(0) == b3-c.at(2).at(2)){
      can = true;
      break;
    }
  }
  if(can){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H


dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for x in range(i):
            dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i] - H[x]))


ans = float('inf')
for i in range(N + 1):
    ans = min(ans, dp[i][max(0,  N - K)])

print(ans)


Measured memory_bytes: 47888
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long tot = 0;
		int v = 0;
		for(int i=0;i<N;i++){
			tot += B[i];
			v |= A[i];
		}
		
		if(v <= K){
			Console.WriteLine(tot);
			return;
		}
		
		long min = long.MaxValue;
		bool[] del = new bool[N];
		for(int j=30;j>=0;j--){
			int kj = (K >> j) & 1;
			int vj = (v >> j) & 1;
			
//Console.WriteLine("j:{0},kj:{1},vj:{2}",j,kj,vj);
			if(kj == 0 && vj == 0) continue;
			if(kj == 1 && vj == 0){
				//ここまでひきわけにできていれば ここで決着がつく．
				long t = 0;
				for(int i=0;i<N;i++) if(del[i]) t += B[i];
				min = Math.Min(min, t);
			}
			if(kj == 1 && vj == 1){
				//ここまで引き分けにしてきた分プラス今回分で決着をつけられる
				long t = 0;
				for(int i=0;i<N;i++) if(del[i] || ((A[i] >> j) & 1) == 1) t += B[i];
				min = Math.Min(min, t);
			}
			if(kj == 0 && vj == 1){
				//ここは引き分けにして下位で決着をつける
				for(int i=0;i<N;i++) if(((A[i] >> j) & 1) == 1) del[i] = true;
			}
		}
		
		// 完全に引き分けにできた場合もOK
		long t0 = 0;
		for(int i=0;i<N;i++) if(del[i]) t0 += B[i];
		min = Math.Min(min, t0);
		
		Console.WriteLine(tot - min);
		
	}
	int N,K;
	int[] A;
	long[] B;
	public Sol(){
		var d = ria();
		N = d[0]; K = d[1];
		A = new int[N];
		B = new long[N];
		for(int i=0;i<N;i++){
			d = ria();
			A[i] = d[0];
			B[i] = d[1];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 17316
import java.util.Scanner;
public class Main {
@SuppressWarnings("resource")
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	long N=sc.nextLong();
	long A=sc.nextLong();
	long B=sc.nextLong();
	if((B-A)%2==0) {
		System.out.println((B-A)/2);
	}else {
		if(N-B<=A-1) {
			System.out.println((2*N-B-A)/2+1);
		}else {


			System.out.println((A+B-2)/2+1);


		}

	}


	}
}

Measured memory_bytes: 23380
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  double n, m, d;
  cin >> n >> m >> d;
  double ans = (n-d)/n*(m-1)/n;
  if (d) ans *= 2;
  cout << fixed << setprecision(6) << ans << endl;
  return 0;
}

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

int N;
string s;
int white[222222];
int black[222222];

signed main() {
  cin >> N >> s;
  rep (i, N) {
    white[i] = (s[i] == '.');
    black[i] = (s[i] == '#');
  }

  repp (i, 1, N) {
    black[i] += black[i-1];
  }

  for (int i = N-2; i >= 0; i--) {
    white[i] += white[i+1];
  }
  // print1(white, white+N+1);
  // print1(black, black+N+1);

  int ans = 1e18;
  for (int i = 0; i < N; i++) {
    int t = black[i] + white[i+1];
    chmin(ans, t);
  }

  int hoge = count(all(s), '.');

  cout << min(ans, hoge) << endl;

  return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int x;
    cin>>x;
    cout<<(1-x)<<"\n";
	return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
    int a,b;
    
    scanf("%d %d",&a,&b);
    if(a==b){
        printf("a == b");
    }else if(a<b){
        printf("a < b");
    }else if(a>b){
        printf("a > b");
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2040
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {

    int[] antena = new int[5];
    int k = 0;

    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      antena[0] = Integer.parseInt(br.readLine());
      antena[1] = Integer.parseInt(br.readLine());
      antena[2] = Integer.parseInt(br.readLine());
      antena[3] = Integer.parseInt(br.readLine());
      antena[4] = Integer.parseInt(br.readLine());
      k = Integer.parseInt(br.readLine());
    } catch (IOException e) {
        e.printStackTrace();
        System.exit(1);
    }

    boolean result = true;
    parent:
    for (int i = 0; i < antena.length - 1; i++) {
      for (int j = i + 1; j <= antena.length-1; j++) {
        if (k < antena[j] - antena[i]) {
          result = false;
          break parent;
        }
      }
    }

    if (result) {
      System.out.print("Yay!");
    } else {
      System.out.print(":(");
    }

  }
}


Measured memory_bytes: 21204
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
using namespace std;
using ll = long long;

int main()
{
    string s;
    cin >> s;
    map<char,int> c_map;
    rep(i, 0, s.size())
        c_map[s[i]]++;
    
    int ans = 2 * min(c_map['1'], c_map['0']);
    cout << ans << endl;
    return 0;
}

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

struct state{ int lx,ly,rx,ry; };

int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};

bool dp[50][50][50][50];

int main(){
	int h,w;
	while(cin >> w >> h,h){
		int lx,ly,rx,ry;
		for(int i = 0;i < 50;i++){
			for(int j = 0;j < 50;j++){
				for(int k = 0;k < 50;k++){
					for(int l = 0;l < 50;l++) dp[i][j][k][l] = false;
				}
			}
		}
		bool flag = false;
		string lf[50],rf[50];
		for(int i = 0;i < h;i++){
			cin >> lf[i] >> rf[i];
			for(int j = 0;j < w;j++){
				if(lf[i][j] == 'L'){
					lx = i;
					ly = j;
				}
				if(rf[i][j] == 'R'){
					rx = i;
					ry = j;
				}
			}
		}
		queue<state> que;
		que.push({lx,ly,rx,ry});
		while(!que.empty()){
			state s = que.front();que.pop();
			if(dp[s.lx][s.ly][s.rx][s.ry]) continue;
			//cout << s.lx << " " << s.ly << " " << s.rx << " " << s.ry << endl;
			if(lf[s.lx][s.ly] == '%' && rf[s.rx][s.ry] == '%') flag = true;
			dp[s.lx][s.ly][s.rx][s.ry] = true;
			for(int i = 0;i < 4;i++){
				int nlx = s.lx + dx[i],nly = s.ly + dy[i],nrx = s.rx + dx[i],nry = s.ry + dy[(i + 2) % 4];
				bool move = false;
				if(nlx >= 0 && nlx < h && nly >= 0 && nly < w && lf[nlx][nly] != '#') move = true;
				else{
					nlx = s.lx;
					nly = s.ly;
				}
				if(nrx >= 0 && nrx < h && nry >= 0 && nry < w && rf[nrx][nry] != '#') move = true;
				else{
					nrx = s.rx;
					nry = s.ry;
				}
				if((lf[nlx][nly] == '%') ^ (rf[nrx][nry] == '%')) continue;
				if(move && !dp[nlx][nly][nrx][nry]){
					que.push({nlx,nly,nrx,nry});
				}
			}
		}
		if(flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 10864
N = int(input())
matrix = [[0 for i in range(N)] for j in range(N)]
for n in range(N):
    A = int(input())
    for a in range(A):
        array = [int(i) for i in input().split()]
        matrix[n][array[0]-1] = 1 if array[1] == 1 else -1
l = [True,False]
from itertools import product
for pattern in product(l,repeat=N):
    able = True
    for i,p in enumerate(pattern):
        if p:
            for a,b in zip(matrix[i],pattern):
                if (b==True and a==-1) or (b==False and a == 1):
                    able = False
                    break
            if able == False:
                break
        else:
            pass
    if able == True:
        break
print(sum(pattern))

Measured memory_bytes: 46576
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;


public class Main {
    
    public static void main(String[] args) throws IOException {
        Deque<Long> stack = new ArrayDeque<>();
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        
        String s = buf.readLine();
        String[] splited = s.split(" ", 0);
      
        //????????????????????¨??£?????????.(?¨?????????????second op first)??¨???
        long first;
        long second;
        for (String currentString : splited) {
            if ("+".equals(currentString)) {
                first = stack.removeFirst();
                second = stack.removeFirst();
                stack.addFirst((second + first));
            } else if ("-".equals(currentString)) {
                first = stack.removeFirst();
                second = stack.removeFirst();
                stack.addFirst((second - first));               
            } else if ("*".equals(currentString)) {
                first = stack.removeFirst();
                second = stack.removeFirst();
                stack.addFirst((second * first));            
            } else if ("/".equals(currentString)) {
                first = stack.removeFirst();
                second = stack.removeFirst();
                stack.addFirst((second / first));
            } else {
                stack.addFirst(Long.parseLong(currentString));
            }
        }
        System.out.println(stack.removeFirst());
    }
}

Measured memory_bytes: 24496
n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)

for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1

ans = max(count)

if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

Measured memory_bytes: 189836
import std.stdio;
import std.algorithm;
import std.math;
import std.conv;
import std.string;

T readNum(T)(){
  return readStr.to!T;
}

T[] readNums(T)(){
  return readStr.split.to!(T[]);
}

string readStr(){
  return readln.chomp;
}

void main(){
  auto nm = readNums!int;
  int n = nm[0], m = nm[1];

  bool[] broken = new bool[](n);
  foreach(i; 0 .. m){
    broken[readNum!size_t - 1] = true;
  }

  ulong[] ans = new ulong[](n);
  if(!broken[0]) ans[0] = 1;
  if(!broken[1]) ans[1] = ans[0] + 1;
  foreach(i; 2 .. n){
    if(!broken[i]) ans[i] = (ans[i-1] + ans[i-2]) % 1_000_000_007;
  }

  writeln(ans[$-1]);
}


Measured memory_bytes: 2940
import java.util.*;
public class Main {
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		int number=sc.nextInt(); long res=0;
		for(int i=1;i<=number;i++) {
			if(i%5!=0 && i %3!=0)
			{
				res+=i;
			}
		}
		System.out.println(res);
	}

}

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

#define N (1<<17)
#define ll long long
#define ld long double
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define pii pair<ll, ll>
#define pll pair<long long, long long>
#define F first
#define S second

using namespace std;

int main () {
	int n, z, w;
	cin>>n>>z>>w;
	int a[n + 1];
	int mx[n + 1];
	for (int i = 1; i <= n; i++) {
		cin>>a[i];
		mx[i] = a[i];
	}
	int ans = abs(a[n] - w);
	for (int i = n - 1; i >= 1; i--) {
		int mi = 1000000001;
		for (int j = i + 1; j <= n; j++) {
			if (j == n) mi = min(mi, abs(a[j] - a[i]));
			else mi = min(mi, abs(a[j] - a[n]));
		}
		ans = max(ans, mi);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int price;      /* price per one drink */
    int n_drink;    /* number of drink */
} Shop;

int compare_shop ( const void *a, const void *b) {
    Shop *a_, *b_;

    a_ = (Shop*)a;
    b_ = (Shop*)b;

    return a_->price - b_->price;
}

int main (void) {
    int i;
    int n_shop, n_drink;
    scanf("%d%d", &n_shop, &n_drink);

    Shop shop[n_shop];
    for ( i=0; i<n_shop; i++ )
        scanf("%d%d", &shop[i].price, &shop[i].n_drink);

    qsort(shop, n_shop, sizeof(Shop), compare_shop);

    int bought_drink=0;
    long long sum_price = 0;
    for ( i=0; i<n_shop; i++ ) {
        if ( bought_drink + shop[i].n_drink >= n_drink ) {
            /* enough drink */
            sum_price += (long long)shop[i].price * (n_drink - bought_drink);
            bought_drink = n_drink;
            break;
        }
        else {
            /* buy all drink in this shop */
            bought_drink += shop[i].n_drink;
            sum_price += (long long)shop[i].price * shop[i].n_drink;
        }
    }

    printf("%lld\n", sum_price);
    return EXIT_SUCCESS;
}


Measured memory_bytes: 1788
#include <stdio.h>

int main() {
    int n, p[101], m[101][101], i, j, l, k, t;
    
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d %d", &p[i], &p[i+1]);
    }
    
    for (i = 1; i <= n; ++i) {
        m[i][i] = 0;
    }
    
    for (l = 2; l <= n; ++l) {
        for (i = 1; i <= n - l + 1; ++i) {
            j = i + l - 1;
            m[i][j] = m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j] ;
            for (k = i + 1 ; k <= j - 1; ++k) {
                t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if (m[i][j] > t) m[i][j] = t;
            }
        }
    }
    
    printf("%d\n", m[1][n]);
    return 0;
}

Measured memory_bytes: 1820
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]


N,K,L = map(int, input().split())
road_list = []
for i in range(K):
    road_list.append([int(x) for x in input().split()])
train_list = []
for i in range(L):
    train_list.append([int(x) for x in input().split()])
    
road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.unite(road_list[i][0], road_list[i][1])
    
for i in range(L):
    train.unite(train_list[i][0], train_list[i][1])
    
R = [i for i in range(N+1)]
T = [i for i in range(N+1)]

for i in range(1, N+1):
    R[i] = road.find_root(i)
    T[i] = train.find_root(i)
    
pair = [0 for i in range(N+1)]
for i in range(1, N+1):
    pair[i] = (R[i], T[i])
    
dic = {}
for i in range(1, N+1):
    if pair[i] in dic:
        dic[pair[i]] += 1
    else:
        dic[pair[i]] = 1
        
for i in range(1, N+1):
    print(dic[pair[i]])

Measured memory_bytes: 83408
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
const ll INF = (ll)1e18 + 1;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int x,y; cin >> x >> y;
    
    cout << x+y/2 << ln;
    return 0;
}

Measured memory_bytes: 256
//#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#include <atcoder/all>
//using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//using i128 = __int128_t;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
constexpr char ln = '\n';
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
inline int topbit(int x) {return x == 0 ? -1 : 31-__builtin_clz(x);}
inline int topbit(long long x) {return x == 0 ? -1 : 63-__builtin_clzll(x);}
inline int botbit(int x) {return x == 0 ? 32 : __builtin_ctz(x);}
inline int botbit(long long x) {return x == 0 ? 64 : __builtin_ctzll(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
inline int kthbit(long long x, int k) {return (x>>k)&1;}
inline void print() {cout << "\n";}
template<class T>
inline void print(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cout << *itr << " ";
    print();
}
template<class T, class... Args>
inline void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
#ifdef MINATO_LOCAL
#define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
inline void debug() {cerr << endl;}
template<class T>
inline void debug(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cerr << *itr << " ";
    debug();
}
template<class T, class... Args>
inline void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
#else
#define dump(x) void(0)
inline void debug() {}
template<class T> inline void debug(const vector<T> &v) {}
template<class T, class... Args> inline void debug(const T &x, const Args &... args) {}
#endif
struct Fast_ios {Fast_ios() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);};} fast_ios;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    int N; cin >> N;
    vector<int> A(N),B(N);
    rep(i,N) cin >> A[i] >> B[i];

    rep(i,N-2) {
        bool ok = true;
        rep(j,3) {
            if (A[i+j]!=B[i+j]) ok = false;
        }
        if (ok) {
            cout << "Yes" << ln;
            return 0;
        }
    }

    cout << "No" << ln;
}



Measured memory_bytes: 3660
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


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

    ll ans = 1;
    while(N > 1){
        ans *= 2;
        N /= 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3604
let quick_sort (a : (int * char * int) array) cmp =
  let partition p r =
    let x = a.(r) in
    let swap i j = let t = a.(i) in a.(i) <- a.(j); a.(j) <- t
    in
    let rec doit i j =
      if j >= r then i
      else begin
        if cmp a.(j) x <= 0 then (swap (i + 1) j; doit (i + 1) (j + 1))
        else doit i (j + 1)
      end
    in
    let i = doit (p - 1) p in
    swap (i + 1) r;
    i + 1
  in
  let rec doit p r =
    if p < r then begin
      let q = partition p r in
      doit p (q - 1);
      doit q r
    end
  in
  doit 0 (Array.length a - 1)

let stable_p (a : (int * char * int) array) n =
  let p (xi, _, xd) (yi, _, yd) = xd = yd && xi > yi
  in
  let rec doit i =
    if i = n - 1 then true
    else if p a.(i) a.(i + 1) then false
    else doit (i + 1)
  in
  doit 0

let () =
  let n = read_int () in
  let a = Array.init n (fun i -> Scanf.scanf "%c %d\n" (fun c d -> (i, c, d))) in
  quick_sort a (fun (_, _, x) (_, _, y) -> compare x y);
  print_endline (if stable_p a n then "Stable" else "Not stable");
  Array.iter (fun (_, c, d) -> Printf.printf "%c %d\n" c d) a

Measured memory_bytes: 8784
k,a,b=map(int,input().split())
if b-a==0:
  print(k+1)
  exit()
if b-a<0:
  print(k+1)
  exit()

if k-(a-1)<=0:
  print(k+1)
  exit()
  
  
ans=k+1
k-=(a-1)
# now=a個
now=a
if k%2==1:
  now+=1
  k-=1
now=now+(b-a)*(k//2)
ans=max(now,ans)

print(ans)
  

Measured memory_bytes: 61852
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    char[] S = sc.next().toCharArray();
    boolean even = S.length % 2 == 0;
    boolean match = S[0] == S[S.length - 1];
    System.out.println((even ^ match) ? "Second" : "First");
  }
}


Measured memory_bytes: 13972
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1e9;

int main() {
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        int x, l; cin >> x >> l;
        v[i] = make_pair(x + l, x - l); 
    } 
    sort(v.begin(), v.end());
    int ans = 0, ran = -INF;
    for (int i = 0; i < n; i++) {
        if (ran <= v[i].second) {
            ans++;
            ran = v[i].first;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in, n) for(int i=0; i<n; i++) cin>>in[i]
#define forout(out, n) for(int i=0; i<n; i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    int n; cin>>n;
    vector<ll> l(n);
    forin(l, n);

    int ans=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(l[i] != l[j] && l[i] != l[k] && l[j] != l[k]){
                    ll tmp=max(l[i], l[j]);
                    ll maxnum=max(tmp, l[k]);
                    ll sum=l[i] + l[j] + l[k];
                    if(maxnum < sum-maxnum) ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
}

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

const int MAX_N = 110000;

int memo[MAX_N]; // memo[i] が i についての答え
int rec(int n) {
	if (n == 0) return 0; // 終端条件
	if (memo[n] != -1) return memo[n]; // すでに探索済みならリターン

	int res = n; // INF の気持ち

	// 1, 6, 6^2, ..., を試す (n を超えない範囲で)
	for (int pow6 = 1; pow6 <= n; pow6 *= 6) res = min(res, rec(n - pow6) + 1);

	// 1, 9, 9^2, ..., を試す (n を超えない範囲で)
	for (int pow9 = 1; pow9 <= n; pow9 *= 9) res = min(res, rec(n - pow9) + 1);

	// メモしながらリターン
	return memo[n] = res;
}

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

	// テーブルを -1 で初期化
	for (int i = 0; i < MAX_N; ++i) memo[i] = -1;
	cout << rec(N) << endl;
}


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

int main() {
  int N, K; cin >> N >> K;
  vector<long> H(N);
  for (long &i : H) {
    cin >> i;
  }

  sort(H.begin(), H.end());
  long sum = 0;
  if (H.size() > K) {
    for (long i = 0; i < H.size()-K; i++) {
      sum += H.at(i);
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 1792
#include <map>
#include <cmath>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    long long x;
    cin >> x;
    cout << (360 / (__gcd(x, 1LL * 360)) * x) / x << endl;
    return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string>
using namespace std;
int main(){
    string a;
    cin>>a;
    bool flag = false;
    for(int i=0; i<3; i++){
        if(a[i]=='7') flag = true;
    }
    if(flag){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}




Measured memory_bytes: 3628
N = int(input())
S = input()
kai = []
alpha = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for n in range(len(S)):
    for num,c in enumerate(alpha):
        if S[n] == c:
            if num + N > 25:
                num = num + N - 26
                kai.append(alpha[num])
                break
            kai.append(alpha[num + N])
            break

print("".join(kai))

Measured memory_bytes: 3188
// 2020-08-15 21:00:00
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  string s;
  cin >> s;
  int ans = 0;
  if(s == "RRR") ans = 3;
  else if(s == "SRR") ans = 2;
  else if(s == "RSR") ans = 1;
  else if(s == "RRS") ans = 2;
  else if(s == "SSR") ans = 1;
  else if(s == "SRS") ans = 1;
  else if(s == "RSS") ans = 1;
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair <int,int> PAIR;
const int maxn = 5e5 + 7;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

int main(){
	int a,b,c,k;
	scanf("%d %d %d %d",&a,&b,&c,&k);
	int cnt = 0;
	while(b<=a){
		b*=2;
		cnt++;
	} 
	while(c<=b){
		c*=2;
		cnt++;
	}
	if(cnt<=k){
		cout<<"Yes\n";
	}else {
		cout<<"No\n";
	}
	return 0;
} 

Measured memory_bytes: 3680
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int n,m;
map<int,int> cnt[100001];
vi vec[100001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int x; cin >> x;
		cnt[x%m][x]++;
	}
	for(int i = 0; i < m; i++)
	{
		for(mit it = cnt[i].begin(); it != cnt[i].end(); it++)
		{
			vec[i].pb(it->se);
		}
	}
	int ans = 0;
	for(int i = 0; 2*i <= m; i++)
	{
		if(i==0||i==m-i)
		{
			int sum=0;
			for(int j = 0; j < vec[i].size(); j++)
			{
				sum+=vec[i][j];
			}
			ans+=sum/2;
		}
		else
		{
			int clr1 = 0;
			int clr2 = 0;
			int sum1 = 0;
			int sum2 = 0;
			for(int j = 0; j < vec[i].size(); j++)
			{
				sum1 += vec[i][j];
				clr1 += (vec[i][j]/2);
			}
			for(int j = 0; j < vec[m-i].size(); j++)
			{
				sum2 += vec[m-i][j];
				clr2 += (vec[m-i][j]/2);
			}
			if(sum1>=sum2)
			{
				int mindel = min(clr1, (sum1-sum2)/2);
				sum1 -= 2*mindel;
				ans += min(sum1,sum2) + mindel;
			}
			else
			{
				int mindel = min(clr2, (sum2-sum1)/2);
				sum2 -= 2*mindel;
				ans += min(sum1,sum2) + mindel;
			}
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 15104
n, m = map(int,input().split())
all_li = []
for _ in range(m):
    li = list(map(int,input().split()))
    all_li.append(li)
#print(all_li)
flag_memo = [False]*n
flag_memo[0] = True
#print(flag_memo)
kazu_li = [1]*n
#print(kazu_li)

for a in all_li:
    kazu_li[a[0]-1] -= 1
    kazu_li[a[1]-1] += 1
    if flag_memo[a[0]-1]:
        flag_memo[a[1]-1] = True
    if kazu_li[a[0]-1] == 0:
        flag_memo[a[0]-1] = False
print(flag_memo.count(True))

Measured memory_bytes: 61912
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

vector<int> to[100005];
int n;

vector<int> dist;
void dfs(int v, int d = 0, int p = -1)
{
    dist[v] = d;
    for (int u : to[v])
    {
        if (u == p)
            continue;
        dfs(u, d + 1, v);
    }
}

vector<int> calcDist(int s)
{
    dist = vector<int>(n);
    dfs(s);
    return dist;
}

int main()
{

    cin >> n;
    int s, t;
    cin >> s;
    cin >> t;
    --s;
    --t;

    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a;
        cin >> b;
        --a;
        --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    vector<int> distS = calcDist(s);
    vector<int> distT = calcDist(t);

    int mx = 0;
    for (int i = 0; i < n; ++i)
    {
        if (distS[i] < distT[i])
        {
            mx = max(mx, distT[i]);
        }
    }
    int ans = mx - 1;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 10744
#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;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1e+9 + 7;
// constexpr int mod = 998244353;

struct edge{
    int from, to, cost;
    edge() = default;
    edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int L;
    cin >> L;
    vector<edge> res;
    vector<int> pow2(21);
    pow2[0] = 1;
    for(int i = 1; i < 21; ++i) pow2[i] = pow2[i - 1] * 2;
    int ub = 0;
    while(pow2[ub + 1] <= L)    ++ub;
    int n = ub;
    for(int i = 0; i < n; ++i)  res.emplace_back(edge(i, i + 1, 0));
    int pos = ub;
    for(int i = 0; i < ub; ++i){
        res.emplace_back(edge(pos - 1, pos, pow2[i]));
        --pos;
    }
    int rest = L - pow2[ub];
    int now = pow2[ub];
    for(int i = 20; i >= 0; --i){
        if((rest >> i) & 1){
            res.emplace_back(edge(0, ub - i, now));
            now += pow2[i];
        }
    }
    int m = res.size();
    cout << n + 1 << " " << m << "\n";
    for(int i = 0; i < m; ++i){
        int from = res[i].from + 1, to = res[i].to + 1, cost = res[i].cost;
        cout << from << " " << to << " " << cost << "\n";
    }
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

class DisjointSet {
 public:
  DisjointSet(int size) : parent_(size), size_(size, 1) {
    for (int i = 0; i < size; ++i) {
      parent_[i] = i;
    }
  }
  int Find(int x) {
    int& p = parent_[x];
    if (p != x) p = Find(p);
    return p;
  }
  void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (Size(x) > Size(y)) std::swap(x, y);
    parent_[x] = parent_[y];
    size_[y] += size_[x];
  }
  int Size(int x) { return size_[Find(x)]; }
  bool Same(int x, int y) { return Find(x) == Find(y); }

 private:
  std::vector<int> parent_, size_;
};

int main() {
  in(ll, n, m);
  vector<ll> a(m), b(m);
  rep(i, m) cin >> a[i] >> b[i];
  vector<ll> ans(m);
  DisjointSet ds(n + 1);
  ll sum = n * (n - 1) / 2;
  for (int i = m - 1; i >= 0; --i) {
    ans[i] = sum;
    if (!ds.Same(a[i], b[i])) {
      dbg(ds.Size(a[i]), ds.Size(b[i]));
      sum -= ds.Size(a[i]) * ds.Size(b[i]);
      ds.Union(a[i], b[i]);
    }
  }
  rep(i, m) out(ans[i]);
}


Measured memory_bytes: 6372
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>
#include <sstream>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);
const ll MD = 1000000007LL;

struct Board{
	vector<vint> v;
    ll _hash;

	Board(vector<vint> v){
		this->v = v;
        _hash = hash();
	}

	vector<Board> transition(){
		vector<Board> ret;

		vint dx{1, 0, -1, 0};
		vint dy{0, 1, 0, -1};

		int x0 = 0, y0 = 0;
		rep(y, 3) rep(x, 3){
			if(v[y][x] == 0) {x0 = x; y0 = y;}
		}

		rep(d, 4){
			int xn = x0 + dx[d];
			int yn = y0 + dy[d];
			if(xn >= 0 && xn < 3 && yn >= 0 && yn < 3){
				vector<vint> vv = v;
				vv[yn][xn] = v[y0][x0];
				vv[y0][x0] = v[yn][xn];
				ret.push_back(Board(vv));
			}
		}

		return ret;
	}

	ll hash() const{
		ll ret = 0;
		ll m = 1;
		rep(y, 3) rep(x, 3){
			ret += v[y][x] * m;
			m *= 10;
		}
        return ret;
	}

	bool operator < (const Board &p) const {
        ll h1 = _hash;
        ll h2 = p._hash;
		return h1 < h2;
	}

	bool operator == (const Board &p) const{
        ll h1 = _hash;
        ll h2 = p._hash;
        return h1 == h2;
	}
};

int main() {
	vector<vint> v0;
	rep(y, 3){
		vint v;
		rep(x, 3) { int n; cin >> n; v.push_back(n);}
		v0.push_back(v);
	}
	Board b0 = Board(v0);

	vector<vint> ve;
	vint ve1{1, 2, 3}; ve.push_back(ve1);
	vint ve2{4, 5, 6}; ve.push_back(ve2);
	vint ve3{7, 8, 0}; ve.push_back(ve3);
	Board be = Board(ve);

	set<Board> S;
	queue<pair<Board, int>> q;

	q.push(make_pair(b0, 0));
    // fprintf(stderr, "%09lld\n", b0.hash());
    // fprintf(stderr, "%09lld\n", be.hash());

	while(true){
		auto p = q.front(); q.pop();
		Board b = p.first;
		int t = p.second;

        S.find(b);
        S.end();
		if(S.find(b) != S.end()) continue;
        S.insert(b);
        // fprintf(stderr, "%09lld %d\n", b.hash(), t);

		if(b == be) {cout << t << endl; return 0;}

		vector<Board> trans = b.transition();
		for(Board bb: trans){
			q.push(make_pair(bb, t+1));
		}
	}

}

Measured memory_bytes: 53516
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://atcoder.jp/contests/abc172/tasks/abc172_b

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static String S, T;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        S = br.readLine();
        T = br.readLine();
        
        for(int i = 0; i < S.length(); i++){
           if(S.charAt(i) != T.charAt(i)){
                result++;
           }
        }
        System.out.println(result);
    }

}

Measured memory_bytes: 36676
class Node():
    p = None
    l = None
    r = None
    char = ''
    count = 0

    def __init__(self, char='', count=0):
        self.char = char
        self.count = count


def solve(n, h):
    if n.char:
        # print('{}:{}'.format(n.char, h))
        return len(h) * n.count
    else:
        ret = 0
        if n.l: ret += solve(n.l, h + '0')
        if n.r: ret += solve(n.r, h + '1')
        return ret


# --------------------
S = input()
C = {}
T = []

for s in S:
    C.setdefault(s, 0)
    C[s] += 1

T = [Node(*x) for x in C.items()]
T.sort(key=lambda x: x.count)

if len(T) == 1:
    n = Node()
    n.l = T.pop(0)
    T.append(n)
else:
    while len(T) != 1:
        n = Node()
        n.l = T.pop(0)
        n.r = T.pop(0)
        n.count = n.l.count + n.r.count
        T.append(n)
        T.sort(key=lambda x: x.count)

print(solve(T[0], ''))


Measured memory_bytes: 5788
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
x, y  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

for n in range(x + 1):
    t = x - n
    k = n

    if 2 * t + 4 * k == y:
        print('Yes')
        break
else:
    print('No')


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

using namespace std;

#define INF (1ll << 62)
#define pb push_back
#define ii pair<int,int>
#define OK cerr <<"OK"<< endl
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define endl '\n'
  
string x;
int d;

int dp[10007][102][2];
int MOD = 1000000007;

int mod(int n) {
    return (n + MOD) % MOD;
}

int f(int ind, int r, int leq) {
    
    if(ind == x.size()) {
        return (r == 0);
    }

    int &ret = dp[ind][r][leq];
    if(ret != -1)
        return ret;

    ret = 0;
    int lim = (leq ? 9 : x[ind] - '0');
    for(int i = 0; i <= lim; i++) {
        ret += f(ind + 1, (r + i) % d, leq | (i < (x[ind] - '0')));
        ret = mod(ret);
    }

    return ret;
}

signed main () {
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  memset(dp, -1, sizeof dp);


  cin >> x;


  cin >> d;

  cout << mod(f(0, 0, 0) - 1) << endl;

}

Measured memory_bytes: 17024