akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int L = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		while(A > 0 || B > 0){
			A -= C;
			B -= D;
			L--;
		}
		System.out.println(L);

	}

}

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


#define SWAP(type,a,b) { type work = a; a = b; b = work; }

/*
    基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
    return array[(begin + end) / 2];  // 中央の要素を基準値とする
}


/*
    クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array,char results[][5], int begin, int end)
{
    long int pivot = select_pivot( array, begin, end );
    int i = begin;
    int j = end;
    char temp[5];

    while( 1 ){
        while( array[i] < pivot ){ ++i; }  // 基準値以上の値が見つかるまで右方向へ進めていく
        while( array[j] > pivot ){ --j; }  // 基準値以下の値が見つかるまで左方向へ進めていく

        if( i >= j ){ break; }  // 左右から進めてきたiとjがぶつかったらループを終える

        // 基準値の位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
        // 基準値の位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
        // 位置関係を交換する。
        SWAP( int, array[i], array[j] );
        strcpy(temp, results[i]);
        strcpy(results[i], results[j]);
        strcpy(results[j], temp);

        // 次回に備えて、注目点をずらす
        i++;
        j--;
    }


    // 基準値の位置より左側に要素が２つ以上あれば、
    // その部分についてクイックソートを再帰させる
    if( i - begin >= 2 ){
        quick_sort_rec( array, results, begin, i - 1 );
    }

    // 基準値の位置より右側に要素が２つ以上あれば、
    // その部分についてクイックソートを再帰させる
    if( end - j >= 2 ){
        quick_sort_rec( array, results, j + 1, end );
    }
}

void sort(int array[], char results[][5], int size){
    // 配列全体を対象にする
    quick_sort_rec( array, results, 0, (int)(size - 1) );
}

void print_array(int data[],char result[][5], int n){
    for(int i = 0; i < n; i++){
        printf("%d %s\n", data[i], result[i]);
    }
    printf("\n");
}

void counts(int data[], char results[][5], int n, int m){
    int cnt_a = 0, cnt_w = 0, cnt = 0, x, p[n], flag[n];
    char ac[5] = "AC";
    for(int i = 0; i < n; i++){
        p[i] = 0;
        flag[i] = 0;
    }
    for(int i = 0; i < m; i++){
        if(strcmp(results[i], ac) == 0 && flag[data[i] - 1] == 0){
            cnt_a ++;
            x = data[i];
            cnt_w += p[data[i] - 1];
            flag[data[i] - 1] = 1;
        }else{
            p[data[i] - 1] ++;
        }
    }
    printf("%d %d\n", cnt_a, cnt_w);
}

int main(void){
    int n, m;
    scanf("%d""%d", &n, &m);
    if(m == 0){
        printf("%d %d\n", 0, 0);
        return 0;
    }
    int num[m];
    char results[m][5];
    for(int i = 0; i < m; i++){
        scanf("%d""%s", &num[i], results[i]);

    }
    /*sort(num, results, m);
    print_array(num, results, m); */
    counts(num, results, n, m);
    return 0;
}

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

long long t,n;
const int INF=1e9+5;
int main() {

        cin >> n;
        vector<int>a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i];
        }
        vector<int>dp(n,INF);
        dp[0]=0;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<=i+2; j++) {
                if (j<n) {
                        dp[j]=min(dp[j], dp[i]+abs(a[i]-a[j]));
                }
            }
        }
        cout << dp[n-1];

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){

    double x[4],y[4];
    while(cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2]>>x[3]>>y[3]){
        double a[3],b[3],c[3],d[3];
        for(int i=0;i<3;i++){
            a[i]=x[(i+1)%3]-x[i];
            b[i]=y[(i+1)%3]-y[i];
        }
        for(int i=0;i<3;i++){
            c[i]=x[3]-x[i];
            d[i]=y[3]-y[i];
        }
        int suc=1;
        for(int i=0;i<3;i++){
            
            if((a[i]*b[(i+1)%3]-a[(i+1)%3]*b[i])*(a[i]*d[(i+1)%3]-c[(i+1)%3]*b[i])<0){
                suc=0;
                break;
            }
        }
        if(suc==0)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }

    return 0;
}

Measured memory_bytes: 1216
import scala.io.StdIn

object Main extends App {
  val s  = StdIn.readLine()

