akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def root(self, x):
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if self.size(x) < self.size(y):
            x, y = y, x
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, K, AB, CD):
    f = UnionFind()
    for a, b in AB:
        f.union(a, b)

    direct = defaultdict(int)
    for a, b in AB:
        direct[a] += 1
        direct[b] += 1
    block = defaultdict(set)
    for c, d in CD:
        block[c].add(d)
        block[d].add(c)


    ans = []
    for i in range(1, N+1):
        cand = f.size(i)
        for u in block[i]:
            if f.same(i, u):
                cand -= 1
        cand -= direct[i]
        cand -= 1
        ans.append(cand)
    return ans



def main():
    N, M, K = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(K)]
    print(*slv(N, M, K, AB, CD))

if __name__ == '__main__':
    main()


Measured memory_bytes: 139860
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a,b,c,d;
        String ans = "Yes";
        
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        
        while((a > 0) && (c > 0)){
            
            c -= b;
            if(c <= 0){
                break;
            }
            a -= d;
            if(a <= 0){
                ans = "No";
                break;
            }
        }
        
        System.out.println(ans);
    }
}


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

// Nを入力したあとでN個の要素をもつ配列を入力する
vector<int> input(int N) {
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  return vec;
}

int main() {
  // Nの入力
  int N;
  cin >> N;

  // 受け取る
  vector<int> X;
  X = input(N);

  sort(X.begin(), X.end());
  double sum = 0;

  rep(i,N){
    sum += X.at(i);
  }

  double mid = sum / (double)N + 0.5;
  int P = (int)mid;

  int result = 0;

  rep(i,N){
    result += pow(X.at(i) - P,2);
  }

  cout << result << endl;
}


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

#define STACK_SIZE 1000

class Stack {
    int A[STACK_SIZE];
    int top=0;
public:
    bool empty() {
        return top == 0;
    }
    bool full() {
        return top == STACK_SIZE-1;
    }
    void push(int x) {
        if (full()) {
            return;
        }
        A[++top]=x;
    }
    int pop() {
        if(empty()) {
            return -1;
        }
        return A[top--];
    }
};

int main() {
    Stack S;
    char buf[100];
    int a,b;
    while (scanf("%s", buf) != EOF) {
        if (buf[0] == '+') {
            b=S.pop();
            a=S.pop();
            S.push(a+b);
        }else if (buf[0] == '-') {
            b=S.pop();
            a=S.pop();
            S.push(a-b);
        }else if (buf[0] == '*') {
            b=S.pop();
            a=S.pop();
            S.push(a*b);
        } else {
            S.push(atoi(buf));
        }
    }
    printf("%d\n", S.pop());
    return 0;
}



Measured memory_bytes: 2696
import java.util.Scanner;
 
class Main {
	public static void main(String[] args) {
 
	    Scanner sc = new Scanner(System.in);
	    String S = sc.next();
	    String T = sc.next();
	    
	    if (S.equals(T.substring(0, S.length()))) {
	      System.out.println("Yes");
	    } else {
	      System.out.println("No");
	    }

	  }
}

Measured memory_bytes: 26936
using System;

public class ABC83C{
  
  public static void Main(){
    long x, y;
    
    string[] str = Console.ReadLine().Split(' ');
    x = long.Parse(str[0]);
    y = long.Parse(str[1]);
    
    int cnt = 0;
    long a = x;
    
    while( a <=y ){
      a *= 2;
      cnt++;
    }
    
    Console.WriteLine(cnt);
  }
}

Measured memory_bytes: 13140
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (int i = (int)(x); i < (int)(n); i++)
#define repfr(i, x, n) for (int i = (int)(x)-1; i >= (int)(n); i--)
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
#define INF 1e9
using ll = int64_t;
#define waru 1000000007

