akhauriyash/Code-Regression huggingface dataset:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,n=MI()
lis=LI()
for i in range(500):
    l=x-i
    u=x+i
    if not l in lis:
        print(l)
        sys.exit()
    elif not u in lis:
        print(u)
        sys.exit()
    

Measured memory_bytes: 9496
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
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; }

lli h, w, k;

int main(void){
    cin >> h >> w >> k;
    vector<string> m(h);
    vector<lli> c(h);
    vector<vector<lli>> ans(h, vector<lli>(w));
    rep(i, h){
        cin >> m[i];
        rep(j, w) if(m[i][j] == '#') c[i]++;
    }
    lli num = 1;
    rep(i, h){
        if(c[i] == 1){
            rep(j, w) ans[i][j] = num;
            num++;
        }else if(c[i] > 1){
            queue<lli> q;
            rep(j, w) if(m[i][j] == '#') q.push(j);
            while(!q.empty()){
                lli j = q.front();
                ans[i][j] = num;
                q.pop();
                for(lli k = j-1; k >= 0&&m[i][k]!='#'; k--) if(ans[i][k] == 0) ans[i][k]=num;
                for(lli k = j+1; k <  w&&m[i][k]!='#'; k++) if(ans[i][k] == 0) ans[i][k]=num;
                num++;
            }
        }
    }
    rep(i, h){
        if(c[i] != 0){
            for(lli j = i-1; j >= 0; j--){
                if(c[j] == 0) rep(k, w) ans[j][k] = ans[i][k];
                else break;
            }
            for(lli j = i+1; j < h; j++){
                if(c[j] == 0) rep(k, w) ans[j][k] = ans[i][k];
                else break;
            }
        }
    }
    rep(i, h){
        rep(j, w){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 4448
#include <iostream>
using namespace std;
int s[3][100000];
int main(void){
    int n,a,b,c;
    cin>>n;
    cin>>a>>b>>c;
    s[0][0]=a;
    s[1][0]=b;
    s[2][0]=c;
    for(int i=1;i<n;i++){
        cin>>a>>b>>c;
       s[0][i]=a+max(s[1][i-1],s[2][i-1]);
       s[1][i]=b+max(s[0][i-1],s[2][i-1]);
       s[2][i]=c+max(s[0][i-1],s[1][i-1]);
    }
    cout<<max(max(s[0][n-1],s[1][n-1]),s[2][n-1])<<endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define lowb lower_bound
#define upb upper_bound
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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 n;
int c[500], s[500], f[500];

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

	cin >> n;
	rep(i, n - 1) {
		cin >> c[i] >> s[i] >> f[i];
	}

	rep(i, n) {
		int t = 0;
		for(int j = i; j < n-1; j++) {
			if(t < s[j]) t = s[j];
			else if(t % f[j] == 0);
			else t = t + f[j] - t % f[j];
			t += c[j];
		}
		cout << t << endl;
	}
	return 0;
}

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

using namespace std;

int main() {
    int n;
    cin>>n;
    int a[n];
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin>>a[i];
        sum+=a[i];
    }
    int avg = ceil(float(sum)/n);
    int avg2 = floor(float(sum)/n);
    int cost = 0;
    int cost2 = 0;
    for(int i = 0; i < n; i++) {
        cost += (a[i]-avg)*(a[i]-avg);
        cost2 += (a[i]-avg2)*(a[i]-avg2);
    }
    cout<<min(cost,cost2);
    return 0;
}

Measured memory_bytes: 3616
// @Author :- Gaurav Bharti
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define empb emplace_back
#define mp make_pair
#define F first
#define S second
#define vii vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define mapii map<int,int> 
#define mapll map<ll,ll>
#define all(a) a.begin(),a.end()
#define test ll t; cin>>t; while(t--)
#define prec(n) fixed<<setprecision(n)
#define ItsFUN ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007



int main(){
	
	ll n;cin >> n;
	cout << (n==0 ? 1 : 0) << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;
int n,a[405];
long long dp[405][405],ans=0,f[405];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=1e18;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i][i]=0,f[i]=f[i-1]+a[i];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+f[j]-f[i-1]);
            }
        }
    }

    cout<<dp[1][n];
    return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 200020
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,dp[N][2];
char s[N];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	memset(dp,~0x3f,sizeof(dp));
	dp[1][0]=1,dp[2][1]=1;
	if(s[1]^s[2])dp[2][0]=2;
	for(int i=3;i<=n;++i){
		dp[i][0]=dp[i-1][1]+1;
		if(s[i]^s[i-1])dp[i][0]=max(dp[i][0],dp[i-1][0]+1);
		dp[i][1]=dp[i-2][0]+1;
	}
	printf("%d\n",max(dp[n][0],dp[n][1]));
	return 0;
}



Measured memory_bytes: 5548
#include <stdio.h>
#include <list>
#include <vector>

using ll = long long;
using namespace std;

ll n, l;
list<ll> alis;
int imarr[100001];
//すべてに+1を忘れずに
vector<int> ans;