  def solve(s: String): String = {
    var ans: Array[Int] = Array.fill(s.length)(1)
    var cur: Array[Int] = Array.fill(s.length)(1)    
    var cnt = 0
    val l = s.length

    s.zipWithIndex.foreach { v =>
      cnt = cnt + 1
      if (v._1 == 'R') {
        ans(v._2) = 0
        // 'L'
      } else {
        ans(v._2 - 1) = ans(v._2 - 1) + (cnt.toDouble / 2).floor.toInt
        ans(v._2) = (cnt.toDouble / 2).ceil.toInt
        cnt = 0
      }
//      println("cnt: " + cnt + "LR: " + v._1 + ":" + ans.mkString(" "))      
    }
//    println(ans.mkString(" "))
    var ans2: Array[Int] = ans.reverse

    cnt = 0
//    println(s.reverse.mkString(" "))            
//    println(ans2.mkString(" "))

    s.reverse.zipWithIndex.foreach { v =>

      cnt = cnt + 1
      if (v._1 == 'L') {
        ans2(v._2) = ans2(v._2) - 1
        // 'R'
      } else {
        ans2(v._2 - 1) = ans2(v._2 - 1) +  (cnt.toDouble / 2).floor.toInt
        ans2(v._2) = ans2(v._2) + (cnt.toDouble / 2).ceil.toInt - 1
        cnt = 0
      }
//      println("cnt: " + cnt + "LR: " + v._1 + ":" + ans2.mkString(" "))
    }
    ans2.reverse.mkString(" ")
  }
  
  println(solve(s))  
}
  



Measured memory_bytes: 40496
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long d,t,s;
    cin>>d>>t>>s;
    float x;
    x=(float)d/s;
    if(x<=t)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
}


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

int main() {
	// your code goes here
int a,b,c;
char op;

while(1){
	cin>>a;
cin>>op;
cin>>b;
	if(op=='+'){
	cout<<a+b<<endl;
	}

if(op=='-'){
cout<<a-b<<endl;
}
if(op=='*'){
cout<<a*b<<endl;
}
if(op=='/'){
	cout<<a/b<<endl;
}
	if(op=='?'){break;}
}
	return 0;
}

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

int main(){

  int n;
  cin >> n;

  vector<int> t(n);
  int t_max = 0;
  for(int i = 0; i < n; i++){
    cin >> t[i];
    t_max = max(t[i],t_max);
  }

  vector<int> vec(10001);
  for(int i = 1; i <= t_max; i++){
    if(t_max%i == 0) vec.push_back(i);
  }

  int ans = 0;
  for(int i = 0; i < n; i++){
    int j = 0;
    while(vec[j] < t[i]) j++;
    ans += vec[j] - t[i];
  }
  cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3324
#include <cstdio>

int main() {
  int a[120];
  int n;
  
  
  scanf("%d", &n);
  for (int i=0; i<n; i++) {
    scanf("%d", &a[i]);
  }

  int count=0;
  int flag = 1;
  while (flag) {
    flag = 0;
    for (int j=n-1; j>0; j--) {
      if (a[j] < a[j-1]) {
	int tmp = a[j];
	a[j] = a[j-1];
	a[j-1] = tmp;
	count++;
	flag = 1;
      }
    }
  }

 
  for (int i=0; i<n-1; i++) {
    printf("%d ", a[i]);
  }
  printf("%d\n", a[n-1]);
  printf("%d\n", count);
}

Measured memory_bytes: 2712
import java.util.Scanner;

public class Main
{

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

		int A=input.nextInt();
		int B=input.nextInt();
		int K=input.nextInt();

		for(int i=0; i<K; i++)
		{
			if(i%2==0)
			{
				if(A%2!=0)
				{
					A--;
				}

				int temp=A/2;
				B+=temp;
				A=A/2;
			}
			else
			{
				if(B%2!=0)
					B--;

				int temp=B/2;
				A+=temp;
				B=B/2;
			}
		}

		System.out.println(A+" "+B);
	}



}



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

class Main{
    public static void main(String[] args){
        FastScanner fsc=new FastScanner();
        int n=fsc.nextInt();
        int k=fsc.nextInt();
        long s=fsc.nextLong();
        fsc.close();
        long[] a=new long[n];
        if(s>=3){
            for(int i=0;i<n;i++){
                if(i<k){
                    a[i]=s;
                } else{
                    a[i]=s-1;
                }
                System.out.print(a[i]+" ");
            }
        } else{
            for(int i=0;i<n;i++){
                if(i<k){
                    a[i]=s;
                } else{
                    a[i]=1_000_000_000l;
                }
                System.out.print(a[i]+" ");
            }
        }
        System.out.println();
    }
    

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte(){
            if(ptr<buflen) return true;
            else{
                ptr = 0;
                try{
                    buflen = in.read(buffer);
                }
                catch(IOException e){
                    e.printStackTrace();
                }
                if(buflen<=0) return false;
            }
        return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) throw new NumberFormatException();
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }
                else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
                else throw new NumberFormatException();
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
        public void close(){
            try{in.close();}
            catch(IOException e){e.printStackTrace();}
        }
    }
}


Measured memory_bytes: 45532
from collections import Counter
import sys
import random
 
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ca = Counter(A)
cb = Counter(B)
for i in range(N+1):
    if ca[i] + cb[i] > N:
        print('No')
        sys.exit()

C = [0] * (N+1)
D = [0] * (N+1)

for i in range(N):
    C[i+1] += C[i] + ca[i+1]
    D[i+1] += D[i] + cb[i+1]

x = 0

for i in range(N):
    x = max(x, C[i+1] - D[i])