std::int64_t gcd(std::int64_t a, std::int64_t b) {
  // a >= b && b != 0
  std::int64_t c;
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
std::int64_t gcd_s(std::int64_t aa, std::int64_t bb) {
  std::int64_t a = max(aa, bb);
  std::int64_t b = min(aa, bb);
  std::int64_t c;
  if (b == 0) {
    return -1;
  }
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
void rle(std::vector<std::pair<char, std::int64_t>> &data, std::string str) {
  char now = str[0];
  std::int64_t count = 0;
  for (std::int64_t i = 0; i < str.size() + 1; i++) {
    if (i == str.size()) {
      data.push_back(make_pair(str[i - 1], count));
      break;
    } else if (now != str[i]) {
      data.push_back(make_pair(now, count));
      now = str[i];
      count = 0;
    }
    count++;
  }

  return;
}

void Main() {
  //自動整形防止用コメント
  string s;
  std::cin >> s;
  std::cout << (s[0] == s[2] ? "Yes" : "No") << '\n';

  return;
}

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


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

int main() {
  string s,t;
  cin>>s>>t;
  int sl=(int)(s.size());
  int tl=(int)(t.size());
  int ans=1000;
  for(int i=0;i<(sl-tl+1);i++){
    int distance=0;
    string sa=s.substr(i,tl);
    for(int j=0;j<tl;j++){
      if(sa.at(j)!=t.at(j))
        distance++;
    }
    ans=min(distance,ans);
  }
  cout<<ans<<endl;
}


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

void solve() {
    map<string, int> keihin;
    int n;
    cin >> n;
    rep(i,n) {
        string s;
        cin >> s;
        keihin[s]++;
    }

    int ans = 0;
    for (auto itr = keihin.begin(); itr != keihin.end(); itr++) {
        ans++;
    }

    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 19204
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = 10**5
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))


Measured memory_bytes: 316488
#include <iostream>
#include <vector>

int main()
{
  int n, m;
  std::cin >> n>>m;
  std::vector<std::vector<int>> light2switch(m);
  for (int i = 0; i < m; i++)
  {
    int num_switch;
    std::cin >>num_switch;
    for (int j = 0; j < num_switch; j++)
    {
      int aaa;
      std::cin >> aaa;
      light2switch[i].push_back(--aaa);
    }
  }
  std::vector<int> light_trigger(m,0);
  for (int i = 0; i < m; i++)
  {
    int a;
    std::cin >> a;
    light_trigger[i] = a;
  }
  int num_turning_on = 0;
  for (int bit = 0; bit < 1<<n; bit++)
  {
    bool all_light_turning_on = true;
    for (int i = 0; i < light2switch.size(); i++)
    {
      int num_on_switch = 0;
      for(const auto& switch_for_each_light: light2switch[i])
      {
        if(bit & 1<<switch_for_each_light)
        {
          num_on_switch ++;
        }
      }
      if(num_on_switch%2 != light_trigger[i])
      {
        all_light_turning_on = false;
      }
    }
    if(all_light_turning_on)
    {
      num_turning_on ++;
    }
  }
  std::cout << num_turning_on << std::endl;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x1,x2,x3,x4,x5;
  cin>>x1>>x2>>x3>>x4>>x5;
  if(x1==0)
    cout<<1<<"\n";
  else if(x2==0)
    cout<<2<<"\n";
  else if(x3==0)
    cout<<3<<"\n";
  else if(x4==0)
    cout<<4<<"\n";
  else
    cout<<5<<"\n";
}

Measured memory_bytes: 3588
w = sorted(list(input().strip()))
L = []

count = 1
for i in range(len(w)-1):
  if w[i] == w[i + 1]:
    count += 1
  elif w[i] != w[i + 1]:
    L.append(count)
    count = 1
L.append(count)

def evens(l):
  for j in l:
    if j % 2 != 0:
      return print('No')
  print('Yes')
    
evens(L)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; a < b; i++);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v) cerr << #v << ":"; rep(i, v.size()) cerr << " " << v[i]; cerr << endl
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; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> A(n);
    vector<int> B(n);
    for(auto &a : A) cin >> a, a--;
    int now = 0;
    while(k) {
        if (k & 1) now = A[now];
        rep(i, n) B[i] = A[A[i]];
        A = B;
        k >>= 1;
    }
    now++;
    cout << now << endl;
}

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



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