int main()
{
	imarr[0] = 0;
	scanf("%lld %lld", &n, &l);
	for (int i = 0; i < n; ++i)
	{
		ll anew;
		scanf("%lld", &anew);
		alis.push_back(anew);
	}
	int i = 0;
	for (auto itr = alis.begin(); itr != alis.end(); ++itr)
	{
		imarr[i + 1] = imarr[i] + (*itr);
		++i;
	}
	int maxren = 0;
	auto maxitr = alis.begin();
	auto itr = alis.begin();
	int place = 0;
	int frontnum = 0;
	for (int i = 0; i < n - 1; ++i)
	{
		if (imarr[i + 2] - imarr[i] >= maxren)
		{
			maxren = imarr[i + 2] - imarr[i];
			maxitr = itr;
			place = i;
		}
		++itr;
	}
	bool impossible = false;
	if (maxren < l)impossible = true;
	auto nextitr = maxitr;
	++nextitr;
	*maxitr += *nextitr;
	alis.erase(nextitr);
	ans.push_back(place);
	++frontnum;
	itr = maxitr;
	for (;;)
	{
		auto nextitr = itr;
		++nextitr;
		auto lastitr = itr;
		bool back_usable(true), front_usable(true);
		if (nextitr == alis.end())
		{
			back_usable = false;
		}
		if (itr == alis.begin())
		{
			front_usable = false;
		}
		else
		{
			--lastitr;
		}

		if (back_usable && front_usable)
		{
			if (*nextitr > *lastitr)
			{
				front_usable = false;
			}
			else
			{
				back_usable = false;
			}
		}
		if (back_usable)
		{
			//あとを結合
			*itr += *nextitr;
			if (*itr < l)impossible = true;
			alis.erase(nextitr);
			ans.push_back(place + frontnum);
		}
		else if (front_usable)
		{
			//前を結合
			*lastitr += *itr;
			if (*lastitr < l)impossible = true;
			alis.erase(itr);
			itr = lastitr;
			--place;
			ans.push_back(place);
		}
		else
		{
			break;
		}
		++frontnum;
	}
	if (impossible)
	{
		printf("Impossible\n");
	}
	else
	{
		printf("Possible\n");
		for (int i = ans.size() - 1; i >= 0; --i)
		{
			printf("%d\n",ans[i] + 1);
		}
	}
	return 0;
}

Measured memory_bytes: 4352
package main

import (
	"fmt"
	"math"
)

func main() {
	a, b, c := SingleInt(), SingleInt(), SingleInt()

	// sum := x*a + y*a + ...
	// sum := (x + y + ...)*a --- x * a  10 * 5
	// c = sum % b
	// sum / b + c =

	// 100 % 33 = 1 --- 34 % 33 = 1
	// bで割ったときのあまりを作る最小の手段
	// b + c = (x + y + ...)*a / b
	// 終了条件は?
	// bで割ったときのあまりとして考えられるのは、b - n - 1 = 0 -- n = b -1

	if a == 1 {
		fmt.Println("YES")
		return
	}

	if a%2 == 0 && c%2 != 0 {
		fmt.Println("NO")
		return
	}

	for i := 1; i <= 100; i++ {
		for j := 1; j <= 100; j++ {
			if b*i+c == j*a {
				fmt.Println("YES")
				return
			}
		}
	}
	fmt.Println("NO")
}

func SingleInt() int {
	var n int
	fmt.Scan(&n)
	return n
}