ans = [B[(i-x)%N] for i in range(N)]

print('Yes')
print(*ans)

Measured memory_bytes: 69108
#include <bits/stdc++.h>
#define FOR(x,n) for(int x = 0; x < n; x++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;

int main() {
  int N; cin >> N;
  
  ll a = 0, b = 0;
  FOR(x,N) {
    ll S, T; cin >> S >> T;
    if(S*(b/T+(b%T!=0)) >= a)
      a = S*(b/T+(b%T!=0)), b = (b/T+(b%T!=0))*T;
    else
      a = (a/S+(a%S!=0))*S, b = T*(a/S);
    if(x == 0) a = S, b = T;
  }
  
  cout << a + b << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll int64_t
#define ull uint64_t
using namespace std;

ull a[200001], b[200001];

int main() {
	IOS;
	ull n, m, k, i = 0, j = 0, time = 0, count = 0;;
	cin >> n >> m >> k;
	for(ull x = 0;x < n;x += 1){
		cin >> a[x];
	}
	for(ull x = 0;x < m;x += 1){
		cin >> b[x];
	}
	while(i < n && time + a[i] <= k){
		time += a[i ++];
	}
	count = i;
	while(j < m && i >= 0){
		time += b[j ++];
		while(time > k && i > 0){
			i --;
			time -= a[i];
		}
		if(time <= k && i + j > count){
			count = i + j;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 6776
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    np.cumsum(mods, out=mods)
    idx = mods[n-1] // div
    count = mods[-1-idx]
    if count <= k:
        print(div)
        exit()

Measured memory_bytes: 21516
/*
author : nit1n
*/
#include<bits/stdc++.h>
#define int long long
using namespace std ;
int mod = 1e9 +7 ; 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ;

	int n ; 
	cin >> n ; 
	vector<int> a(n) ; 
	for(int i = 0; i < n ; ++i)
		cin >> a[i] ;
	vector<int> pref(n+1, 0 ) ; 	 
	pref[n-1] = a[n-1] ; 
	for(int i = n -2 ;i >=0 ; --i)
	{
		pref[i] = pref[i +1] + a[i] ;
		pref[i] %= mod ; 
	}
	int ans = 0 ; 
	for(int i = 0; i < n ; ++i)
	{
		ans +=  a[i]*pref[i+1] ;
		ans %= mod ; 	
	}
	cout << ans ; 

}


Measured memory_bytes: 6356
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
    ll k;cin>>k;
    vector<ll> a(k);
    rep(i,k)cin>>a[i];
    reverse(all(a));
    bool f=1;
    ll l=2,r=2;
    rep(i,k){
        if(l%a[i]==0){
            r=(r/a[i])*a[i]+a[i]-1;
        }else if(l/a[i]<r/a[i]){
            l=(l/a[i]+1)*a[i];
            r=(r/a[i])*a[i]+a[i]-1;
        }else{
            f=0;
            break;
        }
    }
    if(f)cout<<l<<' '<<r<<endl;
    else cout<<-1<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i < (n);i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define SCANF(i) int i;scanf("%d",&i)
typedef long long ll;
using namespace std;
using P = pair<int,int>;
const long long INF = 1LL << 60;
const int IINF=100000000;
const int MOD = (int)1e9 + 7;
//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
vector<int> dx={1,0,-1,0};vector<int> dy={0,-1,0,1};


ll ans = 0;
vector<ll> tri;
bool make_triangle(ll a, ll b, ll c) {
    ll x = a+b;ll y = b+c;ll z = c+a;
    if(a == b || b == c || a == c)return false;
    if(x > c && y > a && z > b)return true;
    return false;
}
signed main () {
    int n;cin >> n;
    tri.resize(n);REP(i,n)cin >> tri[i];
    REP(i,n)FOR(j,i+1,n)FOR(k,j+1,n){
        if(make_triangle(tri[i],tri[j],tri[k]))ans++;
    }
    cout << ans << endl;
}//https://atcoder.jp/contests/abc175/tasks/abc175_b

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define  pb push_back
#define sort1(v) sort(v.begin(),v.end())
#include <sstream>
//gap between 2 primes is less than 300 for n<=10^9
//cout<<fixed<<setprecision(n)<<number - for n digits after decimal
//for all numbers less than 10^9 there are at max 10 distinct prime factors
void multiply(int n,int v[],int res[],int l)
{
    if(n==1)
    {
        res[l]=v[0];
        return ;
    }
    else
    {
        int a[n/2],b[n/2];
        for(int i=0;i<n/2;i++)
        {
            a[i]=v[i]+v[n/2+i];
            b[i]=v[i]-v[n/2+i];
        }
        multiply(n/2,a,res,l);
        multiply(n/2,b,res,l+n/2);
        return ;
    }
}
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    int a[n+1];
    a[0]=0;
    for(int i=0;i<n;i++)
        a[i]=0;
    for(int j=1;j<=n-1;j++)
    {
        int x=j;
        while(x<n)
        {
            a[x]++;
            x+=j;
        }
    }
    int sum=0;
    for(int i=1;i<n;i++)
        sum+=a[i];
    cout<<sum;


}


Measured memory_bytes: 7464
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

ll n;
cin >> n;
string s;
cin >> s;
int count =0;
for(int i=0;i<s.length()-2;i++){
    if(s.at(i)=='A' and  s.at(i+1)=='B' and s.at(i+2)=='C'){
        count++;
    }
}
cout << count << endl; 
return 0;
}


Measured memory_bytes: 256
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    if i==0:
        ans=[a,b]
v=[0]*n
v[ans[0]]=1
v[ans[1]]=1
def check(s):
    for i in g[s]:
        if v[i]==0:
            return i
    return -1
while True:
    a=check(ans[-1])
    if a==-1:
        break
    else:
        ans.append(a)
        v[a]=1
ans.reverse()
while True:
    a=check(ans[-1])
    if a==-1:
        break
    else:
        ans.append(a)
        v[a]=1
print(len(ans))
for i in range(len(ans)):
    ans[i]+=1
print(*ans)

Measured memory_bytes: 65824
import java.io.*;
import java.util.Scanner;

public class Main{
               public static void main(String args[]){
               
                 int x = 0;
                 int y = 0;
                 int z = 0;

                 Scanner in = new Scanner(System.in);
                 

                 String buf1 = in.next();
                 String buf2 = in.next();

                 x = Integer.parseInt(buf1);
                 y = Integer.parseInt(buf2); 
                 z = 2*x+2*y; 
          
   
                 System.out.println(x*y +" "+ z);
            
           }
    }

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



int main(){
    int m,f,b;
    cin>>m>>f>>b;

    if(m+f>=b){
        if(m>=b)cout<<0<<endl;
        else cout<<b-m<<endl;
    }else{
        cout<<"NA"<<endl;
    }

    }

  

    




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

int main(int argv, char *argc[]){
    
    int residence[4][3][10] = {0};
    int inputnum, b, f, r, v, x, y, z;
    
    scanf("%d\n", &inputnum);
    
    
    for(x=0; inputnum>x; x++){
        scanf("%d %d %d %d\n", &b, &f, &r, &v);
        
        residence[b-1][f-1][r-1] += v;
    }
    
    for(x=0; 4>x; x++){
        for(y=0; 3>y; y++){
            for(z=0; 10>z; z++){
            printf(" %d", residence[x][y][z]);
            }
            printf("\n");
        }
        if(3>x)printf("####################\n");
    }
    return 0;
}

Measured memory_bytes: 616
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
//ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int N;
int C[214514];
int mem[214514];
ll dp[214514]={0};
int main(){
	cin>>N;
	rep(i,214514)mem[i]=-1;
	dp[0]=1;
	rep(i,N){
		int x;
		cin>>x;
		dp[i+1]=dp[i];
		int bef=mem[x];
		if(bef!=-1&&bef!=i-1){
			dp[i+1]+=dp[bef+1];
			dp[i+1]%=MOD;
		}
		mem[x]=i;
	}
	cout<<dp[N]<<endl;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
bool rMax(int &a, int b) {
    return b > a ? a = b, true : false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n;
    cin>>n;
    vector<int> dp(3);
    for(int i = 0; i< n; i++){
        vector<int> nextDP(3, 0);
        int a[3];
        cin>>a[0]>>a[1]>>a[2];
        for(int j : {0, 1, 2}){
            for(int k : {0, 1, 2}){
                if(j!=k)
                    rMax(nextDP[k], a[k] + dp[j]);
            }    
        }
        dp = nextDP;
    }
    sort(dp.begin(), dp.end());
    cout<<dp[2]<<"\n";
}


Measured memory_bytes: 3620
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	set<string>s;
	int t(0);
	rep(i, 0, N) {
		int a; cin >> a;
		if (a < 400)s.insert("gray");
		else if (a < 800)s.insert("brawn");
		else if (a < 1200)s.insert("green");
		else if (a < 1600)s.insert("sky");
		else if (a < 2000)s.insert("blue");
		else if (a < 2400)s.insert("yellow");
		else if (a < 2800)s.insert("orange");
		else if (a < 3200)s.insert("red");
		else t++;
	}
	cout << s.size() + (s.size()?0:1) << " " << s.size() + t << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define dbgmint(n,arr) rep(i,n){cerr<<arr[i].x<<" ";}cerr<<endl;
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll h,w,n;
    ll y,x;
    string s,t;
    cin>>h>>w>>n>>y>>x;
    cin>>s>>t;
    auto ok = [&](char cR,char cL,int width,ll st){
        int l = 1;
        int r = width;
        if(s[n-1]==cR)r--;
        if(s[n-1]==cL)l++;
        per(i,n-2){
            if(t[i]==cR){
                l = max(1,l-1);
            }
            if(t[i]==cL){
                r = min(width,r+1);
            }
            if(s[i]==cR){
                r--;
            }
            if(s[i]==cL){
                l++;
            }
            if(l>r)return false;
        }
        return l<=st && st<=r;
    };

    YES(ok('R','L',w,x)&&ok('D','U',h,y));
    return  0;
}


Measured memory_bytes: 920
#include<iostream>
#include<string>
using namespace std;
int max(int a, int b) {
	if (a < b) {
		return b;
	}
	else {
		return a;
	}
}
int main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
	
		if (S[i] == 'A' || S[i] == 'G' || S[i] == 'C' || S[i] == 'T') {
			S[i] ='A';
		}
		else {
			S[i] ='N';
		}
	}
	
	string a1="A", a2 = "AA", a3 = "AAA", a4 = "AAAA", a5 = "AAAAA", a6 = "AAAAAA", a7 = "AAAAAAA", a8 = "AAAAAAAA", a9 = "AAAAAAAAA", a10 = "AAAAAAAAAA";
	size_t ar[10] = {
	(int)S.find(a1), (int)S.find(a2), (int)S.find(a3), (int)S.find(a4), (int)S.find(a5), (int)S.find(a6), (int)S.find(a7), (int)S.find(a8), (int)S.find(a9), (int)S.find(a10),
	};
	size_t max = 0;
	for (int j = 0; j<10; j++) {
		if (ar[j] != -1) {
			max = j + 1;
			
		}

	}
	cout << max;
	
	system("pause");
	return 0;
}