int main() {
	string s,t;
	t = "CODEFESTIVAL2016";
	cin >> s;
	int cnt=0;
	for(int i=0;i<s.size();++i) {
		string sub = s.substr(i,1);
		string tsub = t.substr(i,1);
		if(sub != tsub) ++cnt;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
static const int N=100;


int main(){
  int M[N][N];
  int n,u,k,v;

  cin>>n;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j]=0;
    }
  }

  for(int i=0;i<n;i++){
    cin>>u;
    u--;
    cin>>k;
    for(int j=0;j<k;j++){
      cin>>v;
      v--;
      M[u][v]=1;
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(j) cout<<" ";
      cout<<M[i][j];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3120
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

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

#define endl "\n"
#define mt make_tuple
#define mp make_pair

template <typename T1, typename T2>
bool umax(T1 &a, const T2&b) { return a < b ? a = b, 1 : 0;}
template <typename T1, typename T2> 
bool umin(T1 &a, const T2 &b) {return a > b ? a = b, 1 : 0;}
template <typename T>
T sqr(T a) {return a * a;}

mt19937 rng(20010709);
const int mod = 1000000007;
const int INF = 1000000001;

string s, t;
int dp[3005][3005];

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

    cin >> s >> t;

    s = " " + s;
    t = " " + t;

    for (int i = 1; i < t.size(); i++) {
        for (int j = 1; j < s.size(); j++) {
            umax(dp[i][j], dp[i - 1][j]);
            umax(dp[i][j], dp[i][j - 1]);

            if (t[i] == s[j])
                umax(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }

    string result = "";

    for (int i = t.size() - 1, j = s.size() - 1; i && j;) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
        } else if (dp[i][j] == dp[i][j - 1]) {
            j--;
        } else {
            result += t[i];
            i--;
            j--;
        }
    }

    reverse(result.begin(), result.end());

    cout << result;

    return 0;
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 2005;
const int mod = 1e9 + 7;

int n, m, fac[MAXN * MAXN], inv[MAXN * MAXN], f[MAXN][MAXN];

inline int C(int x, int y) { return 1LL * fac[x] * inv[y] % mod * inv[x - y] % mod; }

inline int F(int x, int y) { return C(y + x, x); }

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read(), fac[0] = fac[1] = inv[0] = inv[1] = 1;
	if (m == 1)
		return puts("1"), 0;
	for (int i = 2; i <= n * m; i ++)
		fac[i] = 1LL * fac[i - 1] * i % mod, inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 2; i <= n * m; i ++)
		inv[i] = 1LL * inv[i] * inv[i - 1] % mod;
	f[0][0] = 1;
	for (int i = 0; i <= n; i ++)
		for (int j = 0; j <= i; j ++)
		{
			if (j < i)
				f[i][j + 1] = (f[i][j] + f[i][j + 1]) % mod;
			if (i < n)
				f[i + 1][j] = (1LL * f[i][j] * F(j + i * (m - 1), m - 2) % mod * (n - i) + f[i + 1][j]) % mod;
		}
	return printf("%d\n", f[n][n]), 0;
}


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

