akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#define MAXN 100010

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume;
int f[MAXN];

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

void dfs(int x,int p){
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			dfs(e[i].to,x);
			f[x]^=f[e[i].to]+1;
		}
}

int main(){
	memset(g,-1,sizeof g);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
	}
	dfs(1,0);
	if(f[1]) puts("Alice");
	else puts("Bob");
}


Measured memory_bytes: 7168
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
const int N=200005,M=1000005;
int n,tot=1,ch[M][26],siz[M][26];
long long ans=0;
char str[M];
string s[N];
void insert(string str){
	int len=str.length();
	int u=1,sta[26];
	memset(sta,0,sizeof(sta));
	for(int i=0;i<len;i++){
		sta[str[i]-'a']++;
	}
	for(int i=0;i<len;i++){
		for(int j=0;j<26;j++){
			if(sta[j]!=0){
				siz[u][j]++;
			}
		}
		int x=str[i]-'a';
		if(!ch[u][x]){
			ch[u][x]=++tot;
		}
		u=ch[u][x];
		sta[x]--;
	}
}
long long calc(string str){
	int len=str.length();
	int u=1;
	for(int i=0;i<len-1;i++){
		u=ch[u][str[i]-'a'];
	}
	return siz[u][str[len-1]-'a']-1;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		s[i]=str;
		reverse(s[i].begin(),s[i].end());
		insert(s[i]);
	}
	for(int i=1;i<=n;i++){
		ans+=calc(s[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 213264
n = int(input())
s = [input() for _ in range(n)]
a=0
b=0
c=0
d=0
for i in s:
    if i=='AC':
        a+=1
    elif i=='WA':
        b+=1
    elif i=='TLE':
        c+=1
    elif i=='RE':
        d+=1

print('AC x %d'% a)
print('WA x %d'% b)
print('TLE x %d'% c)
print('RE x %d'% d)

Measured memory_bytes: 16252
# abs(Ai - (b - i )) + ... のmin
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(len(A)):
    B.append(A[i] - (i + 1))
B.sort()
#print(B)
if N % 2 == 1:
    b = B[N//2]
else:
    b = (B[N // 2] + B[N // 2 - 1]) // 2
#print(b)
sum_val = 0
for i in range(N):
    sum_val += abs(B[i] - b)
print(sum_val)

Measured memory_bytes: 25196
#include <iostream>
#include <regex>

std::string decrypto(std::string str) {
    using namespace std;
    regex pattern(".*(the|this|that).*");
    smatch sm;
    for (int c = 0; c < 'z' - 'a' + 1; ++c) {
        for (size_t i = 0; i < str.size(); ++i) {
            if ('a' <= str[i] && str[i] <= 'z') {
                if (str[i] == 'z') {
                    str[i] = 'a';
                } else {
                    str[i] += 1;
                }
            }
        }
        //if (regex_match(str, sm, pattern)) {
        if (str.find( "the" ) != string::npos || str.find( "this" ) != string::npos || str.find( "that" ) != string::npos) {
            return str;
        }
    }
    return string("");
}

int main() {
    std::string str;
    while (std::getline(std::cin, str)) {
        std::cout << decrypto(str) << std::endl;
    }
}

Measured memory_bytes: 1236
#include "bits/stdc++.h"
using namespace std;

int main() {
    
    string a, b;
    cin >> a >> b;
    string r = a + b;
    int x = 0;
    for (int i=0; i<r.size(); i++) {
		x = x * 10;
		x += (r[i] - '0');
	}
	for (int i=0; i<1000; i++) {
		if (i * i == x) {
			cout << "Yes" << endl;
			exit(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();
		double M = sc.nextInt();
		double a[] = new double[N];
		int vote = 0;
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
			vote += a[i];
		}
		int count = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] >= (vote / (4 * M))) {
				count++;
			}
		}
		//System.out.println(vote);
		//System.out.println(vote / (4 * M));
		//System.out.println(count);
		if (M <= count) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


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

int n, a[200005];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a+1, a+n+1, greater<int>());
    long long ans = 0;
    for(int i = 2; i <= n; i++)
        ans += 1LL*a[(i+1)/2];
    cout << ans;
}


Measured memory_bytes: 4360
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main(void){
  int N;
  cin >> N;
  int ans = 0;
  do{
    ans++;
  } while (ans*ans <= N);
  if(ans*ans > N){
    ans--;
  }
  cout << ans*ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
if M%2==1:
    print(-1)
    exit()
edges=[]
tree=[]
G=UnionFind(N)
H=[[] for i in range(N)]
T=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1
    if G.same(a,b):
        edges.append((a,b))
        H[a].append(b)
    else:
        tree.append((a,b))
        G.unite(a,b)
        T[a].append(b)
        T[b].append(a)
#print(edges)
#print(tree)
q=deque([0])
reached=[0 for i in range(N)]
search=deque([])
parents=[-1 for i in range(N)]
while(len(q)>0):
    #print(q,reached,search)
    r=q.popleft()
    reached[r]=1
    for p in T[r]:
        if reached[p]==0:
            q.append(p)
            parents[p]=r
            search.appendleft(p)
#print(parents)
for i in range(N-1):
    v=search.popleft()
    p=parents[v]
    if len(H[v])%2==0:
        H[p].append(v)
    else:
        H[v].append(p)
for i in range(N):
    for j in H[i]:
        print(i+1,j+1)


Measured memory_bytes: 125600
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	string s; cin >> s;
	int len = s.length();
	int cnt = 0;
	rep(i, len) {
		if (s[i] == 'p')cnt++;
	}
	cout << len / 2 - cnt << endl;
	return 0;
}

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

int main() {

ll a,b,c,k,ans;
cin>>a>>b>>c>>k;
/*ans=min(a,k);
k-=min(a,k);
k-=min(b,k);
ans-=min(c,k);
cout<<ans<<endl;*/

if(a>=k)
{ans=min(a,k);}
else if(a+b>=k)
{ans=a;}
else{
  ans=a-(k-a-b);
  //cout<<"else"<<endl;
}
cout<<ans<<endl;

return 0;
}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    set<int> st;

    int N; cin>>N;
    REP(i,N){
        int a; cin>>a;
        if(st.count(a)==1)
            st.erase(a);
        else
            st.insert(a);
    }
    cout<<st.size()<<endl;

}


Measured memory_bytes: 4864
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B
// DFS algorithm
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int dfs(vector<vector<int>> &A, vector<bool> &U, vector<int> &R, int c)
{
        if (U[c])
                return -1;
        if (R[c])
                return R[c];
        U[c] = true;
        int m = 0;
        for (auto a: A[c]) {
                int d = dfs(A, U, R, a);
                if (d < 0) {
                        m = -2;
                        break;
                }
                m = max(m, d);
        }
        U[c] = false;
        R[c] = ++m;
        return m;
}

int main(int argc, char **argv)
{
        int V, E;
        cin >> V >> E;
        vector<vector<int>> A(V);
        for (int i = 0; i < E; i++) {
                int s, t;
                cin >> s >> t;
                A[s].push_back(t);
        }
        bool cyc = false;
        vector<bool> U(V);
        vector<int> R(V);
        for (int i = 0; i < V; i++) {
                if (!R[i] && dfs(A, U, R, i) < 0) {
                        cyc = true;
                        break;
                }
        }
        if (cyc) {
                cout << "Found cyclic path" << endl;
                return 0;
        }
        vector<int> P(V);
        iota(P.begin(), P.end(), 0);
        sort(P.begin(), P.end(), [&](int x, int y) { return R[x] > R[y]; });
        for (auto p: P)
                cout << p << endl;
        return 0;
}

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

const int maxn= 1e6 + 100;
int prime[maxn];      //就是个素数表
bool sf[maxn];        //判断这个数是不是素数，sf[i]中的i是从1到maxn的数

void init(){         //核心 欧拉筛代码
    int num=0;        //num 用来记筛到第几个质数
    memset(sf,true,sizeof(sf));
    for(int i=2;i<=maxn;i++){          //外层枚举1~maxn
        if(sf[i]) prime[++num]=i;      //如果是质数就加入素数表
        for(int j=1;j<=num;j++){       //内层枚举num以内的质数
            if(i*prime[j]>maxn) break; //筛完结束
            sf[i*prime[j]]=false;      //筛掉...
            if(i%prime[j]==0) break;   //避免重复筛
        }
    }
    sf[1]=false;
    sf[0]=false;  //1 0 特判 
}

int main() {
	init();
	ll n; cin >> n;
	map<ll, ll> mp;
	for (ll i = 2; i * i <= n; i++) {
		if (!sf[i]) continue;
		while (n % i == 0) {
			mp[i]++;
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
	int ans = 0;
	for (auto i : mp) {
		for (int j = 1; i.second >= j; j++)
			i.second -= j, ++ans;
	}
	cout << ans << "\n";
}

Measured memory_bytes: 4908
## main

n = gets.strip.to_i

sums = Hash.new(0)

n.times do
  name, qty = gets.strip.split(' ')
  qty = qty.to_i

  sums[name] += qty
end

names = sums.keys.sort{|a, b| (c = a.length <=> b.length) != 0 ? c : a <=> b}

for name in names
  puts [name, sums[name]].join(' ')
end

Measured memory_bytes: 6108
from itertools import permutations

n,m = map(int, input().split())
gl = [ [False]*(n+1) for _ in range(n+1) ]
for _ in range(m):
    a,b = map(int, input().split())
    gl[a][b] = True
    gl[b][a] = True


ll = list(range(2,n+1))  # list of elements
perml = list(permutations(ll, n-1))
ans = 0

for perm in perml:
    curr = 1
    for v in perm:
        if gl[curr][v]:
            curr = v
        else:
            break
    else:
        ans += 1

print(ans)

Measured memory_bytes: 67476
#include <bits/stdc++.h>
#define boost ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define M 1000000007
#define eb emplace_back
#define watch(x) cout << (#x) <<" is "<< x <<"\n";


using namespace std;
//const int N = 1e6;

int32_t main(){
  boost;
  int tc = 1; //cin >> tc;
  while(tc--)
  {
    int n; cin >> n;
    int ans = 0;
    for(int i=1; i<=n; i++)
    {
      if(i%3 == 0 || i%5 == 0)
        continue;
      ans += i;
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 3652
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input!{
        a: i32,
        b: i32,
        c: i32,
        k: i32,
    };
    let mut ret:i32 = 0;
    ret += std::cmp::min(k, a);
    ret -= std::cmp::max(0, k - a - b);

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


Measured memory_bytes: 2112
#include <stdio.h>

#define MAX 10

void getNext(char input[]){
    char *tmp;
    int i;
    while(input[1]!='\0'){
        tmp=input;
        for(i=0;*(tmp+1)!='\0';i++){
            input[i]=(((*tmp-'0')+(*(tmp+1)-'0'))%10)+'0';
            tmp++;
        }
        input[i]='\0';
    }
}

int main(void){
    char input[MAX+1];
    while(scanf("%s\n",input)==1){
        getNext(input);
        printf("%s\n",input);
    }
    
    return 0;
}



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

struct UnionFind {
  vector<int> d;
  UnionFind(int n): d(n,-1) {}
  
  //繋がりを見つける
  int find(int x) {
    if (d[x] < 0) return x;
    //d[x]に代入することでメモ化計算スピードを早くする
    return d[x] = find(d[x]);
  }
  
  //グループ化
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    //d[x]はーサイズなのでxが大きくなるようにする
    if (d[x] > d[y]) swap(x,y);
    //大きい方に小さい方をくっつける
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  
  //これはおまけ，これがあると便利
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};
//ここまでUnionFind。あとはブロック関係を考える。
//ブロック関係を考えるときは同じ木の中でブロック関係になっている辺の本数を引けば良い。

int deg[100005];
vector<int> to[100005];

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  //ここから友達関係を処理
  UnionFind uf(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    //辺の数を数える
    deg[a]++;
    deg[b]++;
    //グループ化
    uf.unite(a,b);
  }
  //処理完了
  //ブロック関係の処理
  rep(i,k) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    //ある頂点から出ているブロック関係という形で記述
    to[a].push_back(b);
    to[b].push_back(a);
  }
  rep(i,n) {
    //つながりのある人-自分自身-直接の友達の数
    int ans = uf.size(i)-1-deg[i];
    //ブロック関係にある人数分繰り返す
    for (int u : to[i]) {
      //uがもしiと同じグループならansから引く
      if (uf.same(i,u)) --ans;
    }
    //最後なら改行,それ以外は空白
    printf("%d%c", ans, i==n-1?'\n':' ');
  }
  return 0;
}

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

void Print(int xss[][200], int N) {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      cout << xss[i][j] << ", ";
    }
    cout << endl;
  }
  cout << endl;
}

int main() {
  int N, M, R;
  cin >> N >> M >> R;
  vector<int> r(R);
  for (auto& x : r) {
    cin >> x;
    --x;
  }
  sort(r.begin(), r.end());
  int adj[200][200];
  for (int i = 0; i < 200; ++i) {  // Initializes.
    for (int j = 0; j < 200; ++j) {
      adj[i][j] = -1;
    }
  }
  for (int i = 1; i <= M; ++i) {  // For each edge.
    int A, B, C;
    cin >> A >> B >> C;
    --A;
    --B;
    adj[A][B] = C;
    adj[B][A] = C;
  }
//  Print(adj, N);
  // Floyd-Warshall algorithm.
  for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (adj[i][k] == -1 || adj[k][j] == -1)
          continue;
        int bypassed = adj[i][k] + adj[k][j];
        if (adj[i][j] == -1 || adj[i][j] > bypassed) {
          adj[i][j] = bypassed;
          adj[j][i] = bypassed;
        }
      }
    }
  }
//  Print(adj, N);
  int distance_min = INT_MAX;
  do {
    int distance = 0;
    for (int i = 1; i < r.size(); ++i) {
      int town_left = r[i - 1];
      int town_right = r[i];
      distance += adj[town_left][town_right];
    }
//    for (const auto& x : r) cout << x << ", ";
//    cout << ": " << distance << endl;
    distance_min = min(distance_min, distance);
  } while (next_permutation(r.begin(), r.end()));
  cout << distance_min << endl;
}


Measured memory_bytes: 508
const input = require('fs').readFileSync('/dev/stdin', 'utf8');

const n = Number(input.split('\n')[0]);

const colorArr = input.split('\n')[1].split(' ');

const include = (arr, x) => {
  if (arr.indexOf(x) === -1) {
    return false
  } else {
    return true;
  }
};

if (include(colorArr, 'Y')) {
  console.log('Four');
} else {
  console.log('Three');
}


Measured memory_bytes: 7372
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind
#define rt (a); return (a); 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
int gcd(int a, int b) {
	if (b > a)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
int ans = 0;
int s[10][10];
int k[10];
int p[10];
void bit(int m, int n,int d) {
	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			bool w = true;
			rep(i, 0,d ) {
				int x = 0;
				rep(j, 0, k[i])if (now[s[i][j] - 1] == '1')x++;
				if (x%2 != p[i])w = false;
			}
			if(w)ans += 1;
		}
		else {
			for (int i = m - 1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}
;
int main() {
	int n, l;
	cin >> n>>l;
	int M = 10000;
	int I,sum=0;

	rep(i, 0, n) {
		sum += i + l;
		if (abs(M) > abs(i + l))M = i + l;
	}
	int ans = sum - M;
	cout << ans << endl;
		return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(N, A, B, C):

    ans = 0
    pre = -1000
    for i in range(N):
        a = A[i] - 1
        ans += B[a]

        if pre + 1 == a:
            ans += C[pre]

        pre = a

    return ans


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    print(solve(N, A, B, C))


if __name__ == '__main__':
    main()


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

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) cin >> grid[i];
    
    int ans = (H-1)*(W-1);
    for (int i = 0; i < (1<<(H-1)); i++) {
        vector<int> div(H, 0);
        int t = 0;
        bool able = true;
        for (int j = 1; j <= H-1; j++) {
            if ((i>>(j-1))&1) t++;
            div[j] = t;
        }
        vector<int> w(t+1, 0);
        int cut = __builtin_popcount(i);
        for (int j = 0; j < W; j++) {
            bool check = true;
            for (int k = 0; k < H; k++) {
                if (grid[k][j] == '1') w[div[k]]++;
                if (w[div[k]] > K) {
                    check = false;
                    break;
                }
            }
            if (!check) {
                for (int k = 0; k <= t; k++) w[k] = 0;
                cut++;
                for (int k = 0; k < H; k++) {
                    if (grid[k][j] == '1') w[div[k]]++;
                    if (w[div[k]] > K) {
                        able = false;
                        break;
                    }
                }
            }
            if (!able) break;
        }
        if (able) {
            ans = min(ans, cut);
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main() {

	string s;
	cin >> s;

	vector<int> res(s.size());

	int pp = 0;
	int i = 0;
	while (1) {
		int j = 0;
		if (s[i] == 'R' && s[i + 1] == 'L') {
			int counterr = 0;
			int counterl = 0;
			j = 0;
			while (s[i + j] == 'R') {
				counterr++;
				if (i + j == 0) { break; }
				j--;
			}
			j = 1;
			while (s[i + j] == 'L') {
				counterl++;
				if (i + j == s.size()-1) { break; }
				j++;
			}
			res[i] = (counterr-1) / 2 + counterl / 2 + 1;
			res[i + 1] = (counterr) / 2 + (counterl-1) / 2 + 1;
			i = i + j-1;
		}
		i++;
		if (i > s.size() - 1) { break; }
	}

	for (i = 0; i < s.size(); i++) {
		if (i != 0) {
			cout << " " << res[i];
		}
		else {
			cout << res[i];
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <numeric>
#include <iomanip>
#define ll long long
#define intm INT_MAX
#define llm LLONG_MAX

using namespace std;
typedef pair<int,int> P;
const int MOD = 998244353;
const ll mod = 1e9 + 7;
const int mxN = 2e5 + 9;



int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int a;
	cin >> a;
	cout << a + a*a + a*a*a;



}


Measured memory_bytes: 3572
N, A, B = map(int, input().split())
m = 0
for n in range(1, N + 1):
    C = []
    n1 = n
    for k in range(4, -1, -1):
            C.append(int(n1 / (10 ** k)))
            n1 -= C[4 - k] * (10 ** k)
    if A <= sum(C) <= B:
        m += n
print(m)


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	H,A = inputMap()
 
	ans = -(-H // A)
 
	print(ans)



if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
long long gcd(int a, int b){
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
long long lcm(int a, int b){
  
   return a / gcd(a, b) * b;
}

int main(){
  long long a,b,c,d;
  cin>>a>>b>>c>>d;
  long long i=lcm(c,d);
  cout<<b-(a-1)-(((b/c)-((a-1)/c))+((b/d)-((a-1)/d))-((b/i)-((a-1)/i)))<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    p = 1
    for a in A:
        p *= a

    denom = 0
    for a in A:
        denom += p // a

    print(p / denom)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9084
n, m, c = map(int, input().split())
bs = list(map(int, input().split()))
numbers = []
for i in range(n):
    numbers.append(list(map(int, input().split())))

ans = 0
for nums in numbers:
    s = 0
    for k in range(m):
        s += bs[k] * nums[k]
    if s + c > 0:
        ans += 1

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
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; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int main(){
  int n,k;cin>>n>>k;
  set<int> s;
  rep(i,k){
    int d;cin>>d;
    rep(j,d){int e;
      cin>>e;s.insert(e);
    }
  }
  cout<<n-s.size();
}

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

int main() {
  
  int N; cin >> N; int64_t sum = 0;
  
  vector<int> vec(N * 3);
  
  for (int i = 0; i < N * 3; i++) cin >> vec[i];
  
  sort(vec.begin(), vec.end());
  
  int numCenter = N * 3 - 2; int count = 0;
  
  while (true) {
    
    sum += vec[numCenter];
    
    numCenter -= 2; count++;
    
    if (count == N) break;
    
  }
  
  cout << sum << endl;
  
}

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
#include <iomanip>

using namespace std;


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

    int sum =0;

    for(int i=1;i<N;++i){
        sum += (N-1)/i;
    }

    cout << sum<<endl;


}



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

using namespace std;

class Dijkstra {
  using QItem = pair<int, int>;

 public:
  vector<int> minDistance(vector<array<int, 3>> &edges, int n, int src) {
    vector<int> costs(n, -1);
    costs[src] = 0;

    // 各ノードの隣接ノードとその距離を初期化
    vector<vector<pair<int, int>>> distances(n);
    for (auto &edge : edges) {
      int n1 = edge[0], n2 = edge[1], d = edge[2];
      distances[n1].push_back({n2, d});
      distances[n2].push_back({n1, d});
    }

    vector<bool> used(n, false);
    priority_queue<QItem, vector<QItem>, greater<QItem>> q;
    q.push({0, src});

    while (!q.empty()) {
      // 未確定で，コストの一番低いノードを選択する
      auto [min_cost, min_idx] = q.top();
      q.pop();

      // 選択したノードは確定とする
      used[min_idx] = true;

      // 選択したノードの隣接ノードについて，そのコストを再計算する
      for (auto &p : distances[min_idx]) {
        int new_cost = min_cost + p.second;
        if (costs[p.first] < 0 || costs[p.first] > new_cost) {
          costs[p.first] = new_cost;
          q.push({new_cost, p.first});
        }
      }
    }

    return costs;
  }
};

int main(int argc, const char *argv[]) {
  int h, w, ch, cw, dh, dw;
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--, cw--, dh--, dw--;
  vector<string> maze(h);
  for (int i = 0; i < h; ++i) {
    cin >> maze[i];
  }

  vector<array<int, 3>> edges;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (maze[i][j] == '#') {
        continue;
      }

      int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
      int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
      for (int i2 = min_y; i2 <= max_y; ++i2) {
        for (int j2 = min_x; j2 <= max_x; ++j2) {
          if (i2 == i && j2 == j) {
            continue;
          }

          if (maze[i2][j2] == '#') {
            continue;
          }

          int dist = abs(i2 - i) + abs(j2 - j);
          int cost = dist <= 1 ? 0 : 1;
          // cout << i << ' ' << j << ' ' << i2 << ' ' << j2 << ' ' << cost
          // << '\n';
          edges.push_back({i * w + j, i2 * w + j2, cost});
          edges.push_back({i2 * w + j2, i * w + j, cost});
        }
      }
    }
  }

  Dijkstra d;
  vector<int> min_dists = d.minDistance(edges, h * w, ch * w + cw);
  int ans = min_dists[dh * w + dw];
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 428232
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll a,b;
  	ci(a>>b);
  if(b!=1) co(a-b)
  else co(0)
}


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

typedef long long ll;

const int MV = 52 * 52 * 52;

int N, X, D;
vector<int> adj[52];
ll V[52];
int sz[52];

void dfs(int u) {
    sz[u] = 1;

    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        dfs(v);
        sz[u] += sz[v];
        V[u] += V[v];
    }
}

struct Item {
    ll w;
    int v, d;
    bool operator <(const Item &i) const {
        return v * i.w > i.v * w;
    }
};
Item item[52], A[52], B[52];
ll dp[MV];

int main() {
    scanf("%d %d %d", &N, &X, &D);

    scanf("%lld", &V[0]);
    for(int i = 1; i < N; i++) {
        int p; scanf("%lld %d", &V[i], &p);
        p--;

        adj[p].push_back(i);
    }

    dfs(0);

    for(int i = 0; i < N; i++) {
        item[i] = { V[i], sz[i], i? D : (int)1e9 };
    }
    sort(item, item + N);

    for(int i = 0; i < N; i++) {
        A[i] = { item[i].w, item[i].v, min(50, item[i].d) };
        B[i] = { item[i].w, item[i].v, item[i].d - A[i].d };
    }

    for(int i = 0; i < MV; i++) dp[i] = 1e18;
    dp[0] = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < A[i].d; j++) {
            for(int k = MV - 1; k >= A[i].v; k--) {
                dp[k] = min(dp[k], dp[ k - A[i].v ] + A[i].w);
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < MV; i++) {
        int tmp = i;

        ll Y = X - dp[i];
        if(Y < 0) continue;

        for(int j = 0; j < N; j++) {
            ll d = Y / B[j].w;
            d = min(d, (ll)B[j].d);

            Y -= B[j].w * d;
            tmp += B[j].v * d;
        }
        ans = max(ans, tmp);
    }

    printf("%d", ans);
}


Measured memory_bytes: 1408
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[maxn],dp[maxn];
	for(int i=1;i<=n;++i)
	 cin>>a[i];
	memset(dp,inf,sizeof(dp));
	dp[1]=0;
	for(int i=2;i<=n;++i)
	{
		for(int j=1;j<=k;++j)
		{
			if(i-j<1)
			 break;
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j])); 
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 4308
#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long int
#define boost ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0)
#define vi vector<int>
#define P push_back
#define F first
#define S second
#define debug(x) cout<<x<<" "
#define pi vector<pair<int,int> >
#define FOR(i,x,n) for(int i=x;i<n;i++)
#define all(a) a.begin(),a.end()
ll mod=1e9+7;
#define N 99999999
//#define int ll
using namespace std;
#define int double
signed main(){
    boost;
	int n;
    cin>>n;
    vector<double> a(n);
    int sum=1,sum2=0;
    for(int i=0;i<n;i++)cin>>a[i],a[i]=1/a[i];
    for(int i=0;i<n;i++)sum2+=a[i];
    double ans=(long double)1/sum2;
    printf("%.10F",ans);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a * b == 15) {
		cout << "*" << endl;
	}
	else if (a + b == 15) {
		cout << "+" << endl;
	}
	else {
		cout << "x" << 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;

const int mod = 1e9+7;
const int INF = 2000000;
const double PI = acos(-1.0);

ll cal(int n, int times) {
    ll res = 1;
    for(int i = 0; i < times; ++i) {
        res = (res * n) % mod;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    ll ans = (cal(10, n) - cal(9, n) - cal(9, n) + cal(8, n)) % mod;

    ans = (ans+mod) % mod;
    cout << ans << endl;

}


Measured memory_bytes: 3600
#include <iostream>

using namespace std;

const int MAX_N = 52;
int n, rank;
char suit;
char a[4][13];

char suits[4] = {'S','H','C','D'};



int main(){

    for(int i=0;i<13;i++){
    a[0][i] = 1;
    a[1][i] = 1;
    a[2][i] = 1;
    a[3][i] = 1;
    }  

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> suit >> rank;
        switch(suit){
            case 'S':
                a[0][rank-1] = 0;
                break;
            case 'H':
                a[1][rank-1] = 0;
                break;
            case 'C':
                a[2][rank-1] = 0;
                break;
            case 'D':
                a[3][rank-1] = 0;
                break;
        }
    }

    for(int i=0;i<4;i++){
        for(int j=0;j<13;j++){
            if(!(a[i][j])){continue;}
            cout << suits[i] << " " << j+1 << endl;
        }
    }
   
   return 0;
}


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

typedef long long ll;
typedef long double ld;
// use unique(x) - removec consecutive items, returns vec.begin() + number of items
// for vector: sort(all(vec)); vec.erase(unique(all(vec)), vec.end());
// use iota(all(vec), 0) for filling a vector with 0,1,2...
// use fill(all(vec), 1) for filling a vector with 1,1,1...
// use rotate(vec.begin(), vec.begin() + 1, vec.end()) to rotate a vector | middle arg becomes first
// use merge(all(vec1), all(vec2), vec3.begin()) to merge 2 vectors, use vec3.resize(vec1.size() + vec2.size()) first
// ll pos = partition_point(all(vec), pred) - vec.begin(); bool pred(ll a){return a<3};
// print number in binary -> cout << bitset<20>(n);

int main(){
	int n;cin>>n;
	vector<int>a(n),b(n);
	for(int i=0;i<n;++i)cin>>a[i]>>b[i];
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	if(n%2)cout<<b[n/2]-a[n/2]+1<<endl;
	else cout<<b[n/2-1]+b[n/2]-a[n/2-1]-a[n/2]+1<<endl;
}


Measured memory_bytes: 4852
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
  
using namespace std;

int main()
{
	int n;
	while(1){
		cin >> n;
		if(n == 0) break;
		double x[101], y[101], z[101], r[101];
		for(int i = 0; i < n; i++){
			cin >> x[i] >> y[i] >> z[i] >> r[i];
		}
		double kyori_pow2[101][101];
		bool ischecked[101];
		for(int i = 0; i < n; i++){
			kyori_pow2[i][i] = 0.0;
			ischecked[i] = false;
			for(int j = i + 1; j < n; j++){
				double k = sqrt(pow((x[i] - x[j]), 2) + pow((y[i] - y[j]), 2) + pow((z[i] - z[j]), 2));
				kyori_pow2[i][j] = max(0.0, k - r[i] - r[j]);
				kyori_pow2[j][i] = max(0.0, k - r[i] - r[j]);
			}
		}
		double ans = 0.0;
		for(int i = 0; i < n; i++){
			double mind = 10000000.0;
			int j = -1;
			for(int k = 0; k < n; k++){
				if(ischecked[k]) continue;
				if(kyori_pow2[0][k] < mind){
					mind = kyori_pow2[0][k];
					j = k;
				}
			}
			if(j == -1) break;
			ans += mind;
			for(int k = 0; k < n; k++){
				kyori_pow2[0][k] = min(kyori_pow2[0][k], kyori_pow2[j][k]);
			}
			ischecked[j] = true;
		}
		printf("%.3f\n", ans);
	}
	return 0;
}

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

int comp(const void *a, const void *b)
{
  return *(int*)a - *(int*)b;
}

int main()
{
  int i,n;
  int a[100000];
  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  qsort(a, n, sizeof(int), comp);
  printf("%d\n", a[n/2]-a[n/2-1]);
  return 0;
}

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

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

	int N;
	int i,k;
	int ans=0;
	int ctr=0;

	cin >> N;

	ans=N%1000;
	if(ans)
		cout << 1000-ans << endl;
	else
		cout << 0 << endl;

	return 0;
}



Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <cstring>
#include <stack>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int a[n+5];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int max=-11111;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>max) max=a[i];
	}
	sort(a+1,a+n+1);
	int pos=0;
	int b[100005];
	memset(b,0,sizeof(b)); 
	for(int i=1;i<=n;i++)
	{
		b[a[i]]++; 
	} 
	int imax=0,k=1;
	for(int i=1;i<=100000;i++)
	{
		if(b[i]+b[i-1]+b[i+1]>=imax)
			imax=b[i]+b[i-1]+b[i+1];
		k++;
	}	
	cout<<imax;
	return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

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

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

bool cmp(pii a,pii b){
	return a.S<b.S;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,k; cin>>n>>k;
	vector<int> v(n);
	for(auto &i:v) cin>>i;
	vector<int> inv(n,0),less(n,0);
	For(i,0,n-1){
		For(j,0,n-1){
			if(v[i]>v[j]){
				if(j>i) inv[i]++;
				less[i]++;
			}
		}
	}
	int ans=0;
	For(i,0,n-1){
		ans=(ans+inv[i]*k)%MOD;
		ans=(ans+k*(k-1)/2%MOD*less[i])%MOD;
	}
	cout<<ans<<"\n";
	return 0;
}





























Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

void yes(){
  cout << "YES" << endl;
  exit(0);
}

void no(){
  cout << "NO" << endl;
  exit(0);
}

int main(){
  ll n,a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  REP(k,n){
    ll lb = a+k*c+(n-1-k)*(-d);
    ll ub = a+k*d+(n-1-k)*(-c);
    if(lb<=b && b<=ub) yes();
  }
  no();
}



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

int main(){
  int x,a,b;
  cin>>x>>a>>b;
  cout<<(x-a)%b<<endl;
}

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

signed main(){
	ll A, B, C, K;
	cin >> A >> B >> C >> K;

	ll ans = min(A, K);
	K -= A+B;
	if(0 < K)
		ans -= K;

	cout << ans << endl;

	return 0;	
}

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

int main(){
  int n;
  vector<int> a;
  
  cin >> n;
  for(int i = 0; i< n; i++){
    int v = 0;
    cin >> v;
    a.push_back(v);
  }
  sort(a.begin(), a.end());
  
  int sum = 0;
  int flag = 0;
  for(int i = a.size()-1; i > -1; i--){
    if(flag == 0){
      sum += a[i];
      flag = 1;
    } else {
      sum -= a[i];
      flag = 0;
    }
  }
  
  cout << sum << endl;
  
  return 0;
}
  

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

int main()
{
    int16_t k,a,b;
    bool f = false;
    cin >> k;
    cin >> a >> b;
    for (int i = a; i<=b; i++) {
        if (i%k == 0){
            f = true;
            break;
        }
    }
    if (f){
        cout << "OK" << endl;
    }
    else {
        cout << "NG" << endl;
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int i,j,k;
int N,K;
cin >> N >> K;
int M = min(N,K);
int V[N+2];
vector<int> H;
vector<int> H2;
int count = 0;
int count2;
int ans = 0;
int tmp;
V[0]=0;
V[N+1]=0;
for(i=1;i<N+1;i++)cin >> V[i];
for(i=0;i<M+1;i++){
    count += V[i];
    if(V[i]<0)H.push_back(V[i]);
    count2=count;
    for(k=0;k<(int)H.size();k++)H2.push_back(H.at(k));
    for(j=0;j<M-i+1;j++){
        count2+=V[N-j+1];
        if(V[N-j+1]<0)H2.push_back(V[N-j+1]);
        sort(H2.begin(),H2.end());
        tmp = count2;
        for(k=0;k<min(K-i-j,(int)H2.size());k++)tmp -= H2.at(k);
        if(tmp>ans)ans=tmp;
    }
    H2.clear();
}
cout << ans << endl;
}


Measured memory_bytes: 256
import sys
def input():
	return sys.stdin.readline().strip()

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

A.sort()
B.sort()
C.sort()

B_num = []
a = 0
for i in range(N):
	while a < N and A[a] < B[i]:
		a += 1
	if a == N:
		B_num.append(N)
	else:
		B_num.append(a)

for i in range(1, N):
	B_num[i] += B_num[i - 1]


C_num = []
b = 0
for i in range(N):
	while b < N and B[b] < C[i]:
		b += 1
	if b == N:
		C_num.append(B_num[-1])
	elif b > 0:
		C_num.append(B_num[b - 1])
print(sum(C_num))

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

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

using namespace std;
using ll = long long;

void solve();

int main(void){
    int H, W, D;
    cin >> H >> W >> D;
    pair<int, int> A[H*W + D];
    int acc[H*W + D] = {0};
    pair<int, int> nl = make_pair(-1, -1);
    rep(i, H){
        rep(j, W){
            int temp;
            cin >> temp; temp--;
            A[temp] = make_pair(i, j);
        }
    }

    int HW = H*W;
    for(int i = HW-1; i >= HW-D; i--){
        for(int j = i-D; j >= 0; j-=D){
            acc[j] = acc[j+D] + abs(A[j].first-A[j+D].first) + abs(A[j].second-A[j+D].second);
        }
    }

    int Q;
    cin >> Q;
    rep(i, Q){
        int l, r;
        cin >> l >> r;
        cout << acc[l-1] - acc[r-1] << endl;
    }
    return 0;
}

void solve(){}

Measured memory_bytes: 2560
import sys
import math
sys.setrecursionlimit(10000)

mod = 10**9 + 7

n, k = map(int, input().split())
dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a in dic:
        dic[a] += b
    else:
        dic[a] = b
ls = []
for key in dic.keys():
    ls.append(key)
ls.sort()
for i in range(len(ls)):
    val = dic[ls[i]]
    if val >= k:
        print(ls[i])
        exit(0)
    else:
        k -= val


Measured memory_bytes: 54360
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

ll dp[10101];

int main(){
    rep(i, 10101)dp[i] = INF;
    dp[0] = 0;
    ll H, N;
    cin >> H >> N;
    rep(i, N){
        ll a, b;
        cin >> a >> b;
        rep(j, H){
            ll to = j + a;
            chmin(to, H);
            chmin(dp[to], dp[j] + b);
        }
    }
    cout << dp[H] << endl;
    
    return 0;
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int D = scan.nextInt();
        int p=0;
for(int i=0;i<N;i++){
    int X=scan.nextInt();
    int Y=scan.nextInt();

    if (Math.pow(X,2)+Math.pow(Y,2)<=Math.pow(D,2)){p++;}
}
System.out.println(p);
    }

}



Measured memory_bytes: 48768
line=gets.chomp
a=[]
b=1
c=[]
for l in 0..line.length-1
  c[l]=0
end
for i in 0..line.length-1
  if line[i]==line[i+1] then
    b=b+1
  else
    a.push([line[i],b])
    b=1
  end
end
d=0
for j in a
  if j[0]=="R" then
    c[d+j[1]]=c[d+j[1]]+(j[1].to_f/2).floor
    c[d+j[1]-1]=c[d+j[1]-1]+(j[1].to_f/2).ceil
    d=d+j[1]
  elsif j[0]=="L" then
    c[d]=c[d]+(j[1].to_f/2).ceil
    c[d-1]=c[d-1]+(j[1].to_f/2).floor
    d=d+j[1]
  end
end
puts c.join(" ")

Measured memory_bytes: 16380
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <string>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
  string s;
  int k;
  cin >> k;
  cin >> s;
  if(s.size() <= k){
    cout << s << endl;
  }else{
    cout << s.substr(0,k) << "..." << endl;
  }
} 

Measured memory_bytes: 3620