akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

const int N_MAX = 100000;
int dat[N_MAX * 4];

int n;
int n_add;

void init() {
	int k = 0;
	while ((n - 1) >> k) k++;
	n_add = (1 << k) - 1;
	for (int i = 0; i < n_add * 2; ++i) {
		dat[i] = 0;
	}
}

void add(int x, int y) {
	x += n_add;
	while (x > 0) {
		dat[x] += y;
		x = x / 2;
	}
}

int getSumSub(int x, int y) {
	if (x > y)
		return 0;
	else if (x == y)
		return dat[x];

	bool xodd = x % 2;
	bool yodd = y % 2;
	if (xodd && yodd)
		return dat[x] + getSumSub(x / 2 + 1, y / 2);
	else if (xodd && !yodd)
		return dat[x] + getSumSub(x / 2 + 1, y / 2 - 1) + dat[y];
	else if (!xodd && yodd)
		return getSumSub(x / 2, y / 2);
	else
		return getSumSub(x / 2, y / 2 - 1) + dat[y];
}

int getSum(int x, int y) {
	return getSumSub(x + n_add, y + n_add);
}

int main() {
	int q;
	cin >> n >> q;
	init();
	for (int i = 0; i < q; ++i) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c == 0)
			add(x, y);
		else
			cout << getSum(x, y) << endl;
	}
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int A[5],S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> V;
	FOR(i,5) {
		cin>>A[i];
		S+=A[i]/10*10;
		if(A[i]%10) V.push_back(A[i]%10);
	}
	
	sort(ALL(V));
	if(V.size()) S+=(V.size()-1)*10+V[0];
	cout<<S<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main() {
	string S,T;cin>>S>>T;
	ll count=0,maxM=0;
	
	for(int i=0;i<=S.size()-T.size();i++)
	{  int k=0;
	    for(int j=i;j<i+T.size();j++)
	    {   
	        if(S[j]==T[k++])
	        count++;
	    }
	    maxM=max(maxM,count);
	    count=0;
	}
	//cout<<maxM;
	cout<<T.size()-maxM;
	return 0;
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define LL long long
#define FOR(i,c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++)
#define F first
#define S second
using namespace std;

const LL mod = 1e9 + 7;

template<typename T> T gcd(T a, T b) { return b == 0?a: gcd(b, a % b); }
template<typename T> T LCM(T a, T b) { return a*(b/gcd(a, b)); }
template<typename T, typename S> T expo(T b, S e, const T &m){if(e <= 1)return e == 0?1: b;\
	return (e&1) == 0?expo((b*b)%m, e>>1, m): (b*expo((b*b)%m, e>>1, m))%m;}
template<typename T, typename S> T expo(T b, S e){if(e <= 1)return e == 0?1: b;\
	return (e&1) == 0?expo((b*b), e>>1): (b*expo((b*b), e>>1));}
template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
	os<<"("<<t.first<<", "<<t.second<<")";
	return os;
}
template<class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &t) {
	os<<"["; FOR(it,t) { if(it != t.begin()) os<<", "; os<<*it; } os<<"]";
	return os;
}

const int MAXN = 1e5 + 3;

int arr[MAXN], n;
int cnt[MAXN];

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
    cnt[arr[i]]++;
  }
  int res = 0, tot = 0;
  for(int i = 0; i < MAXN; i++) {
    if(cnt[i] > 0) {
      res++;
      tot += cnt[i] - 1;
    }
  }
  if(tot % 2) res--;
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 1024
import math
# k = int(input())
# s = input()



# if len(s) <= k:
# 	print(s)
# else:
# 	s = s.ljust(k)
# 	print(s + "...")

a, b, h, m = map(int, input().split())

angh = (h*math.pi/6) + (m*math.pi/360)
angm = m*math.pi/30

d = a*a + b*b - 2*a*b*math.cos(angh - angm)
print(math.sqrt(d))

Measured memory_bytes: 9484
D = {"R": 1, "G": 2, "B": 4}
E = {"R": 0, "G": 1, "B": 2}
N = int(input())
T = [E[a] for a in input()]
S = [1 << t for t in T]
s = 0
for i in range(N):
    for j in range(1, min(i+1, N-i)):
        if S[i] + S[i-j] + S[i+j] == 7: s += 1

X = [[0] * N for _ in range(3)]

for i, t in enumerate(T):
    X[t][i] += 1

for i in range(3):
    for j in range(1, N):
        X[i][j] += X[i][j-1]

ans = -s
for i in range(N):
    if T[i] == 0:
        ans += X[1][i] * (X[2][-1] - X[2][i]) + X[2][i] * (X[1][-1] - X[1][i])
    if T[i] == 1:
        ans += X[2][i] * (X[0][-1] - X[0][i]) + X[0][i] * (X[2][-1] - X[2][i])
    if T[i] == 2:
        ans += X[0][i] * (X[1][-1] - X[1][i]) + X[1][i] * (X[0][-1] - X[0][i])
print(ans)


Measured memory_bytes: 74432
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MaxN = 1e6;
int n, m, i, j, t, k, p, q, sum;
char a[4];

