akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

    auto low = numeric_limits<int>::max(), high = 0;
    auto gap = 0, counts = 0;
    for (auto i = 0; i < N; i++)
    {
        int x; cin >> x;

        if (x < low)
        {
            low = x;
            high = 0;
        }
        else if (x > high)
        {
            high = x;
            if (high-low > gap)
            {
                gap = high-low;
                counts = 1;
            }
            else if (high-low == gap) counts++;
        }
    }

    cout << counts << endl;
}


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

std::vector<int> day[31];
std::list<int> member[51];
int n,m,a;
int gi;

int main(void){
	while(cin>>n,n){
		for(int i=0;i<31;i++)day[i].clear();
		for(int i=0;i<n;i++)member[i].clear();
		for(int i=0;i<n;i++)member[i].push_front(i);
		bool flag=false;
		for(int i=0;i<n;i++){
			cin>>m;
			for(int j=0;j<m;j++){
				cin>>a;
				day[a].push_back(i);
			}
		}

		for(int gi=0;gi<31;gi++){
			// cout<<"day"<<gi<<":"<<endl;
			if(day[gi].size()<=1)continue;
			for(int i=1;i<day[gi].size();i++){ member[day[gi][0]].merge(member[day[gi][i]]); }
			// member[day[gi][0]].sort();
			member[day[gi][0]].unique();
			for(int i=1;i<day[gi].size();i++){ member[day[gi][i]]=member[day[gi][0]]; }
			/*
				 for(int i=0;i<n;i++){
				 cout<<"list:"<<i<<endl;
				 for(list<int>::iterator it=member[i].begin();it!=member[i].end();it++){
				 cout<<*it<<" ";
				 }
				 cout<<endl;
				 }
				 */
			for(int i=0;i<n;i++){
				if(member[i].size()==n){
					flag=true;
					cout<<gi<<endl;
					goto LAB;
				}
			}
		}
LAB:
		if(!flag)cout<<"-1"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
#define ll long long
#define INF LONG_LONG_MAX
#define pb push_back
#define mp make_pair
#define MAXN 1000009
#define MOD 1000000007
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
using namespace std;

int main(){
    int n,ans=1,maxi=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        int x=i,cnt=0;
        while(x%2==0){
            x/=2;
            cnt++;
        }
        if(cnt>maxi){
            maxi=cnt;
            ans=i;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
main(){
  int n;
  cin>>n;
  int ans=1,t=0;
  for(int i=1;i<=n;++i){
    int x=i,cnt=0;
    while(x%2==0){
      x/=2;
      cnt++;
    }
    if(cnt>t){
      ans=i;
      t=cnt;
    }
  }
  cout<<ans<<endl;
}


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


int main() {

  int n;
  cin>>n;

  int wk_max=0, cnt=0;
  for(int i=0;i<n;i++){
    int h;
    cin>>h;
    if(h>=wk_max){
      cnt++;
      wk_max=max(h,wk_max);
    }
  }

  cout<<cnt<<endl;

  return 0;
}



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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(abs(a-b) <= d && abs(c-b) <= d){
        cout << "Yes" << endl;
    } else if(abs(a-c) <= d){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");
long bignum = 1_000_000_007;
auto dp = new long[](100_100);

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    auto n = lread();
    auto a = aryread();
    long sunuke, rascoon = a.sum;
    auto accum = long.max;
    foreach (i, e; a)
    {
        sunuke += e;
        rascoon -= e;
        if (i < n - 1)
            accum = min(abs(sunuke - rascoon), accum);
    }
    accum.writeln();
}

Measured memory_bytes: 11652
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

#define inf  1000001
#define ind  -1000001
typedef int long long ll;


int main(){
    vector<ll> v;
    int n;
    cin>>n;
    ll mxp;
    ll mip;
    
    rep(i,n){
        ll x;
        cin>>x;
        v.push_back(x);
    }
    mxp=max_element(v.begin(),v.end())-v.begin();
     mip=min_element(v.begin(),v.end())-v.begin();
    if(mip==mxp){
        cout<<0<<endl;return 0;
    }
    cout<<2*n-1<<endl;
    
    if(abs(v[mip])<abs(v[mxp])){
        for(int i=0;i<v.size();i++){
            cout<<mxp+1<<" "<<i+1<<endl;
        }
        for(int i=1;i<n;i++){
            cout<<i<<" "<<i+1<<endl;
        }
    }else{
        for(int i=0;i<v.size();i++){
            cout<<mip+1<<" "<<i+1<<endl;
        }
        for(int i=n-1;i>0;i--){
            cout<<i+1<<" "<<i<<endl;
        }
    }
    return 0;
}


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


int main() {
   int H, W, K; cin >> H >> W >> K;
   vector<string> grid_origin(H);
   rep(i, H)cin >> grid_origin[i];

   ll res = 0;
   for(int bh= 0; bh<(1 << H); bh++){
       for(int bw=0; bw<(1 << W); bw++){
           vector<string> grid = grid_origin;
           for(int i=0; i<H; i++){
               if(bh & (1 << i)){
                   rep(a, W){
                       grid[i][a] = 'r';
                   }
               }
           }
           for(int i=0; i<W; i++){
               if(bw & (1 << i)){
                   rep(a, H){
                       grid[a][i] = 'r';
                   }
               }
           }
           int cnt = 0;
           rep(i, H){
               rep(j, W){
                   if(grid[i][j] == '#')cnt++;
               }
           } 
           if(cnt==K)res++;          
       }
   }
   cout << res << ln;
}


Measured memory_bytes: 3632
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int d[100][100];
    int n;
    scanf("%d",&n);
    fill(*d,*d+100*100,1<<25);
    for(int i=0;i<n;i++)d[i][i]=0;
    for(int i=0;i<n;i++){
        int r,k;
        scanf("%d%d",&r,&k);
        r--;
        for(int j=0;j<k;j++){
            int t;
            scanf("%d",&t);
            t--;
            d[r][t]=1;
        }
    }

    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]);
            }
        }
    }
    int m;
    scanf("%d",&m);
    while(m--){
        int s,g,t;
        scanf("%d%d%d",&s,&g,&t);
        s--;g--;
        int val=d[s][g];
        if(t<=val)puts("NA");
        else printf("%d\n",val+1);
    }
    return 0;

}

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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int n, m; cin >> m >> n;
  vector<int> x(n);
  for(int i=0;i<n;++i) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  vector<int> d(n-1);
  for(int i=0;i<n-1;++i) {
    d[i] = x[i+1] - x[i];
  }

  sort(d.begin(), d.end());
  

  ll ans = 0;
  for(int i=0;i<n-m;++i) {
    ans += d[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
def check_p(packages, n, trucks, max_p):
    i = 0
    for _ in range(trucks):
        sum = 0
        while sum + packages[i] <= max_p:
            sum += packages[i]
            i += 1
            if i == n:
                return i
    return i

n, k = map(int, input().split())
packages = []
for _ in range(n):
    packages.append(int(input()))

left = 0
right = 10 ** 5 * 10 ** 4
while left + 1 < right:
    mid = (left + right) // 2
    num = check_p(packages, n, k, mid)
    if num < n:
        left = mid
    else:
        right = mid
print(right)



Measured memory_bytes: 9556
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pl = pair<ll, ll>;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}, dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	queue<ll> que;
	rep(i, 9) que.push(i + 1);
	rep(i, n) {
		ll q = que.front();
		que.pop();
		if (i == n - 1)
			cout << q << endl;
		else {
			if (q % 10 > 0) que.push(q % 10 - 1 + q * 10);
			que.push(q % 10 + q * 10);
			if (q % 10 < 9) que.push(q % 10 + 1 + q * 10);
		}
	}
	return 0;
}

