akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<atcoder/mincostflow>

using namespace std;
using ll = long long;
inline int ri() { int n; cin >> n; return n;}
const ll INF = 1e12;


int main()
{
    int n, k; cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)cin >> a[i][j];
    atcoder::mcf_graph<int, ll> mf(2 * n + 2);
    int S = 2 * n, T = 2 * n + 1;
    mf.add_edge(S, T, n * k, INF);

    for(int i = 0; i < n; i++) {
        mf.add_edge(S, i, k, 0);
        mf.add_edge(i + n, T, k, 0);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            mf.add_edge(i, j + n, 1, INF - a[i][j]);
        }
    }

    auto p = mf.flow(S, T, n * k);
    vector<atcoder::mcf_graph<int,ll>::edge> v = mf.edges();
    cout << n * k * INF - p.second << endl;

    for(auto e : v) {
        if(e.from == S || e.to == T)continue;
        if(e.flow == 1) {
            a[e.from][e.to - n] = -1;
        }
    }


    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)cout << (a[i][j] == -1 ? "X" : ".") << (j == n - 1 ? "\n" : "");
    }





}

Measured memory_bytes: 3900
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
 
int main(){
 long double  A=0;
 long double  B=0;
 long double  C=0;
cin>>A>>B>>C;
  if(sqrt(A)+sqrt(B)+1.0E-14<sqrt(C)){
  cout<<"Yes"<<endl;
  }
  else{
  cout<<"No"<<endl;
  }
}

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

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ii, ii> iiii;

const int mod1 = 1000000007;
const int mod2 = 1000000009;
const int arg1 = 37;
const int arg2 = 1000007;

int n;
string S;
map <iiii, int> M;
ll res;

ii Add(const ii &h, char let)
{
	return ii((ll(h.first) * arg1 + ll(let - 'a' + 1)) % mod1,
			  (ll(h.second) * arg2 + ll(let - 'a' + 1)) % mod2);
}

void Gen(int lvl, int lim, ii h1, ii h2)
{
	if (lvl >= lim) M[iiii(h1, h2)]++;
	else {
		Gen(lvl + 1, lim, Add(h1, S[lvl]), h2);
		Gen(lvl + 1, lim, h1, Add(h2, S[lvl]));
	}
}

void Count(int lvl, int lim, ii h1, ii h2)
{
	if (lvl <= lim) res += M[iiii(h1, h2)];
	else {
		Count(lvl - 1, lim, Add(h1, S[lvl]), h2);
		Count(lvl - 1, lim, h1, Add(h2, S[lvl]));
	}
}

int main()
{
	cin >> n;
	cin >> S;
	Gen(0, n, ii(0, 0), ii(0, 0));
	Count(2 * n - 1, n - 1, ii(0, 0), ii(0, 0));
	cout << res << endl;
	return 0;
}

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

ll gcd(ll a,ll b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

ll kaizyou(ll N){
  ll num=1;
  for(ll i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

 
int main(){
  int N,R;
  cin >> N >> R;
  if(N<=10){
    cout << R+(10-N)*100 << endl;
  }
  else{
    cout << R << endl;
  }
}
      
  
  
  

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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

ll Mod = 998244353;
const int N = 2e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll mul(ll a, ll b){
	return (a * b) % Mod;
}

ll dp[3 * N][N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n >> Mod;

	dp[0][0] = 1;
	for(int i = 1; i <= 3*n; i++){
		for(int j = 0; j <= n; j++){
			dp[i][j] = dp[i - 1][j];
			if(j){
				if(2 <= i) dp[i][j] += mul(i - 1, dp[i - 2][j - 1]);
				if(3 <= i) dp[i][j] += mul(mul(i - 2, i - 1), dp[i - 3][j - 1]);
			}
			dp[i][j] %= Mod;
		}
	}

	ll ans = 0;
	for(int i = 0; i <= n; i++) ans += dp[3 * n][i];
	cout << ans % Mod << '\n';
	return 0;
}


Measured memory_bytes: 94464
#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

/// @brief Calculates scores.
int main() {
    int N, a, alice, bob;
    std::vector<int> vec;

    scanf("%d", &N);

    for (int i = 0; i < N; ++i) {
        scanf("%d", &a);
        vec.push_back(a);
    }

    std::sort(vec.begin(), vec.end(), std::greater<>());
    int i = alice = bob = 0;

    for (auto it = vec.begin(); it != vec.end(); ++it) {
        if (i++ % 2) {
            bob += *it;
        } else {
            alice += *it;
        }
    }

    printf("%d\n", alice - bob);
}


Measured memory_bytes: 256
N, X = map(int, input().split())
List = list(map(int, input().split()))

from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

List.append(X)
List = sorted(List)

diff = [List[i+1]-List[i] for i in range(N)]

ans = reduce(gcd, diff)
print(ans)

Measured memory_bytes: 14252
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int k = scan.nextInt();
        int cnt = 0;
        while (b <= a) { b *= 2; cnt++; }
        while (c <= b) { c *= 2; cnt++; }
        if (cnt <= k) System.out.println("Yes");
        else System.out.println("No");
    }
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);++(i))

string in;
map<char,string> m;
const char cs[32] = {
  ' ', '\'', ',', '-', '.', '?',
  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
  'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
  'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
  'Y', 'Z'
};
const string ss[32] = {
  "101", "000000", "000011", "10010001", "010001", "000001",
  "100101", "10011010", "0101", "0001", "110", "01001", "10011011", "010000",
  "0111", "10011000", "0110", "00100", "10011001", "10011110", "00101", "111",
  "10011111", "1000", "00110", "00111", "10011100", "10011101", "000010",
  "10010010", "10010011", "10010000"
};