func Min(nums ...int) int {
	if len(nums) == 0 {
		panic("function min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}


Measured memory_bytes: 512
a,b,c,x,y=map(int,input().split())
ans1=x*a+y*b
if x>=y:
    ans2=2*y*c+(x-y)*a#(x,y)=(3,2)であればABを4枚買う
else:
    ans2=2*x*c+(y-x)*b
ans3=2*max(x,y)*c
print(min(ans1,ans2,ans3))

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main() {
	string c,s;
	int p=0, t[10]={},i,j,k,a,b,d;
	c = ">+++++[<++++++>-]>+++++[<++++++++>-]>+++++[<++++++++++>-]>++++++[<++++++++++>-]>+++++++[<++++++++++>-]>++++++++[<++++++++++>-]>+++++++++[<++++++++++>-]>++++++++++[<++++++++++>-]>+++++++++++[<++++++++++>-]>++++++++++++[<++++++++++>-]<<<<<<<<<<";
	for(cin>>s,i=0;i<s.length();++i){
		a = (s[i]/10)-3;
		b = a - p;
		p = a;
		for(j=b>0?b:-b;j--;)c+=(b>=0?">":"<");
		
		d=s[i]-(a+3)*10;
		for(k=d;k--;)c+="+";
		c+=".";
		for(k=d;k--;)c+="-";
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 1240
a, b = map(int, input().split())
count = 0
for i in range(a+1):
  for j in range(a+1-i):
    c = (a-i-j)
    s = (10000*i) + (5000*j) + (1000*c)
    if s == b:
      print(i,j,(a-i-j))
      count += 1
      break
  else:
    continue
  break
  
if count == 0:
  print(-1,-1,-1)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define max_n 3010
using namespace std;
int dp[max_n][max_n], pre[max_n][max_n];
char A[max_n], B[max_n], C[max_n];

void dfs(int x, int y) { //找来自的方向 
    if(x == 0 || y == 0) return;
    else if(pre[x][y] == 1) {
        dfs(x - 1, y - 1);
        printf("%c", A[x - 1]);
    }
    else if(pre[x][y] == 2) {
        dfs(x - 1, y);
    }
    else dfs(x, y - 1);
}

int main() {
    memset(pre, 0, sizeof(pre)); //记录dp增加 来自的方向 
    memset(dp, 0, sizeof(dp));
	scanf("%s", A);
	scanf("%s", B);
    int len1 = strlen(A);
    int len2 = strlen(B);
    for(int i = 0; i < len1; i++) {
        for(int j = 0; j < len2; j++) {
            if(A[i] == B[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                pre[i + 1][j + 1] = 1; //来自左上方，下标是字符串下标+1 
            }
            else {
                if(dp[i][j + 1] > dp[i + 1][j]) {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                    pre[i + 1][j + 1] = 2; //来自j + 1； 
                }
                else {
                    dp[i + 1][j + 1] = dp[i + 1][j];
                    pre[i + 1][j + 1] = 3; //来自i + 1 
                }
            }
        }
    }
    dfs(len1, len2);
    return 0;
} 

Measured memory_bytes: 71672
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = -100100100;
typedef pair<int,int> P;

int main(){
    string s;
    cin >> s;
    if(s=="AAA"||s=="BBB"){
        cout << "No" << endl;
        return 0;
    }else{
        cout << "Yes" << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int h,w;
	cin >> h >> w;
	vector<vector<char>> v(h+2,vector<char>(w+2,'#'));
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin >> v[i][j];
		}
	}
	for(int i=0;i<=h+1;i++){
		for(int j=0;j<=w+1;j++){
			cout << v[i][j];
		}
		cout << endl;
	}
}


Measured memory_bytes: 256
import sys

input_len = int(input())
l = input().split()
sort_line = [0 for i in range(input_len)]
for i in range(input_len):
	sort_line[i] = int(l[i])
	

for k in range(input_len):
	if (k > 0):
		sys.stdout.write(" ")
	sys.stdout.write(str(sort_line[k]))
print()

for i in range(1, input_len):
	v = sort_line[i]
	j = i - 1
	while (j >= 0 and v < sort_line[j]):
		sort_line[j+1] = sort_line[j]
		j -= 1
	sort_line[j + 1] = v

	for k in range(input_len):
		if (k > 0):
			sys.stdout.write(" ")
		sys.stdout.write(str(sort_line[k]))
	print()


Measured memory_bytes: 5984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n,m,q;
  cin>>n>>m>>q;
  int a[q];
  int b[q];
  int c[q];
  int d[q];
  rep(i,0,q){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
  }
  
  int ans=0;
  rep(i,0,1<<(m-1+n-2)){
    int e[n];
    e[0]=1;
    int count=0;
    rep(j,0,m-1+n-2){
      if(!(i>>j & 1)){
        count++;
      }
    }
    bool p=false;
    if(count>=n-2){
      p=true;
      int f=1;
      int g=1;
      rep(j,0,m-1+n-2){
        if(i>>j & 1){
          f++;
        }
        else{
          e[g]=f;
          g++;
          if(g==n) break;
        }
      }
      if(g==n-1){
        e[n-1]=f;
      }
    }
    
    if(e[n-1]<=m && p==true){
      int cur=0;
      rep(j,0,q){
        if(e[b[j]-1]-e[a[j]-1]==c[j]){
          cur+=d[j];
        }
      }
      ans=max(ans,cur);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3624
# frozen_string_literal: true

n = gets.to_i
a = n.times.map { gets.to_i }
sa = a.sort_by { |e| -e }
max = sa[0]
nmax = sa[1]

n.times do |i|
  if a[i] == max
    puts nmax
  else
    puts max
  end
end


Measured memory_bytes: 9776
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int cnt = 0;

template< class RandomIter, class Predicate =
	std::less< typename std::iterator_traits< RandomIter >::value_type > >
	static inline bool iter_sorting_swap(RandomIter a, RandomIter b,
		Predicate pred = Predicate())
{
	if (a > b) { return iter_sorting_swap(b, a); }
	// arguments must be a <= b
	return pred(*b, *a) ? std::iter_swap(a, b), true : false;
}

template< class RandomIter >
void quick_sort(RandomIter first, RandomIter last)
{
	if (last - first <= 1) { return; }
	RandomIter i = first, j = last - 1;
	for (RandomIter pivot = first;; ++i, --j)
	{
		while (*i < *pivot) { ++i; }
		while (*pivot < *j) { --j; }
		if (i >= j) { break; }
		if(iter_sorting_swap(i, j))
			cnt++;
	}
	quick_sort(first, i);
	quick_sort(j + 1, last);
}

void func_b(int N) {
	int temp = 0;
	vector<int> p(N);
	
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}
	quick_sort(begin(p), end(p));

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

	}
}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#define llint long long
#define mod 1000000007

using namespace std;

llint n;
string s;

int main(void)
{
	cin >> n >> s;
	s = "#" + s;
	
	llint ans = 1, cnt = 0;
	for(int i = 1; i <= n*2; i++){
		if(s[i] == 'W'){
			if(cnt%2) cnt++;
			else{
				if(cnt == 0){
					cout << 0 << endl;
					return 0;
				}
				ans *= cnt, ans %= mod, cnt--;
			}
		}
		else{
			if(cnt%2 == 0) cnt++;
			else{
				if(cnt == 0){
					cout << 0 << endl;
					return 0;
				}
				ans *= cnt, ans %= mod, cnt--;
			}
		}
	}
	if(cnt != 0) ans = 0;
	
	for(int i = 1; i <= n; i++) ans *= i, ans %= mod;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 772
import           Control.Applicative
import           Control.Monad

import           Data.List             (sortBy)

-- 1024 = 2 ^ 10
-- 1024 = 32 ^ 2

f :: Int -> [Int]
f n = sortBy (flip compare)
      (1 : [b ^ p | b <- [2 .. 32], p <- [2 .. 10], b ^ p <= n])

main :: IO ()
main = do
    n <- readLn :: IO Int
    print $ head (f n)


Measured memory_bytes: 508
#include <stdio.h>
#include <stdlib.h>
int main(void){
 	int N;
  	long int total=0;
  long int height;
  long int now=0;
  int i;
  scanf("%d",&N);
  for(i=0;i<N;i++){
  	scanf("%ld",&height);
    if(height>now){
    	now=height;
    }else{
    	total+=now-height;
    }
  }
  printf("%ld",total);
}

Measured memory_bytes: 1720
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def solve():
    s = input()
    if s == "ABC":
        print("ARC")
    else:
        print("ABC")

    return 0

if __name__ == "__main__":# {{{
    solve()

# vim: set foldmethod=marker: }}}


Measured memory_bytes: 75060
ABCXY = [int(i) for i in input().split()]
A, B, C, X, Y = ABCXY[0], ABCXY[1], ABCXY[2], ABCXY[3], ABCXY[4]
ans = 0

if 2 * C <= A + B:
    min_pizza = min(X, Y)
    ans += min_pizza * 2 * C
    X -= min_pizza
    Y -= min_pizza

if 2 * C <= A:
    ans += X * 2 * C
else:
    ans += X * A

if 2 * C <= B:
    ans += Y * 2 * C
else:
    ans += Y * B

print(ans)

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

using namespace std;

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;

int n;
int b[N], k[N], idb[N], idk[N], rkb[N], rkk[N];
int lm[N], rm[N], dp[N];
vector<int> bob[N];

bool cmp1(int i, int j) {
  return b[i] < b[j];
}
bool cmp2(int i, int j) {
  return (k[i] != k[j])? k[i] < k[j] : b[i] < b[j];
}

namespace T {
  int t[N];
  void Upd(int x, int val) {
    for (; x <= n + 1; x += x & -x) {
      if ((t[x] += val) >= MOD) {
        t[x] -= MOD;
      }
    }
  }
  int Ask(int x) {
    int ret = 0;
    for (; x; x -= x & -x) {
      if ((ret += t[x]) >= MOD) {
        ret -= MOD;
      }
    }
    return ret;
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &b[i], &k[i]);
    idb[i] = idk[i] = i;
  }

  sort(idb + 1, idb + 1 + n, cmp1);
  sort(idk + 1, idk + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i) {
    rkb[idb[i]] = i;
    rkk[idk[i]] = i;
  }
  
  int mxk = 0;
  for (int i = 1; i <= n; ++i) {
    mxk = max(mxk, rkk[idb[i]]);
    rm[idb[i]] = mxk;
  }
  int mik = N;
  for (int i = n; i >= 1; --i) {
    mik = min(mik, rkk[idb[i]]);
    lm[idb[i]] = mik;
  }

  for (int i = 1; i <= n; ++i) {
    bob[rm[i]].push_back(lm[i]);
  }
  
  dp[0] = 1;
  T::Upd(1, 1);
  
  for (int i = 1; i <= n; ++i) {
    sort(bob[i].begin(), bob[i].end());
    for (int j = 0; j < bob[i].size(); ++j) {
      int p = bob[i][j] - 1;
      int sum = (T::Ask(i + 1) - T::Ask(p) + MOD) % MOD;
      (dp[i] += sum) %= MOD;
      T::Upd(i + 1, sum);
    }
  }

  printf("%d\n", dp[n]);
  
  return 0;
}


Measured memory_bytes: 18944
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w;
  while(cin>>h>>w&&h&&w){
    for(int i=1;i<=h;++i){
      for(int j=1;j<=w;++j){
	cout<<"#";
      }
      cout<<endl;
    }
    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3092
#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    int count = 0;
    std::unordered_set<int> done;
    std::unordered_set<int> ppdone;
    for (int i = 0; i<n; ++i) {
        ppdone.insert(i);
    }
    for (int i = 0; i<n; ++i) {
        int n;
        std::cin >> n;

        std::unordered_set<int> pdone;
        bool dup = false;
        for (int a = 2; a * a <= n; ++a) {
            if (n % a != 0) continue;
            while (n % a == 0) {
                n /= a;
            }
            if (done.find(a) != done.end()) {
                dup = true;
            } else {
                done.insert(a);
            }
            if (ppdone.find(a) != ppdone.end()) {
                pdone.insert(a);
            }
        }
        if (n != 1) {
            int a = n;
            if (done.find(a) != done.end()) {
                dup = true;
            } else {
                done.insert(a);
            }
            if (ppdone.find(a) != ppdone.end()) {
                pdone.insert(a);
            }
        }
        ppdone = pdone;
        if (dup) {
            count += 1;
        }
    }
    if (count == 0) {
        std::cout << "pairwise coprime" << std::endl;
    } else if (ppdone.size() > 0) {
        std::cout << "not coprime" << std::endl;
    } else {
        std::cout << "setwise coprime" << std::endl;
    }
}


Measured memory_bytes: 42596
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define ld double
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define len length()
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect

const int N = 1e4 + 7, INF = 1e9 + 7;

int dp[N];

void solve() {
    loop1(i, N - 1) dp[i] = INF;
    int h, n; pi p; cin >> h >> n;
    loop1(i, n) {
        cin >> p.F >> p.S;
        dp[p.F] = min(dp[p.F], p.S);
    }
    for (int i = N - 2; i > 0; --i)
        dp[i] = min(dp[i], dp[i + 1]);
    loop1(i, h)
        for (int j = 1; j < i; ++j)
            dp[i] = min(dp[i], i / j * dp[j] + dp[i % j]);
    cout << dp[h];
}

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

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>

#define INF 100000000000
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

struct UnionFind{
    vector<long long int> par; //par[i] : iの親の番号
    vector<long long int> rnk; //root[i] : iの木のランク

   //コンストラクタ
    UnionFind(long long int n): par(n), rnk(n){
        //木の初期化
        for(long long int i = 0; i < n; i++){
            par[i] = i;
            rnk[i] = 1;
        }
    }

   //データxが属する木の根を再帰で取得
   long long int root(long long int x){
       if(par[x] == x){
           return x;
       }else{
           return par[x] = root(par[x]);
       }
   }

   //xとyが同じ木に属しているかを判定
   bool same(long long int x, long long int y){
       return root(x) == root(y);
   }

   //xとyの木を併合
   void unite(long long int x, long long int y){
       long long int rx = root(x); //xの根
       long long int ry = root(y); //yの根
       if(rx == ry) return; //根が同じならそのまま

       if(rnk[rx] < rnk[ry]){
           par[rx] = ry;
       }else{
           par[ry] =rx;
           if(rnk[rx] == rnk[ry]) rnk[rx]++;
       }
   }
};

int main(){
    long long n, m;
    cin >> n >> m; 
    vector<pair<int, int> > data(m);

    for(int i=0;i<m;i++) {
        long long a, b;
        cin >> a >> b;
        data[i] = make_pair(a-1, b-1);
    }
    int ans = 0;
    for(int i=0;i<m;i++) {
        UnionFind uf(n);

        for(int j=0;j<m;j++) {
            if(i!=j) uf.unite(data[j].first, data[j].second);
        }
        if(uf.root(data[i].first) != uf.root(data[i].second)) ans += 1;
    }
    cout << ans << endl;
}

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

int main() {
    string S;
    cin >> S;
    bool isBad = false;
    for (int x=0; x < S.size(); x++){
        if(S[x]==S[x+1]){
            isBad = true;
        }
    }
    if (isBad){
        cout << "Bad" << endl;
    }
    else {
        cout << "Good" << endl;
    }
    
	return 0;
}


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

//template<typename T>
#define o_set(T) tree<T, null_type,greater<T>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//use it like o_set(ll) x;  --> x.order.....
//-->for pair<ll,ll> : second element as index and for search use INT_MAX...
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set


#define fast ios::sync_with_stdio(false);cin.tie(0);cout<<setprecision(25)
#define pb push_back
#define I insert
#define F first
#define S second
#define digit(x) floor(log10(x))+1
const long long M1=1000000007;
const long long  M2=998244353;
#define L_MAX 1e18
using ll = long long;
using ld = long double;
using ii = pair<ll,ll>;
using matrix = vector<vector<ll>>;
using arr = vector<ll>;
using vs = vector<string>;
using pv = vector<ii>;
#define in1(x) scanf("%lld",&x)
#define in2(x,y) scanf("%lld %lld",&x,&y)
#define all(x) x.begin(),x.end()
#define debug(x) cerr << #x << " is " << x << endl;
template<typename T>
void showArr(T a){
    for(auto i : a) cout<<i<<" ";
    cout<<endl;
}
bool isValid(ll x,ll y,ll n,ll m){
    return (x>=0 and y>=0 and x<n and y<m);
}
ll power(ll a,ll n,ll m){
    ll ans=1;
    while(n>0){
        if(n&1){
            ans=(ans%m * a%m)%m;
        }
        n=n>>1;
        a=(a%m*a%m)%m;
    }
    return ans;
}
ll MMI(ll a,ll m){
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1){
        ll q=a/m,t=m;
        m=a%m,a=t,t=y,y=x-q*y,x=t;
    }
    if(x<0) x+=m0;
    return x;
}

ll dx[]={-1,1,0,0},dy[]={0,0,-1,1};
//ll dx[]={-1,1,-1,1,0,0,-1,1} , dy[]={-1,1,0,0,-1,1,1,-1};
int main(){
    fast;
    ll t;
    ld d;
    cin>>t>>d;
    ll ans=0;
    while(t--){
        ll x,y;
        cin>>x>>y;
        ld dist=sqrt(x*x+y*y);
        if(dist<=d)
            ans++;
    }
    cout<<ans<<endl;
    
    
    return 0;
}

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

#define For(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Rep(i,n) For(i,0,n)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<P, int> PPI;

#define INF 1000000000

#define MAX_N 1000

int W, H;
char p[10][61];
int vis[10][61];

struct peace{
	int xl, xr, sumn;
	int bn[10];
};

peace P[100];
int pcnt = 0;

void dfs(peace *a, int x, int y, int c, char s, char flag){
	vis[x][y] = c;
	a->sumn++;
	a->bn[x]++;
	if((y+1 == H) || (y+1<H && p[x][y+1] != '.' && p[x][y+1] != s && flag == 1)){
		if(a->xl > x) a->xl = x;
		if(a->xr < x+1) a->xr = x+1;
	}
	For(dx,-1,2)For(dy,-1,2){
		if((dx == 0 && dy == 0) || (dx != 0 && dy != 0)) continue;
		if(x+dx >= 0 && x+dx < W && y+dy >= 0 && y+dy < H){
			if((p[x+dx][y+dy] == s) && (vis[x+dx][y+dy] < c)){
				dfs(a, x+dx, y+dy, c, s, flag);
			}
			if((dy == -1 && p[x][y+dy] != '.') && (vis[x+dx][y+dy] < c)){
				dfs(a, x+dx, y+dy, c, p[x][y+dy], 0);
			}
		}
	}
}

void solve(){
	Rep(i,H){
		Rep(j,W){
			if(p[j][i] != '.' && vis[j][i] == 0){
				P[pcnt].sumn = 0;
				P[pcnt].xl = 100;
				P[pcnt].xr = -1;
				Rep(k,10) P[pcnt].bn[k] = 0;
				dfs(&P[pcnt], j, i, pcnt+1, p[j][i], 1);
				double sent = 0;
				Rep(k,10){
					sent += P[pcnt].bn[k]*(double)(k+0.5);
				}
				sent /= P[pcnt].sumn;
				if(sent <= P[pcnt].xl || sent >= P[pcnt].xr){
					cout << "UNSTABLE" << endl;
					//dbg(i);
					//dbg(j);
					return;
				}
				pcnt++;
			}
		}
	}
	cout << "STABLE" << endl;
}

int main(){
	while(1){
		cin >> W >> H;
		if(W == 0 && H == 0) break;
		pcnt = 0;
		Rep(i,H)Rep(j,W){ cin >> p[j][i]; vis[j][i] = 0; }
		solve();
	}
	return 0;
}

Measured memory_bytes: 1168
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 50

int main() {
  int i, j;
  long long int K;
  scanf("%lld", &K);
  long long int shou = K / N;
  long long int amari = K % N;
  long long int basic = (N-1) + shou;

  printf("%lld\n", N);

  for (i = 0; i < amari;i++) {
    printf("%lld", basic + N - (amari - 1));
    printf(" ");
  }
  for (i = amari; i < N;i++) {
    printf("%lld", basic - amari);
    printf(" ");
  }
  return 0;
}

Measured memory_bytes: 128
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
	static Scanner s=new Scanner(System.in);
	public static void main(String[] __){
		TreeSet<Rect> ts=new TreeSet<>(
					Comparator.comparingInt(Rect::getDiagSq).thenComparingInt(Rect::getH)
				);
		for(int i=1;i<=150;i++) for(int j=i+1;j<=150;j++) ts.add(new Rect(i,j));
		while(true){
			int h=s.nextInt(),w=s.nextInt();
			if(h+w==0) return;
			System.out.println(ts.higher(new Rect(h,w)));
		}
	}
}
class Rect{
	int h,w;
	Rect(int h,int w){
		this.h=h;
		this.w=w;
	}
	int getDiagSq(){
		return h*h+w*w;
	}
	int getH(){
		return h;
	}
	@Override
	public String toString(){
		return h+" "+w;
	}
}

Measured memory_bytes: 36648
from collections import Counter

N, M = map(int, input().split())
li = []
for _ in range(M):
  a, b = map(int, input().split())
  li.append(a)
  li.append(b)
  
cli = Counter(li)
if all([v % 2 == 0 for i, v in cli.items()]):
  print("YES")
else:
  print("NO")

Measured memory_bytes: 16000
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int n,r;

int main()
{
	cin>>n>>r;
	if(n<10) cout<<r+100*(10-n)<<endl;
	else cout<<r<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

struct tree {
	int id, left, right, parent;
};

void init(tree trees[], int n) {
	for (int i = 0; i < n; i++) {
		trees[i].parent = -1;
	}
}

void sort(tree trees[], int n) {
	tree temp;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n - i; j++) {
			if (trees[j - 1].id > trees[j].id) {
				temp = trees[j - 1];
				trees[j - 1] = trees[j];
				trees[j] = temp;
			}
		}
	}
}

void setParent(tree trees[], int n){
	for (int i = 0; i < n; i++) {
		if (trees[i].left != -1) {
			trees[trees[i].left].parent = trees[i].id;
		}
		if (trees[i].right != -1) {
			trees[trees[i].right].parent = trees[i].id;
		}
	}
}

void Preorder(tree trees[], int node) {
	std::cout << " " << trees[node].id;
	if (trees[node].left != -1) {
		Preorder(trees, trees[node].left);
	}
	if (trees[node].right != -1) {
		Preorder(trees, trees[node].right);
	}
}

void Inorder(tree trees[], int node) {
	if (trees[node].left != -1) {
		Inorder(trees, trees[node].left);
	}
	std::cout << " " << trees[node].id;
	if (trees[node].right != -1) {
		Inorder(trees, trees[node].right);
	}
}

void Postorder(tree trees[], int node) {
	if (trees[node].left != -1) {
		Postorder(trees, trees[node].left);
	}
	if (trees[node].right != -1) {
		Postorder(trees, trees[node].right);
	}
	std::cout << " " << trees[node].id;
}
int main() {
	int n;
	tree trees[25];

	// ??????????????°?????\???
	std::cin >> n;

	init(trees, n);
	int id, left, right;
	for (int i = 0; i < n; i++) {
		std::cin >> id >> left >> right;
		trees[i].id = id;
		trees[i].left = left;
		trees[i].right = right;
	}

	sort(trees, n);
	setParent(trees, n);

	for (int i = 0; i < n; i++) {
		if (trees[i].parent == -1) {
			std::cout << "Preorder" << std::endl;
			Preorder(trees, i);
			std::cout << std::endl << "Inorder" << std::endl;
			Inorder(trees, i);
			std::cout << std::endl << "Postorder" << std::endl;
			Postorder(trees, i);
		}
	}
	std::cout << std::endl;
	return 0;
}

Measured memory_bytes: 1164
# -*- coding: utf-8 -*-
# get a integer
N = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
point = 0
temp_a = 0
temp_c = 0
# calc
for i in range(N):
  if((a[i] == (temp_a + 1)) and (i >= 1)):
    point = point + b[a[i]-1] + c[a[i]-1-1]
  else:
    point = point + b[a[i]-1]
      
  temp_a = a[i]
   

# output

print(str(point));



Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		System.out.println(Math.abs(a - c) <= d ? "Yes"
							: Math.abs(a - b) <= d && Math.abs(b - c) <= d ? "Yes"
							: "No");

		sc.close();
	}

}




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