Measured memory_bytes: 4772
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string { sc.Scan(); return sc.Text() }
func scanRunes() []rune { return []rune(scanString()) }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	m := scanInt()

	ans := 1
	if n == 1 {
		ans = m
	}
	for i := 2; i*i <= m; i++ {
		if m%i == 0 {
			if m/i >= n {
				ans = max(ans, i)
			}
			if i >= n {
				ans = max(ans, m/i)
			}
		}
	}

	fmt.Fprintln(wr, ans)
	
}


Measured memory_bytes: 640
#!/usr/bin/env python3

N, M = map(int, input().split())

C = {}
for i in range(N):
    C[i+1] = 0

D = {}

for i in range(M):
    P, Y = map(int, input().split())
    D[Y] = [P, i]

ret = {}
for y, p in sorted(D.items(), key=lambda x: x[0]):
    C[p[0]] += 1
    ret[p[1]] = str(p[0]).zfill(6) + str(C[p[0]]).zfill(6)
    
for i, r in sorted(ret.items(), key=lambda x: x[0]):
    print(r)



Measured memory_bytes: 62532
// Create time: 2019-09-02  15:56:22
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N (1 << 21)
#define rint register int
using namespace std;
const int Mod = 1e9 + 7;

int n, m, K, mp[24][24];
int f[22][N], g[22][N], nxt[22][N];

inline void ad(int& x, int y) {
    x += y, x -= x >= Mod ? Mod : 0;
}

inline int get(int S, int pos) {
    for (rint i = pos; i < n; ++i)
        if ((S >> i) & 1)
            return (S ^ (1 << i)) | (1 << pos);
    return S | (1 << pos);
}

inline void output(int s, char ch) {
    for (rint i = 0; i < n; ++i)
        if ((s >> i) & 1) putchar('1');
        else putchar('0');
    putchar(ch);
}

