akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int n;
int mod(int a,int b)
{
	if(a<0&&a%b!=0)
	{
		n=a/b+1;
		return a-(a/b+1)*b;
	}
	n=a/b;
	return a%b;
}
 
int main()
{
	int r,n2,i;
	char a[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};//ÀûÓÃ×Ö·û
	vector<int> array;
	scanf("%d",&n);
	if(n==0)
	{
		printf("0");
		return 0;
	}
	n2=n;
	while(n!=0)
		array.push_back(mod(n,-2));
	for(i=array.size()-1;i>=0;i--)
		printf("%c",a[array[i]]);
	return 0;
}

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

int main() {
  int a, b, sum;
  cin >> a >> b;
  
  for (int i=a; i <= b; i++){
    int c, d, f, g;
    c = i / 10000;
    d = (i % 10000) / 1000;
    f = (i % 100) / 10;
    g = i % 10;
    
    if (c == g && d == f){
      sum++;
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
int main(){
#define int long long
  int N,K;cin>>N>>K;
  vector<vector<int>>A(N);
  for(int i=0;i<N-1;i++){
    int a,b;cin>>a>>b;
    A[a-1].push_back(b-1);
    A[b-1].push_back(a-1);
  }
  
  queue<int> q;q.push(0);
  vector<int>nums(N,-1);nums[0]=K;
  while(q.size()){
    int f=q.front();q.pop();
    int t=0;
    for(int i=0;i<A[f].size();i++){
      if(nums[A[f][i]]==-1){
        q.push(A[f][i]);
        if(f==0)nums[A[f][i]]=(K-1-t)%M;
        else nums[A[f][i]]=(K-2-t)%M;
        t++;
      }
    }
  }
  int ans=1;
  for(int i=0;i<N;i++)ans=(ans*nums[i])%M;
  cout<<ans%M<<endl;
}

Measured memory_bytes: 8052
if __name__ == "__main__":
    xy = tuple(map(int, input().split()))

    g1 = (1, 3, 5, 7, 8, 10, 12)
    g2 = (4, 6, 9, 11)

    if(len(set(xy) & set(g1)) == 2):
        print("Yes")
    elif(len(set(xy) & set(g2)) == 2):
        print("Yes")
    else:
        print("No")


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

ll power(ll x, ll y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
int main()
{
	ll A,B,C,D;
	cin >> A >> B >> C >> D;
	ll t1=C/B;
	ll t2=A/D;
	if(C%B)
		t1++;
	if(A%D)
		t2++;
	if(t1<=t2)
		cout << "Yes\n";
	else
		cout << "No\n";
}

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

int main(){
  int N;
  cin>>N;
  deque<int> a;
  for(int i=0;i<N;i++){
    int j;
    cin>>j;
    if(i%2==0)
      a.push_back(j);
    else
      a.push_front(j);
  }
  if(N%2==0){
    for(int i=0;i<N-1;i++)
      cout<<a.at(i)<<' ';
    cout<<a.at(N-1)<<endl;
  }
  else{
    for(int i=N-1;i>0;i--)
      cout<<a.at(i)<<' ';
    cout<<a.at(0)<<endl;
  }
}

Measured memory_bytes: 2944
n = input()

a = map(int, raw_input().split())

ans = {}

for i in a:
    if i + 1 not in ans:
        ans[i + 1] = 1
    else:
        ans[i + 1] += 1
    if i - 1 not in ans:
        ans[i - 1] = 1
    else:
        ans[i - 1] += 1
    if i not in ans:
        ans[i] = 1
    else:
        ans[i] += 1

print max(ans.values())
        

Measured memory_bytes: 16364
import sys
input=sys.stdin.readline
def main():
    N=int(input())
    A=list(map(int,input().split()))
    flag=True
    for i in range(N):
        if A[i]%2==0:
            if A[i]%3==0 or A[i]%5==0:
                pass
            else:
                flag=False
                break
    if flag:
        print("APPROVED")
    else:
        print("DENIED")
if __name__=="__main__":
    main()

Measured memory_bytes: 3060
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
edge = [[] for _ in range(N+1)]
color = [-1] * (N+1)
for _ in range(N-1):
    u,v,w = LI()
    edge[u].append((v,w))
    edge[v].append((u,w))

def set_color(u,c):
    color[u] = c
    for v,w in edge[u]:
        if color[v] >= 0 : continue
        set_color(v,(w % 2) ^ c)
set_color(1,0)
print(*color[1:],sep='\n')


Measured memory_bytes: 80392
import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

def main():
  n = int(input())
  alist = list(map(int, input().split()))

  nn = 1
  for i in range(2, n+1):
    nn = nn * i % MOD

  rev = [pow(i, MOD-2, MOD) * nn % MOD for i in range(1, n+1)]
  for i in range(1, n):
    rev[i] = (rev[i] + rev[i-1]) % MOD

  ans = 0
  for i in range(n):
    ans += alist[i] * (rev[i] + rev[n-i-1] - rev[0]) % MOD
    ans %= MOD

  print(ans)


if __name__ == '__main__':
  main()


Measured memory_bytes: 59544
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 


def main():
    n,r = inpm()
    if n >= 10:
        print(r)
    else:
        print(r+100*(10-n))
    
if __name__ == "__main__":
    main()




Measured memory_bytes: 39020
require 'matrix'

colors = [0, 255].repeated_permutation(3).map{|a| Vector[*a]}
names = %w(
    black   
    blue    
    lime    
    aqua    
    red 
    fuchsia 
    yellow  
    white   
)
color_name = Hash[*colors.zip(names).flatten]

loop do
    s = gets[1..-2]
    break if s == ''
    u = Vector[*s.scan(/../).map{|x| x.hex}]
    puts color_name[colors.min_by{|v| (v - u).r}]
end

Measured memory_bytes: 9124
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# print(N, A, B, C)

ans = 0
last = -1
for i in range(N):
    a = A[i]
    ans += B[a - 1]
    if last != -1 and last + 1 == a:
        ans += C[last - 1]
    last = a

print(ans)


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

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

#define rrep(i,n) for(int i =n; i >=0; --i)

#define rep_(i,m,n) for(int i =m; i <n; ++i)

#define INF 2e9

#define ll long long

const ll MOD = 1000000007;

const  long double PI=(acos(-1));

const  long double EPS=0.0000000001;


long long gcd(long long a, long long b){
    if(a%b==0)return b;
    else return gcd(b,a%b);
}

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

int main(){
    ll a,b,c,d;cin >> a >> b >> c >>d;

    ll cd = lcm(c,d);


    ll cd_cnt = (long long)(b/cd) - (long long)((a-1)/cd);
    ll c_cnt = (long long)(b/c) - (long long)((a-1)/c);
    ll d_cnt = (long long)(b/d) - (long long)((a-1)/d);

    cout << (b -a +1) - c_cnt - d_cnt + cd_cnt << endl;
    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)==2)
    {
        if((a==1 || a==3 || a==5 || a==7 || a==8 || a==10 || a==12) && (b==1 || b==3 || b==5 || b==7 || b==8 || b==10 || b==12))
        {
            printf("Yes\n");
        }
        else if((a==4 || a==6 || a==9 || a==11) && (b==4 || b==6 || b==9 || b==11))
        {
             printf("Yes\n");
        }
        else if(a==2 && b==2)
        {
             printf("Yes\n");
        }
        else
        {
             printf("No\n");
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
    int a,b,c,x;
    int ans=0;
    std::cin >> a >> b >> c >>x;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int l=0;l<=c;l++){
                if(x==500*i+100*j+50*l){
                    ans++;
                }
            }
        }
    }
    std::cout << ans << std::endl;
    return 0;
}


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

int gcd(int p, int q){
  while(q != 0){
    int r = p % q;
    p = q;
    q = r;
  }
  return p;
}

int main()
{
  //入力
  int num;
  cin>>num;

  //操作と出力
  long int count=0;
  
  for(int i=1;i<=num;i++){
    for(int j=1;j<=num;j++){
      for(int k=1;k<=num;k++){
        count+=gcd(gcd(i,j),k);
      }
    }
  }
  cout<< count <<endl;
  
  return 0;
}

Measured memory_bytes: 3160
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  double A=0.8;
  double x,y,b,p,a,h;
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> x >> y >> b >> p;
    if(5<=b&&2<=p){
      x=x*A;
      y=y*A;
      cout << x*b+y*p << endl;
    }else{
      a=x*b+y*p;
      if(b<5&&p<2){
	h=x*5*A+y*2*A;
      }else if(b<5&&2<=p){
	h=x*5*A+y*p*A;
      }else if(5<=b&&p<2){
	h=x*b*A+y*2*A;
      }
      if(a<h){
	printf("%g\n",a);
      }else{
	printf("%g\n",h);
      }
    }
  }
  
  return(0);
}