void init() {
  // first convert
  m.insert(make_pair('A', "00000"));
  m.insert(make_pair('B', "00001"));
  m.insert(make_pair('C', "00010"));
  m.insert(make_pair('D', "00011"));
  m.insert(make_pair('E', "00100"));
  m.insert(make_pair('F', "00101"));
  m.insert(make_pair('G', "00110"));
  m.insert(make_pair('H', "00111"));
  m.insert(make_pair('I', "01000"));
  m.insert(make_pair('J', "01001"));
  m.insert(make_pair('K', "01010"));
  m.insert(make_pair('L', "01011"));
  m.insert(make_pair('M', "01100"));
  m.insert(make_pair('N', "01101"));
  m.insert(make_pair('O', "01110"));
  m.insert(make_pair('P', "01111"));
  m.insert(make_pair('Q', "10000"));
  m.insert(make_pair('R', "10001"));
  m.insert(make_pair('S', "10010"));
  m.insert(make_pair('T', "10011"));
  m.insert(make_pair('U', "10100"));
  m.insert(make_pair('V', "10101"));
  m.insert(make_pair('W', "10110"));
  m.insert(make_pair('X', "10111"));
  m.insert(make_pair('Y', "11000"));
  m.insert(make_pair('Z', "11001"));
  m.insert(make_pair(' ', "11010"));
  m.insert(make_pair('.', "11011"));
  m.insert(make_pair(',', "11100"));
  m.insert(make_pair('-', "11101"));
  m.insert(make_pair('\'', "11110"));
  m.insert(make_pair('?', "11111"));
}

void solve() {
  string s;
  rep (i,in.size()) s += m[in[i]];
  string ans;

  while (s.size()) {
    bool isChanged = false;
    rep (i,32) {
      if (ss[i].size() > s.size()) continue;
      bool ok = true;
      rep (j,ss[i].size()) if (ss[i][j] != s[j]) ok = false;
      if (!ok) continue;

      string t = " ";
      t[0] = cs[i];
      ans += t;
      isChanged = true;
      s.erase(0, ss[i].size());
      break;
    }
    if (!isChanged) break;
  }
  cout << ans << endl;  
}

int main() {
  init();
  while (getline(cin, in)) solve();
  return 0;
}

Measured memory_bytes: 0
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    A, B, K = map(int, input().split())

    if A < K:
        B = max(0, B - (K - A))
        A = 0
    else:
        A = A - K

    print(A, B)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 2940
package main

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

func main() {
	fmt.Println(abc178b(os.Stdin))
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func abc178b(r io.Reader) int {
	sc := bufio.NewScanner(r)
	sc.Split(bufio.ScanWords)

	a, b, c, d := nextInt(sc), nextInt(sc), nextInt(sc), nextInt(sc)

	s := []int{a * c, a * d, b * c, b * d}
	sort.Sort(sort.Reverse(sort.IntSlice(s)))

	return s[0]
}


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

int main() {
    int n;

    while (cin >> n, n) {
        int g[20] = {0};
        while (n--) {
            int age;
            cin >> age;
            g[age / 10]++;
        }
        for (int i = 0; i <= 5; i++) {
            cout << g[i] << endl;
        }
        cout << accumulate(&g[6], g+20, 0) << endl;
    }
    return 0;
}

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

int k,len;
string s,ans[8];

void push(string x){
        int i;
        for(i=1;i<=5;i++){
                if(x==ans[i]) return;
                if(x<ans[i]) break;
        }
        for(int j=6;j>=i+1;j--){
                ans[j]=ans[j-1];
        }
        ans[i]=x;
//      cout << x << ' ' << i << endl;
}

int main(){
        for(int i=0;i<=7;i++) ans[i]+='z'+1;
        cin >> s >> k;
        len=s.size();
        for(int i=1;i<=len && i<=5;i++){
                for(int j=0;j<=len-i;j++){
                        push(s.substr(j,i));
//                      cout << s.substr(j,i) << endl;
//                      for(int i=1;i<=k;i++){
//                              cout << ans[i] << ' ';
//                      }
//                      cout << endl;
                }
        }
        cout << ans[k];
        return 0;
}


Measured memory_bytes: 256
from math import atan
from math import pi

a,b,x=map(int,input().split())
v = a*a*b
if x < v/2:
    a2 = 2*x/a/b
    t = atan(b/a2)*180/pi
    print(t)
else:
    t = atan(2*(b-x/a/a)/a)*180/pi
    print(t)
    


Measured memory_bytes: 3060
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
//namespace mp = boost::multiprecision;
//using llll = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
//using Real = mp::number<mp::cpp_dec_float<1024>>;
using ll = long long;
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

int main(){
  string s;
  cin>>s;
  ll ans=0;
  if(s[0]==s[1]&&s[2]==s[3]&&s[0]!=s[2])ans=1;
  if(s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1])ans=1;
  if(s[0]==s[3]&&s[1]==s[2]&&s[0]!=s[1])ans=1;
  if(ans==1){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    string w;
    cin >> w;

    vl v(26);
    rep(i, w.size()) {
        v[w[i] - 'a']++;
    }

    bool ok = true;
    rep(i, 26) {
        if(v[i]%2 == 1) {
            ok = false;
        }
    }

    if(ok) {
        out("Yes");
    }
    else {
        out("No");
    }

    re0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  int N; cin >> N;
  for (int x = 0; N - 4 * x >= 0; ++x){
    if ((N - 4 * x) % 7 == 0) {cout << "Yes" << endl; return 0;}
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		
		int counter=0;
		
		for(int i=0;i<n;i++) {
			
			int buf=sc.nextInt();
			
			if(buf%2==1) {
				counter++;
			}
			
		}
		
		if(counter%2==0) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}


		sc.close();


	}



}


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