Measured memory_bytes: 504
#include <cstdio>

typedef long long LL;
const int MN = 55, MV = 1 << 18;

LL Binom[MN][MN], Ans;
int N, K, S, T, A[MN], part[MV];

int main() {
	scanf("%d%d%d%d", &N, &K, &S, &T);
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &A[i]);
		if ((A[i] & S) != S || (A[i] | T) != T) {
			--i, --N;
			continue;
		}
	}
	for (int i = 0; i <= N; ++i) {
		Binom[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			Binom[i][j] = Binom[i - 1][j - 1] + Binom[i - 1][j];
	}
	for (int i = 0; i <= N; ++i)
		for (int j = 2; j <= K; ++j)
			Binom[i][j] += Binom[i][j - 1];
	for (int X = 0; X < MV; ++X) {
		if ((X & S) != S || (X | T) != T) continue;
		LL Sum = 0;
		for (int i = 1; i <= N; ++i) ++part[A[i] & X];
		for (int i = 1; i <= N; ++i) if(part[A[i] & X])
			Sum += Binom[part[A[i] & X]][K], part[A[i] & X] = 0;
		Ans += Sum * (__builtin_parity(X ^ S) ? -1 : 1);
	}
	printf("%lld\n", Ans);
	return 0;
}

Measured memory_bytes: 2744
n = int(input())
out_of_range = 1000000000
r = [out_of_range+1, -out_of_range-1]
l = [out_of_range+1, -out_of_range-1]
u = [out_of_range+1, -out_of_range-1]
d = [out_of_range+1, -out_of_range-1]