int main()
{
	int b[3];
	while(~scanf("%s", a))
	{
		for(i = 0; i < 3; i++)   b[i] = 0;
		for(i = 0; i < 3; i++)
		{
			if(a[i] == 'a')  b[0]++;
			if(a[i] == 'b')  b[1]++;
			if(a[i] == 'c')  b[2]++;
		}
		if(b[0] != 0 && b[1] != 0 && b[2] != 0)   printf("Yes\n");
		else  printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 256
N, P = [int(x) for x in input().split()]
As = [int(x) for x in input().split()]

def combination(n, r):
    ans = 1
    for i in range(n, n - r, -1):
        ans *= i
    for i in range(r):
        ans //= (i + 1)
    return ans
n_e = len(list(filter(lambda x: x % 2 == 0, As)))
n_o = N - n_e

ans = 0
for i in range((1 if P == 1 else 0), n_o + 1, 2):
    ans += int(pow(2, n_e)) * combination(n_o, i)

print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>

typedef struct {
	int tx, ty;
	int time;
	int power;
} MOUSE;

MOUSE queue[40000];
int head, tail;

void push(MOUSE t)
{
	queue[tail % 40000] = t;
	tail++;
}

void pop(MOUSE *t)
{
	*t = queue[head % 40000];
	head++;
}
char v[1000][1001];
int main(void)
{
	MOUSE start, temp;
	char city[1000][1001];
	
	int x, y;
	int sx, sy;
	int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
	int i, j;
	int cheese;
	
	scanf("%d%d%d", &y, &x, &cheese);
	
	getchar();
	for (i = 0; i < y; i++){
		for (j = 0; j < x; j++){
			scanf("%c", &city[i][j]);
			if (city[i][j] == 'S'){
				start.tx = j;
				start.ty = i;
			}
		}
		getchar();
	}
	
	memset(v, -1, sizeof(v));
	
	v[start.ty][start.tx] = 1;
	start.time = 0;
	start.power = 1;
	head = tail = 0;
	push(start);
	while (1){
		pop(&temp);
		
		if (temp.power > cheese){
			break;
		}
		
		for (i = 0; i < 4; i++){
			if (0 <= temp.tx + dx[i] && temp.tx + dx[i] < x && 0 <= temp.ty + dy[i] && temp.ty + dy[i] < y && city[temp.ty + dy[i]][temp.tx + dx[i]] != 'X' && v[temp.ty + dy[i]][temp.tx + dx[i]] == -1){
				start = temp;
				start.tx = temp.tx + dx[i];
				start.ty = temp.ty + dy[i];
				start.time = temp.time + 1;
				v[start.ty][start.tx] = 1;
				if ('0' <= city[start.ty][start.tx] && city[start.ty][start.tx] <= '9' && start.power >= city[start.ty][start.tx] - '0'){
					start.power++;
					city[start.ty][start.tx] = '.';
					head = tail = 0;
					memset(queue, 0, sizeof(queue));
					push(start);
					memset(v, -1, sizeof(v));
					break;
				}
				push(start);
			}
		}
	}
	
	printf("%d\n", temp.time);
	
	return (0);
}

Measured memory_bytes: 2956
import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int x_start=0,x_end=w,y_start=0,y_end=h;

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            if(a==1){
                x_start=Math.max(x,x_start);
            }
            else if(a==2){
                x_end=Math.min(x,x_end);
            }
            else if(a==3){
                y_start=Math.max(y,y_start);
            }
            else if(a==4){
                y_end=Math.min(y,y_end);
            }
        }
        if (x_end<=x_start || y_end<=y_start) {
            System.out.println(0);
        }
        else
            System.out.println((x_end-x_start)*(y_end-y_start));

    }
}


Measured memory_bytes: 22996
(defun waru (n i)
  (if (= 0 (mod n i))
      (- (/ n i) 1)
      (floor (/ n i))))

(defun solve (n)
  (let ((cnt 0))
    (dotimes (i (- n 1))
      (setf cnt (+ cnt (waru n (+ i 1)))))
    (format t "~a" cnt)))

(let ((n (read)))
  (solve n))


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

double blend(double a, double b) {
	return (a + b) / 2;
}

int main() {
	int N = 0;
	double v[50] = { 0 };
	double ans = 0;
	double V[50] = { 0 };
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	sort(v, v + N,greater<double>());

	for (int i = 0; i < N - 2; i++) {
		v[N-i-2] = blend(v[N - i - 1], v[N - i - 2]);

	}

	ans = blend(v[0], v[1]);
	cout << ans;
}

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

int num[10];
bool flag;

void rec(int time){
  if(time==4){
    for(int i=1;i<10;i++){
      if(num[i] == 2){
	flag = true;
	return;
      }
    }
  }
  if(flag)return;

  for(int i=1;i<10;i++){
    if(num[i]>2){
      num[i] -=3;
      rec(time+1);
      num[i] += 3;
    }
  }
  
  for(int i=1;i<8;i++){
    if(num[i] && num[i+1] && num[i+2]){
      num[i]--;
      num[i+1]--;
      num[i+2]--;
      rec(time+1);
      num[i]++;
      num[i+1]++;
      num[i+2]++;
    }
  }
  
  return;
}
int main(){
  string s;

  while(cin >> s){
    for(int i=1;i<10;i++)num[i] = 0;
    for(int i=0;i<(int)s.size();i++)num[s[i]-'0']++;
  
    vector<int> ans;
    for(int i=1;i<10;i++){
      if(num[i]<4){
	num[i]++;
	flag = false;
	rec(0);
	if(flag)ans.push_back(i);
	num[i]--;
      }
    }

    if(ans.empty())cout << 0 << endl;
    else{
      for(int i=0;i<(int)ans.size()-1;i++)cout << ans[i] << " ";
      cout << ans[(int)ans.size()-1] << endl;
    }
  }
}

Measured memory_bytes: 0
import bisect
n, m = (int(i) for i in input().split())
yl = [[] for _ in range(n)]
dl = []

for _ in range(m):
    p, y = (int(i) for i in input().split())
    yl[p-1].append(y)
    dl.append((p, y))

[yl[i].sort() for i in range(n)]

for p, y in dl:
    print("{:0>6}{:0>6}".format(p, bisect.bisect_left(yl[p-1], y)+1))