int main(void)
{
  std::string s, t;
  std::cin >> s >> t;

  int count = 0;
  for(int i=0; i<s.size(); i++)
  {
   	if(s[i] != t[i]) { count += 1; } 
  }
  
  std::cout << count << std::endl;
  return 0;
}

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

const int mod = 1000000007;

struct mint {
    ll x;

    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint operator-() const { return mint(-x); }

    mint &operator+=(const mint a) {
      if ((x += a.x) >= mod) x -= mod;
      return *this;
    }

    mint &operator-=(const mint a) {
      if ((x += mod - a.x) >= mod) x -= mod;
      return *this;
    }

    mint &operator*=(const mint a) {
      (x *= a.x) %= mod;
      return *this;
    }

    mint operator+(const mint a) const {
      mint res(*this);
      return res += a;
    }

    mint operator-(const mint a) const {
      mint res(*this);
      return res -= a;
    }

    mint operator*(const mint a) const {
      mint res(*this);
      return res *= a;
    }

    mint pow(ll t) const {
      if (!t) return 1;
      mint a = pow(t >> 1);
      a *= a;
      if (t & 1) a *= *this;
      return a;
    }

    mint inv() const {
      return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
      return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
      mint res(*this);
      return res /= a;
    }
};

signed main() {
  int n,k;
  cin >> n >> k;

  vector<int> a(n);
  vector<int> s,t;

  // t : negative, s : positive
  rep(i,n) {
    cin >> a[i];
    if(a[i] < 0) t.push_back(a[i]);
    else s.push_back(a[i]);
  }

  int S = s.size();
  int T = t.size();

  bool ok = false;
  if(S > 0) {
    if(n == k) ok = (T % 2 == 0);
    else ok = true;
  } else {
    ok = (k % 2 == 0);
  }

  vector<int> v(n);
  rep(i,n) v[i] = abs(a[i]);
  sort(v.begin(),v.end());

  mint ans = 1;
  if(!ok) {
    for (int i = 0; i < k; i++) {
      ans *= v[i];
    }
    ans *= (-1);
    cout << ans.x << '\n';
  } else {
    sort(s.begin(),s.end());
    sort(t.rbegin(), t.rend());
    if(k % 2 == 1) {
      ans *= s.back();
      s.pop_back();
    }

    vector<ll> p;
    while(s.size() >= 2) {
      ll tmp = s.back(); s.pop_back();
      tmp *= s.back(); s.pop_back();
      p.push_back(tmp);
    }
    while(t.size() >= 2) {
      ll tmp = t.back(); t.pop_back();
      tmp *= t.back(); t.pop_back();
      p.push_back(tmp);
    }
    sort(p.rbegin(),p.rend());
    rep(i, k / 2) ans *= p[i];
    cout << ans.x << '\n';
  }

}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;