int main(void){
	string s;
	while(cin >> s){
		int ioi=0,joi=0;
		for(int i=0;i<s.size()-2;i++){
			if(s[i] == 'I' && s[i+1] == 'O' && s[i+2] == 'I') ioi++;
			if(s[i] == 'J' && s[i+1] == 'O' && s[i+2] == 'I') joi++;
		}
		cout << joi << endl;
		cout << ioi << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
//const int MOD=998244353;
const int INF=1e9;
const long long LINF=1e18;
#define int long long
//template
template <typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
//main
signed main(){
  int N;cin>>N;
  fin(N*N*N);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

/* typedef */

typedef long long ll;

/* constant */

const int INF = 1 << 30;
const int MAX = 100000;
const int MOD = 1000000007;
const int NIL = -1;
const double pi = 3.141592653589;
/* global variables */
struct Node {
    int parent,  // parent
        left,    // left child
        right;   // right sibling
};
struct Node T[MAX];
vector<int> Depth(MAX, 0);

/* function */
int getDepth(int u);
void setDepth(int u, int p);
void printChildlen(int u);
void printNodeType(int t);
void printAns(int u);

/* main */
int main(){

    int n, v, d, c, l;
    cin >> n;

    for (int i = 0; i < n; i++) {
        T[i].parent = T[i].left = T[i].right = NIL;
    }

    for (int i = 0; i < n; i++) {
        cin >> v;
        cin >> d;
        int tmp;
        for (int j = 0; j < d; j++) {
            cin >> c;
            T[c].parent = v;
            if (j == 0) {
                T[v].left = c;
                tmp = c;
            }
            if (j != 0) {
                T[tmp].right = c;
                tmp = c;
            }
        }
    }

    int root = 0;
    for (int i = 0; i < n; i++) 
        if (T[i].parent == NIL)
            root = i;

    setDepth(root, 0);

    for (int i = 0; i < n; i++)
        printAns(i);

    return 0;
}


int getDepth(int u) {
    int depth = 0;
    while (T[u].parent != NIL) {
        depth++;
        u = T[u].parent;
    }
    return depth;
}

void setDepth(int u, int p) {

    Depth[u] = p;
    if (T[u].left != NIL)
        setDepth(T[u].left, p+1);
    if (T[u].right != NIL)
        setDepth(T[u].right, p);
}

void printChildlen(int u) {
    int child;
    if (T[u].left != NIL) {
        child = T[u].left;
        cout << child;
        while (child != NIL) {
            child = T[child].right;
            if (child != NIL) {
            cout << ", " << child;
            }
            else {
                break;
            }
        }
    }
}

void printNodeType(int v) {
    if (T[v].parent == NIL) {
        cout << "root";
    }
    else if (T[v].left == NIL) {
        cout << "leaf";
    }
    else {
        cout << "internal node";
    }
}

void printAns(int u) {

    cout << "node " << u << ": ";
    cout << "parent = " << T[u].parent << ", ";
    cout << "depth = " << Depth[u] << ", ";
    
    printNodeType(u);
    
    cout << ", [";

    printChildlen(u);
    cout << "]";
    cout << '\n';
}



Measured memory_bytes: 4396
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;


int main(){
  ll ans=0,temp;
  ll N,K,V[60];
  cin>>N>>K;
  for(int i=0;i<N;i++){
    cin>>V[i];
  }
  if(K/2>=N){
    for(int i=0;i<N;i++){
      if(V[i]>0) ans+=V[i];
    }
    cout<<ans<<endl;
    return 0;
  }else{
    vector<ll> v;
    for(int i=K/2;i<=min(N,K);i++){
      for(int j=0;j<=i;j++,temp=0){
        for(int k=0;k<j;k++){
          v.push_back(V[k]*-1);
        }
        for(int k=0;k<i-j;k++){
          v.push_back(V[N-1-k]*-1);
        }
        sort(v.begin(),v.end());
        /*cout<<"ikuyo"<<endl;
        for(int l=0;l<v.size();l++){
          cout<<v[l]<<endl;
        }*/
        for(int k=0;k<i;k++){
          if(k>=2*i-K && v[k]>0) break;
          temp+=v[k]*-1;
        }
        v.erase(v.begin(),v.end());
        ans=max(ans,temp);
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#include <cstdio>
#define ll long long
#define rep(i,s,n) for(ll i = (ll)(s); i < (ll)(n); i++)
#define all(a) (a).begin(),a.end()
#define mod 1000000007
#define P pair<ll,ll>
using namespace std;
using graph =vector<vector<ll>>;
const ll MAX = 510000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void cominit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算nCk
ll com(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// 二項係数計算nPk
ll per(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n-k] % MOD) % MOD;
}

// mod. m での a の逆元 a^{-1} を計算する
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/* ユークリッドの互除法 最大公約数*/
ll gcd(ll a, ll b) {
	return b ? gcd(b,a%b) : a;
}



/*最小公倍数*/

ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}


/*二点間の距離*/
double dist(pair<double,double> a,pair<double,double> b){
	return sqrt(pow((a.first - b.first) ,2) + pow((a.second - b.second),2));
}

//繰り返し自乗法
double ism(double aa,ll p){
    double ap=aa;
    double ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans*=ap;
        }
        p/=2;
        ap=ap*ap;
    }
    return ans;

}
//繰り返し自乗法(アマリトリバージョン)
ll ismm(ll aa,ll p,ll m){
    ll ap=aa;
    ll ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans=(ans*ap)%m;    
        }
        p/=2;              
        ap=(ap*ap)%m;
    }
    return ans;

}
/*
ll solve(ll i,ll m,vector<ll>t,ll n){
    if(m==0){
        return 1;
    }
    if(i>=n){
        return 0;
    }
    
    
    cout<<i+1<<" "<<m<<endl;
    cout<<i+1<<" "<<m-t[i]<<endl;
    ll res=solve(i+1,m,t,n)||solve(i+1,m-t[i],t,n);
    return res;
}
*/


//小数点12桁
struct all_init
{
    all_init()
    {
        cout << fixed << setprecision(12);
    }
} All_init;


int main()
{
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>>v(n+1);
    vector<P>p(m);
    rep(i,0,m){
        ll x,y;
        cin>>x>>y;
        p[i]={x,y};
        v[x].push_back(y);
    }
    rep(i,1,n+1){
        sort(all(v[i]));
    }
    rep(i,0,m){
        printf("%06lld",p[i].first);
        printf("%06lld\n",(ll)(lower_bound(all(v[p[i].first]),p[i].second)
        -v[p[i].first].begin())+1);
    }
}


Measured memory_bytes: 8576
import java.util.*;
import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		char c = (char)sc.next().charAt(0);
		if(c == 'A') System.out.println("T");
		else if(c == 'C')System.out.println("G"); 
		else if(c == 'T')System.out.println("A");
		else System.out.println("C");
	}
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = a; i <= b; ++i)
    {
        string s = to_string(i);
        string t = s;
        reverse(ALL(t));
        if (s == t)
        {
            ++cnt;
        }
    }
    cout << cnt << endl;
}

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


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){

    int h, w;
    cin >> h >> w;

    char board[h][w];

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){

            bool found = false;

            if (board[i][j] == '.') continue;

            // check boundaries ...
            if (i - 1 >= 0){
                if (board[i-1][j] == '#'){
                    found = true;
                }
            }
            
            if (i + 1 < h){
                if (board[i+1][j] == '#'){
                    found = true;
                }
            }

            if (j - 1 >= 0){
                if (board[i][j-1] == '#'){
                    found = true;                 
                }
            }
            
            if (j + 1 < w){
                if (board[i][j+1] == '#'){
                    found = true;                 
                }
            }
  
            if (found) continue;
            else {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int count(int X){
  int cnt = 0;
  while( X % 2 == 0 ){
    cnt++; X /= 2;}
  return cnt;}

int main(){
  int N; cin >> N; int mc = 0; int ans = 1;
  for(int i = 1; i <= N; i++){
   if( mc > count(i)){continue;}
  else{ ans = i; mc = count(i);}}
  cout << ans << endl;
  return 0;}
    


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

int main(){
    long long N,a,b,sum=0,minB=1000000000,i;
    cin >> N;
    for(i=0; i<N; i++){
        cin >> a >> b;
        sum+=a;
        if(a>b && minB>b)
        minB=b;
    }
    if(minB==1000000000)
    cout << 0 << endl;
    else
    cout << sum-minB << endl;
    return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

int main(){
  ll N,f=0;
  cin>>N;
  string s;
  while(N--){
    cin>>s;
    if(s[0]=='Y')f=1;
  }
  if(!f)puts("Three");
  else puts("Four");
  return 0;
}


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

long long mygcd(long long a, long long b, long long& x, long long& y) {
  long long d = a;
  if (b != 0) {
    d = mygcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

long long n, n2;
long long calc(long long a, long long b);

int main() {
  cin >> n;
  long long res = n;
  n *= 2;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) res = min(res, calc(i, n / i));
  cout << res << endl;
  return 0;
}

long long calc(long long a, long long b) {
  long long x, y, g;
  g = mygcd(a, b, x, y);
  if (g != 1) return n;
  if (x > 0) {
    swap(a, b);
    swap(x, y);
  }
  long long num = -x / b, res = n;
  x %= b;
  y -= a * num;
  if (x == 0) {
    x -= b;
    y += a;
  }
  res = min(res, -a * x * g);
  y -= a;
  x += b;
  if (y == 0) {
    x += b;
    y -= a;
  }
  res = min(res, -b * y * g);
  return res;
}

Measured memory_bytes: 3564
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
inline bool ok(int x, int l, int r) {
    int sum = 0;
    while (x) {
        sum += x%10;
        x /= 10;
    }
    if (sum <= r && sum >= l) return true;
    return false;
}
int main(int argc, char const *argv[])
{
    int n, l, r, sum = 0;
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++)
        if (ok(i, l, r)) sum += i;
    printf("%d\n", sum);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
    int k, s;
    cin >> k >> s;
    int ans = 0;
    for (int x = 0; x <= k; x++) {
        for (int y = 0; y <= k; y++) {
            int z = s-x-y;
            if (0 <= z && z <= k) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int n,m,k,s;

  scanf("%d %d", &n, &m);
  s = m;
  int max = s;
  int i[10000][2] = {};

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

      s += i[k][0];
      s -= i[k][1];

      if ( s < 0 ) {
	max = 0;
	break;
      }
      
      if ( max < s)
	max = s;
    }

  printf("%d\n", max);

  return 0;

}

Measured memory_bytes: 680
#include <iostream>

using namespace std;

int main(){
  int M1,D1,M2,D2;
  cin>>M1>>D1;
  cin>>M2>>D2;
  if(M2==(M1+1) && D2 == 1){
    cout<<1<<endl;
  }else{
    cout<<0<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
    int A,B,C,X;
    char S[10];
    scanf("%d %d %d %d",&A,&B,&C,&X);
   if(A+B>C+X){
       printf("Left");
   }else if(A+B==C+X){
       printf("Balanced");
   }else{
       printf("Right");
   }
    return 0;
}

Measured memory_bytes: 128
w,h,n = map(int,input().split())
x0 = 0
y0 = 0
x1 = w
y1 = h
for i in range(n):
  x,y,a = map(int,input().split())
  if a == 1:
    x0 = max(x0,x)
  elif a == 2:
    x1 = min(x1,x)
  elif a == 3:
    y0 = max(y0,y)
  else:
    y1 = min(y1,y)
print( max(0,(x1-x0)) * max(0,(y1-y0)) )

Measured memory_bytes: 3064
import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))

def binary_search(x, lst, l , r):
    while l < r:
        mid = (l + r) // 2
        mid_val = lst[mid]
        if x == mid_val:
            return mid - 1
        elif x < mid_val:
            r = mid - 1
        else:
            l = mid + 1
    else:
        return l

ans = 0
for i in range(N):
    max_ab = bisect.bisect_left(A, B[i])
    max_bc = N - bisect.bisect_right(C, B[i])
    ans += (max_ab * max_bc)
print(ans)

Measured memory_bytes: 24052
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define lli long long int
#define pb push_back
using namespace std;
lli gcd(lli a,lli b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	lli a,b,c,d;
	cin>>a>>b>>c>>d;
	lli gc = gcd(c,d);
	lli lc = c*d;
	lc = lc/gc;
	lli cnt_till_a_c = (a-1)/c;
	lli cnt_till_a_d = (a-1)/d;
	lli cnt_till_a_lc = (a-1)/lc;

	lli cnt_till_b_c = b/c;
	lli cnt_till_b_d = b/d;
	lli cnt_till_b_lc = b/lc;

	lli n_c = cnt_till_b_c - cnt_till_a_c;
	lli n_d = cnt_till_b_d - cnt_till_a_d;
	lli n_lc = cnt_till_b_lc - cnt_till_a_lc;

	lli ans = n_c + n_d - n_lc;

	ans = b - (a-1) - ans;

	cout<<ans<<endl;


	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define str(n) to_string(n)
#define int(w) stoi(w)
#define len(l) l.size()
#define append(l,i) l.push_back(i)
int main() {
    string s;
    cin>>s;
    int n;
    int b=1;
    while (s!=""){
        n=s.size();
        if (n<5){
          b=0;
          break;
        }
      else if (s.substr(n-5,5)=="erase"){
            s.erase(n-5);
        }
        else if (s.substr(n-5,5)=="dream"){
            s.erase(n-5);
        }
      else if(n<6){
        b=0;
        break;
      }
        else if (s.substr(n-6,6)=="eraser"){
            s.erase(n-6);
        }
        else if (n<7){
            b=0;
            break;
        }
        else if (s.substr(n-7,7)=="dreamer"){
            s.erase(n-7);
        }
        else{
            b=0;
            break;
        }

    }
    if (b==1){
        cout<<"YES"<<endl;
    }    
    else{
        cout<<"NO"<<endl;
    }

    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
	int A[3][3],N,b,B[3][3]={0};
	bool res=false;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)cin>>A[i][j];
	}
	cin>>N;
	for(int k=0;k<N;k++){
		cin>>b;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++){
			if(A[i][j]==b)B[i][j]=1;
		}
	}
	if(B[0][0]&&B[0][1]&&B[0][2])res=true;
	if(B[1][0]&&B[1][1]&&B[1][2])res=true;
	if(B[2][0]&&B[2][1]&&B[2][2])res=true;
	if(B[0][0]&&B[1][1]&&B[2][2])res=true;
	if(B[2][0]&&B[1][1]&&B[0][2])res=true;
	if(B[0][0]&&B[1][0]&&B[2][0])res=true;
	if(B[0][1]&&B[1][1]&&B[2][1])res=true;
	if(B[0][2]&&B[1][2]&&B[2][2])res=true;
	if(res)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<cmath>
#include<iostream>

#define PI 3.14159265358979323846
using namespace std;

int length, angle, currentAngle;
double px, py;
 
void walk(){
    double dx = length * cos(currentAngle * PI / 180.0);
    double dy = length * sin(currentAngle * PI / 180.0);
    currentAngle -= angle;
    px += dx;
    py += dy;
}

main(){
    px = 0;
    py = 0;
    currentAngle = 90;
    while(1){
	scanf("%d,%d", &length, &angle);
	if ( length == 0 && angle == 0 ) break;
	walk();
    }
    int x = (int)px;
    int y = (int)py;
    printf("%d\n", x);
    printf("%d\n", y);
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <algorithm>
#define INF 1000000000;
using namespace std;

int dfs(int N,int i ,int *A,int *l,int a,int b,int c){
	if(i == N){
		if(min({a,b,c}) == 0){
			return INF;
		}else{
			return abs(a-A[0])+abs(b-A[1])+abs(c-A[2])-30; 
		}
	}
	int ret1 = dfs(N,i+1,A,l,a,b,c);
	int ret2 = dfs(N,i+1,A,l,a+l[i],b,c) + 10;
	int ret3 = dfs(N,i+1,A,l,a,b+l[i],c) + 10;
	int ret4 = dfs(N,i+1,A,l,a,b,c+l[i]) + 10;
	return min({ret1,ret2,ret3,ret4});
}



int main(){
	int i;
	int N,A[3];
	cin >> N >> A[0] >> A[1] >> A[2];
	int l[N];
	for(i=0;i<N;i++){
		cin >> l[i];
	}
	cout << dfs(N,0,A,l,0,0,0) << endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define TTT "BAI2"
#define mo 1000000007
#define maxn 2005
using namespace std;
int n, a[maxn];
long long res = 0, k;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    fi(i, 1, n) cin >> a[i];
    long long tg = ((k * (k - 1)) / 2) % mo;
    fi(i, 1, n)
    {
        int dem = 0;
        fi(j, i + 1, n)
        if(a[i] > a[j]) dem++;
        res = (res + k * dem) % mo;
        fi(j, 1, i - 1)
        if(a[i] > a[j]) dem++;
        res = (res + dem * tg) % mo;
    }
    cout << res;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000007;
const ll INF = 1061109567;
const double EPS = 1e-10;
int main(){
    int a,b;
  cin>>a>>b;
  cout<<a*b<<endl;
        return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    ll n; string s;
    cin>>n>>s;
    ll x=s.size();
    ll sum=1;
    ll r=0,g=0,b=0;
    rep(i,n){
        if(s[i]=='R')r++;
        if(s[i]=='G')g++;
        if(s[i]=='B')b++;
    }
    sum=r*g*b;
    for(int i=1; i<=x; ++i){
        for(int j=0; j<x-(2*i); ++j){
            if(j+i+i>=x)continue;
            if(s[j]!=s[j+i]&&s[j+i]!=s[j+i+i]&&s[j+i+i]!=s[j]){
                sum--;
            }
        }
    }
    cout<<sum<<endl;
}


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

constexpr int MAX = 1e9 + 1;

void shortest(int[300][300], int);

int main() {
	int D[300][300];

	for (int i = 0; i < 300; i++) {
		for (int j = 0; j < 300; j++) {
			D[i][j] = i == j ? 0 : MAX;
		}
	}

	int n, m, l;
	cin >> n >> m >> l;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		D[a - 1][b - 1] = D[b - 1][a - 1] = c;
	}

	shortest(D, n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (D[i][j] <= l) {
				D[i][j] = 1;
			}
			else {
				D[i][j] = MAX;
			}
		}
	}

	shortest(D, n);

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int s, t;
		cin >> s >> t;
		int r = D[s - 1][t - 1];
		if (r >= MAX) {
			r = 0;
		}
		cout << r - 1 << endl;
	}
}

void shortest(int D[300][300], int n) {
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}
}


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