x_fixed = [out_of_range+1, -out_of_range-1]
y_fixed = [out_of_range+1, -out_of_range-1]

for _ in range(n):
    x, y, di = input().split()
    x, y = int(x), int(y)
    if di == 'R':
        r[0], r[1] = min(x, r[0]), max(x, r[1])
        y_fixed[0] = min(y_fixed[0], y)
        y_fixed[1] = max(y_fixed[1], y)
    elif di == 'L':
        l[0], l[1] = min(x, l[0]), max(x, l[1])
        y_fixed[0] = min(y_fixed[0], y)
        y_fixed[1] = max(y_fixed[1], y)
    elif di == 'U':
        u[0], u[1] = min(y, u[0]), max(y, u[1])
        x_fixed[0] = min(x_fixed[0], x)
        x_fixed[1] = max(x_fixed[1], x)
    else:
        d[0], d[1] = min(y, d[0]), max(y, d[1])
        x_fixed[0] = min(x_fixed[0], x)
        x_fixed[1] = max(x_fixed[1], x)

exists_l = l[0] <= out_of_range
exists_r = r[0] <= out_of_range
exists_u = u[0] <= out_of_range
exists_d = d[0] <= out_of_range
exists_x_fixed = x_fixed[0] <= out_of_range
exists_y_fixed = y_fixed[0] <= out_of_range

def append_cross_time(l, r, time:set, contains_fixed:bool):
    for i in range(2):
        t = (l[i] - r[i])
        if t >= 0 :
            time.add(t if contains_fixed else t / 2)

time = {0}
if exists_l and exists_r:
   append_cross_time(l, r, time, False)
if exists_l and exists_x_fixed:
   append_cross_time(l, x_fixed, time, True)
if exists_r and exists_x_fixed:
   append_cross_time(x_fixed, r, time, True)
if exists_u and exists_d:
   append_cross_time(d, u, time, False)