#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define REP(i, n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a, b) a = min((a),(b))
#define CHMAX(a, b) a = max((a),(b))
#define ZP(a, len) cout << setfill('0') << setw(len) << right << a << endl;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

signed main() {
    string s;
    cin >> s;
    string agct = "AGCT";
    int ans = 0, cnt = 0;
    for (auto c : s) {
        if (agct.find(c) != agct.npos) {
            cnt++;
        } else {
            ans = max(cnt, ans);
            cnt = 0;
        }
    }
    ans = max(cnt, ans);
    cout << ans << endl;
    return 0;
}


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

int main(){

    int n;
    cin >> n;

    vector<int> color(8);
    int more = 0;
    int val;
    for(int i = 0; i < n; i++){
        cin >> val;
        val = val / 400;
        if(val < 8) color[val] = 1;
        if(val >= 8) more ++;
    }

    int color_count = 0;
    for(int i = 0; i < 8; i++){
        if(color[i]) color_count++;
    }

    cout << max(1, color_count) << " " << (color_count + more) << endl;


}

Measured memory_bytes: 256
import math

N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
ave = 0
cnt = 0
import itertools
for v in itertools.permutations([int(x) for x in range(N)],N) :
    for i in range(1,len(v)) :
        ave += math.sqrt((xy[v[i-1]][0]-xy[v[i]][0])**2+(xy[v[i-1]][1]-xy[v[i]][1])**2)
    cnt += 1