Measured memory_bytes: 3300
#include <stdio.h>

int main(void){
    int k, a, b, c = 0;
    scanf("%d%d%d", &k, &a, &b);
    for(a; a <= b; a++){
        if(a%k == 0){
            c = 1;
            break;
        }
    }
    if(c == 0){
        printf("NG\n");
    }else{
        printf("OK\n");
    }
    return 0;
}


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

int main(){
  int i,j,cnt=0;
  string s;
  cin>>s;
  int c=0,f=0;
  for(i=0;i<s.size();i++){
    if(s[i]=='C')c=1;
    if(c==1){
      if(s[i]=='F')f=1;
    }
  }
  if(c==1 && f==1)cout<<"Yes";
  else cout<<"No";
}

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

#define count_ones __builtin_popcountl
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lca(a, b) a / __gcd(a, b) * b
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    if (*min_element(all(a)) != 1) {
        cout << -1;
        return 0;
    }
    ll cur = 1, ans = 0;
    for (ll i = 0; i < n; i++) {
        if (a[i] == cur) {
            cur++;
        } else {
            ans++;
        }
    }
    cout << ans;

    return 0;
}

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


int main() {
    int n,m;

   cin>>n>>m;
vector<int> h(n);
vector<int> f(m);
vector<int> s(m);
vector<bool> e(n);
int ans=0;
for (int i = 0; i < n; i++)
{
    cin>>h[i];
}
for (int i = 0; i < m; i++)
{
    cin>>f[i]>>s[i];
   
}
for (int i = 0; i < m; i++)
{
   int one=f[i]-1;
   int two=s[i]-1;
   if(h[one]>h[two]){
e[two]=1;
}
if(h[one]<h[two]){e[one]=1;}
if(h[one]==h[two]){e[one]=1;e[two]=1;}

}
for (int i = 0; i < n; i++)
{
if(e[i]==0)ans++;


}
cout<<ans<<endl;

}

