akhauriyash/Code-Regression huggingface dataset:
from itertools import groupby

S = input()
N = int(input())

if len(S) == 1:
    print(N//2)
    exit()

if len(S) == 2 and S[0] == S[1]:
    print(N)
    exit()

check = S
check_num = sum(len(list(v))//2 for k, v in groupby(check))
check2 = S * 2
check2_num = sum(len(list(v))//2 for k, v in groupby(check2))
check3 = S * 3
check3_num = sum(len(list(v))//2 for k, v in groupby(check3))
check4 = S * 4
check4_num = sum(len(list(v))//2 for k, v in groupby(check4))

if N % 2 == 0:
    print(check2_num + (check4_num-check2_num)*(N//2-1))
else:
    print(check_num + (check3_num-check_num)*(N//2))
#ans = check_num*N + (check2_num-2*check_num)*(N-1)
#ans3 = check_num*3 + (check2_num-2*check_num)*(3-1)
#if check3_num == ans3:
#    print(ans)
#else:
#    print(round(N/2)*check_num + N//2*(check2_num-check_num))


Measured memory_bytes: 3064
#include <iostream>
#include <set>
using namespace std;
int main (void) {
    int n;
    set<int> s;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        s.insert(d);
    }

    cout << s.size() << endl;
    
    return 0;
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=list(map(int,input().split()))

candFriends=UnionFind(n)
elim=[0]*n

for i in range(m):
    a,b=list(map(lambda x:int(x)-1,input().split()))
    candFriends.union(a,b)
    
    elim[a]-=1
    elim[b]-=1

for i in range(k):
    c,d=list(map(lambda x:int(x)-1,input().split()))

    rootc=candFriends.find(c)
    rootd=candFriends.find(d)

    if rootc==rootd:
        elim[c]-=1
        elim[d]-=1


print(' '.join([str(candFriends.size(i)+elim[i]-1) for i in range(n)]))

Measured memory_bytes: 14996
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<k;i++){
        vector<int> b(n+1);
        for(int j=0;j<n;j++){
            int left=max(0,j-a[j]);
            int right=min(n,j+a[j]+1);
            b[left]++;b[right]--;
        }
        for(int j=0;j<n;j++){
            b[j+1]+=b[j];
        }
        b.pop_back();
        if(a==b) break;
        a=b;
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 4848
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,m,a,b,A[200001][2]={0},ans=0;
    cin>>n>>m;
    rep(i,n) A[i+1][0]++;
    A[1][1]=1;
    rep(i,m){
        cin>>a>>b;
        A[a][0]--,A[b][0]++;
        if(A[a][1]==1) A[b][1]=1;
        if(A[a][0]==0) A[a][1]=0;
    }
    rep(i,n) if(A[i+1][1]) ans++;
    cout<<ans;
}

Measured memory_bytes: 1792
n = int(input())
k = int(input())

def re_def(num, c, n=n, k=k):
    if c==n:
        return num
    for i in range(2):
        if i==0:
            num1 = re_def(num*2, c+1)
        else:
            num2 = re_def(num+k, c+1)
    return min([num1, num2])
print(re_def(1,0))

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    getline(cin,s);
    
    for(int i=0; i<s.length(); i++){
        int a = (int) s[i];
        if(65<=a && a<=90){
            a = a+(97-65);
            s[i] = (char) a;
        }else if(97<=a && a<=122){
            a = a-(97-65);
            s[i] = (char) a;
        }else continue;
    }
    
    cout<<s<<endl;
    
    return 0;
    
}


Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <cstdio>
#include <cmath>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using P1 = pair<int, P>;
#define FOR(t, a, b) for (int t = (a); t < (b); ++t)
#define REP(t, n) FOR(t, 0, n)

int main()
{
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int many = max(x, y);
    int ans = INT_MAX;

    int loop = 0;
    for (int i = 2 * many; i >= 0; i -= 2)
    {
        int tempans = 0;
        tempans += c * i;
        if (x > y)
        {
            tempans += a * loop;
            if (i / 2 < y)
            {
                tempans += b * (y - i / 2);
            }
        }
        else
        {
            tempans += b * loop;
            if (i / 2 < x)
            {
                tempans += a * (x - i / 2);
            }
        }
        if (ans > tempans)
        {
            ans = tempans;
        }
        loop++;
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n;
   cin >> n;
   map<string, long long> mp;
   long long ans = 0;
   for(int i = 0; i < n; i++) {
       string foo;
       cin >> foo;
       sort(foo.begin(), foo.end());
       ans += mp[foo];
       mp[foo]++;
   }
   cout << ans << endl;
}

Measured memory_bytes: 11432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (1e5) + 5;
bool done[N];
int memo[N];
int a[N], n;

int dp(int pos) {
	if (pos == n - 1) {
		return 0;
	}
	int &ret = memo[pos];
	if (done[pos]) return ret;
	done[pos] = 1;
	ret = 0;
	if (pos + 1 < n) {
		ret = abs(a[pos] - a[pos + 1]) + dp(pos + 1);
	}
	if (pos + 2 < n) {
		ret = min(ret, abs(a[pos] - a[pos + 2]) + dp(pos + 2));
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	memset(done, 0, sizeof done);
	printf("%d\n", dp(0));
	return 0;
}

Measured memory_bytes: 4224
// A. 

#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long LL;

int main(int argc, char *argv[])
{
	string s;
	cin >> s;
	int ans = 0, cnt = 0;
	for (char c : s) {
		if (c == 'S') {
			++cnt;
		} else {
			if (cnt > 0) {
				--cnt;
			} else {
				++ans;
			}
		}
	}
	ans += cnt;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

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

using namespace std;
using ll = long long;


const ll mod = 1000000007;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
// bool debug=false;

/*---------------------------------------------------*/

int main() {
  ll N;
  cin >> N;
  vector<pair<ll, ll>> data(N);
  for(int i = 0; i < N; i++) {
    cin >> data[i].second >> data[i].first;
  }
  sort(all(data));
  ll curr = 0;
  for(int i = 0; i < N; i++) {
    curr += data[i].second;
    if(curr <= data[i].first) continue;
    else {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3328
import java.util.*;

public class Main {
	final static int MMAX = 1000000;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(System.in);
		int s = Integer.parseInt(sc.next());
		sc.close();
		int ans = 0;
		long[] a = new long[MMAX+1];
		a[1] = s;
		HashMap<Long, Integer> amap = new HashMap<>();
		amap.put(a[1], 1);
		for(i=2;i<=MMAX;i++) {
			if(a[i-1]%2==0) {
				a[i] = a[i-1]/2;
			} else {
				a[i] = 3*a[i-1]+1; 
			}
			Integer ii = amap.get(a[i]);
			if(ii == null) {
				amap.put(a[i], i);
			} else {
				ans = i;
				break;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 30676
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
  double a,b;
  while(cin >>a>>b,a||b){
    double x;
    x = sqrt(b*b+a*a/4);
    printf("%.6lf\n",a*a+x*a*2);
  }
  return 0;
}

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

int main() {
  int a=0,ans=0;
  string t;
  cin >> t;
  for(int i=0;i<t.size();i++) {
    if(t.at(i)=='A') a++;
    else if(t.at(i)=='T') a++;
    else if(t.at(i)=='C') a++;
    else if(t.at(i)=='G') a++;
    else a=0;
    ans=max(ans,a);
  };
  cout << ans << endl;
}

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

#define rep(i,beg,end)   for (auto i=(beg);i<(end);i++)
#define rrep(i,beg,end)   for (auto i=(beg);i>=(end);i--)
#define all(cont)           begin(cont), end(cont)
#define rall(cont)           rbegin(cont), rend(cont)
using ll = long long;
using vi = vector<ll>;
const ll INFMAX = LLONG_MAX;
const ll INFMIN = LLONG_MIN;
const ll MOD = 1000000007;


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b;
	cin >> a >> b;
	b--;
	ll c = 0;
	while (b > 0) {
		b -= a - 1;
		c++;
	}
	cout << c << endl;


	return 0;
}


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

int main(){
	// INPUT
	int num_digit, num_input, digit_substituted, num_substituted;
	cin >> num_digit >> num_input;
	
	vector<int> num_output(num_digit);
	vector<bool> judge_substituted(num_digit);
	vector<int> digit_const(num_input), num_const(num_input);
	for(int i=0;i<num_input;i++){
		cin >> digit_const.at(i) >> num_const.at(i);
	}
	/*
	for(int i=0;i<num_input;i++){
		cout << digit_const.at(i) << " "<< num_const.at(i) << endl;
	}
	*/
	// END of INPUT
	
	// Judge whether number of constaint is zero or not.
	if(num_input==0){
		if(num_digit==1){
			cout << 0 << endl;
			return 0;
		}else if(num_digit == 2){
			cout << 10 << endl;
			return 0;
		}else if(num_digit == 3){
			cout << 100 << endl;
			return 0;
		}
	}
	
	// Exception when number of digit >=2 & the 1st digit is constrained at 0
	if(num_digit>1){
		for(int i=0;i<num_input;i++){
			if(digit_const.at(i)==1 && num_const.at(i)==0){
				cout << -1 << endl;
				return 0;
			}
		}
	}	
	// Initialization of substitution judgement vector
	// and number of output
	for(int i=0;i<num_digit;i++){
		judge_substituted.at(i)=false;
		num_output.at(i) = 0;
	}
	
	// Substitution of number
	for(int i=0;i<num_input;i++){
		digit_substituted = digit_const.at(i)-1;
		num_substituted = num_const.at(i);
		
		// Check whether the constrained digit is already filled or not.
		if(!judge_substituted.at(digit_substituted)){
			num_output.at(digit_substituted) = num_substituted;
			judge_substituted.at(digit_substituted) = true;
		}else if(num_output.at(digit_substituted)!=num_substituted){
			cout << -1 << endl;
			return 0;
		}
		
	}
	
	
	// Check whether the 1st digit is already substituted or not
	if(!judge_substituted.at(0)){
		num_output.at(0) = 1;
	}
	
	for(int i=0;i<num_digit;i++){
		cout << num_output.at(i);
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int inf = 1000000000; //10e9
 
int main() {
    
    int N, M, C;
    cin >> N >> M >> C;

    vector<int> B(M);
    vector<vector<int>> A(N, vector<int>(M));
    for(int i=0; i<M; i++){
        cin >> B.at(i);
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> A.at(i).at(j);
        }
    }

    int count = 0;
    
    for(int i=0; i<N; i++){
        int sum = 0;
        for(int j=0; j<M; j++){
            sum += A.at(i).at(j)*B.at(j);
        }
        sum += C;
        if(sum > 0){
            count++;
        }
    }
    
    cout << count << endl;

    return 0;
}

Measured memory_bytes: 3608
x, y = map(int, input().split())
lst = []
ans = 'No'

for i in range(x):
  lst.append(2)

for i in range(x):
  if sum(lst) == y:
    ans = 'Yes'
    break
  lst[i] = 4
    
if sum(lst) == y:
    ans = 'Yes'
    
print(ans)

Measured memory_bytes: 62900
using System;
public class Hello
{
    public static void Main()
    {
        // Your code here!
        string[] input = Console.ReadLine().Split(' ');
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);
        int x = int.Parse(input[2]);
        
        if(x > a + b||x < a)
        {
            Console.WriteLine("NO");
        }
        else
        {
            Console.WriteLine("YES");
        }
    }
}

Measured memory_bytes: 13140
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		double sum = 0;
		for(int i = 0; i < n; i++)
			sum += (1.0 / sc.nextInt());
		
		sum = 1.0 / sum;
		System.out.println(sum);
	}
}


Measured memory_bytes: 25556
package main

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

func main() {
	X := nextInt()

	n := X / 100
	r := X % 100

	if r <= n*5 {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


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

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()
 
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  string s;
  while(getline(cin, s)) {
    if(s == "END OF INPUT") break;

    int cnt = 0;
    for(int i = 0; i < s.size(); i++) {
      char c = s[i];
      if(('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z')) cnt++;
      else {
        cout << cnt;
        cnt = 0;
      }
    }
    cout << cnt << endl;
  }
}

Measured memory_bytes: 1188
N = int(input())
L= list(map(int, input().split()))
Ls = list(set(L))
res=[]
for i in range(len(Ls)):
  for j in range(i+1,len(Ls)):
    for k in range(j+1,len(Ls)):
      tmp=[Ls[i],Ls[j],Ls[k]]
      if sum(tmp) > 2*max(tmp):
        res.append(tmp)
        
c=0
for i in range(len(res)):
  ctmp=L.count(res[i][0])*L.count(res[i][1])*L.count(res[i][2])
  c+=ctmp
print(c)

Measured memory_bytes: 25492
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		UL L; cin >> L;
		vector<ULL> A(L); rep(i, L) cin >> A[i];
		vector<ULL> dp[5]; rep(i, 5) dp[i].resize(L + 1);
		rep(j, 5) dp[j][0] = 0;
		rep(l, L) {
			dp[0][l + 1] = dp[0][l] + A[l];

			if (A[l] < 2) dp[1][l + 1] = dp[1][l] + 2 - A[l];
			else dp[1][l + 1] = dp[1][l] + A[l] % 2;
			dp[1][l + 1] = min(dp[0][l + 1], dp[1][l + 1]);

			if (A[l] < 1) dp[2][l + 1] = dp[2][l] + 1;
			else dp[2][l + 1] = dp[2][l] + (A[l] - 1) % 2;
			dp[2][l + 1] = min(dp[1][l + 1], dp[2][l + 1]);

			if (A[l] < 2) dp[3][l + 1] = dp[3][l] + 2 - A[l];
			else dp[3][l + 1] = dp[3][l] + A[l] % 2;
			dp[3][l + 1] = min(dp[2][l + 1], dp[3][l + 1]);

			dp[4][l + 1] = min(dp[3][l + 1], dp[4][l] + A[l]);
		}

		cout << dp[4][L] << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>fib(n+1); fib.at(0)=fib.at(1)=1;
	for(int i=2;i<=n;++i){
		fib.at(i)=fib.at(i-1)+fib.at(i-2);
	}
	cout<<fib.at(n)<<"\n"s;
}


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

const ll inf = 1e10;

int main() {
	ll n;
	cin >> n;
	vector<ll> x(n);
	ll ans = inf;
	for (ll i = 0; i < n; ++i)cin >> x[i];
	for (ll t = 0; t < 100; ++t) {
		ll preans = 0;
		for (ll i = 0; i < n; ++i) {
			preans += pow(x[i] - t, 2);
		}
		ans = min(ans, preans);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=4e5+5;
long long n,k,a[N],b[N],l[M],r[M],lt[N],rt[N];
void init()
{
	for (int i=0;i<=n;i++) 
	{
		b[i]=lt[i]=rt[i]=0;
	}
}
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	while (k--)
	{
		bool flag=0;
		init();
		for (int i=1;i<=n;i++)  
		{
			l[i]=max(0LL,i-a[i]);
			r[i]=min(n+1,i+a[i]+1);
			lt[l[i]]++;
			rt[r[i]]++;
		}	
		for (int i=1;i<=n;i++)
		{
			lt[i]=lt[i-1]+lt[i];
			rt[i]=rt[i-1]+rt[i];
			b[i]=lt[i]-rt[i];
		}	
		for (int i=1;i<=n;i++) if (a[i]!=b[i]) flag=1;
		for (int i=1;i<=n;i++) if (a[i]!=b[i]) a[i]=b[i];
		if (flag==0) break;
	}
	for (int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}

Measured memory_bytes: 13012
import java.util.*;
 
public class Main{
public static void main(String[] args){
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
int l=sc.nextInt();
String[] s=new String[n];
for(int i=0; i<n; i++){
s[i]=sc.next();}
 
Arrays.sort(s);
 
for(int i=0; i<n; i++){
System.out.print(s[i]);}
 
 
}}


Measured memory_bytes: 9808
#include <stdio.h>
#include <string.h>
#define N 500000

typedef struct{
  int key, left, right;
}Node;

Node tree[N+1];
int size;

void insert(int x){
  int p = 0;
  while(1){
    if(x < tree[p].key){
      if(tree[p].left == -1){
        tree[p].left = size;
        tree[size++].key = x;
        break;
      }else p = tree[p].left;
    }else{
      if(tree[p].right == -1){
        tree[p].right = size;
        tree[size++].key = x;
        break;
      }else p = tree[p].right;
    }
  }
}

void inorder(int p){
  if(tree[p].left != -1) inorder(tree[p].left);
  printf(" %d", tree[p].key);
  if(tree[p].right != -1) inorder(tree[p].right);
}

void preorder(int p){
  printf(" %d", tree[p].key);
  if(tree[p].left != -1) preorder(tree[p].left);
  if(tree[p].right != -1) preorder(tree[p].right);
}

int find(int p, int x){
  if(tree[p].key == x) return 1;
  if(x < tree[p].key && tree[p].left != -1) if(find(tree[p].left, x)) return 1;
  if(tree[p].key < x && tree[p].right != -1) if(find(tree[p].right, x)) return 1;
  return 0;
}

main(){
  int n, i, first;
  first = 1;
  scanf("%d", &n);
  for(i=0;i<=n;i++) tree[i].key = tree[i].left = tree[i].right = -1;
  size = 0;
  while(n--){
    char str[100];
    scanf("%s", str);
    if(!strcmp(str, "insert")){
      int in;
      scanf("%d", &in);
      if(first){
        tree[size++].key = in;
        first = 0;
      }
      else insert(in);
    }else if(!strcmp(str, "find")){
      int in;
      scanf("%d", &in);
      printf("%s\n", (find(0, in) ? "yes" : "no"));
    }else{
      inorder(0);
      printf("\n");
      preorder(0);
      printf("\n");
    }
  }
  return 0;
}



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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            MainStream();
        }
        static void MainStream()
        {
            Scan sc = new Scan();
            write wr = new write();

            int n = sc.intarr[0];
            int[] ws = sc.intarr;

            int small = ws[0];
            int big = ws[n-1];

            int back_index = 2;

            for (int i=1; i<=n-back_index; i++)
            {
                if(small <= big)
                {
                    small += ws[i];
                }
                else
                {
                    big += ws[n-back_index];
                    back_index++;
                    i--;
                }
            }

            wr.wri(Math.Abs(big - small));
        }


    }

    class Scan
    {
        public string str => Console.ReadLine();

        public string[] strarr => str.Split(' ');

        public long[] longarr => strarr.Select(long.Parse).ToArray();
        public int[] intarr => strarr.Select(int.Parse).ToArray();
        public char[] chararr => str.ToArray();


    }



    class write
    {
        public void wri<Type>(Type x)
        {
            Console.WriteLine(x);
        }
    }

    class Method
    {
        static public int max(params int[] nums)
        {

            int maxx = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                maxx = Math.Max(maxx, nums[i]);
            }
            return maxx;
        }
    }
}


Measured memory_bytes: 13396
m, d = [int(i) for i in input().split()]
counter = 0
for i in range(1, m + 1):
    for j in range(2, 10):
        for k in range(2, 10):
            day = 10 * j + k
            if day > d:
                continue
            if i == j * k:
                counter += 1
print(counter)

Measured memory_bytes: 3064
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
d=m.max()
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(d+1)or-1)

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

#define gc( ) std::getchar( )
#define pc( i ) std::putchar( i )

template < typename T >
inline T read( )
{
	register T x = 0;
	register char ch = gc( );
	register bool f = 0;
	while( !std::isdigit( ch ) )
	{
		f = ( ch == '-' );
		ch = gc( );
	}
	while( std::isdigit( ch ) )
	{
		x = x * 10 + ( ch - '0' );
		ch = gc( );
	}
	return f ? -x : x;
}

template < typename T >
void print( T x )
{
	if( x < 0 )
	{
		x = -x;
		pc( '-' );
	}
	if( x < 10 )
	{
		pc( x + 48 );
		return;
	}
	print < T > ( x / 10 );
	pc( x % 10 + 48 );
	return ;
}

namespace Solution
{
#define Rep( i, j, k ) for( int i = j; i >= k; --i )
#define rdi( ) read < int > ( )
#define rdl( ) read < long long > ( )
#define pti( i ) print < int > ( i ), putchar( ' ' )
#define ptl( i ) print < long long > ( i ), putchar( ' ' )
#define For( i, j, k ) for( int i = j; i <= k; ++i )
	const int Maxn = 7;
	char c[ Maxn ][ Maxn ];
	int n, m, k, cnt, ans;
	std::vector < int > v;
	bool b[ 13 ];
	inline char gck( )
	{
		char ch = gc( );
		while( ch == ' ' || ch == '\n' || ch == '\r' )
			ch = gc( );
		return ch;
	}
	void dfs( int cc )
	{
		if( cc == n + m )
		{
			cnt = 0;
			for( int i = 1; i <= 12; ++i )
				b[ i ] = 0;
			for( std::vector <int>::iterator i = v.begin( ); i != v.end( ); ++i )
				b[ *i ] = 1;
			For( i, 1, n )
				For( j, 1, m )
					cnt += b[ i ] && b[ j + n ] && c[ i ][ j ] == '#';
			if( cnt == k )
				ans++;
			return;
		}
		v.push_back( cc + 1 );
		dfs( cc + 1 );
		v.pop_back( );
		dfs( cc + 1 );
		return;
	}
	void fakemain( )
	{
		n = rdi( );
		m = rdi( );
		k = rdi( );
		For( i, 1, n )
			For( j, 1, m )
				c[ i ][ j ] = gck( );
		dfs( 0 ); 
		pti( ans ); 
		return;
	}

} // namespace Solution

int main( int argc, char* argv[] )
{
	Solution::fakemain( );
	return 0;
}


Measured memory_bytes: 3640
#include<stdio.h>
int main()
{
        int a[5],b[5],hit=0,brow=0;
        int i,j,k;
        while(scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3])!=EOF)
        {
                scanf("%d %d %d %d",&b[0],&b[1],&b[2],&b[3]);
                for(i=0;i<4;i++)
                {
                        if(a[i]==b[i])
                        {
                                hit+=1;
                                a[i]=1000;
                                b[i]=1500;
                        }
                }
                for(i=0;i<4;i++)
                {
                        for(j=0;j<4;j++)
                        {
                                if(a[i]==b[j])
                                {
                                        brow+=1;
                                        a[i]=1000;
                                        b[j]=1500;
                                }
                        }
                }
                printf("%d %d\n",hit,brow);
                for(i=0;i<5;i++)
                {
                        a[i]=0;b[i]=0;
                }
                hit=0;brow=0;
        }
        return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

int main() {
	int m, n, k;
	cin >> m >> n >> k;
	VVI map_j(n+1, VI(m+1, 0));
	VVI map_o(n+1, VI(m+1, 0));
	VVI map_i(n+1, VI(m+1, 0));
	VVI ans;
	for(int y=1;y<=m;y++) {
		for(int x=1;x<=n;x++) {
			char temp;
			cin >> temp;
			map_j[x][y] = map_j[x-1][y];
			map_o[x][y] = map_o[x-1][y];
			map_i[x][y] = map_i[x-1][y];
			switch(temp) {
			case 'J':
				map_j[x][y] = 1 + map_j[x-1][y];
				break;
			case 'O':
				map_o[x][y] = 1 + map_o[x-1][y];
				break;
			case 'I':
				map_i[x][y] = 1 + map_i[x-1][y];
				break;
			}
		}
	}
	for(int x=1;x<=n;x++) {
		for(int y=1;y<=m;y++) {
			map_j[x][y] += map_j[x][y-1];
			map_o[x][y] += map_o[x][y-1];
			map_i[x][y] += map_i[x][y-1];
		}
	}
	/*for(int y=0;y<=m;y++) {
		for(int x=0;x<=n;x++) {
			cout << map_j[x][y] << " ";
		}
		cout << endl;
		}*/
	//return 0;
	for(int i=0;i<k;i++) {
		int x0, y0, x1, y1;
		cin >> y0 >> x0 >> y1 >> x1;
		int ans_j = map_j[x1][y1] - map_j[x1][y0-1] - map_j[x0-1][y1] + map_j[x0-1][y0-1];
		int ans_o = map_o[x1][y1] - map_o[x1][y0-1] - map_o[x0-1][y1] + map_o[x0-1][y0-1];
		int ans_i = map_i[x1][y1] - map_i[x1][y0-1] - map_i[x0-1][y1] + map_i[x0-1][y0-1];
		VI e_ans;
		e_ans.push_back(ans_j);
		e_ans.push_back(ans_o);
		e_ans.push_back(ans_i);
		ans.push_back(e_ans);
	}
	for(auto it = ans.begin();it != ans.end();it++) {
		cout << (*it)[0] << " ";
		cout << (*it)[1] << " ";
		cout << (*it)[2] << endl;
	}
	return 0;
}

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

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}
inline int readopt()
{
    char c=Get();
    while(c!='+'&&c!='-') c=Get();
    return c;
}

typedef long long LL;
int num,n,k;
char opt;
LL f[2][3];

inline LL mymax(const LL &x,const LL &y){return x>y?x:y;}

int main()
{
    n=read();
    f[k=0][0]=read();
    f[0][1]=f[0][2]=-(1ll<<60);
    for(int i=1;i<n;i++,k^=1)
    {
        opt=readopt();num=read();
        if(opt=='+')
        {
            f[k^1][0]=mymax(mymax(f[k][0],f[k][1]),f[k][2])+num;  //原地转移 或 拆1/2个括号
            f[k^1][1]=mymax(f[k][1],f[k][2])-num;  //原地转移 或 拆1个括号
            f[k^1][2]=f[k][2]+num;  //原地转移
        }
        else
        {
            f[k^1][0]=mymax(mymax(f[k][0],f[k][1]),f[k][2])-num;  //原地转移 或 拆1/2个括号
            f[k^1][1]=mymax(mymax(f[k][1],f[k][2])+num,f[k][0]-num);  //原地转移 或 拆1个括号 或 添1个括号
            f[k^1][1]=mymax(mymax(f[k][1]-num,f[k][2]-num),f[k^1][1]);  //拆1/2个括号又添1个括号
            f[k^1][2]=mymax(f[k][2]-num,f[k][1]+num);  //原地转移 或 添1个括号
            f[k^1][2]=mymax(f[k][2]+num,f[k^1][2]);  //拆1个括号又添1个括号
        }
    }
    LL ans=mymax(mymax(f[k][0],f[k][1]),f[k][2]);
    printf("%lld\n",ans);
    return 0;
}

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

int main() {
  int n, i, ans = 1;
  cin >> n;
  
  vector<int> d(n);
  for(i = 0; i < n; i++){
    cin >> d.at(i);
  }
  
  sort(d.begin(), d.end());
  
  for(i = 1; i < n; i++){
    if(d.at(i - 1) != d.at(i)){
      ans++;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string S,T;
 	cin>>S>>T;
  	for(int i=0;i<S.length();++i){
		if(S[i]!=T[i]){
			cout<<"No\n";
			return 0;
		}
    }
  	cout<<"Yes\n";
}

Measured memory_bytes: 3624
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;

int to[100005],nxt[100005],hed[100005] = {0},ec = 0;
void add_edge(int f,int t){
	ec ++; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;
}

int n,k,a[100005],ans = 0;

int dfs(int v,int dep){
	int tmp = dep;
	for(int i = hed[v];i;i = nxt[i]){
		tmp = max(tmp,dfs(to[i],dep + 1));
	}
	if(a[v] != 1 && tmp - dep == k - 1){
		a[v] = 1;
		ans ++;
		return -1;
	}
	return tmp;
}

int main(){
	scanf("%d %d",&n,&k);
	scanf("%d",&a[1]); if(a[1] != 1) ans ++; a[1] = 1;
	for(int i = 2;i <= n;i ++){
		scanf("%d",&a[i]);
		add_edge(a[i],i);
	}
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}

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

int main(){
  int n;
  long long a[100000];
  long long sum;
  long long tmp;
  int flag=0;
  int zflag=0;
  scanf("%d\n",&n);
  for(int i=0;i<n;i++) scanf("%lld",&a[i]);
  sum=llabs(a[0]);
  tmp=llabs(a[0]);
  if(a[0]<0) flag=1;
  if(a[0]==0) zflag=1;
  for(int i=1;i<n;i++) {
    sum+=llabs(a[i]);
    if(llabs(a[i])<tmp) tmp=llabs(a[i]);
    if(a[i]<0) flag=(flag+1)%2;
    if(a[i]==0) zflag=1;
  }
  if(zflag||flag) sum-=tmp*2;
  printf("%lld",sum);
  return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main(){
  int N;
  vector<int> A;
  cin >> N;

  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    A.push_back(a);
  }

  sort(A.begin(),A.end());
  int ans = A[N-1] - A[0];

  //cout << A[0] <<endl;
  cout << ans <<endl;


  return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=input()
ans=[]
def f(i,j):
    if i==0:
        print(" ".join(map(str,ans[::-1])))
        return
    if j>i:
        j=i
    while s[i-j]=="1":
        j-=1
    if j==0:
        print(-1)
        return
    ans.append(j)
    f(i-j,m)
f(n,m)

Measured memory_bytes: 96964
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define gr vector<vector<pii>>
#define fi first
#define se second
#define MOD 998244353
#define MAXN (int)(1E6 + 111)
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    cout << (n + 1) / 2 << endl;
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define int long long

typedef pair<int, int> ii;

int n, sum;

vector<pair<int, ii>> ans;

priority_queue<int> pq;

signed main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int h, p;
        cin >> h >> p;
        ans.pb({h + p, {p, h}});
    }
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++) {
        pq.push(ans[i].se.fi);
        sum += ans[i].se.fi;
        if(sum > ans[i].fi) {
            while(!pq.empty() && sum > ans[i].fi) {
                sum -= pq.top();
                pq.pop();
            }
        }
    }
    cout << pq.size();
}


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

dic={}
for _ in range(N):
    a,b=list(map(int,input().split()))
    for i in range(-1,2):
        for j in range(-1,2):
            if (a+i)<=1 or b+j<=1 or a+i>=H or b+j >=W:
                continue
            s=(a+i)*W+b+j
            if dic.get(s,0)==0:
                dic[s]=1
            else:
                dic[s]+=1
arr=[0 for i in range(10)]
for v in dic.values():
    arr[v]+=1
arr[0]=(H-2)*(W-2)-sum(arr)
for x in arr:
    print(x)

Measured memory_bytes: 102700
/**
     **author : _KMS_
     **created : 05-03-2020
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =6e5,MOD=1e9+7;
typedef long long ll;
string s,p="",q;
map<ll,ll>mp;
ll k;
int main() {
      
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n;
   cin>>n>>k;
   for(int i=0;i<n;i++)
   {
         ll a,b;
         cin>>a>>b;
         mp[a]+=b;
   }
   ll tot=0;
   for(auto x : mp)
   {
         tot+=x.second;
         if(tot>=k)
         {
               cout<<x.first<<endl;
               return 0;
         }
   }
  
   
   return 0;
}

Measured memory_bytes: 4224
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int L, R, D; cin>>L>>R>>D;
  int ans=0;
  for(int i=L;i<=R;++i) {
    if(i%D==0) ans++;
  }
  cout<<ans<<endl;
}



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

using namespace std;


#define MAXN 100001
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n, a[MAXN], ans = 0;
  vector <ll> sol;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a, a+n);
  for (int i = n-1; i >= 0 && sol.size()<2; --i) {
    if (a[i]==a[i-1]) {
      --i;
      sol.push_back(a[i]);
    }
  }
  if (sol.size()==2) {
    ans = sol[0]*sol[1];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define fr(i,n) for(int i=0;i<(n);i++)
#define Fr(i,n) for(int i=0;i++<(n);)
#define ifr(i,n) for(int i=(n)-1;i>=0;i--)
#define iFr(i,n) for(int i=(n);i>0;i--)

int main(){
    string a;
    cin>>a;
    int n=a.length(),s=1,m[200010]={},t=-1,u,ka;
    vector<int> v[26];
    bool f[26]={},g;
    fr(i,n) v[a[i]-'a'].pb(i);
    fr(i,26) v[i].pb(n);
    m[n]=0;
    ifr(i,n){
        m[i]=s;
        f[a[i]-'a']=1;
        g=1;
        fr(j,26) g=g&&f[j];
        if(g){
            s++;
            fr(j,26) f[j]=0;
        }
    }
    u=s;
    fr(i,s){
        fr(j,26){
            ka=(*upper_bound(v[j].begin(),v[j].end(),t));
            if(m[ka]==u-1){
                cout<<(char)('a'+j);
                u--;
                t=ka;
                break;
            }
        }
    }
}

Measured memory_bytes: 2180
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;



signed main(){
    IOS;
    int k;
    string s;
    cin >> k >> s;
    for (int i = 0; i < min((int)s.length(), k); i++)
        cout << s[i];
    if (s.length() > k) cout << "...";
    return 0;
}

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

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

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x3 = y1 - y2 + x2;
    int y3 = x2 - x1 + y2;
    int x4 = y2 - y3 + x3;
    int y4 = x3 - x2 + y3;

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << "\n";

    return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int a = scanner.nextInt(), b = scanner.nextInt();
			int n = b - a;
			System.out.println(n * (n - 1) / 2 - a);
		}
	}
}


Measured memory_bytes: 35564
#include <iostream>
#include <map>
#include <functional>
#include <vector>
#include <cmath>

class Factoriser
{
    std::vector<int> factors;

public:
    using map_type = std::map<int, int>;
    
    Factoriser(int N)
    {
        factors.resize(N+1, 0);
        int sqrN = static_cast<int>(std::sqrt(N));

        for (int i = 2; i <= sqrN; ++i)
        {
            if (factors[i] == 0)
            {
                for (int j = i * 2; j <= N; j += i)
                {
                    if (factors[j] == 0)
                    {
                        factors[j] = i;
                    }
                }
            }
        }
    }

    map_type Factorise(int M) const
    {
        map_type P;
        int mm = M;

        while (factors[mm])
        {
            ++P[factors[mm]];
            mm /= factors[mm];
        }

        if (mm >= 2) ++P[mm];
        return P;
    }
    
    bool IsPrime(int M) const
    {
        return factors[M] == 0;
    }
};


///////////////////////////////////////////////////

using plist_citr_t = Factoriser::map_type::const_iterator;
using vi = std::vector<int>;

bool contains_dfs(int a, std::function<bool(int)> exists, int cur, plist_citr_t it, plist_citr_t last)
{
    if (cur == a) return false;
    if (it == last)  return exists(cur);

    auto [p, m] = *it++;
    for (int i = 0; i <= m; ++i)
    {
        bool r = contains_dfs(a, exists, cur, it, last);
        if (r) return true;
        cur *= p;
    }
    return false;
}

bool contains(int a, std::function<bool(int)> exists, const Factoriser &fac)
{
    auto plist = fac.Factorise(a);
    return contains_dfs(a, exists, 1, plist.begin(), plist.end());
}

int main()
{
    int N;
    std::map<int, int> A;
    std::cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a;
        std::cin >> a;
        ++A[a];
    }

    constexpr int MAX_A = 1000000;
    std::vector<int> kusi(MAX_A+1, 0);
    for (auto [a, i] : A)
        kusi[a] = i;
        
    Factoriser fac(MAX_A);

    int ans = 0;
    if (kusi[1] > 1)
    {
        ans = 0;
    }
    else if (kusi[1] == 1)
    {
        ans = 1;
    }
    else
    {
        for (auto [a, i] : A)
        {
            // auto exist = [&A](int a){ return A.count(a) > 0; };
            auto exist = [&kusi](int a){ return kusi[a] > 0; };
            if (i == 1 && !contains(a, exist, fac)) ++ans;
        }
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 20340
#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
using namespace std;

int main(void) {
  string str;   // 入力される原文
  getline(cin, str);
  stringstream sstr(str);  // sstrをstrで初期化
  vector<string> word;   // 出てきた単語を重複しないように保持するためのvecor
  vector<int> count;   // 出てきた単語の回数を保持するためのvector
  bool check;   // 出てきた単語が既出かどうかを判断するためのbool
  
  while(sstr >> str) {   // sstrからstrに単語ごとに代入される。strは毎回リセットされる。
    check = false;
    for(int i = 0; i < word.size(); ++i) {
      if(str == word[i]) {
        ++count[i];
        check = true;
      }
    }
    if(! check) {
      word.push_back(str);
      count.push_back(1);
    }
  }
  
  int often = 0;
  for(int i = 0; i < count.size(); ++i) {
    if(count[often] < count[i]) {
      often = i;
    }
  }
  cout << word[often] << " ";
  
  string longest = "";
  for(int i = 0; i < word.size(); ++i) {
    if(longest.size() < word[i].size()) {
      longest = word[i];
    }
  }
  cout << longest << endl;
}


Measured memory_bytes: 3116
import java.util.Scanner;

public class Main {

    public static class Knapsack01 {

        int capacity;
        int n;
        int[] cost;
        int[] value;

        public Knapsack01(int n, int capacity, int[] cost, int[] value) {
            this.n = n;
            this.capacity = capacity;
            this.cost = cost;
            this.value = value;
        }

        int solve() {
            int[] rowCurr = new int[capacity + 1];
            for (int numOfItems = 1; numOfItems <= n; numOfItems++) {
                for (int weight = capacity; weight >= cost[numOfItems - 1]; weight--) {
                    if (weight >= cost[numOfItems - 1]) {
                        rowCurr[weight] = Math.max(
                                rowCurr[weight - cost[numOfItems - 1]] + value[numOfItems - 1],
                                rowCurr[weight]);
                    }
                }
            }
            return rowCurr[capacity];
        }

    }

    static Scanner in = new Scanner(System.in);

    static Knapsack01 readCase() {
        while (in.hasNext()) {
            int n = in.nextInt();
            int capacity = in.nextInt();
            int[] cost = new int[n];
            int[] value = new int[n];
            for (int i = 0; i < n; i++) {
                value[i] = in.nextInt();
                cost[i] = in.nextInt();
            }
            Knapsack01 knapsack01 = new Knapsack01(n, capacity, cost, value);
            return knapsack01;
        }
        return null;
    }

    public static void main(String[] args) {
        Knapsack01 knapsack01 = null;
        while ((knapsack01 = readCase()) != null) {
            System.out.println(knapsack01.solve());
        }
    }

}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int A, B;
	cin >> A >> B;
	char s[100][100];
	int ca = 0, cb = 0;
	REP(i, 100){
		REP(j, 100){
			if(i < 50) s[i][j] = '.';
			else s[i][j] = '#';
		}
	}
	A--; B--;
	REP(i, 50){
		FOR(j, 1, 99){
			if(B != 0 && (i+j)%3 == 0){
				s[i][j] = '#';
				B--;
			}
		}
	}
	for(int i = 99;i >= 50;i--){
		FOR(j, 1, 99){
			if(A != 0 && (i+j)%3 == 0){
				s[i][j] = '.';
				A--;
			}
		}
	}
	cout << 100 << " " << 100 << endl;
	REP(i, 100){
		REP(j, 100){
			cout << s[i][j];
		}
		cout << endl;
	}
}

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

int main() {

	unsigned int H;
	unsigned int W;
	unsigned int N;
	cin >> H;
	cin >> W;
	cin >> N;

	unsigned int ans;
	ans = N / max(H, W);
	if (N % max(H, W) == 0) {
		cout << ans << endl;
	}
	else {
		ans += 1;
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#coding=utf-8

def check_circle(s):
    x = str(s)
    flag = True
    for i in range(int(len(x) / 2)):
         if x[i] != x[-1 * (i + 1)]:
              flag = False
    return flag

def solve(N, M):
    return abs((N - 2) * (M - 2))
    if N == 1:
        return N * M - 2
    if M == 1:
        return N * M - 2
    return N * M - 4
    if N == M and N == 1:
        return 1
    if N == M and N == 0:
        return 0

    if N >= 2:
        tate = 2 * (M - 2)
    elif N == 1:
        tate = M - 2
    if M >= 2:
        yoko = 2 * (N - 2)
    elif M == 1:
        yoko == M - 2
    else:
        yoko = N - 2
    ans = tate + yoko
    return ans

def main():
    N, M = input().split(' ')
    print(solve(int(N), int(M)))


if __name__ == '__main__':
    main()



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

int main() {
    int a, b, c;
    int x, y, z;
    cin >> x >> y >> z;
    a = x;
    x = y;
    y = a;
    //2 1 3
    //3 1 2
    b = x;
    x = z;
    z = b;
    cout << x << " " << y  << " " << z;

    return 0;
}


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

typedef long long int ll ;

ll gcd(ll aaa,ll bbb) {
    if(bbb==0) {
        return aaa;
    }
    return gcd(bbb,aaa%bbb);
}

ll lcm(ll m,ll n)
{
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {

	long A,B,K,ans,count=0;
	cin >> A >> B >> K;
	for(long i = min(A,B); i > 0; i--) {
		if(A % i == 0 && B % i == 0) {
			ans = i;
			count++;
		}
		if(K == count) {
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>

int main(int argc, char const *argv[]) {
  int W, H, x, y, r;
  scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
  if(x-r<0){
    printf("No\n");
  }
  else if(x+r>W){
    printf("No\n");
  }
  else if(y-r<0){
    printf("No\n");
  }
  else if(y+r>H){
    printf("No\n");
  }
  else{
    printf("Yes\n");
  }
  return 0;
}

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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)

signed main () {
  // 03:58:00
  cin.tie(0);
  cout << setprecision(10);

  map<char, int> a;
  int n;
  cin >> n;
  string s;
  REP(i, n) {
    cin >> s;
    a[s[0]]++;
  }

  vector<int> b;
  b.pb(a['M']);
  b.pb(a['A']);
  b.pb(a['R']);
  b.pb(a['C']);
  b.pb(a['H']);

  int ans = 0;
  
  REP(i, 3) {
    FOR(j, i+1, 4) {
      FOR(k, j+1, 5) {
        ans += b[i] * b[j] * b[k];
      }
    }
  }

  cout << ans << endl;
}


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

using namespace std;

#define pb push_back
const int maxi=1e6+7;
int a[maxi];
int n;
string s;
int cnt1[maxi],cnt[maxi];
int ma1,mb1,ma2,mb2;
map<int,int> mp,mp1;
int main()
{
    cin>>n;

    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (i&1)
            cnt[i/2+1]=a[i];
        else
            cnt1[i/2]=a[i];
    }

    for (int i=1;i<=n/2;i++)
    {
        mp[cnt[i]]++;
        mp1[cnt1[i]]++;
        if (mp[ma1]<mp[cnt[i]])
        {
            ma2=ma1;
            ma1=cnt[i];
        } else
        if (mp[ma2]<mp[cnt[i]] && ma1!=cnt[i])
            ma2=cnt[i];

         if (mp1[mb1]<mp1[cnt1[i]])
        {
            mb2=mb1;
            mb1=cnt1[i];
        } else
        if (mp1[mb2]<mp1[cnt1[i]] && mb1!=cnt1[i])
            mb2=cnt1[i];

    }

    if (ma1!=mb1) printf("%d\n",n-mp[ma1]-mp1[mb1]); else
        printf("%d",n-max(mp[ma1]+mp1[mb2],mp[ma2]+mp1[mb1]));

    return 0;
}


Measured memory_bytes: 13312
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a,int b){return a < b ? a : b;}

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for(i = 1; i <= n; i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }
  head = 1;
  tail = n + 1;

  while(head != tail){
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;

    if(u.t > 0) enqueue(u);
    else {
      printf("%s %d\n",u.name, elaps);
    }
  }
  return 0;
}





Measured memory_bytes: 11884