ave = ave / cnt
print(ave)

Measured memory_bytes: 9240
#include<bits/stdc++.h>
using namespace std;
const int N=305,mod=1e9+7;
inline void add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
int dp[N][N][N],n,m,ans;
vector<int>l[N],x[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		l[b].push_back(a);
		x[b].push_back(c);
	}
	dp[0][0][0]=1;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				int r=max(max(i,j),k);
				int &f=dp[i][j][k];
				for(int z=0;z<l[r].size();z++)
				{
					int s=(i>=l[r][z])+(j>=l[r][z])+(k>=l[r][z]);
					if(s!=x[r][z])
						f=0;
				}
				add(dp[r+1][j][k],f);
				add(dp[i][r+1][k],f);
				add(dp[i][j][r+1],f);
				if(r==n)
					add(ans,f);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 113456
#include <bits/stdc++.h>
#define ll long long

using namespace std;

class UnionFind {
public:
  vector<int> parent;
  UnionFind(int n) { parent = vector<int>(n, -1); }
  int root(int a) {
    if(parent[a] < 0)
      return a;
    return parent[a] = root(parent[a]);
  }
  int size(int a) { return -parent[root(a)]; }
  bool connect(int a, int b) {
    a = root(a);
    b = root(b);
    if(a == b)
      return false;
    if(size(a) < size(b))
      swap(a, b);
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }
};

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> a(m), b(m), d(m + 1);
  UnionFind uni(n);
  for(int i = m - 1; i >= 0; i--) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  d[0] = n * (n - 1) / 2;
  for(int i = 0; i < m; i++) {
    d[i + 1] -= uni.size(a[i]) * uni.size(b[i]);
    if(uni.connect(a[i], b[i]))
      d[i + 1] += d[i];
    else
      d[i + 1] = d[i];
  }
  for(int i = m - 1; i >= 0; i--)
    cout << d[i] << endl;
}