Measured memory_bytes: 4492
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define ll long long int
#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 REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
const int INF = 1001001001;
const ll MOD = 1e9+7;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){std::fill((T*)array, (T*)(array+N),val);}


__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


signed main(){
	double a,b,x; cin>>a>>b>>x;
	double ans1 = atan(2.0*(pow(a,2.0)*b-x)/pow(a,3.0));
	double ans2 = atan(2.0*x/(a*pow(b,2.0)));
	if((a*a*b/2)<x) cout<< ans1/PI*180 <<endl;
	else cout<< 90.0-ans2/PI*180 <<endl;
	
	cerr << ans1/PI*180 SP 90.0-ans2/PI*180 << endl;
	// cout << min(ans1,PI/2-ans2)/PI*180 << endl;
  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

// fact(n)
int fact(int n){
	if(n == 1)	return 1;
	else return (n * fact(n - 1));
}

// nCr(n,r)
int nCr(int n, int r){
	if(r == 0 || r == n)	return 1;
	else if(r == 1)	return n;
	return (nCr(n - 1, r - 1) + nCr(n - 1, r));
}

int gcd(int a,int b){
	if(!(a % b)) return b;
	return gcd(b,a % b);
}

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

// qsort(array, size, sizeof(int),comp);
int comp(const int *a,const int *b){
	return (*a - *b);
}

// append(array,*size,addNum)
void append(int *array,int *size,int num){
	realloc(array, sizeof(int) * (*size + 1));
	array[(*size)] = num;
	++(*size);
}

// pop(array,*size) & nongetpop(array,*size)
int pop(int *array,int *size){
	int temp = array[(*size - 1)];
	nongetpop(array,&(*size));
	return temp;
}

int nongetpop(int *array,int *size){
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
}

int main(int argc, char const *argv[])
{
	int a,b;
	int ans = 0;
	scanf("%d%d",&a,&b);
	for (int i = 0; i < 2; ++i)
	{
		if(a <= b){
			ans += b;
			--b;
		}
		else{
			ans += a;
			--a;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

//typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

vector<vector<int>> c(10, vector<int>(10));

void floyd(){
    for(int k=0; k<10; k++){
        for(int i=0; i<10; i++){
            for(int j=0; j<10; j++){
                c[i][j]=min(c[i][j], c[i][k]+c[k][j]);
            }
        }
    }
}


int main(){
    int h;
    int w;
    int ans=0;
    cin >> h >> w;
    int a;
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin >> c[i][j];
        }
    }

    floyd();

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> a;
            if(a!=-1){
                ans+=c[a][1];
            }
        }
    }

    //for(int i=0; i<10; i++){
    //    for(int j=0; j<10; j++){
    //        cout << c[i][j] << " ";
    //    }
    //    cout << endl;
    //}

    cout << ans << endl;

}


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

#define ll long long