Measured memory_bytes: 29684
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  vector<string> C(2);
  cin >> C[0] >> C[1];
  reverse(C[1].begin(), C[1].end());
  if (C[0] == C[1])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int counter = 0;
  int flag = 1;
  while (1) {
    for (int i = 0; i < n; i++) {
      if (a[i] % 2 == 0) a[i] /= 2;
      else {
        flag = 0;
        break;
      }
    }
    if (flag == 1) counter++;
    else break;
  }
  cout << counter << endl;
}

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

using namespace std;

int main(){
    int N, K;
    string S;
    cin >> N >> S >> K;

    char target = S[K-1];
    for(int i = 0; i < N; i++){
        if(S[i] != target){
            S[i] = '*';
        }
    }
    cout << S << endl;

    return 0;
}

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

int main() {
    string S; cin >> S;
    int ans = 0;
    for (int i = 1; i < S.length(); i++){
        if (S[i] != S[i-1]) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
    int a,b,c,d;
    cin >> a>>b>>c>>d;
    if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)){
        cout << "Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

class Main{
    private static final Scanner sc = new Scanner(System.in);
    public static void main(String[] Args) throws IOException{
        final dice d1 = new dice();
        for(int i = 0; i<6; i++)
            d1.face[i] = Integer.parseInt(sc.next());
        final dice d2 = new dice();
        for(int i = 0; i<6; i++)
            d2.face[i] = Integer.parseInt(sc.next());
        if(d1.isSame(d2)) System.out.println("Yes");
        else System.out.println("No");
    }
}

class dice{
    public int face[] = new int[6];
    private static final String dir = "EEENWWWSEEENWWWSEEENWWWS";
    public void rotate(char dir){
        int temp;
        switch(dir){
        case 'N':
            temp = face[0];
            face[0] = face[1];
            face[1] = face[5];
            face[5] = face[4];
            face[4] = temp;
            break;
        case 'E':
            temp = face[0];
            face[0] = face[3];
            face[3] = face[5];
            face[5] = face[2];
            face[2] = temp;
            break;
        case 'W':
            temp = face[0];
            face[0] = face[2];
            face[2] = face[5];
            face[5] = face[3];
            face[3] = temp;
            break;
        case 'S':
            temp = face[0];
            face[0] = face[4];
            face[4] = face[5];
            face[5] = face[1];
            face[1] = temp;
            break;
        }
    }
    public boolean equals(dice d){
        for(int i = 0; i<6; i++){
            if(face[i]!=d.face[i]) return false;
        }
        return true;
    }
    public boolean isSame(dice d){
        for(int i = 0; i<24; i++){
            if(this.equals(d)) return true;
            d.rotate(dir.charAt(i));
        }
        return false;
    }
};

Measured memory_bytes: 26312
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long Int;
string str;
char b(char x){
	if(x == 'A')return 'z';
	if(x == 'a')return 'Z';
	return x - 1;
}

int main(){
	int a[1080], n;
	while(cin >> n, n){
		for(int i = 0;i < n;i++)cin >> a[i];
		cin >> str;
		for(int i = 0;i < str.size();i++){
			int c = str[i];
			for(int j = 0;j < a[i % n];j++)c = b(c);
			cout <<(char)c;
		}cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>
#include <string>
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    // 入力
    int N;
    cin>>N;
    int H;
    cin>>H;
    int a[N],b[N];
    long sword_sum=0;
    int a_max=-1;
    int max_turn=-1;
    int throw_turn=0;
    for(int i=0;i<N;i++){
    	cin>>a[i];
    	if(a[i]>a_max) a_max=a[i];
    	cin>>b[i];
    	//sword_sum+=b[i];
    }
    for(int i=0;i<N;i++){
    	if(b[i]<a_max) {					//なぜか<=ではうまくいかない
    		//cout<<"removed"<<b[i]<<endl;
    		b[i]=0;
    	} else {
    		sword_sum+=b[i];
    		throw_turn++;
    	}
    }
 
	//cout<<throw_turn<<endl;
	//cout<<sword_sum<<endl;
    long sword_sum_temp=sword_sum;
    if(sword_sum>=H){
    	sort(b,b+N);
    	max_turn=N;
    	for(int i=0;i<N;i++){
    		sword_sum_temp-=b[i];
    		//cout<<b[i]<<endl;
    		if(sword_sum_temp<H) break;
    		else max_turn--;
    	}
    }
    else{
    	//cout<<"cannot kill with only throwing"<<endl;
    	max_turn=throw_turn+(H-sword_sum+a_max-1)/a_max;
    }
    cout<<max_turn<<endl;
 
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    long long ans = 0;
    int N,M;
    cin >> N >> M;
    
    int dist[100][100];
    vector< pair< pair<int,int>, int > > edge;
    
    for ( int i = 0; i < 100; i++ ) {
    for ( int j = 0; j < 100; j++ ) {
        dist[i][j] = INT_MAX / 2;
        if ( i == j ) { dist[i][j] = 0; }
    }
    }
    
    
    for ( int i = 0; i < M; i++ ) {
        int a,b,c;
        cin >> a >> b >> c;
        
        a--;
        b--;
        
        dist[a][b] = c;
        dist[b][a] = c;
        
        edge.push_back( make_pair( make_pair(a,b), c ) );
    }
    
    for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < N; j++ ) {
    for ( int k = 0; k < N; k++ ) {
        dist[j][k] = min( dist[j][k], dist[j][i] + dist[i][k] );
    }
    }
    }
    
    for ( auto& e : edge ) {
        int a = e.first.first;
        int b = e.first.second;
        int c = e.second;
        
        bool is_shortest = false;
        for ( int i = 0; i < N; i++ ) {
            for ( int j = 0; j < N; j++ ) {
                if ( dist[i][j] == dist[i][a] + dist[b][j] + c ) {
                    is_shortest = true; break;
                }
            }
            if ( is_shortest ) { break; }
        }
        
        if ( !is_shortest ) { ans++; }
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
N,A,B=map(int,input().split())
goods=[int(i) for i in input().split()]
dp=[[[0,0] for i in range(N+1)] for i in range(N)]
for i in range(N):
  for j in range(i+2):
    if i==0 and j==1:
      dp[0][1]=[goods[i],1]
    elif j==0:
      dp[i][0]=[0,1]
    else:
      if dp[i-1][j][0]<dp[i-1][j-1][0]+goods[i]:
        dp[i][j][0]=dp[i-1][j-1][0]+goods[i]
        dp[i][j][1]=dp[i-1][j-1][1]
      elif dp[i-1][j][0]>dp[i-1][j-1][0]+goods[i]:
        dp[i][j][0]=dp[i-1][j][0]
        dp[i][j][1]=dp[i-1][j][1]
      else:
        dp[i][j][0]=dp[i-1][j-1][0]+goods[i]
        dp[i][j][1]=dp[i-1][j-1][1]+dp[i-1][j][1]
                           
ans1,ans2=0,0
for i in range(A,B+1):
  if ans1<dp[N-1][i][0]/i:
    ans1=dp[N-1][i][0]/i
    ans2=dp[N-1][i][1]
  elif ans1==dp[N-1][i][0]/i:
    ans2+=dp[N-1][i][1]
print(ans1)
print(ans2)
   
      
    

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

#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;


int main()
{
    ll n, m;
    ll tmp;
    cin >> n >> m;
    priority_queue<ll> q;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        q.push(tmp);
    }

    for (int i = 0; i < m; i++) {
        tmp = q.top();
        q.pop();
        q.push(tmp/2);
    }
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += q.top();
        q.pop();
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1400
# E - Gluttony

import numpy as np

N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted((list(map(int, input().split()))), reverse = True))

lower = 0
upper = A[-1] * F[0]

# 達成可能な最高成績を二分探索する
while lower <= upper:
    result = (lower + upper) // 2
    # resultを達成可能なAと実際のAの差異の総和が必要な修行コスト
    # np.arrayの和を求める場合、sum(array)よりarray.sum()の方が速い(使わないとTLE)
    if np.clip(A - result//F, 0, None).sum() <= K:
        ans = result
        upper = result - 1
    else:
        lower = result + 1

print(ans)

Measured memory_bytes: 37276
#include<bits/stdc++.h>
#define test int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define sz 100000
typedef long long ll;
using namespace std;


int main()
{
ll n,k,c=0; cin>>n>>k;
double x,y,p,q;
while(n--)
{
    cin>>x>>y;
    p=sqrt(pow(x,2)+pow(y,2));
    //cout<<p<<endl;
    if(p<=k)
    {
       c++;
    }
}
cout<<c<<endl;
}


Measured memory_bytes: 3748
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の標準入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		Integer nArray[] = new Integer[n];
		int mArray[] = new int[m];
		// nの値だけ整数の標準入力
		for(int i = 0; i < n; i++) {
			nArray[i] = sc.nextInt();
		}
		// mの値だけ整数の標準入力
		for(int j = 0; j < m; j++) {
			mArray[j] = sc.nextInt();
		}
		// ソート
		Arrays.sort(nArray, Collections.reverseOrder());
		Arrays.sort(mArray);
		// 条件一致の時"No War"を出力
		if(x < mArray[0] && mArray[0] <= y && nArray[0] < mArray[0]) {
			System.out.println("No War");
		} else {
			System.out.println("War");
		}
		sc.close();
	}
}


