akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define INF 2000000000

using namespace std;

int main(void){
	int n,m;
	
	while(cin >> n >> m){
		if((n|m) == 0) break;
		
		int s,t,cost;
		
		int f[n][n];
		for(int i=0;i<n;i++)for(int j=0;j<n;j++){
			f[i][j] = INF;
		}
		
		for(int i=0;i<m;i++){
			cin >> s >> t >> cost;
			f[s][t] = cost;
			f[t][s] = cost;
		}
		//Minimum Spaning Tree
		vector<int> connected;
		connected.push_back(0);
		int ret = 0;
		while(connected.size() != n){
			int mini=INF,tmp,tmpindex;
			for(int i=0;i<connected.size();i++){
				for(int j=0;j<n;j++){
					if(f[connected[i]][j] < mini && 
					find(connected.begin(),connected.end(),j) == connected.end()){
						mini = f[connected[i]][j];
						tmpindex = j;
					}
				}
			}
			ret += mini;
			connected.push_back(tmpindex);
		}
		cout << ret << endl;
	}
}

Measured memory_bytes: 0
import java.util.*;
public class Main {
	
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		
		long N = sc.nextLong();
		
		long sqrt = (long)Math.sqrt(N);
		for (long i = sqrt; i >= 1; i--) {
			if (N % i == 0) {
				int ans = Math.max(String.valueOf(i).length(), String.valueOf(N / i).length());
				System.out.println(ans);
				return;
			}
		}
	}
}

Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;

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

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

int main() {
	int N, M; cin >> N >> M;
	int ans = N * (N - 1) + M * (M - 1);
	ans /= 2;
	cout << ans << endl;
	return 0;
}

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

int bubbleSort(int A[], int N) {

int sw = 0;
bool flag = 1;
for(int i = 0; flag; i++){
    flag = 0;
    for(int j = N-1; j >= i+1; j--){
       if (A[j] < A[j-1]){
       swap(A[j], A[j-1]);
       flag = 1;
       sw++;
    }
  }
}

 return sw;
}

int main() {
int A[100], N, sw,i;
cin >> N;
for(int i= 0; i < N; i++)cin >> A[i];

sw = bubbleSort(A, N);

for( int i = 0; i < N; i++){
    if (i) cout << " ";
    cout << A[i];
}
cout << endl;
cout << sw << endl;

return 0;
}

Measured memory_bytes: 3048
from math import atan, degrees

def angle(a, b, x):
	return degrees(atan(((a * b ** 2) / ( 2 * x)) if x <= 0.5 * b * a ** 2 else ((2 * (b - (x / (a ** 2)))) / a)))
	
print(angle(*map(int, input().split())))

Measured memory_bytes: 9268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

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

    int N;
    cin >> N;
    vector<int> b(N);
    REP(i, N) cin >> b[i];
    vector<int> ans;
    while (b.size() > 0) {
        bool found = false;
        for (int i = b.size() - 1; i >= 0; i--) {
            if (b[i] == i + 1) {
                b.erase(b.begin() + i);
                ans.push_back(i + 1);
                found = true;
                break;
            }
        }
        if (!found) {
            cout << -1 << '\n';
            return 0;
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << '\n';
}


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

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

typedef long long ll;

const int mod = 1e9 + 7;

using namespace std;



int main(void) {
	int N, K; cin >> N >> K;
	vector<int> ball(N, 0);

	rep(i, N) {
		int a; cin >> a; a--;
		ball[a]++;
	}

	sort(ball.begin(), ball.end(), greater<int>());

	int cnt = 0;
	rep(i, K)cnt += ball[i];

	cout << N - cnt << endl;

	return 0;
}

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

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

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

int main () {
    int N;
    cin >> N;
    string ans="APPROVED";
    for (int i=0;i<N;i++) {
        int A;
        cin >> A ;
        if (A%2==0) {
            if (A%3==0 || A%5==0) ans="APPROVED";
            else {
                ans="DENIED";
                break;
            }

        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        var sc = new Scanner(System.in);
    
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        var c = new char[h][w];
        for(int i = 0; i < h; i++){
            c[i] = sc.next().toCharArray();
        }
        
        int ans = 0;
        for(int i = 0; i < 1<<h; i++){
            for(int j = 0; j < 1<<w; j++){
                int count = 0;
                for(int l = 0; l < h; l++){
                    if((i & (1<<l)) != 0) continue;
                    for(int m = 0; m < w; m++){
                        if((j & (1<<m)) != 0) continue;
                        if(c[l][m] == '#') count++;
                    }
                }
                if(count == k) ans++;
            }
        }
        System.out.println(ans);
    }
}

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

int main () {
  int n;
  cin >> n;
  vector<int> a(n+1), b(n);
  rep(i, n+1) cin >> a[i];
  rep(i, n) cin >> b[i];
  ll ans = 0;
  rep(i, n) {
    //左を全力で殴る
    int left = min(a[i], b[i]);
    a[i] -= left;
    b[i] -= left;
    ans += left;
    //右を全力で殴る
    int right = min(a[i+1], b[i]);
    a[i+1] -= right;
    b[i] -= right;
    ans += right;
  }
  cout << ans << endl;
}

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

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

    long long x;
    cin >> x;
    int c500 = x / 500; 
    int r500 = x % 500; 
    int c5 = r500 / 5; 
    cout << c500 * 1000 + c5 * 5 << "\n";
    return 0;
}


Measured memory_bytes: 3664
n = int(input())
data = [input().rstrip() for _ in range(n)]
used = [data[0]]
 
for i in range(1, n):
    if data[i][0] == data[i - 1][-1] and data[i] not in used:
        used.append(data[i])
    else:
        print("No")
        exit()
print('Yes')


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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 300005;

int n, m, x, y, a[N];
bool l[N], r[N];
LL ans;

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m);
  for (int i = 1; i <= n; ++i) {
    Read(a[i]);
  }
  for (int i = 1, t; i <= n; ++i) {
    Read(t);
    if (t % (m << 1) == 0) {
      ans += t;
    } else {
      ans += 1LL * (t / (m << 1) + 1) * (m << 1), t %= m << 1;
      if (t <= a[i] << 1) {
        l[i] = true;
      }
      if (t <= m - a[i] << 1) {
        r[i] = true;
      }
    }
  }
  for (int i = 1; i < n; ++i) {
    if (x && r[i]) {
      if (l[i]) {
        ++y;
      }
      --x, ans -= m << 1;
    } else if (!l[i] && r[i]) {
      if (y) {
        --y, ++x;
      }
    } else if (l[i]) {
      ++x;
    }
  }
  if (!r[n]) {
    ans += m << 1;
  }
  printf("%lld\n", ans);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