Measured memory_bytes: 4096
import java.util.Scanner;

/**
 * 2019/06/09
 * AtCoder Beginner Contest 129
 * 
 * D - Lamp
 * 
 * @author rued97
 */
public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		
		int H = sc.nextInt();
		int W = sc.nextInt();
		boolean S[][] = new boolean[H][W];		// 障害物なし：true 障害物あり：false
		for(int i = 0; i < H; i++) {
			String line = sc.next();
			for(int j = 0; j< W; j++) {
				S[i][j] = (line.charAt(j) == '.');
			}
		}
		
		int cnts[][] = new int[H][W];
		// 横方向計
		for(int i = 0; i < H; i++) {
			int cntsj = 0;
			int tmpSum = 0;
			for(int j = 0; j < W; j++) {
				if(S[i][j] == false) {
					while(cntsj < j) {
						cnts[i][cntsj] = tmpSum;
						cntsj++;
					}
					cnts[i][cntsj] = 0;
					cntsj++;
					tmpSum = 0;
				} else {
					tmpSum++;
				}
			}
			while(cntsj < W) {
				cnts[i][cntsj] = tmpSum;
				cntsj++;
			}
		}
		// 縦方向加算
		for(int j = 0; j < W; j++) {
			int cntsi = 0;
			int tmpSum = 0;
			for(int i = 0; i < H; i++) {
				if(S[i][j] == false) {
					while(cntsi < i) {
						cnts[cntsi][j] += tmpSum - 1;
						cntsi++;
					}
					cntsi++;
					tmpSum = 0;
				} else {
					tmpSum++;
				}
			}
			while(cntsi < H) {
				cnts[cntsi][j] += tmpSum - 1;
				cntsi++;
			}
		}
		
		int max = 0;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j< W; j++) {
				if(cnts[i][j] > max) {
					max = cnts[i][j];
				}
			}
		}
		System.out.println(max);
	}
	
}