Measured memory_bytes: 25044
#include <iostream>

using namespace std;

typedef long long ll;

int C[501];
int S[501];
int F[501];


int main()
{
    int N;
    cin >> N;
    for (int i = 1; i < N; ++i)
    {
        cin >> C[i] >> S[i] >> F[i];
    }

    for (int i = 1; i < N; ++i)
    {
        int t = S[i] + C[i];
        for (int j = i+1; j < N; ++j)
        {
            if (t > S[j])
            {
                int tmp = (t - S[j]) % F[j];
                t += tmp == 0 ? 0 : F[j] - tmp;
            }
            else
            {
                t = S[j];
            }
            t += C[j];
        }
        cout << t << endl;
    }
    cout << 0 << endl;

    return 0;
}

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

using namespace std;
int NAX=3001;
#define ll long long

int main(){
	ll n;
	scanf("%lld",&n);
	vector<ll> arr(n);
	for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
	vector<vector<ll> > dp(NAX,vector<ll>(NAX));
	
	for(int i=n-1;i>=0;i--){
		for(int j=i;j<n;j++){
			if(i==j)
				dp[i][j]=arr[i];
			else
				dp[i][j]=max(arr[i]-dp[i+1][j],arr[j]-dp[i][j-1]);
		}
	}
	printf("%lld",dp[0][n-1]);
	
}


Measured memory_bytes: 70784
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#pragma region macro
#include <bits/stdc++.h>
typedef long long int64;
using namespace std;
using P = pair<int64, int64>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
#define bn '\n'
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " , ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
#pragma endregion
//fixed<<setprecision(10)<<ans<<endl;