Measured memory_bytes: 2176
N = int(input())
P = list(map(float, input().split()))
dp = [[0]*(N+1) for i in range(N+1)]
dp[0][0] = 1
# dp[X][I] := X回目の操作を終えてi回面が出る確率
for i in range(1, N+1):
    p = P[i-1]
    for j in range(i+1):
        if j >= 1:
            dp[i][j] = dp[i-1][j]*(1-p) + dp[i-1][j-1]*p
        else:
            dp[i][j] = dp[i-1][j]*(1-p)
ans = 0
for i in range(N//2+1, N+1):
    ans += dp[N][i]
print(ans)


Measured memory_bytes: 203792
a=int(input())
b=int(input())
c=int(input())
x=int(input())
ctr=0

def cal(p,q,r):
  s=500*p+100*q+50*r
  return s

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      d=cal(i,j,k)
      if(d==x):
        ctr+=1

print(ctr)

Measured memory_bytes: 3064
#![allow(non_snake_case)]
#![allow(unused_imports)]
use proconio::input;
use std::cmp::max;
use std::cmp::min;
use std::collections::HashMap;
use std::collections::VecDeque;

fn main() {
    input! {
        N: i64,
    }

    // できるだけ平方根に近い数で、割り切る値を探す
    for i in (1..(N as f64).sqrt().floor() as i64 + 1).rev() {
        if N % i == 0{
            let j = N / i;
            let ans = (i - 1) + (j - 1);
            println!("{}", ans);
            return;
        }
    }

    // 素数なら仕方がないので (1, N) に行く
    let ans = N - 1;
    println!("{}", ans);
}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

template <typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll x, ll y)
{
    return x / gcd(x, y) * y;
}

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

    int n;
    cin >> n;
    vector<ll> a(n + 1), b(n);
    for (int i = 0; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    ll ret = 0;
    for (int i = 0; i < n; i++)
    {
        ll mi = min(a[i], b[i]);
        ret += mi;
        a[i] -= mi;
        b[i] -= mi;
        mi = min(b[i], a[i + 1]);
        ret += mi;
        a[i + 1] -= mi;
    }
    cout << ret << endl;
}


Measured memory_bytes: 1792
#include <stdio.h>

int             main(void)
{
        int     n;
        int     dp[1000001] = {0};
        int     ret = 0;
        int     i, j;

        scanf("%d", &n);
        dp[0] = 0;
        dp[1] = 1;
        for (i = 1; i <= n - 1; i++)
        {
                j = 1;
                if (i == 1)
                {
                        j = 2;
                }
                while (i * j <= n - 1)
                {
                        dp[i * j] += 1;
                        j++;
                }
        }
        for (i = 1; i <= n - 1; i++)
        {
                ret += dp[i];
        }
        printf("%d\n", ret);
        return (0);
}