int main(){
    // 制約見て！！！デカかったらlong longにすること！
    int n,r;
    cin >> n>>r;
    if(n>=10){
        cout << r<<endl;
    }else{
        cout<<r+100*(10-n)<<endl;
    }
}

Measured memory_bytes: 256
def main():
    n = int(input())
    t, x, y = [0], [0], [0]
    for i in range(n):
        a, b, c = map(int, input().split())
        t.append(a)
        x.append(b)
        y.append(c)

    for i in range(1, n+1):
        dt = t[i]-t[i-1]
        dx = x[i]-x[i-1]
        dy = y[i]-y[i-1]

        if abs(dx) + abs(dy) > dt:
            print("No")
            return 0

        if dt % 2 != (abs(dx)+abs(dy)) % 2:
            print("No")
            return 0
            
    print("Yes")

main()



Measured memory_bytes: 11756
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> t(n), v(n);
    cin >> t >> v;
    struct seg { int x1, x2, y; };
    int x;
    vector<seg> segs = {{-1, x = 0, 0}};
    for(int i = 0; i < n; i++) {
        segs.push_back({x, x += t[i], v[i]});
    }
    segs.push_back({x, x + 1, 0});
    double ans = 0;
    for(double xx = 0, y = 0; xx <= x; xx += 0.5) {
        double max_y = lim<int>::max();
        for(seg& s : segs) {
            max_y = min(max_y, s.y + max(0.0, s.x1 - xx) + max(xx - s.x2, 0.0));
        }
        ans += double(y + max_y) / 4;
        y = max_y;
    }
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/* A - The Number of Even Pairs */