using namespace std;

string s;
int ans;

int main(){
	cin >> s;
	int length = 0;
	for(int i = 0; i < s.size(); ++i){
		if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
			length++;
			ans = max(ans, length);
		}else{
			length = 0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    
    int a, b;
    scanf("%d%d",&a, &b);
    int sum, dif, pro;
    sum = a+b;
    dif = a-b;
    pro = a*b;
    if(sum > dif){
        if(sum > pro){
            printf("%d\n",sum);
        }else{
            printf("%d\n",pro);
        }
    }else{
        if(dif > pro){
            printf("%d\n",dif);
        }else{
            printf("%d\n",pro);
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

typedef struct list {
  int node;
  int i;
  struct list *next;
} list;

list *graph[MAX];

void initGraph(void) {
  for (int i = 0; i < MAX; i++)
    graph[i] = NULL;
}

void addEdge(int node1, int node2, int i)
{
  list *new1 = (list *)malloc(sizeof(list *));
  new1->node = node2;
  new1->next = graph[node1];
  new1->i = i;
  graph[node1] = new1;

  list *new2 = (list *)malloc(sizeof(list *));
  new2->node = node1;
  new2->next = graph[node2];
  new2->i = i;
  graph[node2] = new2;
}

int color[MAX] = {0};
int max = 0;

void paint(int parent, int now, int edge) {
  list *child = graph[now];
  int colors = 1;
  for (; child != NULL; child = child->next) {
    if (child->node == parent) continue;
    if (colors == edge) colors++;
    color[child->i] = colors;
    paint(now, child->node, colors);
    colors++;
  }
  max = max(max, colors - 1);
  return;
}

int main(void) {
  int n;
  scanf("%d", &n);
  initGraph();
  int a, b;
  rep(i, 1, n) {
    scanf("%d %d", &a, &b);
    addEdge(a, b, i);
  }

  paint(0, 1, 0);

  printf("%d\n", max);
  rep(i, 1, n) {
    printf("%d\n", color[i]);
  }
  return 0;
}

Measured memory_bytes: 8576
while True:
  n, a, b, c, x = map(int, raw_input().split())
  if n + a + b + c + x == 0: break
  ys = map(int, raw_input().split())
  cnt = 0
  reel = 0
  while True:
    if x == ys[reel]:
      reel += 1
      if reel == n:
        break

    x = (a * x + b) % c
    cnt += 1
    if cnt > 10000:
      cnt = -1
      break
  print cnt

Measured memory_bytes: 4232
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=(1<<18)+5;
const int mo=998244353;
int a[N],b[N],c[N],n,S;
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
void check(int *a,int *b,int *c,int n){
	if (n==1){
		if (!b[0]) c[0]=0;
		else c[0]=1ll*b[0]*power(a[0],mo-2)%mo;
		return;
	}
	int nn=n/2,x,y;
	For(i,0,nn-1){
		x=a[i]; y=a[i+nn];
		a[i]=(x+y)%mo; a[i+nn]=(x+mo-y)%mo;
		x=b[i]; y=b[i+nn];
		b[i]=(x+y)%mo; b[i+nn]=(x+mo-y)%mo;
	}
	check(a,b,c,nn);
	check(a+nn,b+nn,c+nn,nn);
	For(i,0,nn-1){
		x=c[i],y=c[i+nn];
		c[i]=1ll*(x+y)*(mo+1)/2%mo;
		c[i+nn]=1ll*(x+mo-y)*(mo+1)/2%mo;
	}
}
int main(){
	scanf("%d",&n);
	For(i,0,(1<<n)-1){
		scanf("%d",&a[i]);
		S+=a[i];
	}
	S=power(S,mo-2);
	For(i,0,(1<<n)-1) a[i]=1ll*a[i]*S%mo;
	For(i,0,(1<<n)-1) b[i]=mo-1;
	a[0]=(a[0]+mo-1)%mo;
	b[0]=(1<<n)-1;
	check(a,b,c,(1<<n));
	int dif=(mo-c[0])%mo;
	For(i,0,(1<<n)-1) c[i]=(c[i]+dif)%mo;
	For(i,0,(1<<n)-1) printf("%d\n",c[i]);
}
/*
(x0,x1,x2,x3)opt(p0,p1,p2,p3)=(x0+2^n-1,x1-1,x2-1,x3-1)
(x0,x1,x2,x3)opt(p0-1,p1,p2,p3)=(2^n-1,-1,-1,-1)
*/

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

int main()
{
  string s;
  cin >> s;
  
  int ans = 0;
  
  if(s == "RRR") ans =3;
  if(s == "RRS") ans =2;
  if(s == "RSR") ans =1;
  if(s == "SRR") ans =2;
  if(s == "RSS") ans =1;
  if(s == "SRS") ans =1;
  if(s == "SSR") ans =1;
  if(s == "SSS") ans =0;
  
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll mod = 1000000007;

inline ll modPow(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b&1)(ret *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n;
	cin>>n;
	vector<ll> c(n);
	ll sum = 0;
	for(auto &x : c){
		cin>>x;
		sum += x;
	}
	sum %= mod;
	sort(c.begin(), c.end());
	ll ans = sum*modPow(2, n - 1)%mod;
	if(n > 1){
		for(int i = 0; i < n; i++){
			ans += c[i]*((n - i - 1)*modPow(2, n - 2)%mod)%mod;
			if(ans >= mod)ans -= mod;
		}
	}
	ans *= modPow(2, n);
	ans %= mod;
	cout<<ans<<endl;


	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <map>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 3e2+17;
LL dis[MAXN][MAXN],n;
bool can[MAXN][MAXN];
map<pair<int,int > ,int > mp;
LL func()
{
	LL ret = 0;
	for (int k = 0; k < n; ++k)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if(dis[i][j]>dis[i][k]+dis[k][j]) return -1;
				if(dis[i][j]==dis[i][k]+dis[k][j]&&k!=j&&k!=i)
				{
					// debug(i);
					// debug(j);
					// cerr<<endl;
					can[i][j] = true;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if(!can[i][j])
				ret += dis[i][j];
		}
	}
	return ret/2;
}
int main(int argc ,char const *argv[])
{
	#ifdef noob
	freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
	#endif
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			can[i][j] = false;
			cin>>dis[i][j];
		}
	}
	cout<<func()<<endl;
    return 0;
}

Measured memory_bytes: 1152
#include <cstdio>
#include <algorithm>
#include <cstring>

#define R register
#define maxn 100010
int a[maxn * 10];
typedef long long ll;
int main()
{
	R int n; scanf("%d", &n);
	for (R int i = 1; i <= n * 3; ++i) scanf("%d", &a[i]);
	R ll ans = 0;
	std::sort(a + 1, a + n * 3 + 1); std::reverse(a + 1, a + n * 3 + 1);
	for (R int i = 1; i <= n; ++i) ans += a[i << 1];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;

int main() {
	
	int n;
	string s;
	cin >> n >> s;
	vi lr(n + 1), rw(n + 1);
	rep(i, n) {
		lr[i + 1] = lr[i];
		rw[n - 1 - i] = rw[n - i];
		if (s[i] == 'R')lr[i + 1]++;
		if (s[n - 1 - i] == 'W')rw[n - 1 - i]++;
	}
	
	int ans = INF;
	rep(i, n + 1)ans = min(ans, max(i - lr[i], n - i - rw[i]));
	cout << ans << endl;

}

Measured memory_bytes: 5156
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    let mut a: Vec<usize> = Vec::with_capacity(n);
    for _i in 0..n {
        a.push(iterator.next().unwrap().parse().unwrap());
    }

    let mut count = 0;
    for i in 0..n {
        let mut minj = i;
        for j in i..n {
            if a[j] < a[minj] {
                minj = j;
            }
        }
        if i != minj {
            let temp = a[i];
            a[i] = a[minj];
            a[minj] = temp;
            count += 1;
        }
    }

    return format!(
        "{}\n{}",
        a.iter().map(|it| it.to_string()).collect::<Vec<String>>().join(" "),
        count
    );
}



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

int main() {
 
  int X, A, B;
  cin >> X >> A >> B;

  if (0 <= A - B) {
    cout << "delicious" << endl;
  } else if (B - A <= X) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }

}

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

int main() {
	int N, K;
	cin >> N >> K;
	int64_t count = 0;
	for (int c = (K & 1) == 0 ? K >> 1 : K, i = c;i <= N;i += c) {
		int j = K - i % K;
		count += (int64_t)((N - j) / K + 1) * ((N - j) / K + 1);
	}
	cout << count;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

まず、aを決め打つ
この時、a+bはKの倍数であるからb=nK-a、c=mK-aとなる
ここでb+cがKの倍数であるから、nK+mK-2aもまたKの倍数であるので、2aがKの倍数である必要がある
逆に、この時にnとmは任意に値を取れるので、はい
*/

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;



int main() {
    
    ll n,m;
    cin >> n >> m;
    const ll p = n+1;
    ll ans[p];
    for (ll i=1;i<=n;i++){
        ans[i] = -1;
    }
    if(n != 1) {
        for (ll i = 1; i <= m; i++) {
            ll s, c;
            cin >> s >> c;
            if (ans[s] != -1) {
                if (ans[s] != c) {
                    cout << -1 << endl;
                    return 0;
                }
            } else {
                if (s == 1 and c == 0) {
                    cout << -1 << endl;
                    return 0;
                }
                ans[s] = c;
            }
        }
        for (ll i = 1; i <= n; i++) {
            if (ans[i] == -1) {
                if (i != 1) {
                    cout << 0;
                } else {
                    cout << 1;
                }
            } else {
                cout << ans[i];
            }
        }
        cout << endl;
    }else{
        for (ll i = 1; i <= m; i++) {
            ll s, c;
            cin >> s >> c;
            if (ans[s] != -1) {
                if (ans[s] != c) {
                    cout << -1 << endl;
                    return 0;
                }
            } else {
                ans[s] = c;
            }
        }
        if(ans[1] == -1){
            cout << 0 << endl;
        }else{
            cout << ans[1] << endl;
        }
    }

}

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

using namespace std;

int main()
{int N;cin >> N;
 vector<int> H(N,0); vector<int> J(N-1,0);
 for(int i = 0; i < N; i++){
   cin >> H[i];}
 if( N == 1){cout << 1 << endl;}
   else{
 int max_height = 0;
 
 for(int i = 0; i < N; i++)
 {max_height = max(H[i],max_height);
  J[i] = max_height;}
  int cnt = 1;
   for(int j = 1 ; j < N; j++)
   {if(J[j-1] <= H[j]){cnt++ ;}}
   
   
   cout << cnt << endl;}
   return 0;}


Measured memory_bytes: 256
#include<map>
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define sz(a) ((int)(a).size())
#define pii pair<int,int>
#define R(a) scanf("%d",&a)
#define per(i,a,b) for(int i=a;i>=int(b);i--)
#define rep(i,a,b) for(int i=a;i<=int(b);i++)
#define rix(i,x) for(int i=last[x];i;i=pre[i])
const double eps=1e-8;
int sgn(double x){return x<-eps?-1:x>eps;}
int Mn(int&a,int b){if(a>b){a=b;return 1;}return 0;}
int Mx(int&a,int b){if(a<b){a=b;return 1;}return 0;}
ll gcd(ll a,ll b){return a==0?b:gcd(b%a,a);}
ll inv(ll a,ll b){return a==1?1:(1-b*inv(b%a,a))/a;}
ll exg(ll a,ll b,int&x,int&y){!a?x=0,y=1:(exg(b%a,a,y,x),x-=b/a*y);}
ll pow(ll a,ll b,ll M) {ll t=1;for(a%=M;b;b>>=1){if(b&1)t=t*a%M;a=a*a%M;}return t;}
const int N=1e5+5;
int a[N],n,m;
int main()
{
	cin>>n>>m;rep(i,1,m){
		int x,y;R(x);R(y);
		a[x]++;a[y]++;
	}
	int fg=1;rep(i,1,n)if(a[i]%2)fg=0;
	if(fg)puts("YES");else puts("NO");
}














Measured memory_bytes: 640
N, M = map(int, input().split())
A, B = [input() for _ in range(N)], [input() for _ in range(M)]

for i in range(N - M + 1):
    for j in range(N - M + 1):
        match = True
        for k in range(M):
            match = match and A[k + j][i:M + i] == B[k]
        if match:
            print("Yes")
            exit()

print("No")


Measured memory_bytes: 3060
def euqlid(a,b):
    if a < b :
        tmp = a
        a = b
        b = tmp

    while b != 0:
        rem = a % b
        a = b
        b = rem

    return a
N,X = list(map(int, input().split()))
x = list(map(int, input().split()))
x.append(X)
x.sort()
l = []
for i in range(N):
    l.append(x[i + 1] - x[i])
if len(l)  == 1:
    print(l[0])
    exit()
else:
    ans = euqlid(l[0],l[1])

for i in range(2,N - 1):
    ans = euqlid(ans,l[i])
print(ans)

Measured memory_bytes: 14480
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		
		Scanner scan = new Scanner(System.in);
		
		int a = scan.nextInt();	
		int b = scan.nextInt();	
		int c = scan.nextInt();	
		int d = scan.nextInt();	
		int e = scan.nextInt();	
		
		if(a == 0) {
			System.out.print(1);
		}
		else if(b == 0) {
			System.out.print(2);
		}
		else if(c == 0) {
			System.out.print(3);
		}
		else if(d == 0) {
			System.out.print(4);
		}
		else if(e == 0) {
			System.out.print(5);
		}
	
	}

}


Measured memory_bytes: 35700
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  rep(i, n) {
    ll a;
    cin >> a;
    if (a % 2 == 0) {
      if (a % 3 != 0 && a % 5 != 0) {
        cout << "DENIED" << endl;
        return 0;
      }
    }
  }
  cout << "APPROVED" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int inf = 1000000000;
int cost[10][10];
void floyd(){

    for(int k=0; k<10; k++){
        for(int i=0; i<10; i++){
            if(cost[i][k] == inf) continue;
            for(int j=0; j<10; j++){
                if(cost[k][j] == inf) continue;

                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
            }
        }
    }
}

int main(){
    int H, W; cin >> H >> W;
    vector<int> cnt(10, 0);

    for(int i=0; i<10; i++) for(int j=0; j<10; j++) cost[i][j] = inf;
    for(int i=0; i<10; i++) for(int j=0; j<10; j++) cin >> cost[i][j];

    for(int i=0; i<H; i++) for(int j=0; j<W; j++){
        int a; cin >> a;
        if(a != -1) cnt[a]++;
    }

    floyd();

    ll ans = 0;
    for(int i=0; i<10; i++){
        if(cnt[i] == 0 || i == 1) continue;
        ans += cost[i][1]*cnt[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            
            
            long[] num = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
            char[] str = Console.ReadLine().ToCharArray();

            str[num[1] - 1] = str[num[1] - 1].ToString().ToLower().ToCharArray()[0];
            


            Console.WriteLine(new string(str));
        }
        
    }
}


Measured memory_bytes: 11092
import itertools
N = int(input())
L = list(map(int,input().split()))

ans = 0
if len(L) <= 2 :
    print(ans)
else:
    for lists in itertools.combinations(L,3):
        if sum(lists) - max(lists) > max(lists):
            if len(lists) != len(set(lists)):
                continue
            else:
                ans += 1


        else:
            continue
    print(ans)

Measured memory_bytes: 9152
#include <iostream>

using namespace std;
int main()
{
  int N, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;
  p3 = p4 = p5 = p6 = p7 = p8 = p9 = p10 = 0;
  cin >> N;
  cin >> p1;
  cin >> p2;
  cin >> p3;
  cin >> p4;
  cin >> p5;
  cin >> p6;
  cin >> p7;
  cin >> p8;
  cin >> p9;
  cin >> p10;
  int price[10] = {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10};
  
  int sum = 0;
  int maxPrice = 0;
  
  for(int i = 0;i < N; i++){
    sum = sum + price[i];
    if(maxPrice < price[i]){
      maxPrice = price[i];
    } else{
      continue;
    }
  }
  
  sum = sum - maxPrice/2;
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

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

int main(){
    ll N, M; cin >> N >> M;
    vector<ll> b(N);
    for (ll i = 0; i < N; i++) {
        cin >> b[i]; b[i] = b[i] / 2;
    }   

    if(N == 1){
        printf("%lld\n", M / b[0] - M / (2*b[0]));
        return 0;
    }

    ll L = lcm(b[0], b[1]);
    for (ll i = 2; i < N; i++) {
        L = lcm(L, b[i]);
        if(L > M){
            printf("0\n");
            return 0;
        }
    }

    ll C = M / L;

    ll D = M / (2*L);

    for (ll i = 0; i < N; i++) {
        if( (L / b[i]) % 2 == 0 ){
            D = C;
        }
    }

    printf("%lld\n", C-D);
    


}

Measured memory_bytes: 4056
A, B, C, D, E, F = map(int, input().split())

water = []
for i in range(F//(A*100) + 1):
    for j in range(F//(B*100) + 1):
        n = (i*A + j*B)*100
        if n <= F:
            water.append(n)
water = sorted(list(set(water)))

density_d = {}
density = []

for i in water:
    suger_limit = E*(i//100)

    suger = []

    for j in range(suger_limit//C + 1):
        for k in range(suger_limit//D + 1):
            n = j*C + k*D
            if n <= suger_limit and n + i <= F:
                suger.append(n)
    suger = max(suger)
    if i+suger == 0:
        continue
    else:
        density.append(100*suger/(i+suger))
        density_d[100*suger/(i+suger)] = [i + suger, suger]
density = list(set(density))
a, b = map(int, density_d[max(density)])
print(a,b)


Measured memory_bytes: 5236
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = [list(map(int, readline().split())) for i in range(n - 1)]
gragh = [[] for j in range(n + 1)]
for a, b in ab:
    gragh[a].append(b)
    gragh[b].append(a)
root = 1
parent = [0] * (n + 1)
stack = [root]
order = []

while stack:
    x = stack.pop()
    order.append(x)
    for y in gragh[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
color = [-1] * (n + 1)

for x in order:
    ng = color[x]
    cnt = 1
    for y in gragh[x]:
        if y == parent[x]:
            continue
        if cnt == ng:
            cnt += 1
        color[y] = cnt
        cnt += 1

ans = []
append = ans.append
for a, b in ab:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(ans))
print('\n'.join(map(str, ans)))


Measured memory_bytes: 44764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	int n=read(),m=read();
	int l=1,r=n;
	while(m--)
	{
		l=max(l,read());
		r=min(r,read());
	}
	cout<<max(0,r-l+1)<<endl;
	return 0;
}


Measured memory_bytes: 256
from itertools import accumulate

def divisors(n):
    lst = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            lst.append(i)
            if i != n // i: lst.append(n // i)
    return lst

N, K = map(int, input().split())
*A, = map(int, input().split())
cands = divisors(sum(A))
for d in sorted(cands, reverse=True):
    rems = sorted([a % d for a in A])
    cumsum_rems = [0] + list(accumulate(rems))
    for i in range(1, N):
        minus = cumsum_rems[i]
        plus = d * (N - i) - (cumsum_rems[N] - minus)
        if max(minus, plus) <= K: break
    else:
        continue
    break
print(d)

Measured memory_bytes: 3188
from collections import deque

H,W=map(int,input().split())
Map=[input() for j in range(H)]

def bps(si,sj):
    distance=[[-1]*W for j in range(H)]
    distance[si][sj]=0
    deq=deque([[si,sj]])
    fdis=0
    while deq:
        i,j=deq.popleft()
        for dir_i,dir_j in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=i+dir_i<H and 0<=j+dir_j<W and distance[i+dir_i][j+dir_j]==-1 and Map[i+dir_i][j+dir_j]==".":
                distance[i+dir_i][j+dir_j]=fdis=distance[i][j]+1
                deq.append([i+dir_i,j+dir_j])
    return fdis

bestMapDistance=0
for i in range(H):
    for j in range(W):
        if Map[i][j]==".":
            bestMapDistance=max(bps(i,j),bestMapDistance)

print(bestMapDistance)




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

int main(){
	string s;
	cin >> s;
	
	int i;
	for(i=0; i<s.size(); i++){
		//cout << i << s[i] << endl;
		if(i%2==0){//奇数
			if(s[i]=='L'){
				cout << "No" << endl;
				return 0;
			}
		}
		else{
			if(s[i]=='R'){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


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

int K;
int cnt=0;
vector<long> A, B, C;

struct abcvalue{
	int a;
	int b;
	int c;
	long value;
};

vector<abcvalue> D;
vector<abcvalue> result;

bool comp(const abcvalue &a, const abcvalue &b) {
        return a.value < b.value;
}

bool result_has(abcvalue v) {
	for(vector<abcvalue>::iterator i=result.begin();i!=result.end();++i){
		abcvalue vv = *i;
		if(v.a == vv.a && v.b == vv.b && v.c == vv.c){
			return true;
		}
	}
	return false;
}

int main(){
	int X, Y, Z;
	cin >> X >> Y >> Z >> K;
	for(int i=0;i<X;++i){
		long n;
		cin >> n;
		A.push_back(n);
	}
	for(int i=0;i<Y;++i){
		long n;
		cin >> n;
		B.push_back(n);
	}
	for(int i=0;i<Z;++i){
		long n;
		cin >> n;
		C.push_back(n);
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());
	abcvalue v = {X-1, Y-1, Z-1, A[X-1]+B[Y-1]+C[Z-1]};
	D.push_back(v);
	sort(
			D.begin(),
			D.end(),
			comp
		);
	for(;result.size()<K;){
		abcvalue v = D.back();
		D.pop_back();
		int x = v.a;
		int y = v.b;
		int z = v.c;
		if(result_has(v)){
			continue;
		}
		result.push_back(v);
		if(x-1 >= 0){
			abcvalue v1 = {x-1, y, z, A[x-1]+B[y]+C[z]};
			D.push_back(v1);
		}
		if(y-1 >= 0){
			abcvalue v2 = {x, y-1, z, A[x]+B[y-1]+C[z]};
			D.push_back(v2);
		}
		if(z-1 >= 0){
			abcvalue v3 = {x, y, z-1, A[x]+B[y]+C[z-1]};
			D.push_back(v3);
		}
		sort(
				D.begin(),
				D.end(),
				comp
			);
	}
	for(int i=0;i<K;++i){
		cout << (result.begin()+i)->value << endl;
	}

	return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
//自作関数
template<class T> ll llpow(T x,T n){ll ans=1;while(n--){ans*=x;}return ans;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    int n,q;
    string s;
    string ac="AC";
    cin>>n>>q>>s;
    vector<bool> b(s.size(),false);
    rep(i,s.size()-1){
        string tmp=s.substr(i,2);
        if(tmp==ac)b[i]=true;
    }
    vector<int> to(s.size(),0);
    int sum=0;
    rep(i,s.size()){
        if(b[i])sum++;
        to[i]=sum;
    }
    vector<int> l(q),r(q);
    rep(i,q){
        int lv,rv;
        cin>>lv>>rv;
        l[i]=lv-1;
        r[i]=rv-1;
    }
    rep(i,q){
        cout<<to[r[i]-1]-to[l[i]-1]<<endl;
    }
    return 0;
}




Measured memory_bytes: 2176
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define PB push_back
#define POP pop_back()
#define PII pair<int,int>
#define FI first
#define SE second
#define ULL unsigned long long
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1),eps=1e-8;
const int maxn=2e5+10;
int a[maxn],b[maxn];
int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	sort(a+1,a+1+n);
 	sort(b+1,b+1+n);
 	if(n&1){
 		cout<<b[(n+1)/2]-a[(n+1)/2]+1<<endl;
	}else{
		cout<<(b[n/2+1]+b[n/2]-a[n/2+1]-a[n/2])+1<<endl;
	}
	 return 0;
}
/*
2
1 6
1 6
*/






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

int main() {
    int P, Q;
    while(cin >> P >> Q, P || Q) {
        vector<string> p(P), q(Q);
        for(auto &i : p) cin >> i;
        for(auto &i : q) cin >> i;

        int psum = 0;
        int D[12] = {0}, F[12] = {0};
        for(int i = 0; i < P; i++) {
            string str = p[i];
            int dot = 0;
            while(str[dot] == '.') dot++;
            D[i + 1] = dot;
        }
        for(int i = 0; i < Q; i++) {
            string str = q[i];
            int dot = 0;
            while(str[dot] == '.') dot++;
            F[i + 1] = dot;
        }
        vector<int> X(P + 1), Y(P + 1), Z(P + 1);
        for(int i = 0; i < P; i++) {
            string str = p[i];
            X[i] = count(str.begin(), str.end(), '(') - count(str.begin(), str.end(), ')') + (i == 0 ? 0 : X[i-1]);
            Y[i] = count(str.begin(), str.end(), '[') - count(str.begin(), str.end(), ']') + (i == 0 ? 0 : Y[i-1]);
            Z[i] = count(str.begin(), str.end(), '{') - count(str.begin(), str.end(), '}') + (i == 0 ? 0 : Z[i-1]);
        }
        vector<int> R(P + 1), C(P + 1), S(P + 1);
        for(int i = 0; i < Q; i++) {
            string str = q[i];
            R[i] = count(str.begin(), str.end(), '(') - count(str.begin(), str.end(), ')') + (i == 0 ? 0 : R[i-1]);
            C[i] = count(str.begin(), str.end(), '[') - count(str.begin(), str.end(), ']') + (i == 0 ? 0 : C[i-1]);
            S[i] = count(str.begin(), str.end(), '{') - count(str.begin(), str.end(), '}') + (i == 0 ? 0 : S[i-1]);
        }

        set<int> r, c, s;
        vector<int> ans(Q + 1,-2);
        ans[0] = 0;
        for(int i = 1; i <= 20; i++) {
            for(int j = 1; j <= 20; j++) {
                for(int k = 1; k <= 20; k++) {
                    bool flag = true;
                    for(int l = 0; l < P; l++) {
                        if(X[l] * i + Y[l] * j + Z[l] * k == D[l + 2]) ;
                        else {
                            flag = false;
                            break;
                        }
                    }
                    if(!flag) continue;
                    for(int l = 0; l < Q; l++) {
                        int indention = i * R[l] + j * C[l] + k * S[l];
                        if(ans[l + 1] == -2) ans[l + 1] = indention;
                        else if (ans[l + 1] != indention) ans[l + 1] = -1;
                    }
                }
            }
        }
        for(int i = 0; i < Q - 1; i++) {
            cout << ans[i] << " ";
        }
        cout << ans[Q-1] << endl;
    }

    return 0;
}

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




int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s, tmp = "";
	cin >> s;
	for (char &c : s) {
		if (c == 'B') {
			if (!tmp.empty())
				tmp.pop_back();
		}
		else tmp += c;
	}
	cout << tmp;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n; cin >> n;
  pair<LL, LL> p[n];
  rep(i, n) cin >> p[i].second >> p[i].first;

  sort(p, p + n);
  LL now = 0;
  string ans = "Yes";
  rep(i, n) {
    now += p[i].second;
    if (p[i].first < now) {
      ans = "No";
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3328
#include<iostream>
using namespace std;
int main()
{
	float a,b,t,sum;
	cin >> a >> b >> t;
	sum = a;
	if(a>(t+0.5)){
		printf("0");
	}else{
		int count = 1;
		while(1){
			if((sum+a)>(t+0.5)){
				break;
			}
			sum += a;
			count += 1;
		}
//		3 2 9
		printf("%.0f",b*count);
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int N;
string S;
int dp[2];

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

	cin >> S;
	N = S.size();

	int c = S[0] - '0';
	dp[0] = min(c, 11 - c);
	dp[1] = min(c+1,10-c);
	for (int i = 1; i < N; i++) {
		int c = S[i] - '0';
		int pre0 = dp[0];
		int pre1 = dp[1];
		dp[0] = min(c + pre0, 10 - c + pre1);
		if (c != 9)dp[1] = min(c + 1 + pre0, 9 - c + pre1);
		else dp[1] = pre1;
	}
	puts(dp[0]);

	return 0;
}


Measured memory_bytes: 1948
//2003年アジアB Lagrange's Four-Square Theorem
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int square(int sum, int d, int c);
int n;

int main(){
  while(scanf("%d",&n),n){
    printf("%d\n",square(0,1,0) );
  }
  exit(0);
}

int square(int sum, int d, int c){
  if(sum == n) return 1;
  if(c >= 4) return 0;
  int res = 0;
  for(int i = d; i*i <= n; i++){
    if(sum + i*i > n) break;
    res += square(sum + i*i, i, c+1);
  }
  return res;
}



Measured memory_bytes: 2064
import java.util.Scanner;
public class Main {

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

        int k=scan.nextInt();
        int t=scan.nextInt();
        int[]a=new int[t];
        int max=0,sum=0;


        for(int i=0;i<t;i++){
            a[i]=scan.nextInt();
            if(a[i]>max){
                sum+=max;
                max=a[i];
            }
            else
                sum+=a[i];
        }
        if(t==1)
            System.out.println(max-1);
        else if(max>sum+1) {
            int temp=max-sum;
            if(temp<=2)
                System.out.println(1);
            else
                System.out.println(temp-1);
        }
        else
            System.out.println(0);

    }
}

Measured memory_bytes: 9804
#include<bits/stdc++.h>
using namespace std;
main(){
  string s;
  cin>>s;
  int a,z;
  int n=s.size();
  for(int i=0;i<n;++i){
    if(s[i]=='A'){
      a=i;
      break;
    }
  }
  for(int i=n-1;i>=0;--i){
    if(s[i]=='Z'){
      z=i;
      break;
    }
  }
  cout<<z-a+1<<endl;
}

Measured memory_bytes: 640
S = raw_input()
T = raw_input()
s = [0]*(len(S)+1)
for i in range(len(S)):
    s[i+1] = s[i] + (-1 if S[i]=="A" else 1)
t = [0]*(len(T)+1)
for i in range(len(T)):
    t[i+1] = t[i] + (-1 if T[i]=="A" else 1)
q = input()
for _ in range(q):
    a, b, c, d = map(int, raw_input().split())
    print "YES" if (s[b]-s[a-1])%3==(t[d]-t[c-1])%3 else "NO"


Measured memory_bytes: 12660
n=int(input())

root=int(n**0.5)

min_keta=10000000000
for i in range(1,root+1):
    if n%i==0:
        one=len(str(i))
        two=len(str(n//i))
        min_keta=min(min_keta,max(one,two))




print(min_keta)


Measured memory_bytes: 9384
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int c[1010],w[1010];
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> c[i] >> w[i];
    }
    
    int rui[1010];
    bool jud[1010][1010]={false};
    rui[0] = 0;
    for(int i=1;i<=n;i++){
        rui[i] = w[i]+rui[i-1];
        jud[i][i] = true;
    }
    
    for(int i=1;i<n;i++){
        for(int j=1;j+i<=n;j++){
            if(jud[j+1][j+i] && rui[j+i]-rui[j] <= c[j]) jud[j][j+i] = true;
            if(jud[j][j+i-1] && rui[j+i-1]-rui[j-1] <= c[j+i]) jud[j][j+i] = true;
        }
    }
    
    int dp[1010];
    for(int i=0;i<=n;i++) dp[i] = i;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(jud[i][j]) dp[j] = min(dp[j],dp[i-1]+1);
        }
    }
    
    cout << dp[n] << endl;
    
    return(0);
}



Measured memory_bytes: 4104
# ABC1４５C 

import itertools, math

n = int(input())
city_list = [list(map(int, input().split())) for _ in range(n)]

length = 0
length_sum = 0
sum_ = 0

for num, val in enumerate(itertools.permutations(city_list, n)):
    for i in range(len(val) - 1):
        length =  math.sqrt((val[i][0] - val[i + 1][0]) ** 2 +  (val[i][1] - val[i + 1][1]) ** 2)
        length_sum += length
    sum_ += length_sum
    length_sum = 0
    
ans = sum_ / (num + 1)
print(ans)

Measured memory_bytes: 3064