Measured memory_bytes: 5640
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner line= new Scanner(System.in);
        int n=line.nextInt();
        int k=line.nextInt();
        int a[];
      //  int ans=0;
        a= new int[n];
      //  int one=0;
        for(int i=0;i<n;i++){
            a[i]=line.nextInt();
        }
        System.out.printf("%d\n",(n-1+k-2)/(k-1));
        line.close();
    }
}
/*
2 3 1 4 
1 1 1 4  =>2

5,3 => 2
10 3  => 5
1122334455
1  2 3 => 1

7 3 1 8 4 6 2 5
2 1 5 4 (1+3)
*/

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

int a, b, c;

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


Measured memory_bytes: 256
H, W = [int(i) for i in input().split()]

if H == 1 or W == 1:
    print(1)
elif W % 2 == 0:
    print((H * W) // 2)
else :
    odd_row = (W // 2) + 1
    even_row = W // 2
    if H % 2 == 1:
        odd_row_num = (H // 2) + 1
        even_row_num = H // 2
        print((odd_row*odd_row_num) + (even_row*even_row_num))
    else :
        print((odd_row+even_row) * (H // 2))

Measured memory_bytes: 3064
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
long long a[300030],fro[100010],bac[100020],x,ans;
int main(){
	int i,n;
	priority_queue<long long> p,q;
	cin >> n;
	fro[0] = 0;
	bac[0] = 0;
	for(i=0;i<3*n;i++){
		cin >>a[i];
		if(i<n){
			p.push(-a[i]);
			fro[0] += a[i];
		}
		if(i>=2*n){
			q.push(a[i]);
			bac[0] += a[i];
		}
	}
	for(i=0;i<n;i++){
		p.push(-a[n+i]);
		x = p.top();
		p.pop();
		fro[i+1] = fro[i]+a[n+i]+x;
		q.push(a[2*n-1-i]);
		x = q.top();
		q.pop();
		bac[i+1] = bac[i]+a[2*n-1-i]-x;
	}
	ans = fro[0] - bac[0];
	for(i=0;i<=n;i++){
		ans = max(ans,fro[i]-bac[n-i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 5876
import java.util.*;

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

	while(sc.hasNext()){
	    String[] line = sc.nextLine().split(" ");
	    boolean equal = false;
	    for(int i=0; i<26; i++){
		for(int j=0; j<line.length; j++){
		    if(line[j].equals("this") || line[j].equals("that") || line[j].equals("the")){equal = true;}
		}
		if(equal){break;}
		for(int j=0; j<line.length; j++){
		    char[] a = line[j].toCharArray();
		    for(int k=0; k<a.length; k++){
			if(Character.isLowerCase(a[k]))
			    a[k] = (char)((a[k]-'a'+1)%26+'a');
		    }
		    line[j] = new String(a);
		}
	    }
	    for(int i=0; i<line.length-1; i++){
		System.out.print(line[i]+" ");
	    }
	    System.out.println(line[line.length-1]);
	}
    }
}

Measured memory_bytes: 12000
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
p = [int(readline()) for _ in range(n)]
memo = [0] * n
for i, pp in enumerate(p):
    memo[pp - 1] = i
cnt = 1
ans = 0
for bf, af in zip(memo, memo[1:]):
    if bf < af:
        cnt += 1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 1
if ans < cnt:
    ans = cnt
print(n - ans)


Measured memory_bytes: 20488
// D - Triangles

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>

using namespace std;

int main()
{
    int N;
    vector<int> L;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        L.push_back(tmp);
    }
    int result = 0;
    for (int i = 0; i < N - 2; i++) {
        int a = L[i];
        for (int j = i + 1; j < N - 1; j++) {
            int b = L[j];
            for (int k = j + 1; k < N; k++) {
                int c = L[k];
                if ((a < b + c)  && (b < c + a) && (c < a + b)) {
                    result++;
                }
            }
        }
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 888
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<bitset>
using namespace std;
typedef long long LL;

int n, m;
bitset<4000001> f;
int a[4000010];

int main()
{
	scanf("%d", &n); f[0] = 1;
	for(int i = 1; i <= n; i ++) { int x; scanf("%d", &x); f |= f<<x; }
	for(int i = 1; i <= 4000000; i ++) if(f[i]) a[++ m] = i;
	printf("%d\n", a[(m+1)/2]);
}

Measured memory_bytes: 9856
function Main(input) {
	input = input.split("\n");
	tmp = input[0].split(" ");
	var a = parseInt(tmp[0], 10);
	var b = parseInt(tmp[1], 10);
  	var c = a*b;
	c%2 === 0 ? console.log('Even'): console.log('Odd');
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
  int n,m,i,b1=0,b2=0;
  vector<int> a(4);
  for(i=0; i<3; i++){
    cin >> n >> m;
    a[n-1]++; a[m-1]++;
  } 
  sort(a.begin(), a.end());
  if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
x = ''
while 1:
    try:
        x += input()
    except:
        break
    
str_a = [chr(i) for i in range(ord('a'), ord('z') + 1)]
str_A = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
count = [0] * 26
for i in x:
    if i in str_a:
        count[str_a.index(i)] += 1
    elif i in str_A:
        count[str_A.index(i)] += 1
for i, j in zip(str_a, count):
    print('{} : {}'.format(i, j))


Measured memory_bytes: 5564
//package ABC170;
import java.util.*;
import java.io.*;
import java.lang.*;
class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
		}
		HashMap<Integer,Integer> hm=new HashMap<>();
		for(int i=0;i<n;i++)
		{
			if(hm.containsKey(a[i]))
			{
				hm.put(a[i],hm.get(a[i])+1);
			}
			else
			{
				hm.put(a[i],1);
			}
		}
		//System.out.println(Arrays.toString(a));
		int max=Integer.MIN_VALUE;
		for(int i=0;i<n;i++)
		{
			max=Math.max(a[i], max);
		}
		//System.out.println(max);
		
		int mark[]=new int[max+1];
		
		for(int i=0;i<n;i++)
		{
			int ele=a[i];
			while(ele<=max)
			{
				mark[ele]=mark[ele]+1;
				ele=ele+a[i];
			}
		}
		//System.out.println(mark[86]);
		int count=0;
		for(int i=0;i<n;i++)
		{
			//System.out.println(mark[a[i]]);
			if(mark[a[i]]==1)
			{
				//System.out.println(a[i]);
				count++;
			}
		}
		//System.out.println(Arrays.toString(mark));
		
		/*
		
		//24 11 8 3 16;
		Arrays.sort(a);
		
		boolean yes[]=new boolean[n];
		Arrays.fill(yes,true);
		for(int i=0;i<n;i++)
		{
			if(yes[i])
			{
				if(i<n-1 && a[i]==a[i+1])
				{
					yes[i]=false;
					yes[i+1]=false;
				}
				for(int j=i+1;j<n;j++)
				{
					if(a[j]%a[i]==0)
					{
						yes[j]=false;
					}
				}
			}
		}
		
		int count=0;
		for(int i=0;i<n;i++)
		{
			if(yes[i])
			{
				count++;
			}
		}*/
		System.out.println(count);
		
		

	}

}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)

int K;

ll solve() {
    queue<ll> q;
    FOR (i, 1, 10) q.push(i);
    while (1) {
        ll x = q.front(); q.pop();
        K--;
        if (K == 0) return x;
        int y = x % 10;
        x *= 10;
        if (y != 0) q.push(x + y - 1);
        q.push(x + y);
        if (y != 9) q.push(x + y + 1);
    }
}

int main() {
    cin >> K;
    cout << solve() << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    begin(v), end(v)
#define in        []{lint n; cin>>n; return n;}()

int main() { cin.tie(0); ios::sync_with_stdio(false);
    int N = in, M = in;
    vector<vector<int>> to( N, vector<int>(0) );
    rep( i, M ) {
        int x = in-1, y = in-1;
        to[x].push_back(y);
    }

    vector<int> length( N, -1 );
    rep( i, N ) {
        stack<tuple<int,int>> s; s.push( make_tuple(i,0) );
        while( !s.empty() ) {
            int x,j; tie(x,j) = s.top();
            if( j == to[x].size() ) {
                length[x] = 0;
                for( int y : to[x] ) length[x] = max( length[x], length[y]+1 );
                s.pop();
            } else if( length[to[x][j]] != -1 ) {
                s.pop();
                s.push( make_tuple(x,j+1) );
            } else {
                s.push( make_tuple(to[x][j],0) );
            }
        }
    }

    int longest = 0;
    rep( i, N ) longest = max( longest, length[i] );

    cout << longest << "\n";
}


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

#define N 20
#define Q 200
#define true 1
#define false 0

int solve(int, int);
int n, A[N];

int main(){
  int q, m, a, i;

  scanf("%d", &n);
  if(n > N) exit(1);
  for(i=0; i<n; i++){
    scanf("%d", &A[i]);
    if(A[i] < 1 || A[i] > 2000) exit(2);
  }

  scanf("%d", &q);
  if(q > Q) exit(3);
  for(i=0; i<q; i++){
    scanf("%d", &m);
    if(m < 1 || m > 2000) exit(4);
    a = solve(0,m);
    if(a == 1) printf("yes\n");
    else if(a == 0)printf("no\n");
    else printf("%d\n",a);
  }
  return 0;
}

int solve(int i, int m){
  int res;
  
  if(m == 0) return true;
  if(i >= n) return false;
  res = solve(i+1,m) || solve(i+1,m-A[i]);
  return res;
}



Measured memory_bytes: 2100
#include <iostream>
#include <string>
using namespace std;
string alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  int N; cin >> N;
  string s; cin >> s;
  string ans;
  for(char c: s) {
    auto pos = alphabets.find(c);
    pos += N;
    ans.push_back(alphabets[pos]);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

bool compare(pair<ll, ll> a, pair<ll, ll> b){
    if(a.first == b.first)return a.second < b.second;
    return a.first < b.first;
}
int main(){
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> p(m);
    rep(i, m)cin >> p[i].first >> p[i].second;

    sort(ALL(p), compare);

    ll ans = 1;
    ll left, right;
    left = p.front().first;
    right = p.front().second;
    for(ll i=1; i<m; ++i){
        if(right <= p[i].first){
            ans++;
            left = p[i].first;
            right = p[i].second;
        }
        left = p[i].first;
        right = min(right, p[i].second);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <cassert>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> P;
typedef long long int ll;
typedef pair<int,int> Pii;
const int INF=(1<<30)-1;
const ll INFl=9223372036854775807;
const int MAX=310;
const ll MOD=1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int main(void){
	int n;
	cin>>n;
	ll ans=0;
	ll a[100100],b[100100],ab[100100];
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		ans+=(ll)b[i];
		ab[i]=a[i]+b[i];
	}
	ans*=(-1);
	sort(ab,ab+n,greater<int>());
	for(int i=0;i<(n+1)/2;i++)
		ans+=(ll)ab[i*2];
	cout<<ans<<endl;
}


Measured memory_bytes: 2560
N = int(input())
A = list(map(int, input().split()))
t = [(i + 1, A[i]) for i in range(N)]
t_sorted = sorted(t, key=lambda a: a[1])
ans = ''
for i in range(N):
    ans += str(t_sorted[i][0]) + ' '
print(ans)


Measured memory_bytes: 25404
#include <bits/stdc++.h>
using namespace std;
int judge(int p, int q)
{
    if (p >= q)
    {
        return p - q;
    }
    else
    {
        return q - p;
    }
}

int main()
{
    int ans = 0;
    int p[5], k;
    for (int i = 0; i < 5; i++)
    {
        cin >> p[i];
    }
    cin >> k;
    for (int i = 0; i < 5; i++)
    {
        for (int j = i; j < 5; j++)
        {
            if (i != j)
            {
                int jud = judge(p[i], p[j]);
                if (jud <= k)
                {
                    ans++;
                }
            }
        }
    }
    if (ans == 10)
    {
        cout << "Yay!";
    }
    else
    {
        cout << ":(";
    }
    return 0;
}

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

int main()
{

	while (1) {
		int n, x;
		cin >> n >> x;
		if (n == 0 && x == 0) break;
		int same = 0;
		for (int i = 1; i <= n-2; i++) {
			for (int j = i+1; j <= n-1; j++) {
				int k;
				k = x - i - j;
				if (k <= n && i < j && j < k) same += 1;
			}
		}
		cout << same << endl;
	}

	return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 110000, maxd = 11;
int c[maxn][maxd];
int col[maxn];
vi e[maxn];

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

    int n, m, q;
    cin >> n >> m;
    forn(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        e[a].pb(b);
        e[b].pb(a);
    }
//    forn(i, n) forn(j, maxd) c[i][j] = -1;
    cin >> q;
    forn(i, q) {
        int v, d;
        cin >> v >> d >> col[i + 1];
        --v;
        c[v][d] = i + 1;
    }

    ford(i, maxd - 1) forn(v, n) for (int u: e[v]) {
        uax(c[u][i], c[v][i + 1]);
    }

    forn(v, n) {
        int res = 0;
        forn(d, maxd) uax(res, c[v][d]);
        cout << col[res] << '\n';
    }
}


Measured memory_bytes: 11512
import java.util.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	boolean[] npri;
	int size = 100001;

	void solve(){
		get_pri();
		while(in.hasNext()){
			int n = in.nextInt();
			//if(n == 0) return;
			int ans = 0;
			for(int i = 1; i <= n; i++){
				if((!npri[i]) &&(!npri[n - i + 1])) ans++;
			}
			System.out.println(ans);
		}
	}
	
	void get_pri(){
		npri = new boolean[size];
		npri[0] = npri[1] = true;
		for(int i = 2; i < size; i++){
			if(!npri[i]){
				for(int j = i + i; j < size; j += i){
					npri[j] = true;
				}
			}
		}
	}
	
}

// while(in.hasNext()){
		// 	int n = in.nextInt();
		// 	if(n == 0) return;
			
		// }

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

int main(){
  int N;
  cin >> N;
  vector<pair<ll,ll> > p(N);
  for(int i = 0; i < N; ++i){
    cin >> p[i].second >> p[i].first;
  }
  sort(p.begin(), p.end());
  int t = 0;
  bool flag = true;
  for(int i = 0; i < N; ++i){
    t += p[i].second;
    if(t > p[i].first){
      flag = false;
      break;
    }
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 3328
#include <iostream>
#include <numeric>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int N;
	cin >> N ;
	vector<int> vec(N-1);
	vector<int> an(N);
	for (int i = 0; i < N; i++) {
		an.at(i)=0;
	}
	for (int i = 0; i < N-1; i++) {
		cin >> vec.at(i);
		an.at(vec.at(i) - 1)++;

	}
	for (int i = 0; i < N; i++) {
		cout << an.at(i) << endl;

	}
}



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

//int numberofPaths(int h,int w,int a,int b);

int main()
{
    ll n,i,len1,h,t,cnt=0,cnt1=0,x,m,flag=0,k,h1=0,h2=0,od=0,ev=0,y,l;
    double w;
   /* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);*/
	cin>>n>>l;
	ll a[n];
	for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<n;i++)
    {
        if(a[i]+a[i-1]>=l)
        {
            len1=i;
            flag=1;
        }
    }
    if(flag==0)
    {
        cout<<"Impossible"<<endl;
    }
    else{
            cout<<"Possible"<<endl;
   // cout<<len1<<endl;
        for(i=1;i<len1;i++)
        {
            cout<<i<<endl;
        }
        for(i=n-1;i>len1;i--)
        {
            cout<<i<<endl;
        }
        cout<<len1<<endl;
    }
	return 0;
}


Measured memory_bytes: 1536
n=int(input())
edges=[[] for i in range(1+n)]
e={}
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    e[(_,__)]=i
    e[(__,_)]=i
    """
"""#weighted->erase
f=max(len(j)for j in edges)
print(f)
ret=[0]*(n-1)
from collections import deque
dq=deque([(1,1)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
while dq:
    a,c=dq.popleft()
    for to in edges[a]:
        if ret[e[(a,to)]]:continue
        ret[e[(a,to)]]=c
        c=c%f+1
        dq.append((to,c))
        
print(*ret,sep="\n")

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

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

    int a, b;
    cin >> a >> b;
    int diff = b - a;

    int tall = 0;
    for(int i = 1; i <= diff; i++){
        tall += i;
    }

    int ans = tall - b;

    cout << ans << "\n";

    return 0;
}


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


class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

####################################################################################################

import string

N = int(input())
S = input().strip()
Q = int(input())

B = [Bit(N) for _ in range(26)]

abc = string.ascii_lowercase                                            # [a-z] をロード
abc2 = dict()
for i, s in enumerate(abc):
    abc2[s] = i

for i, s in enumerate(S):
    B[abc2[s]].add(i,1)

for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        a = int(q[1]) - 1
        b = q[2]
        for i in range(26):
            if B[i].el[a] == 1:
                B[i].add(a,-1)
        B[abc2[b]].add(a,1)
    if q[0] == "2":
        a = int(q[1]) - 1
        b = int(q[2]) - 1
        res = 0
        for i in range(26):
            res += (B[i].get(a, b+1) > 0)
        print(res)


Measured memory_bytes: 286624
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	void run() {
		for (;;) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if ((n | m) == 0) return;
			double[][] g = new double[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					g[i][j] = sc.nextDouble();
				}
			}

			double[][] dp = new double[2][n];
			for (int i = 0; i < n; i++) dp[0][i] = 1;
			for (int i = 0; i < m - 1; i++) {
				for (int j = 0; j < n; j++) {
					for (int k = 0; k < n; k++) {
						dp[(i + 1) & 1][k] = Math.max(dp[(i + 1) & 1][k], dp[i & 1][j] * g[j][k]);
					}
				}
			}
			
			double max = 0;
			for(int i=0;i<n;i++) max = Math.max(max, dp[(m-1) & 1][i]);
			BigDecimal bd = new BigDecimal(max);
			System.out.println(bd.setScale(2, BigDecimal.ROUND_HALF_UP));
		}
	}

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

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	void debug2(double[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 89620
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<utility>
using namespace std;
#define INF (1<<30)

int dp[150][10][150/2+1];
vector<pair<int,int> > stone[150];

int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		for(int h=0;h<n;h++){
			int k;
			cin>>k;
			stone[h].resize(k);
			for(int i=0;i<k;i++){
				int x,d;
				cin>>stone[h][i].first>>stone[h][i].second;
			}
		}
		fill_n((int*)dp,sizeof(dp)/sizeof(int),INF);
		for(int i=0;i<stone[0].size();i++)dp[0][i][0]=0;
		for(int i=0;i<stone[1].size();i++)dp[1][i][1]=0;
		int ans=INF;
		for(int h=0;h<n;h++){
			for(int i=0;i<stone[h].size();i++){
				for(int j=0;j<=m;j++){
					int v=dp[h][i][j];
					if(v==INF)continue;
					if(h+1<n){
						for(int k=0;k<stone[h+1].size();k++){
							dp[h+1][k][j]=min(dp[h+1][k][j]
								,v+(stone[h][i].second+stone[h+1][k].second)*abs(stone[h][i].first-stone[h+1][k].first));
						}	
					}else ans=min(ans,v);
					if(h+2<n && j<m){
						for(int k=0;k<stone[h+2].size();k++){
							dp[h+2][k][j+1]=min(dp[h+2][k][j+1]
								,v+(stone[h][i].second+stone[h+2][k].second)*abs(stone[h][i].first-stone[h+2][k].first));
						}	
					}else if(j<m)ans=min(ans,v);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

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

int main()
{
	int A1, A2, A3;
	
	cin >> A1 >> A2 >> A3;
	
	if (A1 + A2 + A3 >= 22) {
		cout << "bust" << endl;
	}
	else {
		cout << "win" << endl;
	}
}


Measured memory_bytes: 256
INF = 10 ** 10

def merge(A, left, mid, right):
    c = 0
    n1 = mid - left
    n2 = right - mid
    Left = [A[left+i] for i in range(n1)]
    Right = [A[mid+i] for i in range(n2)]
    Left.append(INF)
    Right.append(INF)
    i=0
    j=0
    for k in range(left, right):
        c += 1
        if Left[i] <= Right[j]:
            A[k] = Left[i]
            i += 1
        else:
            A[k] = Right[j]
            j += 1
    return c

def mergeSort(hoge, left, right):
    c = 0
    if left+1 < right:
        mid = (left + right) // 2
        c += mergeSort(hoge, left, mid)
        c += mergeSort(hoge, mid, right)
        c += merge(hoge, left, mid, right)
    return c

if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    c = mergeSort(hoge, 0, len(hoge))
    print (' '.join([str(x) for x in hoge]))
    print (c)


Measured memory_bytes: 66796
N, K =map(int,input().split())
A = list(map(int,input().split()))
ans = []
for i in range(K,N):
    if (A[i]/A[i-K])>1:
        ans.append("Yes")
    else:
        ans.append("No")

for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 31688
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  bool x;cin >> x;
  if(x) cout << 0 << endl;
  else cout << 1 << endl;
  return 0;
}


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

#define f first
#define s second
#define ll long long
#define pb push_back
#define mp make_pair
#define inp(x) cin>>x
#define print(x) cout<<x
#define pii pair<int,int>
#define pll pair<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define reset(d,val) memset(d,val,sizeof(d))
#define sort(v) sort(v.begin(),v.end())
#define sort_arr(arr,i,f) sort(arr+i,arr+f)
#define pq priority_queue<int,vector<int>,greater<int> >
#define pq1 priority_queue<pll,vector<pll>,greater<pll> >

const int mod = 1e9+7;

int n;
ll w,wt[101],val[101],sm=100000;

ll dp[100001];



int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>w;
	for (int i = 0; i <=sm; ++i)
	{
		dp[i] = 1e16;
	}
	dp[0] = 0;
	for(int i=0;i<n;i++){
		cin>>wt[i]>>val[i];
		for(int j=sm;j>=0;j--){
			if(j-val[i]>=0) dp[j] = min(dp[j],dp[j-val[i]]+wt[i]);
		}
	}
	ll ans = 0;
	for (ll i = 0; i <=sm; ++i)
	{
		if(dp[i]<=w) {
			ans = max(ans,i);
		}
	}

	cout<<ans;
	return 0;
}


Measured memory_bytes: 1024
n,m,c=map(int, input().split())
b=list(map(int, input().split()))
ans=0
for _ in range(n):
	a=list(map(int, input().split()))
	r=c+sum([a[i]*b[i] for i in range(m)])
	ans += 1 if r>0 else 0
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
    int n, a;
    cin >> n >> a;
    cout << n*n-a << endl;
    return 0;
}

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

using namespace std;

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

	bool isReverse = false;

	for (int i = 0; i < Q; i++) {
		int T;
		cin >> T;
		if (T == 1) {
			isReverse = !isReverse;
			continue;
		}
		int F;
		string C;
		cin >> F >> C;

		// xor
		if ((F == 1) == !isReverse) {
			S.insert(0, C);
		} else {
			S.append(C);
		}
	}

	if (isReverse) {
		reverse(S.begin(), S.end());
	}

	cout << S << endl;

	return 0;
}


Measured memory_bytes: 900
n = int(input())
H = [int(s) for s in input().split()]
H.append(0)
def sub(x,y):
    global H
    print(H,"H")
    
    for i in range(x,y):
        H[i] = H[i] -1
    print(H, "H[i]")
        
count = 0
for i in range(n):
    if H[i] > H[i+1]:
        count += H[i] - H[i+1]
print(count)
"""
def garden(a,b):
    global H
    global count
    if a==b :
        return count
    
    for i in range(a,b):
        if H[i] == 0:
            print("a=%d,b=%d,i=%d,1"%(a,b,i))
            return garden(a, i) + garden(i+1, b)
    
    if sum(H) == 0:
        return count
    sub(a,b)#全ての花を伸ばすべき
    count += 1
    print(count,"count")
    garden(a,b)
print(garden(0,n))
"""





Measured memory_bytes: 3064
#include <stdio.h>
int main(void)
{
	int i, n, suchi = 0;
	long min, max, sum;
	max = -1000000;
	min = 1000000;
	sum = 0;
	scanf("%d", &suchi);
	for (i = 0; i < suchi; i++)
	{
		scanf("%d", &n);
		if (max < n)
		{
			max = n;
		}
		if (min > n)
		{
			min = n;
		}
		sum += n;
	}
	printf("%ld %ld %ld\n", min, max, sum);
	return 0;
}


Measured memory_bytes: 2108
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
x=a[n-1]/2
ans=a[0]
for i in range(1,n-1):
    if abs(ans-x)>abs(a[i]-x):
        ans=a[i]
print("{} {}".format(a[n-1],ans))

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

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

const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// head

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

    int a, b, c;
    cin >> a >> b >> c;
    cout << ((c % (__gcd(a,b)) == 0) ? "YES" : "NO") << endl; 
    return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>

int main() {
  int n,a[101],i,j,m;
  scanf("%d",&n);
  for(i=0; i<n; i++) scanf("%d",&a[i]);
  int cnt=0;
  for(i=0; i<n; i++) {
    m=i;
    for(j=i+1; j<n; j++) {
      if(a[j]<a[m]) m=j;
    }
    if(a[i]>a[m]) {
      int tmp=a[i];
      a[i]=a[m];
      a[m]=tmp;
      cnt++;
    }
  }
  for(i=0; i<n; i++) {
    if(i) printf(" ");
    printf("%d",a[i]);
  }
  printf("\n%d\n",cnt);
  return 0;
}



Measured memory_bytes: 2144
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>

//AOJ0077
#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(int x=from;x<to;x++)

using namespace std;


int main(void){

string ws;

	while(cin >> ws){
		if(cin.eof()) break;
		rep(i,ws.size()){
			string aat="";
			if(ws[i] == '@'){
				rep(j,ws[i+1]-'0') aat += ws[i+2];
				ws.replace(i, 3, aat);
			}
		}
		cout << ws <<endl;
	}
	
	return 0;
	
}

Measured memory_bytes: 1208
def resolve():

    n = int(input())
    mat = [[0] * 10 for _ in range(10)]

    for k in range(1, n+1):

        str_k = str(k)

        i = int(str_k[0])
        j = int(str_k[-1])

        mat[i][j] += 1

    ans = 0
    for i in range(10):
        for j in range(10):
            ans += mat[i][j] * mat[j][i]

    print(ans)
    
resolve()

Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		HashMap<Long, Integer> oriin = new HashMap<>();
		
		for(int i = 0; i < n; i++)
		{
			a[i] = sc.nextLong();
			oriin.put(a[i], (i%2));
		}
		
		int wr = 0;
		long[] b = a.clone();
		Arrays.sort(b);
		for(int i = 0; i < n; i++)
		{
			int ori = oriin.get(b[i]);
			if(ori != (i%2))
				wr++;
		}
		
		wr/=2;
		System.out.println(wr);
	}

}


Measured memory_bytes: 66096
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> v = new ArrayList<>();
        for (int i=0;i<n;i++){
            v.add(scanner.nextInt());
        }
        Collections.sort(v);
        int a = v.get(n/2 - 1);
        int b = v.get(n/2);
        System.out.println(b-a);


    }

}

Measured memory_bytes: 58452
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, 0, n){
        cin >> a[i];
    }
    reverse(a.begin(), a.end());
    int l = 0, r = n - 1;
    for(int i = 0; i < n; i++){
        if(i % 2 == 0){
            b[l++] = a[i];
        }else{
            b[r--] = a[i];
        }
    }
    // if(n % 2 == 0) reverse(b.begin(), b.end());
    for(int ii = 0; ii < b.size(); ii++){
        if(ii) cout << ' ';
        cout << b[ii];
    }
    cout << endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
#define REP(i,a,n) for(int (i)=(a); (i)<(int)(n); (i)++)
#define rep(i,n) REP(i,0,n)
#define vec vector 


int char_to_int(char c){
  switch(c){
    case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return 0;
  }
}


int main(){
  unsigned long a, b, c;
  cin >> a >> b >> c;
  
  unsigned long right, left;
  left = 4*a*b;
  
  long long tempo; tempo = abs(c-(a+b));
  right = tempo*tempo;
  
  if(left < right){
    cout << "Yes";
  }else{
    cout << "No";
  }
  
  
  
  
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int n,d,sum,avg;
    scanf("%d %d",&n,&d);
    sum = n / (d * 2 + 1);
    avg = n % (d * 2 + 1);
    if(avg > 0)
    {
        sum++;
    }
    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 128
#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(){
  string s;
  cin>>s;
  if(s=="ABC") cout<<"ARC"<<endl;
  else cout<<"ABC"<<endl;
}

Measured memory_bytes: 3624