#include <stdio.h>

int combi(int n, int k){
  if(n < k) return 0;
  else if(n == k || k == 0) return 1;
  else if(k == 1) return n;
  else return combi(n - 1, k) + combi(n - 1, k - 1);
}

int main(void){
  int N, M;
  scanf("%d %d", &N, &M);
  printf("%d\n", combi(N, 2) + combi(M, 2));
}


Measured memory_bytes: 128
import java.io.*;
import java.util.*;
import static java.lang.System.in;

public class Main {
    static long mod = 1000000000+7;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //String[] buf = reader.readLine().split(" ");
        int n = sc.nextInt(), m = sc.nextInt();
        long[] dp = new long[n+1];
        boolean[] bad = new boolean[n+1];
        for(int i=0;i<m;i++){
            int a = sc.nextInt();
            bad[a] = true;
        }
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            if(bad[i]) continue;
            dp[i] = dp[i-1];
            if(i>1) dp[i] += dp[i-2];
            dp[i] %= mod;
        }
        System.out.println(dp[n]);
    }
}



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

#define Q 1000000007

// CombはMOD計算がしやすいように二項係数で求める
int comb(int n, int k){
  vector<vector<int>> tbl(n+1, vector<int>(k+1));
    
  for (int i=0; i<=n; i++){
    tbl[i][0] = 1;
    if (i<=k) tbl[i][i] = 1;
  }
  for (int i=1; i<=n; i++){
    for (int j=1; j<=k; j++){
      tbl[i][j] = tbl[i-1][j]+tbl[i-1][j-1];
      tbl[i][j] %= Q;
    }
  }
  return tbl[n][k];
}