int N;
map<pair<int,int>,int> color;
vector<vector<int>> edge;
int color_num = 0;
void dfs(int v,int pre_col,int pre_node){
    int col = 1;
    for(auto to:edge[v]){
        if(to==pre_node) continue;
        int from = v;
        if (from > to) swap(from,to);
        if(col==pre_col) col++;
        color[mp(from,to)]=col;
        chmax(color_num, col);
        dfs(to,col,from);
        col++;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    edge.resize(N);
    int a,b;
    vector<pair<int,int>> memo;
    REP(i,N-1){
        cin >> a >> b;
        if(a>b) swap(a,b);
        edge[--a].emplace_back(--b);
        edge[b].emplace_back(a);
        memo.emplace_back(a,b);
    }

    dfs(0,0,-1);
    cout << color_num << bn;
    REP(i,N-1) cout << color[memo[i]] << bn;
}

Measured memory_bytes: 13180
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n=int(input())
l=[*map(int,input().split())]
g=0
from math import *
for x in l:
  g=gcd(g,x)
if g>1: f(2)
def sieve(x):
  p=[]
  s=[0]*x
  for i in range(2,x):
    if s[i]<1:
      p+=[i]
      for j in range(i,x,i): s[j]=i
  return s
s=sieve(M)
C=[0]*M
for x in l:
  t=set()
  while x>1:
    t.add(s[x])
    x//=s[x]
  for y in t:
    if C[y]: f(1)
    C[y]=1
f(0)

Measured memory_bytes: 189160
/* ex6_2
   cy_an  */

#include <stdio.h>
#include <string.h>

int main(void){

    // 変数宣言
    int length;
    char word[102];
    // wordの入力
    fgets(word, 102, stdin);
    // wordの長さの取得
    length = strlen(word);

    // 表示
    printf("%c%d%c\n", word[0], length-3, word[length-2]);

    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		long h = sc.nextLong();
		long count = 0;
		long num = 1;

		while(h >= 1) {
			h = h / 2;
			count += num;
			num *= 2;
		}

		System.out.println(count);

	}

}


Measured memory_bytes: 35656
h,w=map(int,input().split())
s = [["."for i in range(w+2)]]
for i in range(h):s.append(["."]+list(input())+["."])
s.append(["."]*(w+2))
l=[]
for i in range(1,h+1):
 l2=[]
 for j in range(1,w+1):
  if s[i][j]=="#":l2.append("#")
  else:l2.append(str([s[i+1][j],s[i+1][j+1],s[i+1][j-1],s[i][j+1],s[i][j-1],s[i-1][j-1],s[i-1][j],s[i-1][j+1]].count("#")))
 l.append("".join(l2))
print(*l,sep="\n")

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

using namespace std;

const int MAX_N = 1000000, INDEX = 1;
const long long MOD = 1000000007;

long long n, dp[MAX_N + INDEX], ps[MAX_N + INDEX];

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

    cin >> n;

    dp[0] = 1, dp[1] = n;
    ps[0] = 0, ps[1] = n;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + ps[max(0, i - 3)] + n * (n - 1) - max(0, i - 3);

        dp[i] %= MOD;

        ps[i] = ps[i - 1] + dp[i];

        ps[i] %= MOD;
    }

    cout << dp[n] << endl;

    return 0;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
//M:Candies

using namespace::std;

const int MAXN = 1e2 + 1,MAXK = 1e5 + 1,MOD = 1e9 + 7;
int DP[MAXN][MAXK];

void sum(int &a,int b){
	a += b;
	if(a >= MOD)
		a -= MOD;
	else if(a < 0)
		a += MOD;
}

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

	int N,K;
	cin >> N >> K;

	DP[0][0] = 1;
	for(int i = 1;i <= N;i++){
		int ai;
		cin >> ai;

		for(int j = 1;j <= K;j++)
			sum(DP[i - 1][j],DP[i - 1][j - 1]);

		for(int j = 0;j <= K;j++)
			sum(DP[i][j],DP[i - 1][j] - (j <= ai ? 0 : DP[i - 1][j - ai - 1]));
	}
	
	cout << DP[N][K] << '\n';

	return 0;
}


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

int main(){
  int A, B;
  cin >> A >> B;
  if(A==1) A=14;
  if(B==1) B=14;
  if(A<B){
    cout << "Bob" << endl;
    return 0;
  }else if(A>B){
    cout << "Alice" << endl;
    return 0;
  }
  cout << "Draw" << endl;
  return 0;
}

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

#define P 0
#define N 1

int main(void) {
	int n, k; cin >> n >> k;
	vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i];
	
	vector<int> dp(k+1, -1);
	for (int i = 0; i < a[0]; i++) {
		dp[i] = P;
	}
	
	for (int i = a[0]; i <= k; i++) {
		for (int j = 0; j < n; j++) {
			if (i < a[j]) break;
			if (dp[i-a[j]] == P) dp[i] = N;
		}
		if (dp[i] == -1) dp[i] = P;
	}	
	//for (int i = 0; i <= k; i++) cout << dp[i] << " "; cout << endl;
	cout << (dp[k] == N ? "First" : "Second");
	
	return 0;
}

Measured memory_bytes: 768
function Main(input){
  var inp= input.split("\n");
  var cnt = 0;
  var j;
  var text= [];
  var N = parseInt(inp[0]);

  var i;
  for(i=1;i<=N;i++){
    text.push(parseInt(inp[i]));

  }
 for (i = 0;i<N;i++){
   var flag = 1;
   for(j=i+1;j<=N;j++){
     if(text[i]==text[j]){flag=0;}
   }
     if(flag==1){cnt++;}  
 }
  console.log('%d',cnt);
}
  Main(require("fs").readFileSync("/dev/stdin","utf8"));
  