if exists_d and exists_y_fixed:
   append_cross_time(d, y_fixed, time, True)
if exists_u and exists_y_fixed:
   append_cross_time(y_fixed, u, time, True)
time = list(time)
time.sort()

min_area = out_of_range * out_of_range
for t in time:
    dx = max(l[1] - t, r[1] + t, x_fixed[1]) - min(l[0] - t, r[0] + t, x_fixed[0])
    dy = max(d[1] - t, u[1] + t, y_fixed[1]) - min(d[0] - t, u[0] + t, y_fixed[0])
    min_area = min(dx * dy, min_area)

print(min_area)

Measured memory_bytes: 74632
#include <stdio.h>
int main(){
	int x ,y;
	while(1){
		scanf("%d %d",&x, &y);
		if(x == 0 && y == 0) break;
		else if(x<y){
			printf ("%d %d\n",x, y);
		}else if(x>y || x == y){
			printf ("%d %d\n",y ,x);
		}
	}
		return 0;
}

Measured memory_bytes: 600
from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"

def main():
    inlist = []
    while True:
        n,k = mi()
        if n == 0 and k == 0:
            break
        inlist.append([n,k])
    for tmp in inlist:
        n = tmp[0]
        l = tmp[1]
        cnt = 0
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                for k in range(j+1,n+1):
                    if i+j+k == l:
                        cnt+=1
        print(cnt)




main()




Measured memory_bytes: 6588
#  --*-coding:utf-8-*--


def f(A, k):
    s = 0
    for p, a in enumerate(A):
        if s+a > k:
            return (s, p)
        s += a


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    S = sum(A)
    k = S/2
    (s, p) = f(A, k)
    
    x = int(min(k-s, s+A[p]-k)*2 + 0.5)
    print(x)



if __name__ == '__main__':
    main()


Measured memory_bytes: 26220
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	string S;
	cin >> S;

	int zero_count = 0;
	int one_count = 0;

	for (int i = 0; i < S.size(); i++)
	{
		if (S[i] == '0') zero_count++;
		else one_count++;
	}

	cout << 2 * min(zero_count, one_count);

	return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
#define INF (1<<21)
int G[N][N];
int d[N],pi[N],color[N];
int n;
void dijkstra(void){
  int i,u,v,mincost;
  for(u=0;u<n;u++){
    d[u]=INF;
    pi[u]=NIL;
    color[u]=WHITE;
  }
  d[0]=0;
  while(1){
    mincost=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost=d[i];
	u=i;
      }
    }
    if(mincost==INF) break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK && G[u][v]!=INF){
	if(d[u]+G[u][v]<d[v]){
	  d[v]=d[u]+G[u][v];
	  pi[v]=u;
	  color[v]=GRAY;
	}
      }
    }
  }
}
int main(){
  int i,j,k,u,v;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      G[i][j]=INF;
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      scanf("%d",&G[u][v]);
    }
  }
  dijkstra();
  for(i=0;i<n;i++) printf("%d %d\n",i,d[i]);
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#define s true
using namespace std;
int abs(int i,int j){
	int f=i-j;
	if(f<0){
		i*=-1;
	}
	return f;
}

int main(){
	int a,b;
	for(int i=1;i<6;i++){
	cin>>a;
	if (a==0){
		b=i;
	}
	}
	cout<<b;
return 0;
}

Measured memory_bytes: 3160
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
int h,w;
int cam[60][60];
int main(void)
{
    char c;
    cin >> h >> w;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> c;
            if(c == '#') cam[i][j] = 1;
        }
    }
    
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(cam[i][j] == 1){
                if(cam[i+1][j] || cam[i-1][j] || cam[i][j+1] || cam[i][j-1]) continue;
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))
A.sort()
diff = 10**10
ans = A[0]
#print(A[n-1]//2+1)
for i in range(n-1):
    if abs(A[n-1]/2-A[i]) < diff:
         ans = A[i]
         diff = min(diff,abs(A[n-1]/2-A[i]))
print(A[n-1],ans)

Measured memory_bytes: 62704
a, b, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = []
for i in range(m):
    p, q, r = map(int, input().split())
    x.append(a[p-1]+b[q-1]-r)
print(min(min(x), min(a)+min(b)))

Measured memory_bytes: 18612
//Moh_K_Imar .......
//22/08/2020  ... 11.38
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    ll k,a,b;
    cin>>k>>a>>b;
    ll counter=0;
    for(int i=a;i<=b;i++){
        if(i%k==0){
            counter++;
        }
    }
    if(counter!=0)cout<<"OK"<<endl;
    else cout<<"NG"<<endl;


    return 0;
}