int main(void){
  int n,m;
  long long ans;
  cin >> n >> m;
  
  ans = 1;
  for (int d=2; m>1; d++){
    int p=0;
    while (m%d==0){
      m /= d;
      p++;
    }
//    cout << d << " " << p << endl;
    if (p){
      ans *= comb(n-1+p, p);
      ans %= Q;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15104
function main(input) {
const colors = input.split('');
const N = colors.length
var ansone = 0;
for(var i=0;i<=N-1;++i){
if((parseInt(colors[ i ],10) + i + 1 ) % 2 == 0 ){ ++ansone ;}
}
var anstwo = 0;
for(var j=0;j<=N-1;++j ){
if((parseInt(colors[ j ],10) + j + 1 ) % 2 == 1 ){ ++anstwo ;}
}
console.log(Math.min( ansone , anstwo ));
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  
  if(a.at(a.size() - 1) == b.at(0) && b.at(b.size() - 1) == c.at(0)) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll a,b,c,ans=0;
	cin>>a>>b>>c;
	while(a%2==0&&b%2==0&&c%2==0){
		if(a==b&&b==c&&c==a){
			cout << -1;
			return 0;
		}
		ans++;
		ll A=a/2,B=b/2,C=c/2;
		a=B+C;b=A+C;c=A+B;
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define rep(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(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
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;}
//******************************************************************************
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}


signed main()
{
	//IOS();
	int N,M;
	cin>>N>>M;
	vector<int>a(N),b(M);
	vector<int>cnt(N*M+1,0);
	for(int i = 0;i < N;i++){
		cin>>a[i];
		if(++cnt[a[i]]>1){
			cout<<0<<endl;
			return 0;
		}
	}
	fill_v(cnt,0);
	for(int i = 0;i < M;i++){
		cin>>b[i];
		if(++cnt[b[i]]>1){
			cout<<0<<endl;
			return 0;
		}
	}
	sort(all(a));
	sort(all(b));
	int ans = 1;
	rrep(i,1,N*M+1){
		int aid = lower_bound(all(a),i) - a.begin();
		int bid = lower_bound(all(b),i) - b.begin();
		if(i==a[aid]&&i==b[bid])continue;
		if(i==a[aid]){
			(ans*=M-bid)%=MOD;
			continue;
		}else if(i==b[bid]){
			(ans*=N-aid)%=MOD;
			continue;
		}
		int t = (N-aid)*(M-bid)-(N*M-i);
		if(t<=0){
			cout<<0<<endl;
			return 0;
		}
		(ans*=t)%=MOD;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 8064
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 1e5 + 200;
const long long MNN = 5e3 + 100;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const long long OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong a, b, c;

int main () {
    ios;
    cin >> a >> b >> c;
    if(a + b + 1 >= c){
        cout << b + c;
    }else if(a + b - 1 < c){
        cout << b + (b + a + 1);
    }
    return 0;
}


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

using namespace std;
typedef long long ll;

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

  auto fset = vector<bitset<10> >(N, bitset<10>());
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 10; j++) {
      int b;
      cin >> b;
      if (b == 1) {
        fset[i].set(j);
      } else {
        fset[i].reset(j);
      }
    }
  }

  auto pset = vector<vector<int> >(N, vector<int>(11));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 11; j++) {
      cin >> pset[i][j];
    }
  }

  int ans = INT_MIN;
  for (int mask = 1; mask < 1 << 10; mask++) {
    bitset<10> b(mask);
    int t = 0;
    for (int i = 0; i < N; i++) {
      int c = (b & fset[i]).count();
      t += pset[i][c];
    }
    ans = max(ans, t);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256