int main() {
#ifdef whyqx
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif
    cin >> n >> m >> K; --n;
    memset(mp, -1, sizeof mp);
    for (int i = 1, x, y, q; i <= K; ++i)
        scanf("%d%d%d", &x, &y, &q), mp[x][y - 1] = q;
    for (rint i = 0; i < n; ++i)
        for (rint S = 0, sz = 1 << n; S < sz; ++S)
            nxt[i][S] = get(S, i);
    f[0][0] = 1;
    for (rint i = 1; i <= m; ++i) {
        for (rint j = 0; j < n; ++j)
            for (rint S = 0, sz = 1 << n; S < sz; ++S) {
                if (!f[j][S]) continue;
                if (mp[i][j] == -1 || ((S >> j) & 1) == mp[i][j])
                    ad(f[j + 1][S], f[j][S]);
                if (((S >> j) & 1) == 0 && mp[i][j] != 0)
                    ad(f[j + 1][nxt[j][S]], f[j][S]);
                f[j][S] = 0;
            }
        for (rint S = 0, sz = 1 << n; S < sz; ++S)
            f[0][S] = f[n][S], f[n][S] = 0;
    }
    long long ans = 0;
    for (rint S = 0, sz = 1 << n; S < sz; ++S)
        (ans += f[0][S]) %= Mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 160128
#include <stdio.h>

const int Mod = 1000000007;

int main()
{
	int i, N, K, a[101];
	scanf("%d %d", &N, &K);
	for (i = 1; i <= N; i++) scanf("%d", &(a[i]));
	
	int j;
	long long dp[100001] = {1}, sum[100001];
	for (i = 1; i <= N; i++) {
		for (j = 1, sum[0] = dp[0]; j <= K; j++) sum[j] = (sum[j-1] + dp[j]) % Mod;
		for (j = K; j > a[i]; j--) dp[j] = (sum[j] - sum[j-a[i]-1] + Mod) % Mod;
		for (; j >= 1; j--) dp[j] = sum[j] % Mod;
	}
	printf("%lld\n", dp[K]);
	fflush(stdout);
	return 0;
}

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

typedef long long ll;
ll x, y, a, b, c;

int main() {
    ios::sync_with_stdio(false);
    cin >> a >> b >> c >> x >> y;
    ll minn = min(x, y), maxn = max(x, y);
    ll ans = x * a + y * b;
    ans = min(ans, 2 * minn * c + (x - minn) * a + (y - minn) * b);
    ans = min(ans, 2 * maxn * c);
    cout << ans << endl;
    return 0;
}


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

Measured memory_bytes: 14252
/*
ÂmÂ[ÂhÂÃ° n/2 ÂÃÂÃ2ÂÃÂÃÂOÂÂÂ[ÂvÂÃÂÂªÂÂ¯ÂÃ©

  ÂOÂÂÂ[Âv1   ÂOÂÂÂ[Âv2
  ---------   ---------
          1           0
          2           5
          3           4

ÂÂ±ÂÃ2ÂÃÂÃÂOÂÂÂ[ÂvÂÃ°ÂÃÂÂºÂÃÂÂÂÃÂÃÂMÂUÂMÂUÂÃÂÃÂÃÂÂ°ÂÃ©ÂÃ1ÂpÂ^Â[ÂÂÂÃÂÂ«ÂÂ ÂÂªÂÃ©.
  0 -> 1 -> 5 -> 2 -> 4 -> 3

ÂÂ³ÂÃ§ÂÃ, ÂÂ±ÂÃÂpÂ^Â[ÂÂÂÃ°ÂÂ½ÂÂÂvÂÃ±ÂÃ¨ÂÃÂÂÂÃÂÃÂÃ±Â]ÂÂ³ÂÂ¹ÂÃÂÂ¢ÂÂ­ÂÃ,
  0 -> 1 -> 5 -> 2 -> 4 -> 3
  1 -> 2 -> 0 -> 3 -> 5 -> 4
  2 -> 3 -> 1 -> 4 -> 0 -> 5
ÂÃÂÃ°ÂÂ¤ÂLÂÂµÂÃÂÂ¢(n / 2)ÂÃÂÃÂSÂÃ¦ÂÃÂÃ°ÂÂ¾ÂÃ©ÂÂ±ÂÃÂÂªÂÃÂÂ«ÂÃ©.

n=ÂÃ´ÂÂÂÃÂÂ ÂÃ©ÂÃÂÂ«, ÂÂ±ÂÃÂ@ÂÂ¥ÂÃÂÂµÂÂ½ÂÂªÂÃÂÃÂSÂÃ¦ÂÃÂÃ°ÂgÂÃÂÃÂÂ¢ÂÃÂÂ½ÂÃªÂÂ,
ÂSÂÃ¦ÂÃÂÃÂgÂÃ­ÂÃÂÂ¢ÂÃ¦ÂÂ¤ÂÃÂÂ³ÂÃÂÃÂGÂbÂWÂÂª1ÂÃÂÃ ÂÂ­ÂÂ¶ÂÂµÂÃÂÂ¢.

ÂÂ±ÂÃÂÂ±ÂÃÂÂ©ÂÃ§, ÂÂ±ÂÃÂÃ»Â@ÂÂªÂÃªÂÃÂÂ½ÂÂ­ÂÂ³ÂÃ±ÂSÂÃ¦ÂÃÂÃ°ÂÃ¬ÂÃ©ÂÂ±ÂÃÂÂªÂÃÂÂ«ÂÃ©.


ÂÂÂÂ½ÂÃÂÂ
  ÂoÂÃÂÂªÂÂ½ÂÂ·ÂÂ¬ÂÃ©ÂÃÂ\ÂzÂÃÂÂ«ÂÃ©ÂÃªÂÂÂÃ, printfÂÃ°ÂgÂÂ¤

 */

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int n, k;

  while(cin >> n >> k){
    if(n / 2 < k){
      printf("-1\n");
      //cout << "-1\n";
      continue;
    }

    int p[n + 2];
    p[0] = 0;

    for(int i = 1; i < n; i += 2){
      p[i] = i / 2 + 1;
      p[i + 1] = n - p[i];
    }

    for(int i = 0; i < k; i++){
      if(i != 0) puts("");

      for(int j = 0; j < n - 1; j++){
        int a = (p[j] + i) % n + 1;
        int b = (p[j + 1] + i) % n + 1;

        printf("%d %d\n", a, b);
        //cout << a << " " << b << endl;
      }
    }
  }
}

Measured memory_bytes: 912
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(0); ios::sync_with_stdio(false)
using namespace std;