Measured memory_bytes: 3596
class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    
    def find_root(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find_root(self.parents[x])
            return self.parents[x]
    def make_union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        
        if x == y : return
        self.size[x] += self.size[y]
        self.parents[y] = x

def main():
    n, m = map(int, input().split())
    uf = UnionFindPathCompression(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.make_union(a - 1, b - 1)
    
    ans = max(uf.size)
    print(ans)

if __name__ == "__main__":
    main()

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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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

vector <ll> a;

int main(void)
{
  ll n, m;
  cin >> n >> m;
  ll sum = 0;
  REP(i, m) {
    ll a1;
    cin >> a1;
    sum += a1;
  }
  cout << (sum <= n ? n - sum : -1) << endl;

}


Measured memory_bytes: 3632
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while ( sc.hasNext() ) {
			int i = 0;
			double in,t,y;
			in = sc.nextDouble();
			t = in / 9.8;
			y = 4.9 * (t*t);
			while ( 5*i-5<y ) i++;
			System.out.println(i);
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

vector<int> v[505];

int main(){
    int n, m, Q;
    cin >> n >> m >> Q;
    rep(i, m) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        v[l].push_back(r);
    }
    rep(i, n) {
        sort(whole(v[i]));
    }
    rep(qi, Q) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        int ans = 0;
        for (int i=p; i<=q; i++) {
            auto it = upper_bound(whole(v[i]), q);
            ans += (it-v[i].begin());
        }
        cout << ans << endl;
    }
    
    
    return 0;
}


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

int main() {
  string S, T;
  cin >> S >> T;
  map<char, char> S2T, T2S;
  bool fail_flag = false;
  for (int i = 0; i < S.length(); i++) {
    if (S2T.find(S[i]) == S2T.end()) {
      S2T[S[i]] = T[i];
    } else if (S2T[S[i]] != T[i]) {
      fail_flag = true;
      break;
    }
    if (T2S.find(T[i]) == T2S.end()) {
      T2S[T[i]] = S[i];
    } else if (T2S[T[i]] != S[i]) {
      fail_flag = true;
      break;
    }
  }
  string ans = "Yes";
  if (fail_flag) {
    ans = "No";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 776
from collections import deque
N, K, C = map(int, input().split())
S = input()

fastest = deque([])
latest = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.append(N - (date - 1))
    date += C + 1

for i in range(K):
    f = fastest.popleft()
    l = latest.pop()
    if f == l:
        print(f)

Measured memory_bytes: 19800
/**
 * @author torith
 * @date 2018-10-24
 */

#include <bits/stdc++.h>

using namespace std;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    map <int,int> cnt;
    for (int i = 0; i < N; ++i) {
        int t;
        cin >> t;
        cnt[t] = cnt[t] + 1;
    }

    int ans = 0;
    for (auto &m : cnt){
        if(m.first <= m.second) ans += m.second - m.first;
        else ans += m.second;
    }

    cout << ans << "\n";


    return 0;
}



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

//#define var auto
#define ll long long

using namespace std;

int ans = 0;
int h, w;
vector<string> grid;
vector<vector<bool>> arrived;
void dfs(int y, int x) {
	if (y < 0 || h <= y || x < 0 || w <= x) return;
	if (grid[y][x] == '#') return;
	if (arrived[y][x])return;
	arrived[y][x] = true;
	ans++;
	dfs(y - 1, x);
	dfs(y, x + 1);
	dfs(y + 1, x);
	dfs(y, x - 1);
}

int main() {
	while (true)
	{
		cin >> w >> h;
		if (w == 0) break;
		grid = vector<string>(h);
		arrived = vector<vector<bool>>(20, vector<bool>(20, false));
		ans = 0;
		for (int i = 0; i < h; i++) {
			cin >> grid[i];
		}
		int sy, sx;
		for (int i = 0; i < h; i++) {;
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == '@') {
					sy = i;
					sx = j;
				}
			}
		}
		dfs(sy, sx);
		cout << ans << endl;
	}
}



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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n,cnt=0,ans=0,a[10000000],b[10000000],c,cmp,data,k,m,h,w,x,y,xcmp,ycmp,sum=0;

string s;

vector<int> z;

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

       cin >> n >> k;
       pair<int,int> p[1000000];
       rep(i,n){
           cin >> a[i] >> b[i];
           p[i]=make_pair(a[i],b[i]);
       }
       sort(p,p+n);
       rep(i,n){
           cmp+=p[i].second;
           if(cmp>=k){
               Cout(p[i].first);
               return 0;
           }
       }
       
return 0;
}


Measured memory_bytes: 10880
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

// dijkstra
template<typename Edge>
struct dijkstra {
  using Graph = std::vector<std::vector<Edge>>;
  using T = typename Edge::cost_type;
  using GP = std::pair<T, int>;
  using Q = std::priority_queue<GP, std::vector<GP>, std::greater<GP>>;

  Graph& G;
  int N;
  std::vector<T> d;
  T INF;
  dijkstra(Graph& Graph, T inf): G(Graph), N(Graph.size()), INF(inf) {}

  void search(int s) {
    Q q;
    d.assign(N, INF);
    d[s] = 0;
    q.push(GP(0, s));
    while(!q.empty()) {
      GP p = q.top(); q.pop();
      int v = p.second;
      if(d[v] < p.first) continue;
      for(auto e: G[v]) {
        T newd = d[v]+e.cost;
        if(newd >= d[e.to]) continue;
        if(newd >= INF) continue;
        d[e.to] = newd;
        q.push(GP(d[e.to], e.to));
      }
    }
  }
};