Measured memory_bytes: 7372
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <bitset>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < (n); i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  vector<pair<long, long>> LR(N);
  vector<long> L;
  vector<long> R;

  long max_prob = 0;
  rep (i, N) {
    long l, r;
    cin >> l >> r;
    max_prob = max(max_prob, r - l + 1);
    LR[i] = make_pair(l, r);
    L.push_back(l);
    R.push_back(r);
  }
  sort(LR.begin(), LR.end());

  {
    // 1問とその他に分けるケースのカバー
    sort(L.begin(), L.end());
    reverse(L.begin(), L.end());
    sort(R.begin(), R.end());
    for (auto it: LR) {
      long f_L = it.first;
      long f_R = it.second;
      long f_score = f_R - f_L + 1;
      long s_L = L[0];
      long s_R = R[0];
      if (s_L == f_L) s_L = L[1];
      if (s_R == f_R) s_R = R[1];
      long s_score = s_R - s_L + 1;
      max_prob = max(max_prob, f_score + s_score);
    }
  }

  // for (auto it: LR) cout << it.first << ", " << it.second << endl;

  vector<long> minRmemo(N);
  vector<long> minRmemoRev(N);
  minRmemo[0] = LR[0].second;
  for (long i = 1; i < N; i++) {
    minRmemo[i] = min(minRmemo[i-1], LR[i].second);
  }
  minRmemoRev[N-1] = LR[N-1].second;
  for (long i = N - 2; i >= 0; i--) {
    minRmemoRev[i] = min(minRmemoRev[i+1], LR[i].second);
  }

  long split_ans = 0;
  for (long i = 0; i < N - 1; i++) {
    long foo = minRmemo[i] - LR[i].first + 1;
    if (foo < 0) foo = 0;

    long bar = minRmemoRev[i+1] - LR[N-1].first + 1;
    if (bar < 0) bar = 0;

    split_ans = max(split_ans, foo + bar);
  }

  long ans = max(max_prob, split_ans);
  // cout << "max_prob: " << max_prob << ", split_ans: " << split_ans << endl;
  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 5228
S1 = input()
S2 = input()
R = len(S1)
C = len(S2)
dp = [[0]*(C+1) for i in range(R+1)]
for i in range(R+1):
    dp[i][0] = i
for j in range(C+1):
    dp[0][j] = j

for i in range(1,R+1):
    for j in range(1,C+1):
        if S1[i-1] == S2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)

print(dp[-1][-1])


Measured memory_bytes: 41948
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n;
vector< vector<int> > graphlist(200200, vector<int>());

int main() {
    cin >> n;
    for(int i = 0; i < n-1; ++i) {
        int a;
        cin >> a; a--;
        graphlist.at(a).push_back(i);
    }

    for(int i = 0; i < n; ++i) {
        cout << graphlist.at(i).size() << endl;
    }
}

Measured memory_bytes: 14256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

int N;

int main(void) {
    int R,G,B;
    Int sum = 0;

    cin>>R>>G>>B>>N;

    for(int r = 0;r*R <= N;r++) {
        for(int g = 0;g*G <= N;g++) {
            if(r*R+g*G > N)
                break;
            int b = (N-r*R-g*G)/B;
            if(r*R+g*G+b*B == N) {
                sum++;
            }
        }
    }

    cout<<sum<<endl;

    return 0;
}




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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;

const ll INF=1LL<<60;
const int MOD=1e9+7;
const int N=2e5+5;