Measured memory_bytes: 59932
from collections import deque

N = int(input())

dic = {i:[] for i in range(1,N+1)}

rlt = [0]*(N-1)

for i in range(N-1):
  a,b = map(int, input().split())
  dic[a].append((b,i))
  dic[b].append((a,i))
  
h = deque([(1,1)])

while h:
  j = 1
  c = 0
  t = h.popleft()
  for k in dic[t[0]]:
    if k[0] == t[1]:
      c = rlt[k[1]]
      break
  for k in dic[t[0]]:
    if k[0] == t[1]:
      continue
    if c == j:
      j += 1
    rlt[k[1]] = j
    h.append((k[0],t[0]))
    j += 1
    
print(max(rlt))  
for l in rlt:
  print(l)  

Measured memory_bytes: 97112
// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX = 100001;
//
//
void solve(){
    int n;
    cin>>n;
    vector<ll> fst(n), snd(n);
    for(int i = 0; i < n; i++)
        cin>>fst[i]>>snd[i];
    double fstmedian, sndmedian;
    sort(fst.begin(), fst.end());
    sort(snd.begin(), snd.end());
    ll ans;
    if(n&1){
        fstmedian = fst[n/2];
        sndmedian = snd[n/2];
        ans = sndmedian - fstmedian + 1;
    }
    else{
        fstmedian = (fst[n/2-1] + fst[n/2])/2.00;
        sndmedian = (snd[n/2 -1] + snd[n/2])/2.00;
        ans = 2*(sndmedian - fstmedian) + 1;
    }
    cout<<ans;
}
int main(){ 
        hs;
        ll t;
        t=1;
        // cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}

Measured memory_bytes: 6348
#include<stdio.h>
int main(void)
{
	int n,x[101],m,a,i,j,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x[i]);

	}
	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%d",&a);
		if(x[a]+1!=x[a+1]&&x[a]!=2019){
			x[a]=x[a]+1;
		}
	}
	for(i=1;i<=n;i++){
		printf("%d\n",x[i]);
	}
	return 0;
}


Measured memory_bytes: 2148
#include <bits/stdc++.h>
#define ll long long
#define f(i, x, n) for(int i = x; i < n; i++)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define dbg3(x, y, z) cout << x << " " << y << " " << z << endl
#define mod 1000000007
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    int a, b, c;
    cin >> a >> b >> c;
    dbg3(c, a, b);
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;

void main()
{
    while(true)
    {
        auto line = readln;
        if(!line)break;
        auto f = line.chomp.to!real;
        f.classify.writeln;
    }
}

string classify(real w)
{
    if(w <= 48) return "light fly";
    if(w <= 51) return "fly";
    if(w <= 54) return "bantam";
    if(w <= 57) return "feather";
    if(w <= 60) return "light";
    if(w <= 64) return "light welter";
    if(w <= 69) return "welter";
    if(w <= 75) return "light middle";
    if(w <= 81) return "middle";
    if(w <= 91) return "light heavy";
    return "heavy";
}

Measured memory_bytes: 1064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    int N;
    cin >> N;
    long long A[N+1],B[N+1];

    rep(i,N+1)  cin >> A[i];

    rep(i,N) cin >> B[i];
    B[N]=0;

    long long ans=0;
    long long db=0;
    rep(i,N+1){
        if(db>=A[i]){
            ans+=A[i];
            db=B[i];
            continue;
        }
        else {
            B[i]+=db;
        }
        if(A[i]-B[i]>=0){
            ans+=B[i];
            db=0;
        }else{
            db=B[i]-A[i];
            ans+=A[i];
        }
    }
    cout << ans << endl;


}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}

template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto &e : x)
        	out << e << (&e == &*--x.end() ? "" : ", ");
	return out << '}';
}

template<class... Args> void dump(Args&&... args) {
	((cerr << args << ";  "), ...);
}
 
#ifdef DEBUG
#  define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << "\n"
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

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

	char a, b, c;
	cin >> a >> b >> c;
	cout << a << b << c << "\n";
}


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

int main(){
  string o, e, ans="";
  cin >> o;
  cin >> e;
  
  for (int i=0; i<o.size(); i++) {
    ans += o[i];
    if (i<e.size()) ans += e[i];
  }
  
  cout << ans << endl;
    
  return 0;  
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<ll, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<int> t;
    int a;
    for(int i = 1; i <= n; i ++ ){
        cin >> a;
        if(t.empty() || t.back() != a){
            t.push_back(a);
        }
    }
    vector<int> seq;
    for(int i = 1; i < t.size(); i ++ ){
        if(t[i] > t[i-1])
            seq.push_back(1);
        else
            seq.push_back(0);
    }
    int res = 1;
    for(int i = 1; i < seq.size(); i ++ ){
        if(seq[i] != seq[i-1]){
            res ++ ;
            i ++ ;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 1400