struct edge {
  typedef int64_t cost_type;
  cost_type cost;
  int to;
  edge(cost_type c, int t): cost(c), to(t) {}
};


int main() {
  int N, M; std::cin >> N >> M;
  std::vector<std::vector<edge>> G(N*3);
  for(int i = 0; i < M; ++i) {
    int u, v; std::cin >> u >> v; --u; --v;
    G[u].emplace_back(1, N+v);
    G[N+u].emplace_back(0, N+N+v);
    G[N+N+u].emplace_back(0, v);
  }
  dijkstra<edge> dij(G, N+N);
  int S, T; std::cin >> S >> T; --S; --T;
  dij.search(S);
  int ans = dij.d[T];
  if(ans > N) ans = -1;
  fin(ans);
  return 0;
}


Measured memory_bytes: 18944
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)

sm = sum(a[:n-p+1])

for k in range(n-p+1):
    sm -= a[k]
    if a[k]+m < a[n-p]:
        continue
    elif (n-p-k)*(a[k]+m) - sm +(p+k)*m < v*m:
        continue
    else:
        print(n-k)
        exit()

Measured memory_bytes: 62744
# -*- coding: utf-8 -*-
import numpy as np
from copy import deepcopy

def main():
    # # 整数の入力
    # a = int(input())
    # # スペース区切りの整数の入力
    # b, c = map(int, input().split())
    # # 文字列の入力
    # s = input()
    # # 出力
    # print("{} {}".format(a+b+c, s))
    N = int(input())
    H_list = list(map(int, input().split()))
    flag = False
    for i in range(N-1,0,-1):
        # i ... N-1, N-2, ..., 1
        if H_list[i-1] - H_list[i] > 1:
            print("No")
            flag = True
            break
        elif H_list[i-1] - H_list[i] == 1:
            H_list[i-1] = deepcopy(H_list[i-1]) -1
        else:
            pass
    if flag == False:
        print("Yes")
    # for i in range(N-1):
    #     if H_list[i] - H_list[i+1] > 1:
    #         print("No")
    #         break
    #     elif H_list[i] - H_list[i+1] == 1:
    #         H_list[i] = H_list[i] - 1
    #         if (i > 0) and (H_list[i]<H_list[i-1]):
    #             print("No")
    #             break
    #     else:
    #         pass
    # print("Yes")


if __name__=='__main__':
    main()


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

int main(){
	int h,w,i,j,count = 0;
	char a[10][10];
	cin >> h >> w;
	for(i = 0;i < 10;i++){
		for(j = 0;j < 10;j++){
			a[i][j] = '.';
		}
	}
	for(i = 1;i <= h;i++){
		for(j = 1;j <= w;j++){
			cin >> a[i][j];
		}
	}
	i = j = 1;
	a[i][j] ='.';
	while(1){
		if(i == h && j == w)break;
		if(a[i][j+1] == '#'){
			j++;
			a[i][j] = '.';
			continue;
		}
		else if(a[i+1][j] == '#'){
			i++;
			a[i][j] = '.';
			continue;
		}
		else if(a[i+1][j] == '.' && a[i][j+1] == '.'){
			break;
		}
	}

	for(i = 0;i < 10;i++){
		for(j = 0;j < 10;j++){
			if(a[i][j] == '#')count++;
		}
	}

	if(count == 0){
		cout << "Possible" <<endl;
	}
	else{
		cout << "Impossible" <<endl;
	}

	return 0;
}

Measured memory_bytes: 256
import bisect

N,M,K = map(int, input().split())

A = [0]
sumOfA = 0
for a in map(int, input().split()):
    sumOfA += a
    A.append(sumOfA)

idxA = bisect.bisect_right(A, K) - 1
ans = idxA

sumOfB = 0
for idxB, b in enumerate(map(int, input().split())):
    K -= b
    if K < 0:
        break

    while(idxA > 0):
        if A[idxA] <= K:
            break
        
        idxA -= 1


    ans = max(ans, idxB + idxA + 1)

print(ans)



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

int main() {
    long long ans;
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N), F(N);
    for(int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    for(int i = 0; i < N; i++) {
        cin >> F.at(i);
    }
    sort(A.begin(), A.end());
    sort(F.begin(), F.end(), greater<int>());
    long long X = 1e12;
    long long l = 0, r = X;
    while(l < r) {
        long long M = (l + r) / 2;
        long long Count = 0;
        for(int i = 0; i < N; i++) {
            Count += max(0LL, A.at(i) - M / F.at(i));
        }
        if(K >= Count)
            r = M;
        else
            l = M + 1;
        // cout << l << " " << r << endl;
    }
    ans = l;

    cout << ans << endl;
}

Measured memory_bytes: 1792