int main(){
    int A, B; cin >> A >> B;
    int g=__gcd(A, B);
    ll res=(ll)A*B/g;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b; cin >> a >> b;
  string s; cin >> s;
  bool ok = true;
  rep(i, s.size()) {
    if(i == a && s[i] != '-')  ok = false;
    else if(i != a && s[i] == '-') ok = false;
  }
  cout << (ok ? "Yes" : "No") << endk;
  return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 2000 + 100;
const int INF = 0x1f1f1f1f;

int n, ans;
char a[MAXN], b[MAXN];
int l[MAXN], r[MAXN];

bool check()
{
	for(int i = 0; i < n; i++)
		if(b[i] == '1')
			return true;
	for(int i = 0; i < n; i++)
		if(a[i] == '1')
			return false;
	return true;
}

void init()
{
	int last = -1;
	for(int i = 0; i < n; i++)
		last = (b[i] == '1' ? i : last);
	for(int i = 0; i < n; i++)
		last = (b[i] == '1' ? i : last), l[i] = (i - last + n) % n;
	last = -1;
	for(int i = n - 1; i >= 0; i--)
		last = (b[i] == '1' ? i : last);
	for(int i = n - 1; i >= 0; i--)
		last = (b[i] == '1' ? i : last), r[i] = (last - i + n) % n;
}

typedef pair<int, int> pii;

void work()
{
	init();
	for(int d = 0; d <= n - 1; d++)
	{
		static pii vec[MAXN];
		static int lef[MAXN], rig[MAXN];
		int tot = 0;
		for(int i = 0; i < n; i++)
			if(a[i] != b[(i + d) % n] && !(r[i] <= d))
				vec[++tot] = make_pair(l[i], r[(i + d) % n]);
		sort(vec + 1, vec + tot + 1);
		lef[0] = 0;
		for(int i = 1; i <= tot; i++)
			lef[i] = max(lef[i - 1], vec[i].first);
		rig[tot + 1] = 0;
		for(int i = tot; i >= 1; i--)
			rig[i] = max(rig[i + 1], vec[i].second);
		int tmp = INF;
		for(int i = 0; i <= tot; i++)
			tmp = min(tmp, 2 * lef[i] + d + 2 * rig[i + 1]);
		for(int i = 0; i < n; i++)
			tmp += (a[i] != b[(i + d) % n]);
		ans = min(ans, tmp);
		// cerr << d << ' ' << tmp << ' ' << tot << endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> a;
	cin >> b;
	n = strlen(a);

	if(!check())
	{
		cout << -1 << endl;
		return 0;
	}

	ans = INF;
	work();
	reverse(a, a + n);
	reverse(b, b + n);
	work();

	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
//pbds
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>   using orderedSet =tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
//#define fisier 1
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
//BFS+DFS
#define boundary(i,j) (i>=0 && i<n && j>=0 && j<m)
int X[]={-1,1,0,0};
int Y[]={0,0,1,-1};

int main()
{
    int x,y;
    cin>>x>>y;
    if(y%2)
    {
        cout<<"No"<<endl;
        return 0;
    }
    int lo=(y/4)+(y%4)/2;
    int hi=y/2;
   // cout<<lo<<" "<<hi<<endl;
    if(x>=lo && x<=hi) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); ++i)
#define repf(i, from, to) for (int i = (from); i < (to); ++i)
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

// 爆弾マスは-1
// 空きマスは0

int main() {
  int h, w;
  cin >> h >> w;
  V<string> board(h, "");
  rep(i, h) {
    cin >> board[i];
  }

  rep(hi, h) {
    rep(wi, w) {
      if(board[hi][wi] == '#') {
        continue;
      }

      int bomb_count = 0;
      repf(hj, hi - 1, hi + 2){
        repf(wj, wi - 1, wi + 2) {
          if(hj >= 0 && hj < h && wj >= 0  && wj < w) {
            if(board[hj][wj] == '#') {
              bomb_count++;
            }
          }
        }
      }
      board[hi][wi] = '0' + bomb_count;
    }
  }

  rep(hi, h) {
    cout << board[hi] << endl;
  }
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,x,y;
    cin>>n>>x>>y;
    ll c[n];
    rep(0,i,n){
        c[i]=0;
    }
    rep(1,i,n+1){
        rep(i+1,j,n+1){
            ++c[min(j-i,abs(j-y)+abs(i-x)+1)];
        }
    }
    rep(1,i,n){
        cout<<c[i]<<endl;
    }
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
s = 0

for i in a:
    s += i
    s %= mod

s = (s * s) % mod
for i in a:
    s -= i*i
    s %= mod

s = s*(5*(10**8)+4)

print(s%mod)

Measured memory_bytes: 105204
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll a,b;
    cin>>a>>b;
    if((max(a,b)-min(a,b))%2==0)
    cout<<min(a,b)+((max(a,b)-min(a,b))/2)<<endl;
   else
    cout<<"IMPOSSIBLE"<<endl;
    return 0;
}





Measured memory_bytes: 3604
#include "bits/stdc++.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

bool isp(int n){
    if(n==2)return true;
    if(n==1)return false;
    if(n==0)return false;

    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return false;
    }
    return true;
}

int main(){
    int n,x;
    while(cin>>n>>x){
        if(n==0&&x==0)break;
        
        int data[40];
        rep(i,n){
            cin>>data[i];
        }
        
        bool dp[1000001]={};
        rep(i,1000001)dp[i]=false;
        
        dp[0]=true;
        

        for(int i=1;i<=n;i++){
            for(int j=0;j<=x;j++){
//                dp[i][j] = dp[i-1][j];
                if(j-data[i-1]>=0)
                    dp[j] |= dp[j-data[i-1]];

            }
        }
        int ans = -1;
        for(int i=x;i>=0;i--){
            if(dp[i]==true){
                if(isp(i)){
                    ans=i;
                    break;
                }
            }
        }
        if(ans==-1)cout<<"NA"<<endl;
        else cout<<ans<<endl;
        
    }
}

Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
    ll H, W;
    cin >> H >> W;
    ll ans;
    if (H == 1 or W == 1)
    {
        ans = 1;
    }
    else
    {
        ans = (H * W + 1) / 2;
    }
    OUT(ans);
}

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