main() {
    int N; cin >> N;
    vector<int>v;
    while(N!=0){
        if(N%2!=0) {
            N--; v.push_back(1);
        }
        else {v.push_back(0);}
        N/=-2;
    }
    reverse(v.begin(),v.end());
    for(auto a:v){
        cout << a;
    }
    if(v.size()==0) cout << 0;
    cout << endl;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint dp[315][2];
lint num[610][315];
lint d2[315];
lint mo=1000000007;
int n;
int in(int l,int h,int a){
	if(l<=a && a<h) return 1;
	if(l<=a+n*2 && a+n*2<h) return 1;
	return 0;
}
int a[315],b[315];
int main()
{
	int K;
	cin>>n>>K;
	rep(i,n){
		cin>>a[i]>>b[i];a[i]--;b[i]--;
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	d2[0]=d2[1]=1;
	REP(i,1,310) d2[i+1]=d2[i]*(i*2+1)%mo;
	memset(num,0,sizeof(num));
	rep(i,2*n) REP(j,1,n){
		int p=j;
		rep(k,K){
			int x=in(i,i+j*2,a[k]),y=in(i,i+j*2,b[k]);
			//if(i==1 && j==2) cout<<a[k]<<' '<<b[k]<<' '<<x<<' '<<y<<endl;
			if(x+y==1) p=-1;
			if(x+y==2) p--;
		}
		if(p<0) num[i][j]=0;
		else num[i][j]=d2[p];
		//cout<<i<<' '<<j<<' '<<num[i][j]<<endl;
	}
	//cout<<num[1][2]<<endl;
	lint out=d2[n-K];
	rep(i,n*2){
		memset(dp,0,sizeof(dp));dp[0][0]=1;
		rep(j,n) REP(k,j+1,n+1) rep(l,2){
			if((i/2)+j>=n) continue;
			//if(i==5) cout<<j<<k<<endl;
			dp[k][1-l]+=dp[j][l]*num[(i+j*2)%(2*n)][k-j];
			dp[k][1-l]%=mo;
		}
		//cout<<i<<' '<<dp[n][0]<<' '<<dp[n][1]<<endl;
		out+=dp[n][0];out-=dp[n][1];
		out%=mo;
	}
	out%=mo;out+=mo;out%=mo;
	cout<<out<<endl;
}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;
pair<int,int> p[2][110];
bool used[110];
int main(){
	int i,j,n,ans = 0;
	cin >> n;
	for(j=0;j<2;j++){
		for(i=0;i<n;i++){
			int a,b;
			cin >> a >> b;
			if(j==0) p[j][i] = {b,a};
			else p[j][i] = {a,b};
			used[i] = true;
		}
	}
	sort(p[0],p[0] + n); sort(p[1],p[1] + n);
	for(i=n-1;i>=0;i--){
		for(j=0;j<n;j++){
			if(used[j] && p[1][j].second>=p[0][i].first && p[1][j].first>=p[0][i].second){
				used[j] = false;
				ans++;
				break;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
/*************************************************************************
    > File Name: test.cpp
    > Author: Akira 
    > Mail: qaq.febr2.qaq@gmail.com 
 ************************************************************************/

#include<bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))
using namespace std;

#define MaxN 100001
#define MaxM MaxN*10
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
const int mod = 1E9+7;
const double eps = 1e-6;
#define bug cout<<88888888<<endl;
#define debug(x) cout << #x" = " << x;

int N;
LL A[MaxN];
LL B[MaxN];
int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d", &N))
    {
        for(int i=0;i<N;i++) scanf("%lld", &A[i]);
        sort(A,A+N);
        B[0] = A[0];
        for(int i=1;i<N;i++) B[i] = B[i-1] + A[i];
        int ans = 0;
        for(int i=N-2;i>=0;i--)
        {
            //cout << B[i]*2 << " " << A[i+1] << endl;
            if(B[i]*2>=A[i+1]) ans++;
            else break;
        }
        printf("%d\n", ans+1);
    }
    //system("pause");
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define reps(i, n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define repi(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main(){
    ll n,a,b,c,d,e;
    cin>>n>>a>>b>>c>>d>>e;
    ll x=min({a,b,c,d,e});
    cout<<(ll)(n+x-1)/x+4<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>


using namespace std;
typedef long long int ll;

string divider[4] = {"dream", "dreamer", "eraser", "erase"};

int main() {
    string ans;
    string S;
    cin >> S;

    if (!(S[S.length()-1] == 'r' || S[S.length()-1] == 'e' || S[S.length()-1] == 'm')) {
        cout << "NO" << endl;
        return 0;
    }

    reverse(S.begin(), S.end());
    
    for(size_t i = 0; i < 4; i++)
    {
        reverse(divider[i].begin(), divider[i].end());
    }
    
    bool flag = true;
    ll l = 0;
    ll init_size = S.length();
    while(l < init_size && flag) {
        if (S[0] == 'e' && l >= 0) {
            if (!(divider[3] == S.substr(0,5))) {
                flag = false;
            } else {
                S = S.substr(5, S.length());
                l += divider[3].size();
            }
        }
        else if (S[0] == 'm' && l >= 0) {
            if (!(divider[0] == S.substr(0,5))) {
                flag = false;
            } else {
                S = S.substr(5, S.length());
                l += divider[0].size();
            }
        }
        else if (S.substr(0,3) == "res" && l >= 0) {
            if (!(divider[2] == S.substr(0,6))) {
                flag = false;
            } else {
                S = S.substr(6, S.length());
                l += divider[2].size();
            }
        }
        else if (S.substr(0,3) == "rem" && l >= 0) {
            if (!(divider[1] == S.substr(0,7))) {
                flag = false;
            } else {
                S = S.substr(7, S.length());
                l += divider[1].size();
            }
        }
        else {
            flag = false;
        }
        if (S.size() > 0 && S.size() < 5) {
            flag = false;
        }
    }

    if (flag) {cout << "YES" << endl;}
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define xx first
#define yy second
#define ll long long
using namespace std;

struct _in {
	const _in operator , (int &a) const {
		a = 0; char k = getchar (); int f = 1;
		while (k > '9' || k < '0') { if (k == '-') f = -1; k = getchar (); }
		while (k >= '0' && k <= '9') { a = a * 10 + k - '0'; k = getchar (); }
		a *= f;
		return*this;
	}
}in;

//const int N = ;
/*const int mod = ;
inline int add (int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
inline int sub (int u, int v) { return u - v < 0 ? u - v + mod : u - v; }
inline int mul (int u, int v) { return 1LL * u * v % mod; }
inline int qpow (int base, int v) {
	int tot = 1;
	while (v) {
		if (v & 1) tot = mul (tot, base);
		base = mul (base, base);
		v >>= 1;
	}
	return tot;
}*/

const int N = 100000 + 5;
int n, k, q;
int cnt[N];

int main () {
	in, n, k, q;
	for (int i = 1, x; i <= q; ++i)
		{in, x;cnt[x]++;}
	for (int i = 1; i <= n; ++i) {
		cnt[i] = q - cnt[i];
	}
	for (int i = 1; i <= n; ++i)
		if (cnt[i] < k)
			printf ("Yes\n");
		else
			printf ("No\n");
	return 0;
}






























Measured memory_bytes: 1024
#[macro_use]
pub mod basic_stdin {
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    use std::io::stdin;
    use std::io::Read;

    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed reading char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed parsing")
}

}

#[macro_export]
macro_rules! test_function {
    (func = $func:expr, $($input:expr => $output:expr),* $(,)*) => {
        $(
            assert_eq!($func(std::io::Cursor::new($input)) , $output);
        )*
    };
}

#[macro_export]
macro_rules! input_macro {
    (string = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    (reader = $s:expr, $($r:tt)*) => {
        let reader = std::io::BufReader::new($s);
        let mut bytes = std::io::Read::bytes(reader);
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[macro_export]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

fn main() {
    let stdin = std::io::stdin();
    let ret = solve(stdin.lock());

    println!("{}", ret);
}

fn solve<T: std::io::Read>(reader: T) -> String {
    input_macro! {
        reader = reader,
        n: u64,
    }

    if n < 1000 {
        return String::from("ABC");
    }

    return String::from("ABD");
}


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

vector<int> dx = {1, 0};
vector<int> dy = {0, 1};

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin >> n >> m;
	vector<string> s(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	int residue = 0;
	if (s[0][0] == '#' || s[n-1][m-1] == '#') {
		residue++;
	}

	// node (x, y): x*m + y
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 
	vector<int> dist(n*m + 1, 10000000);
	vector<int> vis(n*m + 1);
	dist[0] = 0; pq.push({0, 0});

	while (pq.size()) {
		auto tmp = pq.top();
		int now = tmp.second, w = tmp.first;
		pq.pop();

		int x = now/m, y = now % m;

		if (vis[now]) continue;
		vis[now] = 1;

		for (int d = 0; d < 2; d++) {
			int xx = x + dx[d];
			int yy = y + dy[d];

			if (xx < n && yy < m) {
				pair<int, int> u = {xx*m + yy, s[x][y] != s[xx][yy]};
				if (dist[now] + u.second < dist[u.first]) {
					dist[u.first] = dist[now] + u.second;
					pq.push({dist[u.first], u.first});
				}
			}
		}
	}
	cout << dist[(n-1)*m + m - 1]/2 + residue << '\n';

	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N],s[N],n,m;
int find(int x){
	if(x==fa[x])return x;
	else return fa[x]=find(fa[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		fa[i]=i;
		s[i]=1;
	}
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		x=find(x),y=find(y);
		if(x!=y){
			fa[x]=y;
			s[y]+=s[x];
		}
	}
	int res=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			res=max(res,s[i]);
		}
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 5352
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD = 1e9+7;

ll a[100000];
vector<P> te;
int main()
{
	int n;
	ll ans=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	ll m=a[0]; //最小
	ll s=a[n-1]; //最大
	//最大を増やす
	for(int i=1;i<n-1;i++)
	{
		if(a[i]>=0)
			break;
		te.push_back(P(s,a[i]));
		s-=a[i];
	}
	//最小を減らす
	for(int i=n-2;i>0;i--)
	{
		if(a[i]<0)
			break;
		te.push_back(P(m,a[i]));
		m-=a[i];
	}
	te.push_back(P(s,m));
	ans=s-m;
	cout<<ans<<endl;
	for(int i=0;i<te.size();i++)
		cout<<te[i].first<<" "<<te[i].second<<endl;
	return 0;
}

Measured memory_bytes: 4336
#include<cstdio>
#include<iostream>

#define N 100005
#define M 200001
#define For(a, b, c) for(int a = b; a <= c; ++a)
using namespace std;
int n, m;

inline int read(){
	int u = 0;
	char x = getchar();
	while(x < '0' || x > '9') x = getchar();
	while(x >= '0' && x <= '9') u = (u << 3) + (u << 1) + (x ^ 48), x = getchar();
	return u;
}

int e, be[N], ne[M], to[M];
inline void Add(int u, int v){
	to[++e] = v, ne[e] = be[u], be[u] = e;
}

int a[2];
bool dep[N], vis[N], p;
inline void dfs(int x){
	vis[x] = 1;
	++a[dep[x]];
	for(int i = be[x]; i; i = ne[i]){
		int v = to[i];
		if(!vis[v]){
			dep[v] = dep[x] ^ 1;
			dfs(v);
		}
		else if(dep[v] == dep[x]) p = 1;
	}
}

int main(){
	n = read(), m = read();
	For(i, 1, m){
		int u = read(), v = read();
		Add(u, v), Add(v, u);
	}
	dfs(1);
	if(p){
		printf("%lld", 1ll * n * (n - 1) / 2 - m);
	}
	else{
		printf("%lld", 1ll * a[0] * a[1] - m);
	}
	return 0;
}

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

int main(void){
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    int ans = 0;
    
    for (int i = 1; i < n; i++){
        if (s[i] == 'E') ans++;
    }
    
    int now = ans;
    
    for (int i = 1; i < n; i++){
        
        if (s[i-1] == 'W') now++;
        if (s[i] == 'E') now--;
        
        ans = min(ans, now);
    }
    cout << ans << endl;
}


Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int w=2e5+5;
int main()
{
    int i,j;
    ll x,y;
    cin>>x>>y;
    ll ans=x/y;
    if(x%y!=0)
        ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
long long n,c[N],l,r,d[N],A;
pair<long long,long long>p[N];
vector<int>a[N];
void D(int k,int f)
{
	A+=d[k]; 
	for(int i=0;i<a[k].size();i++)
		if(a[k][i]!=f)
			d[a[k][i]]=d[k]+1,D(a[k][i],k);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].first,p[i].second=i,c[i]=1;
	sort(p+1,p+n+1); 
	for(int i=n;i>1;i--)
	{
		l=1,r=i-1;
		while(l<r)
			if(p[(l+r)/2].first<p[i].first+2*c[i]-n)
				l=(l+r)/2+1;
			else
				r=(l+r)/2;
		if(p[l].first!=p[i].first+2*c[i]-n)
		{
			cout<<-1;
			return 0;
		}
		c[l]+=c[i],a[p[l].second].push_back(p[i].second),a[p[i].second].push_back(p[l].second);
	}
	D(p[1].second,0);
	if(A!=p[1].first)
	{
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<a[i].size();j++)
			if(i<a[i][j])
				cout<<i<<" "<<a[i][j]<<'\n';
	return 0;
}

Measured memory_bytes: 13056
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
namespace Atcoder_0404
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = GetInput_int()[0];
            var result =( N >= 30)?"Yes":"No";
            Console.WriteLine(result);
        }

        #region input


        static string[] GetInput_string()
        {
            var input = Console.ReadLine().Split(' ');
            return input;
        }

        static int[] GetInput_int()
        {
            var input = GetInput_string();
            var result = new int[input.Length];
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = int.Parse(input[i]);
            }
            return result;
        }
        static long[] GetInput_long()
        {
            var input = GetInput_string();
            var result = new long[input.Length];
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = long.Parse(input[i]);
            }
            return result;
        }
        #endregion
        #region sonota
        static void Swap_array<T>(T[] target, int a, int b)
        {
            T temp = target[a];
            target[a] = target[b];
            target[b] = temp;
        }
        static void Swap_list<T>(List<T> target, int a, int b)
        {
            T temp = target[a];
            target[a] = target[b];
            target[b] = temp;
        }
        /// <summary>
        /// 最大公約数
        /// </summary>
        public static int GCD(int a, int b)
        {

            /* 自然数 a > b を確認・入替 */
            if (a < b)
            {
                int tmp = a;
                a = b;
                b = tmp;
            }

            /* ユークリッドの互除法 */
            int r = a % b;
            while (r != 0)
            {
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }

        /// <summary>
        /// 最小公倍数
        /// </summary>
        public static int LCM(int a, int b)
        {
            int x = a * b;
            b = GCD(a, b);
            return x / b;

        }
        #endregion
        
    }
}

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

using namespace std;
using namespace std;
typedef long long ll;
#define endl "\n"
#define loop(n) for (ll i = 0; i < n; i++)
#define loop2(n) for (ll i = 0; i < n; i += 2)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
int Mint = INT_MAX;
ll Mlong = LLONG_MAX;

void fast() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}

int pow(ll a, ll b) {
    if (b == 1)return a;
    if (b == 0) return 1;
    return a * pow(a, b - 1);
}

int n;
int operation = 0;

int counti = 0;


int solve(int s) {
    if(s==0)
        return 0;
    if(s==1)
        return 2;
    if(s==2)
        return 4;



    //cout << s << endl;
    operation++;
    return solve(s-1)+solve(s-2);
}

int main() {
    fast();
    int a, b;
    cin >> a >> b;
    cout<<(a%b==0?a/b:a/b+1);
}


Measured memory_bytes: 256
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    sx, sy, tx, ty = map(int, readline().split())
    C = []
    G = [[] for i in range(N+2)]
    L = 0
    for i in range(N):
        xi, yi, ri = map(int, readline().split())
        sc = ((sx - xi)**2 + (sy - yi)**2 <= ri**2)
        tc = ((tx - xi)**2 + (ty - yi)**2 <= ri**2)
        if (sc and tc) or (not sc and not tc):
            continue
        for j in range(L):
            xj, yj, rj = C[j]
            dd = (xi - xj)**2 + (yi - yj)**2
            rr = (ri - rj)**2
            if dd < rr:
                if ri < rj:
                    G[L].append(j)
                elif ri > rj:
                    G[j].append(L)
        if tc:
            G[N].append(L)
        if sc:
            G[N+1].append(L)
        C.append((xi, yi, ri))
        L += 1

    def calc(s):
        que = deque([s])
        used = [0]*(N+2)
        deg = [0]*(N+2)
        used[s] = 1
        while que:
            v = que.popleft()
            for w in G[v]:
                deg[w] += 1
                if used[w]:
                    continue
                used[w] = 1
                que.append(w)
        que = deque([s])
        dist = [0]*(N+2)
        while que:
            v = que.popleft()
            d = dist[v]+1
            for w in G[v]:
                deg[w] -= 1
                dist[w] = max(dist[w], d)
                if deg[w] == 0:
                    que.append(w)
        return dist
    d0 = calc(N); d1 = calc(N+1)
    ans = max(max(d0), max(d1))
    for i in range(L):
        if d0[i] == 0:
            continue
        xi, yi, ri = C[i]
        for j in range(L):
            if d1[j] == 0:
                continue
            xj, yj, rj = C[j]
            if (xi - xj)**2 + (yi - yj)**2 > (ri + rj)**2:
                ans = max(ans, d0[i] + d1[j])
    write("%d\n" % ans)
    return True
while solve():
    ...


Measured memory_bytes: 15020
#include<stdio.h>
#define M 1000

main(){
  int n,a[M],i,j,v;

    scanf("%d",&n);
      
  for( i=0 ; i<n ; i++ ) 
    scanf("%d",&a[i]);
   
   for( i=1 ; i<=n ; i++ ){
    for( j=0 ; j<n ; j++ ){
      printf("%d",a[j]);
      if(a[j+1] != '\0')
	printf(" ");
      else printf("\n");
    }
    v = a[i];
    j = i-1;
    while(j >= 0 && a[j] > v){
      a[j+1] = a[j];
      j--;
      a[j+1] = v;
    }
    }
  return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a[100],b[100],c[100];
    scanf("%s",a);
    int x=strlen(a);
    scanf("%s",b);
    int y=strlen(b);
     scanf("%s",c);
    int z=strlen(c);
    if(a[x-1]==b[0] && b[y-1]==c[0])
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}



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

int main(int argc, char* argv[]){
    int N;
    int C[501] = {}, S[501] = {}, F[501] = {};
    vector<int> v;
    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++){
            t = max(t, S[j]);
            t += (F[j] - (t % F[j])) % F[j];
            t += C[j];
        }
        v.push_back(t);
    }

    for(auto n:v){
        cout << n << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int prime(int n)
{
    if(n==2)
    {
        return 1;
    }
    if(n%2==0)
    {
        return -1;
    }
    for(int i=3;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
            return -1;
        }
    }
    return 1;
}
int main()
{
    int x;
    cin>>x;
    if((prime(x)==1))
    {
        cout<<x<<endl;
    }
    else
    {
     while(1)
     {
         x++;
         if(prime(x)==1)
         {
             cout<<x<<endl;
             return 0;
         }
     }
    }
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<vector<int>> sum(N, vector<int>(N));
	for (auto i = 0; i < M; ++i)
	{
		int L, R;
		cin >> L >> R;
		--L;
		--R;
		++sum[L][R];
	}

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

	vector<vector<int>> sum2(N, vector<int>(N));
	for (auto i = 0; i < N; ++i)
	{
		for (auto j = i; j < N; ++j)
		{
			for (auto left = i; left < N; ++left)
			{
				sum2[i][j] += sum[left][j];
			}
		}
	}

	vector<int> ans;
	for (auto i = 0; i < Q; ++i)
	{
		int p, q;
		cin >> p >> q;
		--p;
		--q;
		ans.push_back(sum2[p][q]);
	}

	for (auto i = 0; i < Q; ++i)
	{
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3452
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {
	string s;
	cin>>s;
	for(char c:s) {
		if(c=='1')cout<<9;
		else cout<<1;
	}
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3612
import math
a,b,h,m=map(int,input().split())
m_theta=m*2*math.pi/60
h_theta=(h*60+m)*2*math.pi/720
theta=abs(m_theta-h_theta)
print(math.sqrt((a*a)+(b*b)-2*a*b*math.cos(theta)))

Measured memory_bytes: 9532
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,a=0,b=0,c=0,ans=0;
    cin >> n;
    string s[n];
    for(int i=0;i<n;i++){
        cin >> s[i];
        int k = s[i].size()-1;
        if(s[i][0]=='B') a++;
        if(s[i][k]=='A') b++;
        if(s[i][0]=='B'&&s[i][k]=='A') c++;
        for(int j=0;j<k;j++){
            if(s[i][j]=='A'&&s[i][j+1]=='B') ans++;
        }
    }
    a-= c;
    b-= c;
    if(c==0) ans += min(a,b);
    else{
        if(a>0&&b>0) ans += c+1+min(a-1,b-1);
        else if((a==0&&b>0)||(a>0&&b==0)) ans += c;
        else ans += max(0,c-1);
    } 
    cout << ans << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  ll n; cin >> n;
  ll a;
  map<ll, ll> m;
  ll sum=0;
  for(ll i=0; i<n; i++){
    cin >> a;
    m[a]++;
    sum+=a;
  }
  ll q; cin >> q;
  for(ll i=0; i<q; i++){
    ll b, c; cin >> b >> c;
    sum-=m[b]*b;
    sum+=m[b]*c;
    m[c]+=m[b];
    m[b]=0;
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 9416
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define null nullptr
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
#define test int t; cin>>t; while(t--)
#define FAST                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

using namespace std;

typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;
typedef unordered_map<int,int> mp;

const int mod = 1e9+7;
const int inf = 1e17+21;

vector<int> city[1000];

int32_t main(){
    FAST;

   int n,m; cin >> n >> m;
   for(int x=0;x<m;x++){
       int u,v; cin >> u >> v;
        city[u].pb(v);
        city[v].pb(u);
   }

   for(int x=1;x<=n;x++)
    cout << city[x].size() << '\n';

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;//push poll peek
import java.util.ArrayDeque;
import java.util.Queue;//add poll peek
import java.util.ArrayDeque;
import java.math.BigDecimal;

class Main{

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int x = Integer.parseInt(input[0]);
		int a = Integer.parseInt(input[1]);
		int b = Integer.parseInt(input[2]);

		if(a >= b){
			System.out.println("delicious");
		}else if (b - a <= x){
			System.out.println("safe");			 
		}else{
			System.out.println("dangerous");
		}
	}
}


Measured memory_bytes: 21076
from copy import deepcopy

def judge_a(S,T,i,j):
    return S[i+j]==T[j]

def judge_b(S,T,i,j):
    return S[i+j]!=T[j] and S[i+j]=="?"

def ans(ans_list):
    if not ans_list:
        print("UNRESTORABLE")
    else:
        ans_list_2=[]
        for l in ans_list:
            temp=[s if s!="?" else "a" for s in l]
            ans_list_2.append("".join(temp))
        print(min(ans_list_2))

if __name__ == '__main__':
    S_dash=list(input())
    T=list(input())
    N_S=len(S_dash)
    T_N=len(T)
    ans_list=[]

    for i in range(N_S-T_N+1):
        S_2=deepcopy(S_dash)
        flag=True
        for j in range(T_N):
            if judge_a(S_2,T,i,j) or judge_b(S_2,T,i,j):
                S_2[i+j]=T[j]
            else:
                flag=False
                break
        if flag:
            ans_list.append(S_2)
    ans(ans_list)





Measured memory_bytes: 3444
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

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

int main(void){
    int n, maxW; cin >> n >> maxW;
    ll wight[110], value[110], dp[110][100010] = {0};
    REP(i, n) cin >> wight[i] >> value[i];

    REP(i, n){
        for(int sum_w = 0; sum_w <= maxW; sum_w++){
            if(sum_w - wight[i] >= 0){
                chmax(dp[i + 1][sum_w], dp[i][sum_w - wight[i]] + value[i]);
            }
            chmax(dp[i + 1][sum_w], dp[i][sum_w]);
        }
    }

    cout << dp[n][maxW] << endl;
}

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

using namespace std;
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef pair<int,int> pii;
typedef long long ll;

ll expMod(ll a, ll exp, ll mod){
    if(exp == 0) return 1;
    __int128_t pa = expMod(a, exp/2, mod);
    pa = (pa*pa)%mod;
    if(exp%2 == 1) pa = (pa*a)%mod;
    return pa;
}

const ll mod = 1000000000LL + 7;

void linearSieve(int n, vi &minP, vi &primeList){
    // minP[i] = minimum prime in i factorization
    // minP[0] = minP[1] = -1
    // O(n) (int) mem
    // O(n) runtime

    minP.clear(); minP.resize(n+1,0);
    primeList.clear();

    minP[0] = minP[1] = -1;
    for(int i=2;i<=n;++i){
        if(minP[i] == 0){
            minP[i] = i;
            primeList.push_back(i);
        }
        ll x;
        for(int j=0;j < primeList.size() && primeList[j] <= minP[i];++j){
            x = ll(i) * primeList[j];
            if(x > n) break;
            minP[x] = primeList[j];
        }
    }
}

vi sign;
void init(int maxn){
    vi minP, primeL;
    linearSieve(maxn, minP, primeL);
    sign.resize(maxn+1, 0);
    for(int i=2;i<=maxn;i++){
        int x = i;
        int nf = 0;
        int mxE = -1;
        while(x > 1){
            nf++;
            int f = minP[x];
            int e = 0;
            while(x%f == 0){
                x /= f;
                e++;
            }
            mxE = max(e, mxE);
            if(mxE > 1) break;
        }
        if(mxE == 1)
            sign[i] = (nf%2) ? -1 : +1;
    }
}

ll cnt(ll n, ll k, ll x){
    // # n-sec with {1,..,k} s.t gcd = x
    ll ans = expMod(k/x, n, mod);
    // remove 2x,3x, 5x, ...
    // add 6x,10x,...,15x, ...
    // remove 2*3*5 x, ...
    // ignore p^2*...
    for(int j = 2; (x*j) <= k; j++){
        ll tmp = expMod(k/(x*j), n, mod);
        ans += sign[j] * tmp;
        ans %= mod;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    init(k);
    ll ans = 0;
    for(int i=1;i<=k;i++){
        ll tmp = cnt(n, k, i);
        tmp = (tmp*i)%mod;
        ans += tmp;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4248
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <queue>
using namespace std;
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;

const double eps = 1e-10;

int sgn(double x) {
    return (x > eps) - (x < -eps);
}

double p[100010];
int n;

int main() {
    p[0] = 0.0;
    p[1] = 1.0;
    for (int i = 2; i <= 100000; ++i) {
        p[i] = 1.0;
        double now = 1.0, c = 0.5;
        for (int j = 1; j + 1 <= i; ++j) {
            p[i] += now * c;
            p[i] += now * (1 - c) * p[i - j - 1];
            if (sgn(c) == 0) break;
            now *= c;
            c *= 0.5;
        }
    }
    while (scanf ("%d", &n), n) {
        printf ("%lf\n", p[n]);
    }
    return 0;
}

Measured memory_bytes: 0