using namespace std;
const int N = 3e5 + 5;
int a[N], ac[N];
string s;
int get(int i, int j) {
	if (!i)
		return ac[j];
	return ac[j] - ac[i - 1];
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		a[i] = (s[i] == 'E');
		ac[i] = a[i] + (i ? ac[i - 1] : 0);
	}

	int ans = ac[n - 1] - a[0];
	ans = min(ans, (n - 1) - (ac[n - 1] - a[n - 1]));
	for (int i = 1; i < n - 1; i++) {
		int x = get(0, i - 1);
		int x2 = get(i + 1, n - 1);
		ans = min(ans, i - x + x2);
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 2964
n, a = map(int, input().split())
x = [0] + list(map(int, input().split()))
nx = 2501

# DP: x1からxjまでの間でk枚を選んで合計がsになる組み合わせの数
dp = [ [ [0 for s in range(nx+1)] for k in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1

for j in range(1, n+1):
    for k in range(n+1):
        for s in range(nx+1):
            if x[j] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
#print(dp)
ans = 0
for k in range(1, n+1):
    ans += dp[-1][k][a * k]

print(ans)


Measured memory_bytes: 96392
using System;
using System.Linq;
using System.Collections.Generic;

namespace b
{
    class Player{
        private int idxNow;
        private readonly char[] hand;

        public Player(string s){
            this.hand = s.ToCharArray();
            this.idxNow = 0;
        }

        public char GetNext(){
            var c = this.hand[this.idxNow];
            this.idxNow += 1;
            return c;
        }

        public bool HasNext(){
            if(this.idxNow >= this.hand.Length){
                return false;
            }else{
                return true;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var d = new Dictionary<char,Player>();
            d['a'] = new Player(Console.ReadLine().Trim());
            d['b'] = new Player(Console.ReadLine().Trim());
            d['c'] = new Player(Console.ReadLine().Trim());

            var next = 'a';
            while(true){
                var player = d[next];
                if(player.HasNext()){
                    next = player.GetNext();
                }else{
                    Console.WriteLine(char.ToUpper(next));
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 13152
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
//#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int a,b;
   cin>>a>>b;
   cout<<a*b<<endl;
}


Measured memory_bytes: 3644
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
#define inf 0x3f3f3f3f

using namespace std;

typedef struct
{
	int v, d, c;
}EDG;

typedef pair<int, int> P;

EDG e;
vector<EDG>G[10016];
int n, m, d[10016];
priority_queue<P, vector<P>, greater<P> > que;

void dij(int x)
{	
	int i, j, v;
	P p;
	fill(d, d + n + 1, inf);
	d[x] = 0;
	que.push(P(0, x));
	while (!que.empty())
	{
		p = que.top(); que.pop();
		v = p.second;
		if (d[v] < p.first)
			continue;
		for (i = 0; i < G[v].size(); i++)
		{
			e = G[v][i];
			if (d[e.v] > d[v] + e.d)
			{
				d[e.v] = d[v] + e.d;
				que.push(P(d[e.v], e.v));
			}
		}
	}
}

int main()
{
	int i, j, u, v, minn, ans;
	while (scanf("%d%d", &n, &m) && (n || m))
	{
		for (i = 0; i < m; i++)
		{
			scanf("%d%d%d%d", &u, &e.v, &e.d, &e.c);
			G[u].push_back(e);
			v = e.v; e.v = u;
			G[v].push_back(e);
		}
		dij(1);
		for (i = 2, ans = 0; i <= n; i++)
		{
			for (j = 0, minn = inf; j < G[i].size(); j++)
			{
				e = G[i][j];
				if (d[e.v] + e.d == d[i] && minn > e.c)
					minn = e.c;
			}
			ans += minn;
		}
		printf("%d\n", ans);
		for (i = 1; i <= n; i++)
			G[i].clear();
	}
	return 0;
} 

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

string s;
vector<int> edit;

int main(void)
{
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		switch (s[i]) {
			case '0':
				edit.push_back(0);
				break;
			case '1':
				edit.push_back(1);
				break;
			default:
				if (!edit.empty())
					edit.pop_back();
				break;
		}
	}
	for (int i = 0; i < edit.size(); i++)
		cout << edit[i];
	cout << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x,y;
    y=a/d;//老2打死老1的回合数
    x=c/b;
    if(a%d!=0) y+=1;
    if(c%b!=0) x+=1;
    if(x<=y) cout<<"Yes";
    else cout<<"No";
    return 0;
}


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

int main(void){
    string S;
    int ans=0;
    cin>>S;

    for(int i=0;i<S.size();i++){
        int cnt=0;
        while(S.size()-i>=cnt){
            string s=S.substr(i,cnt);
            int size=s.size();
            int count=0;
            for(int j=0;j<size;j++){
                if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T')
                    count++;
            }
            if(count==size&&s.size()>ans)
                ans=size;
            cnt++;
        }
    }

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


Measured memory_bytes: 256
import math
import numpy as np


#横並び
#a, b, c, x = map(int, [input() for i in range(4)])
#z = list(map(int, input().split()))
#n, a, b = map(int, input().split())

#print(len(z))
#for i in z:
#    print(i)

#a = sorted(a,reverse = True)
#print(sum(a[::2]) - sum(a[1::2]))
#z = map(int, [input() for i in range(int(n))])
#data_list = [ list(map(int,input().split(" "))) for i in range(3)]



n = int(input())
ans = 1
ta = 0
xa = 0
ya = 0
for i in range(n):
    t,x,y = map(int, input().split())
    if (((t-ta) - (x-xa) - (y-ya)) % 2) == 0 and ((t-ta) >= (abs(x-xa) + abs(y - ya))):
        ans = ans *1
    else:
        ans = ans * 0
if ans:
    print("Yes")
else:
    print("No")


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

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String sArr[] = br.readLine().split(" ");
            int n = Integer.parseInt(sArr[0]);
            int m = Integer.parseInt(sArr[1]);
            int x = Integer.parseInt(sArr[2]);
            int y = Integer.parseInt(sArr[3]);
            int xArr[] = new int[n];
            int xMax = -999;
            int yArr[] = new int[m];
            int yMin = 999;
            sArr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                xArr[i] = Integer.parseInt(sArr[i]);
                if (xMax < xArr[i]) {
                    xMax = xArr[i];
                }
            }
            sArr = br.readLine().split(" ");
            for (int i = 0; i < m; i++) {
                yArr[i] = Integer.parseInt(sArr[i]);
                if (yMin > yArr[i]) {
                    yMin = yArr[i];
                }
            }
            boolean flag = false;
            for (int i = xMax + 1; i <= yMin; i++) {
                if (i > x && i <= y) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                System.out.println("No War");
            } else {
                System.out.println("War");
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}


Measured memory_bytes: 21972
import java.util.Scanner;
class Main
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        
        if(k%2==0){
            System.out.println((k/2)*(k/2));
        }
        else{
            System.out.println(((k/2)+1)*(k/2));
        }
        sc.close();
    }
}

Measured memory_bytes: 21716
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,input_func:[input_func() for _ in range(n)]

import importlib
import_module = lambda module_name:importlib.import_module(module_name)

init_array_1dim = lambda value,n:[value]*n # 1次元配列を生成
init_array_2dim = lambda value,n,m:[init_array_1dim(value,n) for _ in range(m)] # 2次元配列を生成

gcd_base = lambda value1,value2:import_module('fractions').gcd(value1,value2) # 最大公約数（2値)
gcd = lambda lst:import_module('functools').reduce(gcd_base,lst) # 最大公約数（リスト）
lcm_base = lambda value1,value2:(value1*value2)//gcd_base(value1,value2) # 最小公倍数(2値)
lcm = lambda lst:import_module('functools').reduce(lcm_base,lst,1) # 最小公倍数(リスト)

permutations = lambda lst,n:import_module('itertools').permutations(lst,n) # 順列
combinations = lambda lst,n:import_module('itertools').combinations(lst,n) # 組み合わせ
product = lambda lst1,lst2:import_module('itertools').product(lst1,lst2) # 二つのリストの直積

round = lambda value:round(value) # 四捨五入
ceil = lambda value:import_module('math').ceil(value) # 切り上げ
floor = lambda value:import_module('math').floor(value) # 切り捨て

# キュー
init_q = lambda lst: import_module('collections').deque(lst)
q_pop = lambda q: q.popleft() # 先頭から取り出し
q_push = lambda q,value:q.appendleft(value) # 先頭に追加（値）
q_pushlist = lambda q,lst:q.extendleft(lst) # 先頭に追加（リスト）
q_append = lambda q,value:q.append(value) # 末尾に追加（値）
q_appendlist = lambda q,lst:q.extend(lst) # 末尾に追加（リスト）

# プライオリティキュー
init_heap = lambda a:import_module('heapq').heapify(a)
heap_push = lambda a,v:import_module('heapq').heappush(a,v)
heap_pop = lambda a:import_module('heapq').heappop(a) # 最小値を取り出す

def solution():
    # ここに実装
    S = input_str()

    month_1 = False
    if 1<=int(S[:2])<=12:month_1 = True
    month_2 = False
    if 1<=int(S[2:])<=12:month_2 = True
    
    if month_1 and month_2:
        print('AMBIGUOUS')
        return
    if month_1:
        print('MMYY')
        return
    if month_2:
        print('YYMM')
        return
    print('NA')

if __name__ == '__main__':
    solution()

Measured memory_bytes: 3192
x = int(input())
if x < 2000 and x >= 1800:
    print(1)
elif x < 1800 and x >= 1600:
    print(2)
elif x < 1600 and x >= 1400:
    print(3)
elif x < 1400 and x >= 1200:
    print(4)
elif x < 1200 and x >= 1000:
    print(5)
elif x < 1000 and x >= 800:
    print(6)
elif x < 800 and x >= 600:
    print(7)
elif x < 600 and x >= 400:
    print(8)
else:
    print()

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main()
{
    int a,b;
    cin >> a >> b;
    if(a>b)
    a--;
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
#AGC004 A 22:48-
'''
問題
1x1x1のブロックがAxBxC個積まれた直方体がある
各ブロックを赤か青で塗って次の3条件をみたしたい
1：赤いブロックも青いブロックも1個以上ある
2：赤いブロック全体が1つの直方体になっている
3：青いブロック全体が1つの直方体になっている
このとき赤いブロックの個数と青いブロックの個数の最小値は？
ただしAとBとCは2以上10**9以下

考察
可能な塗り方は縦方向に赤と青で2分するか，横方向でするか，高さ方向でするかのいずれか
縦方向で2分したときの赤と青の個数の差の最小値は(A%2)*B*C
同様に横方向で2分したときの最小値は(B%2)*C*A
同様に高さ方向で2分したときの最小値は(C%2)*A*B
これらの最小値をとればよい
'''

A,B,C=map(int,input().split(' '))

val = [(A%2)*B*C,(B%2)*C*A,(C%2)*A*B]

print(str(min(val)))

Measured memory_bytes: 3060
from collections import deque

H,W = map(int,input().split())
s = [list(input()) for i in range(H)]

directions = [[-1,0],[1,0],[0,-1],[0,1]]

A = [[-1]*W for i in range(H)]  #(sy,sx)からの最短距離
A[0][0] = 0

q = deque([[0,0]])

while q:
    y,x = q.pop()
    for dy,dx in directions:
        if not (0<= y+dy < H and 0 <= x+dx < W):
            continue
        elif s[y+dy][x+dx] == '#':
            continue
        elif A[y+dy][x+dx] != -1:
            continue
        else:
            A[y+dy][x+dx] = A[y][x] + 1
            q.appendleft([y+dy,x+dx])
if A[H-1][W-1] == -1:
    print(-1)
    exit()

a = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            a += 1

print(a-A[H-1][W-1]-1)

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <list>
#include <cstring>

int main(void) {
  int K;

  std::string str;

  std::string s_;
  std::cin >> s_;
  const char* s = s_.c_str();

  std::cin >> str;
  K = std::stoi(str);

  size_t lsize = 0;
  size_t len = s_.length();

  typedef struct s_set {
    int pos;
    int len;

    s_set(int i, int j) : pos(i), len(j) {
    }
  } set;

  std::list<std::string> wlist;
  //std::list<set> wlist;

  wlist.push_back(s_.substr(0, 1));
  //wlist.push_back(set(0, 1));
  //for (int a = 'a'; a <= 'z' && lsize < K; ++a) {        /* a to z   */
  //  for (int b = 'a'; b <= 'z' && lsize < K; ++b) {      /* a to z   */
      for (int i = 0; i < len; ++i) {                    /* 0 to len */
        //if (s[i] == a && (i+1 >= len || s[i+1] == b)) {
          for (int j = 1; j <= len - i && j <= K; ++j) {           /* length 1 to len - i */
            for (auto itr = wlist.begin(); itr != wlist.end(); ++itr) {
              int cmp = s_.compare(i, j, *itr);
              //int cmp = s_.compare(i, j, s_, itr->pos, itr->len);
              if (cmp == 0) {
                break;
              }
              if (cmp < 0) {
                wlist.insert(itr, s_.substr(i, j));
                //wlist.insert(itr, set(i, j));
                lsize++;
                break;
              }
              if (cmp > 0 && itr->c_str() == wlist.rbegin()->c_str()) {
              //if (cmp > 0 && (itr->pos == wlist.rbegin()->pos && itr->len == wlist.rbegin()->len)) {
                wlist.push_back(s_.substr(i, j));
                //wlist.push_back(set(i, j));
                lsize++;
                break;
              }
            }
          }
        //}
      }
  //  }
  //}

  size_t idx = 0;
  for (auto &str : wlist) {
    idx++;
    if (idx == K) {
      std::cout << str << std::endl;
      //std::cout << str.pos << "," << str.len << std::endl;
      //std::cout << s_.substr(str.pos, str.len) << std::endl;
    }
  }

  return 0;
}

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

int main(){

    string w;
    cin >> w;

    int size = w.size();
    map<char, int> dict;

    for (int i=0; i<size; i++){
        dict[w.at(i)]++;
    }

    bool flg = true;
    for (auto p: dict){
        auto value = p.second;

        if (value%2 != 0) flg = false;
    }

    if (flg == true) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string S; cin>>S;
	cout<<(S[2]==S[3]&&S[4]==S[5]?"Yes":"No")<<"\n";
	return 0;
}

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

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

    int c[10][10];
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            c[i][j] = 0;
        }
    }

    for(int i=1; i<=N; i++){
        int head = stoi(to_string(i).substr(0,1));
        int tail = i % 10;
        c[head][tail]++; 
    }

    int sum = 0;

    for(int i=1; i<10; i++){
        for(int j=1; j<10; j++){
            sum += c[i][j] * c[j][i];
        }
    }

    cout << sum << endl;

}


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

int main(){
    int N;
    cin >> N;
    int max = 0, num, count, res = 1;
    for(int i=N;i>0;i--){
        num = i;
        count = 0;
        while(num > 0 && (num % 2) == 0){
            num = num / 2;
            count++;
        }
        if(count > max){
            max = count;
            res = i;
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int h,w;
vector<string> s;

int main(){
    cin >> h >> w;
    s.resize(h);
    for(int i = 0;i < h;i++) cin >> s.at(i);

    vector <vector<int>> c(h,vector<int>(w,0));

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

    for(int x = 0;x < h; ++x){
        for(int y = 0;y<w;++y){
            if(s.at(x).at(y) == '#'){
                c.at(x).at(y) = -1;
                continue;
            }
        for(int dir = 0;dir < 8; ++dir){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
        if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;

        if(s.at(nx).at(ny) == '#') c.at(x).at(y)++;
        }

        }
    }
    for(int i = 0;i<h;++i){
        for(int j = 0;j<w;++j){
            if(c.at(i).at(j) == -1) cout << '#';
            else cout << c.at(i).at(j);
        }
        cout << endl;
    }
}

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

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

int main(){
	ll N,H;
	cin >> N >> H;
	ll ma = 0;
	vector<ll> A;
	vector<ll> B;
	rep(i,N){
		ll a,b;
		cin >> a >> b;
		A.push_back(a); B.push_back(b);
	}
	ma = *max_element(A.begin(),A.end());
	ll ans = 0;
	sort(B.begin(),B.end());
	reverse(B.begin(),B.end());
	for(ll u : B){if(u>ma){H-=u; ans++; if(H<=0)break;}}
	if(H>0){
		ans += H/ma;
		if( H%ma )ans++;
	}
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 2036
import java.util.Scanner;

public class Main {
	int prime[];

	void eratosthenes(int max) {
		prime = new int[max + 1];
		for (int i = 0; i < max + 1; i++) {
			prime[i] = 1;
		}
		prime[0] = prime[1] = 0;
		for (int i = 2; i * i <= max; i++) {
			if (prime[i] == 1) {
				for (int j = i * i; j <= max; j += i) {
					prime[j] = 0;
				}
			}
		}
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		eratosthenes(250000);

		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int ans = 0;
			for (int i = n + 1; i <= 2*n; i++) {
				if (prime[i] == 1) ans++;
			}

			System.out.println(ans);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 23096
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define V vector
#define pb push_back
#define mkp make_pair
#define pi pair<int,int>//struct pi {int fi,se;};
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++)
#define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--)
#define ln length()
#define sz size()
const int N=100005;
///////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////

int32_t main()
{
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // int t;cin>>t;while(t--)
    {
        int i,j,k,n,m,ans=0,cnt=0,sum=0;
        cin>>n;
        if( n <= 599){
            cout << "8"<<endl;
        }else if(n >= 600 && n <= 799){
            cout << "7"<<endl;
        }else if(n >= 800 && n <= 999){
            cout << "6"<<endl;
        }else if(n >= 1000 && n <= 1199){
            cout << "5"<<endl;
        }else if(n >= 1200 && n <= 1399){
            cout << "4"<<endl;
        }else if(n >= 1400 && n <= 1599){
            cout << "3"<<endl;
        }else if(n >=1600 && n <= 1799){
            cout << "2"<<endl;
        }else if(n >= 1800 && n <= 1999){
            cout << "1"<<endl;
        }
    }
}

Measured memory_bytes: 3648
using System;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {

        // 入力
        long[] nk = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var n = nk[0];
        var k = nk[1];

        long[] h = new long[n];
        for (int i = 0; i < n; i++)
        {
            h[i] = long.Parse(Console.ReadLine());
        }

        Array.Sort(h);

        long ans = long.MaxValue;
        for (int i = 0; i < n-(k-1); i++)
        {
            ans = Math.Min(ans, h[i+(k-1)] - h[i]);
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 16092
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    int a, b;
    
    scanf("%d%d", &a, &b);
    
    printf("%d", 6-(a+b));

    return 0;
}



Measured memory_bytes: 1708
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define BUFFER_MAX 100

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	if (a < b) return -1;
	return a > b;
}

int N, K;
int a[8192];

int cardNum;
int cards[8192];

uint64_t canMake[2][BUFFER_MAX];

void merge(uint64_t* dest, const uint64_t* src, int offset) {
	int deltaIndex = offset / 64;
	int shift = offset % 64;
	int i;
	for (i = 0; i < BUFFER_MAX; i++) {
		dest[i] = src[i];
	}
	if (shift == 0) {
		for (i = deltaIndex; i < BUFFER_MAX; i++) {
			dest[i] |= src[i - deltaIndex];
		}
	} else {
		dest[deltaIndex] |= src[0] << shift;
		for (i = deltaIndex + 1; i < BUFFER_MAX; i++) {
			dest[i] |= ((src[i - deltaIndex] << shift) | (src[i - deltaIndex - 1] >> (64 - shift)));
		}
	}
}

/* [min, max) */
int exists(const uint64_t* data, int min, int max) {
	int minIndex = min / 64;
	int minShift = min % 64;
	int maxIndex = max / 64;
	int maxShift = max % 64;
	uint64_t minMask = (~UINT64_C(0)) << minShift;
	uint64_t maxMask = (~UINT64_C(0)) << maxShift;
	if (minIndex == maxIndex) {
		uint64_t mask = minMask & ~maxMask;
		return (data[minIndex] & mask) != 0;
	} else {
		int i;
		if ((data[minIndex] & minMask) != 0) return 1;
		for (i = minIndex + 1; i < maxIndex; i++) {
			if (data[i] != 0) return 1;
		}
		if ((data[maxIndex] & ~maxMask) != 0) return 1;
		return 0;
	}
}

int isFuhituyou(const int* cards, int syugoNum, int targetIndex) {
	int i;
	int current = 0;
	for (i = 0; i < BUFFER_MAX; i++) {
		canMake[current][i] = 0;
	}
	canMake[current][0] = 1;
	for (i = 0; i < syugoNum; i++) {
		if (i != targetIndex) {
			merge(canMake[1 - current], canMake[current], cards[i]);
			current = 1 - current;
		}
	}
	return !exists(canMake[current], K - cards[targetIndex], K);
}

int main(void) {
	int i;
	int sum = 0;
	int yes, no;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	cardNum = 0;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &a[i]) != 1) return 1;
		if (a[i] < K) {
			cards[cardNum++] = a[i];
			if (sum < K) sum += a[i];
		}
	}
	if (sum < K) {
		/* K未満のカードをすべて足してもK未満 → 全て不必要である */
		printf("%d\n", cardNum);
		return 0;
	}
	qsort(cards, cardNum, sizeof(*cards), cmp);
	/* 最初が不必要でない → 全て不必要でない */
	if (!isFuhituyou(cards, cardNum, 0)) {
		puts("0");
		return 0;
	}
	yes = 0;
	no = cardNum;
	while (yes + 1 < no) {
		int mid = yes + (no - yes) / 2;
		if (isFuhituyou(cards, cardNum, mid)) yes = mid; else no = mid;
	}
	printf("%d\n", yes + 1);
	return 0;
}

/*

K以上のカード → 単体でよい集合 → 判定に関係ない (不必要なカードではない)
K未満のカード → aのカードを除いた時、総和がK-a以上K未満になる集合を作れるか？

MAX 5000枚 → 平方分割 72 × 72 程度

各ブロックを除いて作れる数をDP 約5000 × 72
各カードについて、所属するブロックと残りでDP 約72 × 5000

↑1回のDPが5000じゃなくて、5000×5000やんけ＼(^o^)／

仮に一番下のカードaを除いたセットで、総和がK-a以上K未満になる集合を作れるとすると
一番下のカードを加えれば総和がK以上になる → その集合の要素は不必要でない
それ以上のカードを加えても総和がK以上になる → それ以上のカードも不必要でない

作れないなら不必要 (予想)

不必要 → それがあるかによってK以上になるかに影響を与えない → 抜かなくてよい

仮にあるカードが「不必要でない」 → そのカード以上は全て不必要でない
(不必要でない根拠の集合を構成 or そのカードの代わりに「よい集合」にできる ため)

仮にあるカードが「不必要」→ そのカード以下は全て不必要
(そのカード以下に不必要でないカードがあると、上に矛盾するため)

「不必要でない」かの判定 → そのカードを除いてDPでK-a以上K未満にできるか
ビット演算による定数倍高速化：5000×5000 → 5000×80くらい (64倍)

不必要 or notの二分探索

*/


Measured memory_bytes: 256
import numpy as np
import copy
h,w,k=map(int, input().split())
c=[list(input())  for i in  range(h)]
c=np.array(c)
def makeBag(n):
  bagl=[]
  for i in range(2**n):
      bag=[0]*n
      
      for j in range(n):
          if ((i>>j) & 1):
              bag[j]=1
      bagl.append(bag)
  return bagl
bagh=makeBag(h)
bagw=makeBag(w)

ans=0
for i in bagh:
  co=copy.deepcopy(c)
  #行を塗りつぶす
  for ii in range(h):
    if i[ii]==1:
      co[ii][:]=["r"]*len(co[ii][:])
  
  co=co.T
  co2=copy.deepcopy(co)
  for j in bagw:
    co=copy.deepcopy(co2)
    #転置して列を塗りつぶす
    for jj in range(w):
      if j[jj]==1:
        co[jj][:]=["r"]*len(co[jj][:])
  
    #黒の数を数える
    if np.sum(co=="#")==k:
      ans+=1
      
print(ans)

Measured memory_bytes: 27252
#include<stdio.h>

int main(void){
int N,C[30],V[30],i,max;
  scanf("%d",&N);
  
  for(i=0;i<N;i++){
  scanf("%d",&V[i]);
  }
  
  for(i=0;i<N;i++){
  scanf("%d",&C[i]);
  }
  
  for(i=0;i<N;i++){
  if(V[i]-C[i]>0){
  	max+=V[i]-C[i];
  }
  }
  printf("%d",max);
  return 0;
}

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

int main(){
  vector < pair<int,int> > br;
  int n;
  while(1){
    cin>>n;
    if(n==0) break;
    br.clear();
    for(int i=0;i<n;i++){
      int m,a,b;
      cin>>m>>a>>b;
      br.push_back(make_pair(a,m));
      br.push_back(make_pair(b,(-1)*m));
    }
    sort(br.begin(),br.end());
    bool f=0;
    int brsum=0;
    for(int i=0;i<br.size();i++){
    brsum+=br[i].second;
    if(brsum>150){
      f=1;
      break;
    }
    }
    if(f==0) cout<<"OK"<<endl;
    else cout <<"NG"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
#define long long long
using namespace std;
const int N=1e6;
int aa[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  int x;cin>>x;
  cout<<aa[x-1]<<endl;


  return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        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_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)*}
    };
}

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:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

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

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input!(a: i64, b: i64, c: i64);
    let r = c - a - b;
    if r > 0 && r * r > 4 * a * b {
        puts!("Yes\n");
    } else {
        puts!("No\n");
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
n=int(input())
b=list(map(int, input().split()))
a=[0]*n
a[0]=b[0]
a[n-1]=b[n-2]
for i in range(1,n-1):
	a[i]=min(b[i-1],b[i])
sum=0
for i in range(n):
	sum+=a[i]
print(sum)

Measured memory_bytes: 3064
#include<queue>
#include<cstdio>

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

using namespace std;

struct stat{ int a,b,t; };

int main(){
	int T; scanf("%d",&T);
	while(T--){
		int n; scanf("%d",&n);
		bool adj[50][50];
		rep(u,n) rep(v,n) {
			int b; scanf("%d",&b);
			adj[u][v]=(u==v?true:b);
		}
		int a0,b0; scanf("%d%d",&a0,&b0);

		int ans[50][50][2];
		rep(a,n) rep(b,n) rep(t,2) ans[a][b][t]=-1;
		queue<stat> Q;
		rep(u,n){
			ans[u][u][0]=0;
			Q.push((stat){u,u,0});
		}
		while(!Q.empty()){
			int a=Q.front().a,b=Q.front().b,t=Q.front().t; Q.pop();
			if(t==0){
				rep(u,n) if(adj[u][b]) {
					bool ok=false;
					rep(v,n) if(adj[u][v] && ~ans[a][v][0]){ ok=true; break; }
					if(ok && !~ans[a][u][1]){
						ans[a][u][1]=ans[a][b][t]+1;
						Q.push((stat){a,u,1});
					}
				}
			}
			else{
				rep(u,n) if(adj[u][a]) {
					bool ok=true;
					rep(v,n) if(adj[u][v] && !~ans[v][b][1]){ ok=false; break; }
					if(ok && !~ans[u][b][0]){
						ans[u][b][0]=ans[a][b][t];
						Q.push((stat){u,b,0});
					}
				}
			}
		}

		if(~ans[a0][b0][0]) printf("%d\n",ans[a0][b0][0]);
		else                puts("infinity");
	}

	return 0;
}

Measured memory_bytes: 0
W, H, N = map(int, input().split())

border = [0,W,0,H]

for i in range(N):
  x, y, a = map(int, input().split())
  if a == 1:
    border[a-1] = max(border[a-1], x)
  elif a == 2:
    border[a-1] = min(border[a-1], x)
  elif a == 3:
    border[a-1] = max(border[a-1], y)
  elif a== 4:
    border[a-1] = min(border[a-1], y)
if border[1] - border[0] < 0 and border[3] - border[2] < 0:
  print(0)
  exit()
    
print(max((border[1] - border[0]) * (border[3] - border[2]), 0))

Measured memory_bytes: 38256