int main(){
	int n;
	cin >> n;
	
	int p[60]={0};
	for(int i=0; i<n; i++) cin >> p[i];
	
	int a[60]={0};
	for(int i=0; i<n; i++) a[i]=i+1;
	
	int ans=0;
	for(int i=0; i<n; i++){
    if(p[i]!=a[i]) ans++;
	}
	
	if(ans<=2) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

#define rep(i,x) for(int i = 0; i < (int)(x); i++)
#define reps(i,x) for(int i = 1; i <= (int)(x); i++)
#define rrep(i,x) for(int i = ((int)(x) - 1); i >= 0; i--)
#define rreps(i,x) for(int i = ((int)(x)); i > 0; i--)

#define all(x) (x).begin(), (x).end()

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

int gcd(int a, int b){return b?gcd(b,a%b):a;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

using ll = long long;




int main(){
    int N, M;
    cin >> N >> M;
    vector<int> broken(N+1);
    rep(i,M){
        int a;
        cin >> a;
        broken[a] = 1;
    }

    vector<int> dp(N+2);
    dp[N] = 1;
    const int mod = 1e9 + 7;

    rrep(i,N){
        if(broken[i]){
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i+1] + dp[i+2]) % mod;
    }

    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 1024
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

vector<pair<PII, int>> go(int L, int k)
{
	if (L < k)
	{
		vector<pair<PII, int>> res;
		REP(i, L)
			res.push_back(MP(MP(1, 2), i));

		return res;
	}

	int md = L%k;
	if (md)
	{
		auto list = go(L - md, k);
		int last = list.back().first.second;

		REP(i, md)
			list.push_back(MP(MP(1, last), L - i - 1));

		return list;
	}

	auto list = go(L / k, k);
	int last = list.back().first.second;
	list.push_back(MP(MP(last, last + 1), 0));
	REP(i, k - 1)
		list.push_back(MP(MP(last, last + 1), (i + 1)*L / k));

	return list;
}

vector<pair<PII, int>> go(int L)
{
	FORQ(k, 2, 65)
	{
		auto res = go(L, k);
		if (res.back().first.second < 21 && res.size() < 61)
			return res;
	}

	FOR(sub, 1, 60)FORQ(k, 2, 65)
	{
		auto res = go(L - sub, k);
		int last = res.back().first.second;
		if (last < 20 && res.size() < 60 - sub)
		{
			res.push_back(MP(MP(last, last + 1), 0));
			REP(i, sub)
				res.push_back(MP(MP(last, last + 1), L - i - 1));
			return res;
		}
	}

	return{};
}

int main()
{
	int L;
	scanf("%d", &L);

	auto list = go(L);

	printf("%d %d\n", list.back().first.second, list.size());
	for (const auto& p : list)
		printf("%d %d %d\n", p.first.first, p.first.second, p.second);

	return 0;
}

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

using namespace std;

#define ll long long 
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ff first
#define ss second
#define endl "\n"
#define MOD 1000000007
#define MOD1 998244353
#define inf LLONG_MAX

ll GCD(ll x,ll y){if(y==0)return x;return GCD(y,x%y);}
ll LCM(ll x,ll y){return (x*y)/(GCD(x,y));}
ll LOGK(ll x,ll k){if(x>=k)return 1+LOGK(x/k,k);return 0;}
ll MPOW( ll a, ll b, ll m) { if(b==0) return 1; ll x=MPOW(a,b/2,m); x=(x*x)%m; if(b%2==1) x=(x*a)%m; return x;}
ll MINV(ll a,ll m) {return MPOW(a,m-2,m);}

class pnc{
  ll FACT_MAX,MODU;
  vector<ll> fact;
public:
  pnc( ll n, ll m) { FACT_MAX = n; fact.resize(FACT_MAX); MODU = m; MFACT_INIT(MODU);}
  void MFACT_INIT( ll m) { fact[0]=1; for(ll i=1;i<FACT_MAX;++i) fact[i]=(i*fact[i-1])%MODU;}
  ll MFACT( ll n) { return fact[n];}
  ll PERM( ll n, ll r) { return (fact[n]*::MINV(fact[n-r],MODU))%MODU;}
  ll COMB( ll n , ll r) { return (PERM(n,r)*::MINV(fact[r],MODU))%MODU;}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    

    ll test=1;
    //cin>>test;
    while(test--)
    {
        ll a,u,b,v,t;

        cin>>a>>u>>b>>v>>t;

        ll d=abs(a-b);

        if(d<=t*(u-v) && u>v)
        cout<<"YES";
        else
        cout<<"NO";
    }
}

Measured memory_bytes: 3652
// E - Knapsack 2
#include <bits/stdc++.h>
using namespace std;

#define VMAX 100000
#define WMAX 1000000000
vector<int> dp(VMAX+1, WMAX+1);

int main(){
	int N,W; cin>>N>>W;
	dp[0] = 0;
	while(N--){
		int w,v; cin>>w>>v;
		for(int j=VMAX; j>=v; j--) dp[j] = min(dp[j], dp[j-v] + w);
	}

	int a = 0;
	for(a=VMAX; a>=1; a--) if(dp[a]<=W) break;
	cout<< a <<endl;
}

Measured memory_bytes: 640
import sys

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


def solve():
    N, K, Q = map(int, input().split())
    points = [K for _ in range(N)]
    correct = [0 for _ in range(N)]

    for _ in range(Q):
        a = int(input()) - 1
        correct[a] += 1

    for i in range(N):
        points[i] -= (Q - correct[i])

    for i in range(N):
        if points[i] <= 0:
            print('No')
        else:
            print('Yes')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 8676
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (abs(b - a) <= d && abs(c - b) <= d) {
    cout << "Yes" << endl;
  }
  else if (abs(c - a) <= d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
/*
	LINES :
		check for the patterns size of t.size() and count (need to modify)
*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

// #define OJ
#define pb push_back
#define F first
#define S second
#define WLL(t) while(t--)
#define FOR(i,a,b) for(int i = a; i < b; i++) // for string
#define STF(i, a, b) for(size_t i = a; i < b; i++)
#define RFOR(i,a,b) for(int i = a; i >= b; i--)
#define STRF(i, a, b) for(size_t i = a; i >= b; i--) // for string
#define ALL(v) v.begin(),v.end()
#define PRECISION(x) cout<<fixed<<setprecision(x)
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)

void solve(string s , string t, size_t lens, size_t lent);
int main()
{
#ifdef OJ
	READ;
	WRITE;
#endif

	FASTIO;
	string s, t;
	cin >> s >> t;
	size_t lens{s.size()};
	size_t lent{t.size()};
	solve(s, t, lens, lent);
	return 0;
}
void solve(string s , string t, size_t lens, size_t lent)
{
	//the highest possible is lent
	size_t ans{lent};
	//to go through all the patterns of each lent
	size_t siz = lens - lent;
	for (size_t i = 0; i <= siz; i++) {
		size_t tomod{0};// need to modify
		STF(j, 0, lent) {
			if (s[i + j] != t[j])
			{
				tomod++;
			}
		}
		ans = min(ans, tomod);
	}
	cout << ans << "\n";
}

Measured memory_bytes: 3596
#include<stdio.h>

int main()
{

    int a,b,c,r1,r2;
    scanf("%d %d %d",&a,&b,&c);

   r1=b-a;
   r2=c-b;
   if(r1==r2)
   {
       printf("YES");
   }
   else
       printf("NO");


}


Measured memory_bytes: 128